There is no security on this earth, there is only opportunity - General Douglas MacArthur 1 Origins A replacement for DES was needed worked out theoretical attacks, that may break it demonstrated exhaustive key search attacks 1999: NIST issued FIPS PUB 43: DES for legacy systems only; Triple DES prescribed for new systems can use Triple-DES up to 2030 but slow
particularly in software implementations-with small blocks Jan 2, 1997: NIST begins work on the new standard. Sept 12, 1997: formal call for AES proposals 2 AES Requirements issued by NIST in 1997 private key, symmetric block cipher 128-bit data, 128/192/256-bit keys stronger & faster than Triple-DES active life of 20-30 years (+ archival use) provide full specification & design details both C & Java implementations
3 History of Development of AES June 1998: 21 proposals Aug 20, 1998: shortlisted to 15 proposals: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI 197, MAGENTA, MARS, RC6, RIJNDAEL, SAFER+, SERPENT, TWOFISH March 22, 23, 1999: AES2: Second AES Candidate Conference, Rome Aug 1999: five candidates: MARS, RC6, RIJNDAEL, SERPENT, TWOFISH: equally secure; issues of efficiency, speed and less resource hunger were to be studied. 4 AES Shortlist
shortlist in Aug-99: MARS (IBM) - complex, fast, high security margin RC6 (USA) - v. simple, v. fast, low security margin Rijndael (Belgium) - clean, fast, good security margin --academic Serpent (Euro) slow (1/3rd the speed of AES), clean, highest security margin out of the 5 finalists -academic Twofish (USA) complex, Feistel, DES-like structure; v. fast (as fast as AES), high security margin key dependent S-boxes; Uses whitening: at both the start and the end of the cipger process, add key-material to data then subject to further analysis & comment 5 AES Evaluation Criteria
initial criteria : security effort to practically cryptanalyse cost computational algorithm & implementation characteristics (Used to reduce the field from 21 proposals to 15. Thereafter 5 candidates were shortlisted out of the 15, by using the same criterion. ) 6 final criteria for selecting Rijndael out of the five: 1.general security 2. software & hardware implementation ease 3. implementation attacks 4. flexibility (in en/decrypt, other factors) 5. restricted memory requirement (for use in smart devices) 6. Key Agility: ability to change keys fast, with a minimum of resources. 7 AES
October 2, 2000: RIJNDAEL selected as AES Unclassified, publicly disclosed encryption algorithm Available royalty-free world-wide Symmetric-key block cipher 8 Selection of AES saw contrast between algorithms with few complex rounds versus many simple rounds which refined existing ciphers versus new proposals which could be implemented efficiently both in software only and through special purpose ICs AES: issued as FIPS PUB 197 standard in Nov-2001
AES: initially developed as Rijndael Cipher by Joan Daemen and Vincent Rijmen ; 9 Rijndael Cipher an iterative rather than Feistel-type cipher operates on an entire block of data in every round (and not on half the block, as in Feistel type ciphers) designed to be: resistant against known attacks speed and code compactness on many CPUs design simplicity Plaintext Data: written in the form of a matrix
Input Key: also written in the form of a matrix 10 Key Key and data bytes arranged in rectangular arrays K 0,0 K 0,1 K 0,2 K 0,3 K 0,4 K 0,5 K 0,6 K 1,0 K 1,1 K 1,2 K 1,3 K 1,4 K 1,5 K 1,6 K 2,0 K 2,1 K 2,2 K 2,3 K 2,4 K 2,5 K K 0,7 K 1,7 K 2,6 2,7 Variable Key size: 16,24 or 32 bytes;
K i,j K 3,0 K 3,1 aK byte 3,2 K in 3,3the K 3,4 3,5 and K jth K represents ith Krow 3,6 3,7 column. Nk = Number of column vectors of the key 11 Block of data a 0,0 a 0,1 a 0,2 a 0,3
a 0,4 a 0,5 a 0,6 a 0,7 a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6 a 1,7 a 2,0
a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,7 a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6
a 3,7 Variable Block size: 16,24 or 32 bytes; ai,j represents a byte in the ith row and jth column. Nb = Number of column vectors (4-byte vectors) 12 State The plaintext block of data is represented as a matrix. Each cell of the matrix is a byte. The en/de-cryption process is a multi-step process. The matrix is manipulated at each step to yield a new matrix as the output of the step.
At each stage, the matrix of data, whether it is the input to the stage or it is the output of the stage, is called a STATE. The final output of the multi-step encryption process yields the ciphertext. 13 Rijndael Cipher Each stage in the en/de-cryption process A matrix of output, also called a A stage in STATE (The A matrix of output state the en/deinput, would be cryption called a naturally process different from STATE the input
state.) Given: A key K KEY EXPANSION process: One key is expanded into multiple sub-keys of the same size ROUND: a collection of steps, which are sequentially performed on a state, to produce a14 Rijandael encryption (and decryption) process: Number of Rounds (Nr) 10/12/14 times applying (nearly) the same round function. Nr = 6 + Max (Nk, Nb) Nb = 4 Nk = 4 10 Nk = 6 12 Nk = 8 14 Nb = 6
12 12 14 Nb = 8 14 14 14 15 Rijndael Cipher Rijndael Cipher: Three-step Process of encryption : initial XOR of the 128-bit block of plaintext with the sub-key 1 has 9/11/13 rounds. Each round consists of: byte substitution (The same S-box used on every byte, unlike DES, where 8 different S-boxes are used.) shift rows(permute bytes between columns) mix columns (subs using matrix multiply of groups) add round key (XOR state with separate sub-keys for each round) Incomplete last (i.e. 10/12/14th) round (without mix columns operation)
16 Example: Key Expansion for a 128 bit key and 128 bit block If Nb be fixed at 4, the number of rounds Nr = 1 + 10 or 12 or 14, depending upon the value of Nk. No of keys required= Nr + 1. Example: Given: A key of 128 bits. Nk = 4 Key: first rewritten into four components of 4 bytes each, called w(0) to w(3); Each w is of 32 bits.. Then the Key is expanded from 4 to 44 components of 32 bits each, called w(i), i = 0 to 43 For the jth round, the sub-key consists of w(4j) to w(4j+3). Total number of key bits = N(Nr + 1), where N = block size in bits 17 Rijandael Cipher continued The Rijndael cipher has a variable block length
and key length. currently keys with a length of 128, 192, or 256 bits to encrypt blocks with a length of 128, 192 or 256 bits (all nine combinations of key length and block length are possible). Both block length and key length can be extended very easily by multiples of 32 bits. Rijndael can be implemented efficiently on a wide range of processors and in hardware. all operations can be combined into XOR and table lookups - hence very fast & efficient 18 Rijandael Cipher
continued for 128 bit block: processes data as 4 groups of 4 bytes each. Each group is shown as a column in a matrix of four columns. Each column has 4 rows. Each cell of the 4x4 matrix contains one byte. The output in every round creates a new state of 128 bits or of 4 columns of 4bytes each. The ciphertext is the final output generated by the cipher system. 19 Example of selection process: Cryptographic Hash Algorithm (SHA-3) 2005: Prof. Xiaoyun Wang: a differential attack on
SHA-1: can find a hash collision (two messages with the same hash value) on the SHA-1 hash with an estimated work of 263 operations the ideal: 280 operations should be required for any good 160-bit hash function. Recommendation: Use SHA-2 family of hash functions (SHA-224, SHA-256, SHA-384 and SHA512) A competition by NIST: Entries received by October 31, 2008; July 2009: Second Round candidates selected (Reference: http://csrc.nist.gov/ as of Oct 5, 2009) 20 The AES Cipher A FIPS approved cryptographic algorithm that can be used to protect electronic data. AES: uses 128 bit block only. Key may be of 128, 192 or 256 bits. Nk may be 4/6/8. Nr = Number of rounds = 6 + Nk Reference: Federal Information Processing Standards (FIPS) Publication 197 http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf as of Oct 5, 2009 Reference: Federal Information Processing Standards (FIPS) Publication 197 http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf as of Oct 5, 2009
21 This authority (National Protection and Programs Directorate) will assist us in recruiting the best people in the world to come work for us over the next few years as cyber analysts, developers and engineers. So look out were coming. -- Janet Napolitano, Homeland Security Secretary in "DHS could hire 1000 more cyber security professionals", FederalComputerWeek, October 1, 2009 http://fcw.com/Articles/2009/10/01/Web-DHS-hiring-cybersecurity-officials.aspx as of 7th Oct 2009 22 AES vs Rijandael AES: uses 128 bit block only. (Nb = 4 only.) Rijandael can use a block of 128/ 192/ 256 bits. (Nb may be 4/6/8.) Both AES and Rijandael may use cryptographic keys of 128, 192 or 256 bits. (Nk may be 4/6/8.) AES may have 10, 12 or 14 rounds depending upon Nk of 4, 6 or 8 respectively.
23 Steps of a Round Function Round function: composed of 4 steps (except for the incomplete without MixColumn-- last round) Each step has its own particular function: ByteSub: non-linearity ShiftRow: inter-column diffusion Mix Column: inter-byte diffusion within columns Round key addition Figure on the next slide: shows both encryption and decryption processes; STATE at corresponding levels for encryption and
decryption is the same. 24 AES Cipher continued 25 Pseudo Code for Encryption for the earlier rounds, and, for the last round Round(State, RoundKey) { Bytesub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State, Roundkey); } For the last round, it is a little different: Round(State, RoundKey) { Bytesub(State); ShiftRow(State); AddRoundKey(State, Roundkey); }
26 Three Steps of Decryption initial XOR of the ciphertext with the sub-key has 9/11/13 rounds in which state undergoes: InvShift rows(permute bytes between columns) InvByte substitution (The same Inverse S-box used on every byte) add round key (XOR state with separate subkeys for each round) InvMix columns (subs using matrix multiply of groups) Incomplete last (i.e. 10/12/14th) round (without InvMix columns operation) 27 Pseudo Code for Decryption for the earlier rounds, and, for the last round Round(State, RoundKey) { InvShiftRow(State);
InvByteSub(State); AddRoundKey(State, Roundkey); InvMixColumn(State); } For the last round, it is a little different: Round(State, RoundKey) { InvShiftRow(State); InvBytesub(State); AddRoundKey(State, Roundkey); } 28 (SoOiaR) of Encryption vs. SoOiaR of Decryption Let Si be the input state for round i and let Si + 1 be the output state. Encryption Let w(4*i, 4*i + 3) be the RoundKey for the ith round. Si + 1 = AddRoundKey(MixColumn(ShiftRow(Bytesub(Si)))) In the last round, the MixColumn operation is not included. Decryption Let w(4*(10-i), 4*(10-i)+3) be the RoundKey for the ith round.
Si + 1 = InvMixColumn(AddRoundKey (InvBytesub(InvShiftRow (Si)))) In the last round, the InvMixColumn operation is not included. Method of aligning the two sequences: After a study of the 4 operations. 29 AES Cipher continued 30 AES: sources of security AES: Begins and ends with AddRoundKey These steps do not provide much of a security to AES. ByteSub, ShiftRow and MixColumn: No use of key invertible by any one;
but provide non-linearity, diffusion and confusion Jointly the two above provide security. 31 The process of Encryption: Add Round Key XOR state with 128-bits of the round key again processed by column (though effectively a series of byte operations) inverse for decryption is identical since XOR is own inverse, just with correct round key 32 Example Reference:
http://csrc.nist.gov/publications/fips/fips197/ fips197.pdf, page 33 Input M 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34 Cipher Key K = 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c 0th Round (The First Stage): M K = M0 32 88 31 e0 2b 28 ab 09 19 a0 9a e9 43 5a 31 37 7e ae f7 cf = 3d f4 c6 f8 f6 30 98 07 15 d2 15 4f e3 e2 8d 48 a8 8d a2 34 16 a6 88 3c be 2b 2a 08 Each stage generates a new STATE. Thus from M (the input state), this stage generates a new state M0. 33 First Step in a Round of Encryption: ByteSub a 0,0
a 0,1 a 0,2 a 0,3 a 1,0 a 1,1 a 1,3 a 2,0 a 2,1 a 1,2 i,j a 2,2 a 3,0 a 3,1 a 3,2
a 3,3 a a 2,3 Bytes are transformed by applying invertible S-box One single S-box for the complete cipher High non-linearity S - box b 0,0 b 0,1 b 0,2 b 0,3 b 1,0 b 1,1 b 2,1
b b 1,3 b 2,0 b 1,2 i,j b 2,2 b 3,0 b 3,1 b 3,2 b 3,3 b 2,3 34 Byte Substitution
a simple substitution of each byte uses one S-box of 16x16 bytes containing a permutation of all 256 8-bit values each byte of state is replaced by a byte from row (left 4-bits) & column (right 4-bits) eg. byte {95} is replaced by a byte from the 9th row and 5th col of the S-box. (The value in the 9th row and 5th col {2A}) S-box is constructed using a defined transformation of the values in GF(28) designed to be resistant to all known attacks 35 S-Box Reference: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf, page 16 36
Design Criteria for the Sbox Low correlation between input and output bits Output cannot be a simple mathematical function of the input. No fixed point of S-box: input and output for S-box cannot be the same. No opposite fixed point of S-box: input and output cannot be bit-wise complement of each other. 37 Construction of 16 X16 Sbox Each cell of the s-box contains one byte. Rows and columns are numbered from 0 to F. Step 1: Initialization: put in each box the value equal to its position row: column
Ex. : in row 0, column 2, the value would be 0216 or 0000 00102 Step 2: Replace the value in each cell by its multiplicative inverse by GF(28) mod (x8 + x4 + x3 + x + 1). Use extended Euclids algorithm given in the Mathematical Background. 38 Now Please Refer to the Mathematical background. 39 Multiplicative inverse Extended Euclid[m(x), b(x)] Algorithm 1. 2. 3. 4. 5.
6. 7. 8. (A1, A2, A3) (1, 0, m);); (B1, B2, B3) (0, 1, b)) If B3 = 0, return A3 = gcd(m);, b));no inverse exists. If B3 = 1 return B2 as the m);ultiplicative inverse of B. (i.e. b(x).B2 = 1 m);od m);(x) ) Q = A3/B3 (T1, T2, T3) (A1 - Q B1, A2 - Q B2, A3 - QB3) (A1, A2, A3) (B1, B2, B3) (B1, B2, B3) (T1, T2, T3) Go to 2 40 Construction of 16 X16 S-box multiplicative inverse mod (x8+x4+x3+x+1) Ex:In row 0, column 2, the value 0216 ( corresponding to a(x) = x )is replaced by its multiplicative inverse (which is shown below to be 8D16 .)
To find c(x) so that a(x).c(x) = 1 mod (x8 + x4 + x3 + x + 1). A1 A2 A3 B1 B2 B3 Q 1 0 x8+x4+x3+x+1 0 1 x 0 1 x 1 x7+x3+x2+1 1 x7+x3+x2+1 c(x) = x7+x3+x2+1 = 1000 11012 = 8D16 Step3: Use the matrix transformation, of next slide, to transform 8D16 (,called vector x], to a new vector y]). 41 Example: Row 0 and column 2 .. Contd. c(x) = x7+x3+x2+1 = 8D16 = a7x7+a6x6++a1x+a0 x] =
a0 1 a1 = 0 . 1 1 0 . a6 0 0 a7 1 42 S-Box construction:
Example. continued [M1] = 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 y] = [M1] x] + m2] 1 1 1 0 0 0 1 1 1 1 1 1 0 0
0 1 m2] = 1 1 0 0 0 1 1 0 43 Construction of 16 X16 S-box Example. continued Step3 (continued): Y2] = NOTE: M 1
1 0 1 1 0 0 0 1 + 1 1 0 0 0 1 1 0 = 0 0 1 0 1
0 0 0 + 1 1 0 0 0 1 1 0 = 1 1 1 0 1 1 1 0 The transformed value is 7716.
The Inverse S-box, provides the value 02 in the 7th row and 7th AES uses two substitution boxes : S-box for encryption and Inverse S-box for column. decryption The next slide again shows the S-box. 44 S-Box eference: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf, page 16 45 Example of Byte Sub Reference: http://csrc.nist.gov/publications/fips/fips197/ fips197.pdf, page 33 Use M0 of slide 33 as the input data for this example. M0 BYTE SUB 19 3d e3
be a0 f4 e2 2b 9a c6 8d 2a e9 f8 48 08 M11 d4 27 11 ae e0 bf 98
f1 b8 b4 5d e5 1e 41 52 30 46 Inverse Byte Substitution 95 2a 95 S-Box Inv SBox 2a 95
ad Inv SBox S-Box is NOT self-inverse. For the same input, the S-Box and the Inv S-Box will NOT have the 47 same output. Inverse S-Box x y Reference: http://csrc.nist.gov/publications/fips/fips197/fips197.pdf, 48 Construction of Inverse Substitution Box [M3] = 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1
0 1 0 0 1 0 x] = [M3] y] + m4] 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 m4] = 1 0 1 0 0 0
0 0 49 Justification x] = [M3] y] + m4] Using slide 38: x] = [M3] ([M1] x] + m2] ) + m4] = [M3] .[M1] x] + [M3]. m2] + m4] We find [M3] .[M1] = unity matrix [M3]. m2] + m4] = 0] 50 Second Step in a Round of Encryption: ShiftRows a circular byte shift to the left in each row
1st row is unchanged 2nd row does 1 byte circular shift to left 3rd row does 2 byte circular shift to left 4th row does 3 byte circular shift to left In this step, the 4 bytes of each column are distributed over 4 different columns. During decryption, the shifts are circular shifts to the right. This step provides permutation of the data. 51 ShiftRow m n o p
m n o p g h i j h i j g w
x y z y z w x b c d e e b c
d Rows are shifted over 4 different offsets High diffusion over multiple rounds: Interaction with Mix Column 52 Shift offsets: Original Rijandael spec The first row: no shift The second row: circular shift by C1 The third row: circular shift by C2 The fourth row: circular shift by C3 Nb= 4 C1= 1, C2 = 2, C3 = 3 Nb= 6 C1= 1, C2 = 2, C3 = 3 Nb= 8 C1= 1, C2 = 3, C3 = 4 AES has Nb=4 only. 53 Example of ShiftRow Reference: http://csrc.nist.gov/publications/fips/fips197/ fips197.pdf, page 33 Use M11 of slide 46 as the input data for this
example. M11 d4 27 11 ae ShiftRow e0 b8 1e bf b4 41 98 5d 52 f1 e5 30 M12 d4 e0 bf b4 5d 52 30 ae b8 41 11 f1
1e 27 98 e5 54 MixColumn a 0,0 a 0,1 a 0,2 a 0,3 a 1,0 a 1,1 a 2,0 a 2,1 a 3,0 a 3,1
a 1,2 a 1,3 0,j a 2,2 1,j a 2,3 a 3,2 2,j a 3,3 3,j a a a a 2 3 1 1 1 2 3 1 1
1 2 3 3 1 1 2 Bytes in columns are linearly combined b 0,0 b 0,1 b 0,2 b 0,3 High intra-column diffusion: b 1,0 b 1,1
b 1,3 b 2,0 b 2,1 b 3,0 b 3,1 bb 1,2 0,j bb 2,2 1,j bb 3,2 2,j b 3,j Based on theory of error-correcting codes b 2,3 b 3,3 55 Mix Columns
each column is processed separately each byte is replaced by a value dependent on all 4 bytes in the column effectively a matrix multiplication, where each byte is treated as a polynomial in GF(28) using prime poly m(x) =x8+x4+x3+x+1 Input state =S; Output state = S 56 Example:Mix Column: Evaluation of S00 Reference: Mathematical background Use M12 of slide 54 as the input data for this example. S00=(02. S00) (03.S10) (01.S20) (01.S30) values in first column: S00=d4, S10=bf, S20=5d, S30=30 01.30 = 30 0011 0000 01.5d = 5d 0101 1101
03.bf = da 1101 1010 03.bf can be represented by (x +1). a (x) mod m (x) = (x +1).(x7+x5+x4+x3+x2+x+1) mod (x8+x4 + x3 + x + 1) x.(x7+x5+x4+x3+x2+x+1) mod (x8+x4 + x3 + x + 1) = 02.bf = shift left and XOR with 1b = 0111 1110 0001 1011 = 0110 0101 01.bf = bf = 1011 1111 03.bf = 02.bf 01.bf = 1101 1010 57 Example: Mix Column: Evaluation of S00 .2 02.d4 = b3 1011 0011 x.(x7+x6+x4+ x2) mod (x8+x4 + x3 + x + 1) x.(x7+x6+x4+ x2) requires 10101000 0001 1011 = 10110011 0011 0000 0101 1101 1101 1010 10110011 =S00= 0000 0100 = 04 58
Example:Mix Column: Evaluation of S10 Reference: Mathematical background S10=(01. S00) (02.S10) (03.S20) (01.S30) S00= d4, S10= bf, S20= 5d, S30= 30 01.d4 = d4 02.bf = 65 by shifting bf once to the left and xor-ing with 1b Shift 1011 111 to left 0111 1110 0111 1110 0001 1011 = 0110 01012 = 6516 03.5d = 5d 02.5d by splitting 03 into 01 and 02 = 5d ba by shifting 5d once to the left 5d16=0101 11012 SL1011 10102 = ba16 = e7 0101 11012 1011 10102 = 1110 01112 01.30 = 30 S10= d4 65 e7 30 = 66 59 Example: Mix Column Use M12 of slide 54 as the input data for this example. Previous 3 slides: show the calculation of s 00 and s10. Similarly the whole of the state S can be calculated.
M12 d4 bf 5d 30 e0 b4 52 ae MixColumn b8 41 11 f1 1e 27 98 e5 04 66 81 e5
e0 cb 19 9a M13 48 f8 d3 7a 28 06 26 4c 60 Inverse Mix Column MC = MC-1= Hence using MC-1 would be more difficult, since it would require multiplication with more complex polynomials. 61
Selection of values in MixColumn Selected for good mixing: based on a linear code, with maximum distance between code words Small values 01, 02 and 03 lead to faster implementation require only shift and XOR Leads to more difficult decryption; CFB (Cipher Feedback) and OFB (Output Feedback) require encryption process for decryption. 62 Cipher FeedBack (CFB) 63 Output FeedBack (OFB) 64
Inverse Mix Column transformation If s be the input matrix and s be the output matrix, 0E 09 0D 0B 0B 0E 09 0D 0D 0B 0E 09 09 0D 0B 0E [S] =
[S] The above process is the inverse of the forward process, of slide 51, because - 0E 09 0D 0B 0B 0E 09 0D 0D 0B 0E 09 09 0D 0B 0E 02
01 01 03 03 02 01 01 01 03 02 01 01 01 03 02 = 01 00 00 00 00
01 00 00 00 00 01 00 00 00 00 01 65 Inverse Mix Column transformation cont Proof: the output element in row 1 and column 1 A11 = 0E . 02 OB . 01 0D . 01 09 . 03 0E . 02 = 1C by shifting 0E to the left 09 . 03 = 09 09 . 02 by splitting 03 into 01 and 02 = 09 12 by shifting 09 to the left = 1B A11 = 1C 0B 0D 1B
= 01 66 Mix Column transformation: Comments Mix Column during encryption uses values of 01, 02 and 03. these are implemented by shift or by shift XOR. Inverse Mix Column for decryption is more complex. However it was possible to make only one of the two processes simple. It was decided to make encryption process simpler than decryption because encryption is more important : AES may be used for authentication where only encryption may be used. CFB, OFB and CTP modes do not require decryption process (refer DES part 2 slides 11 -23) 67 Example (using the example of
slide 60) Inverse MixColumn M13 0e 0b 09 0e 0d 09 0b od InvMixColumn 0d 09 04 e0 48 28 0b 0d 66 cb f8 06 0e 0b . 81 19 d3 26 09 0e e5 9a 7a 4c M12 S00 = 0e.04 0b.66 0d.81 09.e5 (In the next three 3 slides, we shall show the calculation of S00) 68 Example Inverse MixColumn.. 2 0e.04: (0000 1110).(0000 0100)
Can be visualized as (x3 + x2 + x). b(x) mod (x8+x4+x3+x+1) x. b(x): 0000 1000 x2. b(x): 0001 0000 x3. b(x): 0010 0000 0e.04: 0011 1000 69 0b.66: b(x): 0110 0110 1. b(x): 0110 0110; x. b(x): 1100 1100 x2.b(x):1001 10000001 1011=1000 0011 x3.b(x):0000 01100001 1011=0001 1101 0b.66: 0110 01101100 11000001 1101 = 1011 0111 0d.81: b(x): 1000 0001 x. b(x):0000 00100001 1011=0001 1001 x2.b(x):0011 0010; x3.b(x): 0110 0100 0d.81:1000 00010011 00100110 0100 =1101 0111 70
Example: Inverse MixColumn .. 4 09.e5: b(x):1110 0101 x.b(x):1100 10100001 1011=1101 0001 x2.b(x):1010 00100001 1011=1011 1001 x3.b(x):0111 00100001 1011=0110 1001 09.e5: 0110 10011110 0101 = 1000 1100 S 11 = 0e.04 0b.66 0d.81 09.e5= 0011 10001011 01111101 01111000 1100 = 1101 0100 d4 71 Example (using the example of slide 56) Inverse Mix Column
.. 5 Proceeding in a similar manner, we shall find that, M13 InvMixColumn M12 04 66 81 e5 e0 cb 19 9a 48 28 f8 06 --IMC d3 26 7a 4c d4 e0 b8 bf b4 41 5d 52 11 30 ae f1
1e 27 98 e5 72 Fourth Step in a Round of Encryption: AddRoundKey k k k k 0,3 0,0 0,1 0,2 0,3
a a k k k k 1,1 1,2 1,3 1,0 1,1 1,2 1,3
a a a a k k k k 2,0 2,1 2,2 2,3 2,0 2,1
2,2 2,3 k k k k 3,0 3,1 3,2 3,3 a a a
a 0,0 0,1 0,2 a a 1,0 Makes the round function a a a a dependent upon key 3,0 3,1 3,2
3,3 Computation of round keys: keep it simple b b b b 0,0 0,1 0,2 0,3 Small number of operations b
b b b 1,0 1,1 1,2 1,3 b b b b Small amount of memory 2,0 2,1
2,2 2,3 73 bytes of Key called ri (Ref: Stallings Fig 5-3) 74 Key Expansion for 128 bit key and 128 bit block slide 12 A key of 128 bits or of Nk = 4: first rewritten into four components of 4 bytes each, called w(0) to w(3). Then it is expanded from 4 to 44 components of 32 bits each, called w(i), i = 0 to 43 w(4j) to w(4j+3): For the jth round of encryption, the sub-key consists of w(4j) to w(4j+3). (For decryption, this would be the key for the (10j)th round.)
75 AES Cipher continued 76 AES Key Expansion takes 128-bit (16-byte) key and expands into array of 44/52/60 32-bit words start by copying key into first 4 32-bit words, called w(0) to w(3). then use a loop, in which, each new 4-byte word depends on values in
the immediately previous word & the word, which is 4 places back. in 3 of 4 cases just XOR these together (For w(i) where i 0 mod 4) 77 AES Key Expansion continued K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14
K15 w0 w1 w2 w3 g O w4 w5 w6 w7 78 AES Key Expansion continued every 4th case: (For w(i), where i is a multiple of 4.)
The immediately preceding word goes through a process described by a function g. Three steps of g: RotWord: one byte circular left shift of the previous word SubWord: substitute each of the 4 bytes using the S-box XOR with a 32-bit round constant called Rcon(j) where j is the round number 79 Example: Key Expansion: Calculation of w4 Cipher Key = 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c w0 = 2b7e1516 w1 = 28aed2a6 w2 = abf71588 w3 = 09cf4f3c Calculation of w4: RotWord and SubWord X1 = RotWord (w3) = cf4f3c09 By using the S-box: cf4f3c09 -- S-box 8a84eb01 = X2 Example continued after two slides 80
AES Key Expansion: Rcon(j) Reference for Key expansion Problem: http://csrc.nist.gov/ publications/fips/fips197/fips-97.pdf Page 28 Calculation of w(i) for every 4th case: (For w(i), where i is a multiple of 4.): continued from previous slide The first byte of Rcon(j) is called RC(j). The second, third and the fourth bytes of Rcon(j) are 0. RC(1) = 1; RC(j) = 2.RC(j 1) for j=2 to 10. The multiplication is defined over the field GF(28), with m(x) = x8+x4+x3+x+ Thus RC(2) = 2,RC(8) = 128 rc9(x) = x8 mod m(x) = x4+x3+x+1 RC(9) = 1B RC(10) = 0011 0110 = 3616 = x5+x4+x2+x obtained by shifting RC(9) to the left 81 AES Key Expansion Rcon(j) Formulae Key expansion formulae for i = 0 to 43 w (i) = w (i-1) w (i 4) *if i is not a multiple of 4
w (i) = g {w (i-1)} w (i-4) *if i is a multiple of 4 g {w (i-1)}=R con [j] [ Subword (Rotword (w(i-1))) ] where j = Round number J 1 2 3 4 5 6 7 8 9 10 RC[j] 01 02 04 08 10 20 40 80 1B 36 R con [j] = RC[j] 00 00 00 given in HEX 82 Example: Key Expansion: continued from slide 75
Calculation of w4, w5, w6 and w7 .. .2 Rcon(1) = 01 00 00 00 X3 = 8a84eb01 01000000 = 8b84eb01 w4 = w0 X3 = 2b7e1516 8b84eb01 = a0fafe17 For w5, w6 and w7, only XOR is reqd: w5 =w1 w4 = 28aed2a6 a0fafe17= 88 54 2c b1 w6= w2w5 =abf7158888542cb1=23 a3 39 39 w7=w3 w6 = 09cf4f3c23a33939=2a 6c 76 05 83 Important Considerations:
Round Key Generation Algorithm Knowledge of a part of the cipher key or less than Nk consecutive parts of a round key: Insufficient for calculation of the key Use of round constants to eliminate symmetries 84 AES Key Expansion Example: Calculation of the 9th round key Example: given the key for 8th round is EA D2 73 21 B5 8D BA D2 31 2B F5 60 7F 8D 29 2F The Sub-key for the 8th round consists of w(32) to w(35). The Sub-key for the 9th round consists of w(36) to w(39). w(36) = g {w(35)} w(32) g[w(35)] = (1B00 0000) [subword (rotword(7F 8D 29 2F)) ] = (1B00 0000) [subword (8D 29 2F 7F)] Now use S-Box:
g[w(35)] = (1B00 0000) (5D A5 15 D2) = 46 A5 15 D2 w(36) = (46 A5 15 D2) (EA D2 73 21) = AC 77 66 F3 85 AES Key Expansion Example: Calculation of the 9th round key 2 w(37) = w(36) w(33) = (AC 77 66 F3) (B5 8D BA D2) = 19 FA DC 21 w(38) = w(37) w(34) = (19 FA DC 21) (31 2B F5 60) = 28 D1 29 41 w(39) = w(38) w(35) = (28 D1 29 41) ( 7F 8D 29 2F) = 57 5C 00 6E Key for the 9th round = AC 77 66 F3 19 FA DC 21 28 D1 29 41 57 5C 00 6E 86 AES Decryption vs Encryption
Steps in AES decryption vs those in AES encryption: The steps for encryption and decryption processes are not identical (unlike the case for DES). Moreover in each round, the steps are not in a similar sequence for encryption and decryption. Each Round of Encryption: SubBytes ShiftRows MixColumns AddRoundkey Each Round of Decryption: InvShiftRows InvSubBytes AddRoundkey InvMixColumns Disadvantage: AES requires 2 separate software/firmware systems for encryption and decryption 87 data,
by using only the AES Encryption process Cipher Feedback (CFB): used over a reliable network layer for stream data encryption, authentication Output Feedback (OFB): Can be used over noisy channels for bursty traffic aplications; OFB requires that sender and receiver must remain in sync Counter Mode (CTR): for high-speed network encryptions as in ATM or IPSec; good for bursty high speed links 88 Sequence of Steps in a Round of Decryption An equivalent inverse cipher with the
same sequence ( but of inverse operation) of steps, as for encryption: requires an additional step of InverseMixColumn on the Round Key, before the step of AddRoundKey ( except for the first and the last steps of AddRoundKey) Reference: Cryptography & Network Security by William Stalling, Prentice Hall, 4th Ed ,Figure 5.7, page 158. 89 Some tools may get the job done, but they may not get the job done well - Mike Shema et al, Anti-Hacker Toolkit, pp xxiv, 3rd Ed, McGraw Hill, 2006 90 AES: Implementation Aspects can be efficiently implemented on 8bit CPUs
byte substitution works on bytes using a S-box of 256 entries shift rows is simple byte shifting add round key works on byte XORs mix columns requires matrix multiply in GF(28) which works on byte values, can be simplified to use a table lookup 91 MixColumn 8-bit processor Implementation Tmp = Soj S1j S2j S3j On putting the value of TMP and on replacing {03}.x = {02}.x x, the following 4 equations are equivalent to the above MixColumn operation. Soj = Soj Tmp [2.(Soj S1j )]
S1j = S1j Tmp [2.(S1j S2j )] S2j = S2j Tmp [2.(S2j S3j )] S3j = S3j Tmp [2.(S3j S0j )] 92 To Prove: Soj = Soj Tmp [2.(Soj S1j )] From the matrix equation in the previous slide, Soj = {02}. Soj {03}. S1j S2j S3j We know: {03}. S1j = {02}. S1j S1j RHS = Soj Tmp [2.(Soj S1j )] = Soj Soj S1j S2j S3j [2.(Soj S1j )] = S1j S2j S3j {2}.(Soj) {2}. (S1j ) = {2}.(Soj) {03}. S1j S2j S3j = Soj = LHS 93 MixColumn 8-bit processor
Implementation2 {02}.x requires (i) A left-shift if b7 = 0 OR (ii) A left-shift followed by XOR with 1b16 if b7 = 1. a timing attack. SOLUTION: The 4 terms (Sij S((i+1)mod4)j) for i = 0 to 3: can yield 256 different types of byte values. Let X = = {02}.Y where Y is a byte variable and can have any one of the 256 possible values. X is pre-calculated and stored in a 256-byte look-up table. Soj = Soj Tmp X[Soj S1j] S1j = S1j Tmp X[S1j S2j]
S2j = S2j Tmp X[S2j S3j] S3j = S3j Tmp X[S3j S0j] 94 Implementation Aspects can be efficiently implemented on 32-bit CPUs: redefine steps to use 32-bit words can pre-compute 4 tables; (Pl see page 159-160.) Each 16x16 table: Input of a byte; Output of 32 bits (1 KB of storage) then each column in each round can be computed using 4 table lookups + 4 XORs at a cost of 4 KB to store tables Joan Daemen and Vincent Rijmen believe: This very efficient implementation: a key factor in its selection as the AES cipher
95 Each Round of Rijndael on Modern Processors For bj: use a(0,j), a(1,j-1), a(2,j-2) and a(3,j-3) a 0,0 a 1,0 a 2,0 a 3,0 K2 a a a 0,1 0,2 0,3
a a a 1,1 1,2 1,3 a a a 2,1 2,2 2,3 a a
a 3,1 3,2 3,3 X3,2 T1 T2 b0 b1 b2 b3 T3 T4 X2,2 X1, X0,2
b2 2 just (4 table-lookups and 4 XORS) per column and per round; Storage of 4 tables of 256 entries of 32 bits each. 96 Implementation Aspects .2 Most efficient on Itanium (64 bit machine) Highest performer on limited processing power and limited memory devices twice as fast as the nearest rival from the 5 finalists (MARS, RC6, RIJNDAEL, SERPENT, TWOFISH) Most efficient in feedback modes; second best in CBC/ECB MODES
97 Implementation Aspects .2 .. Throughput decreases by 20% and 40% on increase of key size from 128 to 192 and 256 respectively If implemented in hardware in ECB (Electronic Code Book, where each block of 128 bits is sent separately after encryption) mode, speed matched only by SERPENT Safety Margin 7 for 10 round case (Safety Margin: number of rounds, above which efficient attacks on the algorithm cannot be mounted and keyspace exhaustion becomes the only way to crack it.) 98 Timing and Power Attacks:
Some Facts writing 1s consumes more power than for writing 0s. Table lookups in S-boxes, shifts, rotations, NOT, OR, AND, XOR: Not vulnerable to timing attacks To avoid power attacks: software balancing is required 99 Characteristics of Rijndael symmetrical parallel structure
Well adapted to modern processors Gives implementers a lot of flexibility has not allowed effective cryptanalytic attacks Pentium RISC and parallel processors Suited for Smart cards Flexible in dedicated hardware designed to resist known attacks 100 Misgivings about AES AES (and Serpent) encryption can be written as a group of linear and quadratic equations in a finite field. Mathematicians are trying to develop methods to solve such equations. (XSL, XL and FXL methods). If they succeed, the Encryption method will fail.
Due to Birthday and man-in-the-middle attack, for 128 bit security, a key size of 256 bits is required. But AES is slower for 256 bit key. (Serpent has the same speed for all key sizes. Twofish is slower.) 101 Relative Performance Fast Typical speeds
RC4 (Stream Cipher) Blowfish, CAST-128, AES Skipjack DES, IDEA, RC2 3DES, GOST RC4 = Tens of MB/second 3DES = MB/second Recommendations: For performance, use Blowfish; For job security, use 3DES 102 Advanced Encryption Standard Algorithm (Rijndael) References: http://csrc.nist.gov/publications/fips/fips197/fip s-197.pdf For historical information: http://csrc.nist.gov/CryptoToolkit/a
es/ http://www.esat.kuleuven.ac.be/~rijmen/ rijndael/ 103 Stream Cipher Streaming Cipher: encrypts data unit by unit, where a unit is of certain number of bits (Example: If the unit be a bit, a stream cipher encrypts data unit by unit. Or if the unit be a byte, it encrypts byte by byte) simpler and faster than block cipher; but less secure Two Modes of Stream Cipher: Synchronous Stream Cipher: Sender uses a key to encrypt. Receiver uses the same key to decrypt. Self-Synchronizing Stream Cipher: The key stream
generator (KSG) generates a key, which depends upon the original key and the cipher output. 104 Key Stream Generator (KSG) Key Pseudorandom Byte Generator Stream of bytes The stream of bytes cannot be determined, if the Key is not known. The stream is deterministic. The stream repeats after a long chain of bits. 105 Self-Synchronizing Stream Cipher Stream of bytes
Plaintext Ciphertext In a stream Cipher, a key must not be repeated. 106 Example of a Stream Cipher RC4: A byte by byte encryption algorithm, used in SSL (Secure socket Layer) WEP (Wired Equivalent Privacy)
Developed in 1987 by Ron Rivest for RSA Sept 1994: RC4 algorithm: anonymously posted on Cypherpunks anonymous remailers list 107 RC4: Key and the Temporary Vector Key: 1 to 256 octets First byte of Key: K[0]; Second byte of key: K[1] No of bytes of key = kbytes A 256 byte Temporary vector: T[0] to T[255] If kbytes = 256, for i = 0 to 255, T[i] = K[i] If kbytes < 256, for i=0 to 255, T[i] = K[i mod kbytes]
108 RC4: The State Vector A 256 byte State vector: S[0] to S[255] INITIALIZATION: For i = 0 to 255, S[i] = i Initial PERMUTATION of S: j = 0; For i = 0 to 255, j = (j + S[i] + T[i]) mod 256 Swap (S[i] and S[j]). After initial permutation, the key is not used. 109 Stream Encryption mth byte of Plaintext P[m] i = j = 0; m = 0 while (true){ i = (i + 1) mod 256; j = (j + S[i]) mod 256;
swap (S[i], S[j]); t = (S[i] + S[j]) mod 256; k = S[t]; C[m] = P[m] k; m=m+1 } 110 Strength of RC4 For decryption, xor k with the next byte of ciphertext. For a key length of 128 bits or more, RC4 is secure. The weakness in WEP: due to the weakness of the protocol for key generation ( not due to weakness in RC4). Reference: Fluhrer, S.; Mantin, I.; and Shamir, A. Weakness in the Key Scheduling Algorithm of RC4, Proceedings, Workshop in Selected Areas of
Cryptography, 2001 111 Symmetric Key Ciphers Symmetric key ciphers: efficient, secure Problem: How to share a key securely between the sender and the receiver? If 100 persons want to send message securely to one another 4950 different keys are required (Reference: Niels Ferguson and Bruce Schneier , Practical Cryptography, Wiley 2003) 112
Kamil Trzebiatowski - Me, Myself and I - Educational Consultancy
Dictagloss. Using diagrams to show knowledge. Delivering the content to EAL learners. Scaffolding (substitution tables, writing frames, oral frameworks) Realia, video, artefacts, charts. Key visuals / graphic organizers. Modelling of the use of key language features.LibQUAL+ 2002 Tales from Past Participants Vanderbilt ...
LibQUAL+ 2002 Tales from Past Participants Vanderbilt University Library Flo Wilson, Deputy University Librarian [email protected] Vanderbilt's Survey Experience Background and survey administration Waiting for the data and the analysis What do we think we know?