Unit 2: Modern Symmetric-key Encipherment - Subjective Questions

Definition: is a finite field containing exactly elements. Each element can be represented as an -bit binary word or as a polynomial of degree less than with coefficients in .

Key properties:

• The coefficients are either or .
• Addition is performed using bitwise XOR.
• Multiplication is polynomial multiplication followed by reduction modulo an irreducible polynomial of degree .
• Every nonzero element has a unique multiplicative inverse.

Cryptographic importance:

• Finite-field operations provide efficient and reversible transformations.
• AES uses in its SubBytes and MixColumns transformations.
• Field arithmetic contributes to confusion, diffusion, and resistance against algebraic and differential attacks.

An element of can be represented by an -bit word or a polynomial of degree at most .

For example, in :

• The word represents .
• The word represents .

Addition is coefficient-wise modulo , which is equivalent to bitwise XOR:

In polynomial form:

The two occurrences of cancel because in . Subtraction is identical to addition in this field because every element is its own additive inverse.

Multiplication procedure:

1. Represent the operands as binary polynomials.
2. Multiply the polynomials using arithmetic over .
3. Reduce the result modulo a selected irreducible polynomial of degree .

Thus, multiplication is defined as:

A nonzero element has an inverse satisfying:

The inverse may be calculated using the extended Euclidean algorithm.

Need for irreducibility: If were reducible, some nonzero elements could become zero divisors and would not have multiplicative inverses. An irreducible modulus ensures that the resulting algebraic structure is a field.

An irreducible polynomial over is a nonconstant polynomial that cannot be factored into lower-degree nonconstant polynomials whose coefficients belong to .

To construct , polynomial arithmetic is performed modulo an irreducible polynomial of degree :

The modulus keeps every result within degree and ensures that all nonzero elements have multiplicative inverses.

AES uses the polynomial:

Its hexadecimal representation is 0x11B. This polynomial is used when reducing byte products in AES finite-field operations.

DES is a symmetric block cipher based on a 16-round Feistel network.

Main characteristics:

• Plaintext block size: bits.
• Supplied key size: bits.
• Effective key size: bits, because eight bits are used for parity.
• Number of rounds: .

Encryption structure:

1. Apply the Initial Permutation (IP) to the plaintext.
2. Divide the result into two -bit halves, and .
3. For each round :

4. Swap the final halves.
5. Apply the inverse initial permutation .

The permutations mainly support bit rearrangement, while the round function and key schedule provide the cryptographic security.

The DES round function accepts a -bit right half and a -bit round key .

Operations:

1. Expansion permutation: Expands from to bits using the E-table. Some input bits are repeated.
2. Key mixing: XORs the expanded value with the round key:

3. Substitution: Divides into eight -bit groups. Each group enters one S-box and produces bits, reducing the result to bits.
4. P-permutation: Rearranges the output bits to spread each S-box output across different S-box inputs in later rounds.

The S-boxes introduce nonlinearity and confusion, while expansion and permutation help create diffusion and the avalanche effect.

The DES key schedule derives sixteen -bit round keys from the supplied -bit key.

Steps:

1. Apply Permuted Choice 1 (PC-1), which discards the eight parity bits and permutes the remaining bits.
2. Divide the result into two -bit halves, and .
3. Perform one-bit or two-bit circular left shifts on both halves according to the round number.
4. Combine the shifted halves to obtain a -bit value.
5. Apply Permuted Choice 2 (PC-2) to select and permute bits, producing .

Rounds , , , and use one-bit shifts; the other rounds use two-bit shifts. The resulting subkeys differ across rounds and determine the key-dependent behavior of DES.

In a Feistel cipher, the round function itself does not need to be invertible. A round is defined by:

The previous values can be recovered as:

This works because XOR is self-inverse:

Therefore, DES decryption uses the same round arrangement and round function as encryption, but supplies the round keys in reverse order: . This property simplifies both hardware and software implementations.

Avalanche effect: A small change in the plaintext or key should cause a large and unpredictable change in the ciphertext. In a well-designed cipher, changing one input bit changes approximately half of the output bits. DES achieves this through repeated S-box substitutions, permutations, and mixing across sixteen rounds.

Complementation property: If , DES satisfies:

Here, the overline denotes bitwise complementation. Thus, complementing both the plaintext and key produces the complement of the original ciphertext.

This property can reduce the work of certain exhaustive-search scenarios by about a factor of two, but it does not by itself provide a practical break of DES.

DES was carefully designed, but its -bit effective key is too short for modern security requirements.

Brute-force attack:

• The key space contains possible keys.
• Specialized hardware can search this space in a practical amount of time.
• Public demonstrations have confirmed that DES keys can be recovered through exhaustive search.

Cryptanalytic attacks:

• Differential cryptanalysis studies how input differences affect output differences.
• Linear cryptanalysis uses linear approximations involving plaintext, ciphertext, and key bits.
• Full 16-round DES was designed with significant resistance to these attacks, although they are important for evaluating its security margin.

Triple DES: Triple DES applies DES three times, commonly using the EDE sequence:

It increased the effective key strength and preserved compatibility with DES, but it is slow, has a small -bit block size, and has largely been replaced by AES.

AES is a symmetric block cipher standardized by NIST in 2001 after the AES competition. It is based on the Rijndael algorithm developed by Joan Daemen and Vincent Rijmen.

Principal characteristics:

