Week7.ps (mpage)

f : {0, 1}32 × {0, 1}48 → {0, 1}32.
These notes are based in part on Susan Landau’s You can find a pictorial representation of f in Fig- paper: “Standing the test of time: the data en- ure 4.5. Here is how f (A, J) is computed: 1. Expand A to a bitstring of length 48, using a DES was adopted in 1977 as a standard for “un- 2. Compute E(A) ⊕ J. View E(A) ⊕ J as the con- classified” applications. After a public solicitation catenation of 8 6-bit strings, B1B2 · · · B8.
from NBS, IBM developed this system. It was ini- 3. Apply S-box Si to Bi. DES has 8 different tially expected that it would be the standard for S-boxes. Each S-box maps 6 bits to 4 bits.
10-15 years. However, it remained a strong cryp- Let Ci = Si(Bi). We now have a 32-bit string 4. Permute C1C2 · · · C8 using a fixed permutation P . f (A, J ) = P (C1C2 · · · C8).
DES is a special type of iterated cipher called a Feistel Cipher. In each round i, the state is split into two halves of equal length, called Li and Ri.
For all rounds i ≥ 1, Look at page 112 to see what the S-boxes looklike.
DES is a 16-round Feistel cipher with block length64 and a 56-bit key. Each round key has 48 bits.
A different subset of key bits is used in each round.
Traditionally, a DES S-box is depicted as a 4 × 16array. Given a 6-bit string b1b2 · · · b6, you can findthe output of the S-box in row b See Figure 4.4 for a pictorial representation of the DES begins with a fixed initial permutation andends with its inverse. These permutations have nocryptographic significance, and are often ignoredin the cryptanalysis.
2. No output bit of an S-box should be too close to a linear function of the input bits. [Better would have been: No linear combination of When DES was proposed as standard, there was output bits of an S-box should be too close to 3. Each “row” of an S-box should contain all pos- First and foremost, it was felt that 56 bits (keyspace size 256) was not enough to be secure.
4. If two inputs to an S-box differ in exactly 1 bit, In 1998, a $250,000 computer built by the Elec- their outputs must differ by at least 2 bits.
tronic Frontier Foundation (the “DES Cracker”)found a DES key in 56 hours, testing 88 billion 5. If two inputs to an S-box differ exactly in the keys per second. In 1999, the DES Cracker and middle 2 bits, their outputs must differ by at 100,000 networked computers found a DES key in 22 hours, testing over 245 billion keys per second.
6. If two inputs to an S-box differ in their first 2 bits and agree on the last 2, the two outputs A second concern was the S-boxes. People were concerned that the S-boxes might contain hidden 7. For any nonzero 6-bit difference between in- “trapdoors” that would allow the NSA to decrypt puts, no more than 8 of the 32 pairs of in- messages. No such trapdoor has ever been found.
puts exhibiting this difference may result in the The IBM researchers had not anticipated linear Biham and Shamir discovered differential crypt- cryptanalysis. In 1994, Matsui used 243 plaintext- analysis for DES. Their attack needed only 247 ciphertext pairs and 50 days to decrypt a DES- chosen plaintexts, so this attack is not practical.
encoded message. Again, this is not really practi- They also found that almost every variation on DES that they tried was weaker than original DES.
Still, linear and differential cryptanalysis are ex- knew about differential cryptanalysis when they developed DES, and that they had tried to tosystems must be designed to be “secure” make DES secure against differential cryptanaly- against differential and linear cryptanalysis.
sis. They also kept their knowledge of differentialcryptanalysis a secret for almost 20 years, until it There are certain keys one should avoid when us- Here are the (secret) criteria for S-box design ing DES. These are the “weak keys”: keys such 1. Each S-box should have 6 bits of input and 4 that every subkey is the same, and the “possiblyweak keys”: keys that generate only 4 different bits of output. (Largest possible if DES were subkeys. All these keys are known and can thus These notes are based in part on Susan Landau’spaper: “Communications security for the twenty- Evaluation criteria would be: security, cost, and first century: the advanced encryption standard.” algorithm and implementation characteristics.
You can find a link to this paper on the coursepage.
Submissions were due on June 15, 1998. Of the21 submissions, 15 fulfilled the AES criteria. In In 1997, the NIST (the National Institute of Stan- August 1999, the NIST chose the following 5 final- dards and Technology, formerly the NBS) began ists: MARS, RC6, Rijndael, Serpent, and Twofish.
the process of choosing a replacement for DES,to be called the Advanced Encryption Standard All finalists were felt to be secure. On October 2, 2000, Rijndael was selected as the AES. You canfind short descriptions of the 5 finalists in Landau’s At that time, triple-DES had become popular, but it was too slow and the 64-bit block length wastoo small. (Aside: double-DES is not much harderto break by brute-force than DES using a “meet-in-the-middle” attack.) Recall that AES has block length 128, and three The NIST solicited proposals from the interna- allowable key lengths: 128 bits, 192 bits, and 256 bits. AES is an iterated cipher. The number ofrounds (N ) depends on the key length: N = 10 for The requirements for the algorithms were as fol- 128-bit keys, N = 12 for 192-bit keys, and N = 14 • The algorithm must implement private-key • The algorithm must be a block cipher.
• The algorithm must work on 128-bit blocks and support 3 keys sizes: 128, 192, and 256 2. For each of the N rounds, perform operation ByteSub (a substitution using an S-box); per- form operation ShiftRow (a permutation); per- • If selected, the algorithm should be available form operation MixColumn (unless it is the last A field is a set containing elements 0 and 1, where All operations in AES are byte-based.
0 = 1, with two operations: multiplication and ad-dition. Both operations are closed, commutative, The state consists of 128 bits = 16 bytes, viewed and associative, and the distributive law holds. 0 is the additive identity, and 1 is the multiplicativeidentity.
Every element has an additive inverse.
Every non-zero element has a multiplicative in- For every prime power pn, there is exactly one field with pk elements. This field is called GF (pk) (Ga- We will now see how to construct these fields.
Z2[X] is the set of all polynomials with coefficients The ByteSub operation performs a substitution in Z2. For example, X + 1 is in Z2[X] and so are X4 + X3 + 1 and 0. We can add, subtract, and bytes to bytes. You can find this S-box on page multiply in Z2[X] (just take all coefficients mod It is represented as a 16 x 16 array.
hexadecimal digits X and Y , you can find πS(XY )in the intersection of row X and column Y .
We can also do division with remainder. For ex-ample, if we divide X2 + X + 1 into X4 + X3 + 1, In contrast to the DES S-boxes, the AES S-box the quotient is X2 + 1 and the remainder is X.
can be defined algebraically. It was designed forresistance against linear and differential cryptanal- So, X4 + X3 + 1 ≡ X mod(X2 + X + 1).
It turns out that Z2[X] mod(X2 + X + 1) is the The AES box incorporates operations in the finite The elements of the field are 0, 1, X, and X + 1, GF (28) = Z2[X] mod(X8 + X4 + X3 + X + 1).
and the operations are addition and multiplicationmodulo X2 + X + 1.
The operation ShiftRow cyclicly shifts the ele-ments of the ith row i elements to the right.
The operation MixColumn replaces each column You cannot just use any polynomial to get a field; you must use an irreducible polynomial.
A polynomial F (X) in Z2[X] is is irreducible if it doesn’t factor into two polynomials of lower de-gree.
The book describes the key schedule for 10-roundAES, which used a 128-bit key. We need 11 round Z2[X] mod(F (X)) is a field if and only if F (X) is keys, each of which consists of 16 bytes. The key schedule is word oriented. The concatenation ofthe 11 round keys is called the expanded key, andconsists of 44 words.
You can find the exact algorithm on page 131.
As mentioned previously, although the S-box is im-plemented as a lookup table (see Table 5.1), it hasa simple mathematical description.
View a byte as an element of GF (28). For exam-ple, view the byte 01010011 as the field element Now take the inverse of this field element inGF (28). In our example, this is X7 + X6 + X3 + X.
View this element as a bit vector, with the right- Every byte corresponds to a field element and vice most bit in the top position. In our example, we get the vector (0, 1, 0, 1, 0, 0, 1, 1).
vector by the matrix on page 132, and add vector(1, 1, 0, 0, 0, 1, 1, 0). View the resulting vector as abyte (taking the top bit to be the rightmost bit).
This is the output of the S-box.
In our example, the output is 11101101, which wecan verify with the S-box table.

Source: http://staticfree.info/rit/crypto/class_notes/week7.tiled.pdf