Advanced Encryption Standard (AES) Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University
Advanced Encryption Standard (AES) Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University
History Clear a replacement for DES was needed -Have theoretical attacks that can break it -Have demonstrated exhaustive key search attacks -Block size small -Can use Triple-DES-but slow US NIST issued call for ciphers in 1997 -15 candidates accepted in Jun 98 -5 were shortlisted in Aug-99 -Rijndael was selected as the AES in Oct 2000 -Issued as FIPS PUB 197 standard in Nov 2001 2
2 History Clear a replacement for DES was needed ─ Have theoretical attacks that can break it ─ Have demonstrated exhaustive key search attacks ─ Block size small ─ Can use Triple-DES – but slow US NIST issued call for ciphers in 1997 ─ 15 candidates accepted in Jun 98 ─ 5 were shortlisted in Aug-99 ─ Rijndael was selected as the AES in Oct 2000 ─ Issued as FIPS PUB 197 standard in Nov 2001
AES Requirements Symmetric key 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 -NIST have released all submissions unclassified analyses 3
3 AES Requirements Symmetric key 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 NIST have released all submissions & unclassified analyses
Aes Evaluation criteria Initial criteria: 一 Security-randomness,soundness,effort for practical cryptanalysis -Cost-computational efficiency,no licensing fee,small memory -Algorithm implementation characteristics-flexibility,implementable in both software and hardware,simplicity Final criteria -General security-NIST relies on the cryptanalysis by crypto researchers Ease of software hardware implementation 一 Implementation attacks-finding keys based on implementation characteristics .Timing attacks:an encryption or decryption algorithm often takes slightly different amounts of time on different inputs. Power analysis:the power consumed by a smart card at any particular time during the cryptographic operation is related to the instruction being executed and to the data being processed.For example,multiplication consumes more power than addition,and writing 1s consumes more power than writing 0s -Flexibility (encryption,decryption,keying,and other factors) 4
4 AES Evaluation Criteria Initial criteria: ─ Security – randomness, soundness, effort for practical cryptanalysis ─ Cost – computational efficiency, no licensing fee, small memory ─ Algorithm & implementation characteristics – flexibility, implementable in both software and hardware, simplicity Final criteria ─ General security – NIST relies on the cryptanalysis by crypto researchers ─ Ease of software & hardware implementation ─ Implementation attacks – finding keys based on implementation characteristics ● Timing attacks: an encryption or decryption algorithm often takes slightly different amounts of time on different inputs. ● Power analysis: the power consumed by a smart card at any particular time during the cryptographic operation is related to the instruction being executed and to the data being processed. For example, multiplication consumes more power than addition, and writing 1s consumes more power than writing 0s ─ Flexibility (encryption, decryption, keying, and other factors)
AES Shortlist After testing and evaluation,shortlist in Aug 99: -MARS (IBM)-complex,fast,high security margin -RC6 (USA)-very simple,very fast,low security margin -Rijndael(Belgium)-clean,fast,good security margin -Serpent(Euro)-slow,clean,very high security margin -Twofish(USA)-complex,very fast,high security margin Then subject to further analysis comment Saw contrast between algorithms with -Few complex rounds vs.many simple rounds -which refined existing ciphers vs.new proposals 5
5 AES Shortlist After testing and evaluation, shortlist in Aug 99: ─ MARS (IBM) - complex, fast, high security margin ─ RC6 (USA) - very simple, very fast, low security margin ─ Rijndael (Belgium) - clean, fast, good security margin ─ Serpent (Euro) - slow, clean, very high security margin ─ Twofish (USA) - complex, very fast, high security margin Then subject to further analysis & comment Saw contrast between algorithms with ─ Few complex rounds vs. many simple rounds ─ which refined existing ciphers vs. new proposals
The AES Cipher-Rijndael Designed by Rijmen-Daemen in Belgium An iterative rather than Feistel Cipher -Processes data as block of 4 columns of 4 bytes -Operates on entire data block in every round ·Designed to be: -resistant against known attacks -Speed and code compactness on many CPUs -Design simplicity 6
6 The AES Cipher - Rijndael Designed by Rijmen-Daemen in Belgium An iterative rather than Feistel Cipher ─ Processes data as block of 4 columns of 4 bytes ─ Operates on entire data block in every round Designed to be: ─ resistant against known attacks ─ Speed and code compactness on many CPUs ─ Design simplicity
AES Parameters Key Size (words/bytes/bits) 4/16/128 6/24/192 8/32/256 Plaintext Block Size(words/bytes/bits) 4/16/128 4/16/128 4/16/128 Number of Rounds 10 12 14 Round Key Size(words/bytes/bits) 4/16/128 4/16/128 4/16/128 Expanded Key Size(words/bytes) 44/176 52/208 60/240 7
7 AES Parameters
Advanced Encryption Standard (AES) Input 128 bit plaintext 128 bit cipher key 33 88 31 e0 k k4 ks k12 43 5a 31 37 k1 ks ko k13 f6 30 9807 k2 k6 K10 K14 a8 8d a2 34 ka k7 ku k15 Encryption Progress Key Expansion 8
8 Advanced Encryption Standard (AES) 33 88 31 e0 43 5a 31 37 f6 30 98 07 a8 8d a2 34 Input 128 bit plaintext k0 k4 k8 k12 k1 k5 k9 k13 k2 k6 k10 k14 k3 k7 k11 k15 128 bit cipher key Encryption Progress Key Expansion
Encryption Progress Encryption Progress Initial round State Cipher Key 一 Substitute Bytes -Shift Rows AddRoundKey ⊕ Mix Columns -Add Round Key 1-SubBytes 9 rounds 2-ShiftRows 3-MixColumns Round key 1~9 4-AddRoundKey ⊕ SubBytes final rounds ShiftRows Round key 10 AddRoundKey ⊕ 9
9 Encryption Progress Encryption Progress ─ Substitute Bytes ─ Shift Rows ─ Mix Columns ─ Add Round Key Initial round 9 rounds final rounds 1~9
Encryption Progress-Substitute Bytes d4 e0 b8 le 27 bf b4 41 11 98 5d 52 ae fl e5 30 y 业 hex 0 1 2 3 4 5 6 7 8 9 a b d e f 0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76 1 ca 82 c9 7d fa 59 47 fO ad d4 a2 af 9c a4 72 c0 2 b7 fd 93 26 36 3f f7 cc 34 e5 f1 71 d8 31 15 3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 4 09 83 2c la 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 5 53 dl 00 ed 20 fc bl 5b 6a cb be 39 4a 4c 58 cf 6 do ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 9 60 81 4f de 22 2a 90 88 46 ee b8 14 de 5e 0b db a e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a d 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 cl 1d 9e e el f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df f 8c al 89 0d bf e6 42 68 41 99 2d Of b0 54 bb 16 10
10 Encryption Progress – Substitute Bytes 19 a0 9a e9 3d f4 c6 f8 e3 e2 8d 48 be 2b 2a 08 d4 d4 e0 b8 1e 27 bf b4 41 11 98 5d 52 ae f1 e5 30