• Fixed block size: bits.
• Supported key sizes: , , and bits.
• Number of rounds: , , and , respectively.
• Structure: substitution-permutation network rather than a Feistel network.
• Internal data representation: a matrix of bytes called the state.
• Main transformations: SubBytes, ShiftRows, MixColumns, and AddRoundKey.

AES offers strong security, efficient implementation in hardware and software, and substantially larger key sizes than DES.

AES processes a -bit block as sixteen bytes arranged column by column in a state matrix:

The first four input bytes form the first column, the next four form the second column, and so on.

Key-size relationships:

• AES-128: key words and rounds.
• AES-192: key words and rounds.
• AES-256: key words and rounds.

Each word contains bits, and every encryption round uses one -bit round key.

SubBytes is a nonlinear byte-substitution transformation. Every byte in the AES state is independently replaced by another byte using a fixed S-box.

S-box construction:

1. Interpret the input byte as an element of .
2. Find its multiplicative inverse modulo:

3. Define the inverse of 0x00 as 0x00 for this construction.
4. Apply a fixed affine transformation over to the inverse.

Purpose:

• Introduces strong nonlinearity and confusion.
• Prevents the cipher from being represented as a simple linear system.
• Helps resist linear and differential cryptanalysis.

During decryption, InvSubBytes uses the inverse S-box to reverse the substitution.

ShiftRows: Each row of the state is cyclically shifted to the left by a different offset:

• Row : no shift.
• Row : shift by one byte.
• Row : shift by two bytes.
• Row : shift by three bytes.

MixColumns: Each state column is treated as a four-byte vector and multiplied by a fixed matrix over :

ShiftRows moves bytes between columns, while MixColumns combines the four bytes within each column. Together, they spread the effect of one changed input byte across many state bytes over subsequent rounds, producing strong diffusion. The final AES round omits MixColumns.

AddRoundKey combines the state with a -bit round key using bitwise XOR:

It is the operation through which the secret key directly influences the data. Since XOR is self-inverse, applying the same round key again reverses the transformation.

AES encryption sequence:

• Initial step: AddRoundKey.
• Standard rounds: SubBytes, ShiftRows, MixColumns, and AddRoundKey.
• Final round: SubBytes, ShiftRows, and AddRoundKey; MixColumns is omitted.

The substitution layer provides confusion, the row and column transformations provide diffusion, and key addition makes every stage dependent on the expanded secret key.

AES-128 expands a -bit cipher key into words, where each word contains bits. Four words are used by each of the initial key addition and ten rounds.

Let the original key words be . Remaining words are generated by:

for most values of . When is a multiple of :

Operations:

• RotWord: cyclically rotates a four-byte word by one byte to the left.
• SubWord: applies the AES S-box to each byte.
• Rcon: adds a round-dependent field constant.

These operations introduce nonlinearity, remove symmetry, and ensure that each round receives a distinct key.

AES decryption uses the expanded round keys in reverse order and applies inverse transformations.

Inverse operations:

• InvShiftRows: cyclically shifts rows to the right by offsets , , , and .
• InvSubBytes: replaces each byte using the inverse AES S-box.
• InvMixColumns: multiplies each column by the inverse field matrix.
• AddRoundKey: XORs the state with a round key and is its own inverse.

Decryption sequence:

1. Apply AddRoundKey using the final encryption round key.
2. For intermediate rounds, apply InvShiftRows, InvSubBytes, AddRoundKey, and InvMixColumns.
3. In the last decryption round, apply InvShiftRows, InvSubBytes, and AddRoundKey without InvMixColumns.

Because every encryption transformation is invertible, the original plaintext is recovered exactly when the correct key is used.

DES permits encryption and decryption through the same Feistel structure with reversed keys. AES requires explicit inverse transformations for decryption. AES also offers a larger block size, stronger key lengths, and better modern performance, so it has replaced DES and most Triple DES applications.

A block cipher encrypts only one fixed-size block. A mode of operation defines how it securely processes messages containing multiple blocks and may also provide authentication.

• ECB: Encrypts each block independently. Identical plaintext blocks produce identical ciphertext blocks, exposing patterns. It is generally unsuitable for structured data.
• CBC: XORs each plaintext block with the previous ciphertext block. It requires an unpredictable initialization vector and padding. Encryption is sequential.
• CTR: Encrypts successive counter values and XORs them with plaintext. It supports parallel processing and does not require padding. A nonce-counter pair must never be reused with the same key.
• GCM: Combines counter-mode encryption with an authentication mechanism. It provides authenticated encryption with associated data and detects modification.

For most new systems, an authenticated-encryption mode such as AES-GCM is preferred because confidentiality alone does not prevent ciphertext tampering.

Modern block ciphers such as AES are used in network protocols, storage encryption, database protection, virtual private networks, wireless security, and authenticated-encryption systems.

Deployment precautions:

• Use a standardized authenticated-encryption mode such as AES-GCM when appropriate.
• Generate keys with a cryptographically secure random-number generator.
• Protect keys using secure storage, access control, rotation, and destruction procedures.
• Never reuse a nonce with the same key in CTR- or GCM-based systems.
• Verify authentication tags before releasing decrypted plaintext.
• Use established cryptographic libraries rather than custom implementations.
• Protect implementations from timing, cache, power-analysis, and fault-injection attacks.
• Avoid obsolete algorithms and modes such as DES and ECB.

The mathematical strength of a block cipher is insufficient by itself; secure key management, mode selection, nonce handling, and implementation are equally important.