Aes g4j2j
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3i3n4
Overview 26281t
& View Aes as PDF for free.
More details 6y5l6z
- Words: 3,366
- Pages: 47
Adopted
by National Institute of Standards and Technology (NIST) on May 26, 2002. AES is a simple design, a high speed algorithm, with low memory costs. AES is a symmetric block cipher.
The same key is used to encrypt and decrypt the message. The plain text and the cipher text are the same size.
AES
has a fixed block size of 128 bits called a state
ABCDEFGHIJKLMNOP A B C D
E F G H
I J K L
M N O P
(ASCII)
41 42 43 44
45 46 47 48
49 4A 4B 4C
4D 4E 4F 50
AES
key is either 128 bits, 192 bits or 256 bits
128 bits (4 words): 11223344556677889900AABBCCDDEEFF 11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
or 192 bits (6 words) 1122334455667788 9900AABBCCDDEEFF 1122334455667788 11 55 99 CC 11 55
22 66 00 DD 22 66
33 77 AA EE 33 77
44 88 BB FF 44 88
or 256 bits (8 words) 1122334455667788 9900AABBCCDDEEFF 1122334455667788 9900AABBCCDDEEFF
11 55 99 CC 11 55 99 CC
22 66 00 DD 22 66 00 DD
33 77 AA EE 33 77 AA EE
44 88 BB FF 44 88 BB FF
Expanded Key Length Key Length Block Size Number of (words) (Nk words) (Nb words) Rounds Nr AES-128 4 44 4 10 AES-192 6 52 4 12 AES-256 8 60 4 14 4 10 Rijndael - 128 4 44 6 12 8 14 4 12 Rijndael - 192 6 52 6 12 8 14 4 14 Rijndael - 256 8 60 6 14 8 14 * DES 256 2 16 2 * of 64 bits, only 56 are used
The
key security feature is the size of the key.
Assuming that one could build a machine that could recover a DES key in a second (i.e., try 255 keys per second), then it would take that machine approximately 149 thousand-billion (149 trillion) years to crack a 128-bit AES key. To put that into perspective, the universe is believed to be less than 20 billion years old.
• Accepting Moore's Law, doubling processor speed every 18 months, AES will be secure for another 109.5 years.
AES
Operates on the binary field GF(28).
This can be represented as a polynomial b(x) with binary coefficients b {0,1}:
b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0
• Multiplication in GF(28) consists of multiplying two polynomials modulo an irreducible polynomial of degree 8. – AES uses the following irreducible polynomial m(x) = x8 + x4 + x3 + x + 1
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
Sample Key: 11223344556677889900AABBCCDDEEFF
The
first 4 (Nk) words are set equal to the key
w[0] w[1] w[2] w[3]
11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
For words 4 through 43
i = Nk // Nk = 4 while (i < Nb*(Nr+1)) { // Nb*(Nr+1)= 4*(10+1)= 44 temp = w[ i –1] If ( i%Nk == 0 ) rotate word left 1 byte process each byte through sbox XOR with RCON[i/Nk-1] // just first byte of w[i] w[ i ] = w[ i-4 ] XOR temp i++}
AES Algorithm Key Expansion w[0] w[1] w[2] w[3]
11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
i=4 i = Nk // Nk = 4 while (i < Nb*(Nr+1)) { // Nb*(Nr+1)= 4*(10+1)= 44 temp = w[ i - 1 ] temp = w[3] = CC DD EE FF
If ( i%Nk == 0 ) temp = CC DD EE FF temp = DD EE FF CC rotate word left 1 byte process each byte through sbox temp = sbox[DD] sbox[EE] sbox[FF] sbox[CC] = C1 28 16 4B XOR with RCON[i/Nk-1] RCON[0] = 01 temp = (C1 temp = C0
01) 28 16 28 16 4B
4B
i xi
0 0x01
i xi
1 0x02
8 0x1b
Powers of x = 0x02 2 3 4 0x04 0x08 0x10
5 0x20
Powers of x = 0x02 9 A B C 0x36 0x6c 0xd8 0xab
6 0x40
D 0x4d
7 0x80
E 0x9a
rCon can be implemented with a look-up-table 2i in GF(28) Removes symmetry and linearity from key expansion.
For words 4 through 43
i = Nk // Nk = 4 i=4 while (i < Nb*(Nr+1)) {// Nb*(Nr+1)= 4*(10+1)= 44 temp = W[i-1] If (i%Nk == 0) rotate word left 1 byte process each byte through sbox XOR with RCON[i] // just first element of w w[i] = w[i-4] XOR temp temp = C0 28 i++}
w[i] = w[i-4] XOR temp
16
4B
w[0] w[1] w[2] w[3] w[4]
11 55 99 CC D1
22 66 00 DD 0A
33 77 AA EE 25
44 88 BB FF 0F
i=4 temp = C0 28 16 4B w[i] = w[i-4] XOR temp w[4] = (11 C0) (22 28) (33 16) w[4] = D1
0A
25 0F
(44
4B)
For words 4 through 43
i = Nk // Nk = 4 i=5 while (i < Nb*(Nr+1)) { // Nb*(Nr+1)= 4*(10+1)= 44 temp = w[i1] If (i%Nk == 0) temp = w[4] = D1 0A 25 0F rotate word left 1 byte process each byte through sbox XOR with RCON[i/Nk-1] // just first element of W w[i] = w[i-4] XOR temp i++}
w[0] w[1] w[2] w[3] w[4]
11 55 99 CC D1
22 66 00 DD 0A
33 77 AA EE 25
44 88 BB FF 0F
i=5 temp = D1 0A 25 0F w[i] = w[i-4] XOR temp w[5] = (55 D1) (66 0A) (77 25) w[5] = 84
C6
52 87
(88
0F)
Beginning Key Expansion for: 11 22 33 44 55 66 77 88 99 00 AA BB CC DD EE FF i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
subword
rCon
C1 28 16 4B
C0 28 16 4B
C8 47 2E 3E
CA 47 2E 3E
B0 A9 3B ED
B4 A9 3B ED
92 D2 D3 F8
9A D2 D3 F8
76 27 C5 B1
66 27 C5 B1
90 66 40 A9
B0 66 40 A9
B8 68 E1 11
F8 68 E1 11
9C 0B 6C D4
1C 0B 6C D4
F2 D1 66 D6
E9 D1 66 D6
A0 D5 49 58
96 D5 49 58
w[i-4]XORtemp w[i] 11 55 99 CC D1 84 1D D1 1B 9F 82 53 AF 30 B2 E1 35 05 B7 56 53 56 E1 B7 E3 B5 54 E3 1B AE FA 19 07 A9 53 4A EE 47 14 5E 78 3F 2B 75
22 66 00 DD 0A 6C 6C B1 4D 21 4D FC E4 C5 88 74 36 F3 7B 0F 11 E2 99 96 77 95 0C 9A 1F 8A 86 1C 14 9E 18 04 C5 5B 43 47 10 4B 08 4F
33 77 AA EE 25 52 F8 16 0B 59 A1 B7 30 69 C8 7F E3 8A 42 3D 26 AC EE D3 66 CA 24 F7 87 4D 69 9E EB A6 CF 51 8D 2B E4 B5 C4 EF 0B BE
44 88 BB FF 0F 87 3C C3 31 B6 8A 49 DC 6A E0 A9 24 4E AE 07 95 DB 75 72 3C E7 92 E0 2D CA 58 B8 F9 33 6B D3 2F 1C 77 A4 77 6B 1C B8
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
41 42 43 44
41 11 42 22 43 33 44 44
45 46 47 48
45 55 46 66 47 77 48 88
State 49 4A 4B 4C
4D 4E 4F 50
49 99 4D CC 4A 00 4E DD 4B AA 4F EE 4C BB 50 FF
Expanded Key w[0] w[4] 11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
After AddRoundKey 50 60 70 00
10 20 30 C0
D0 4A E1 F7
81 93 A1 AF
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
SubBytes
is the SBOX for AES This make AES a non-linear cryptographic system. For every value of b there is a unique value for b’
It is faster to use a substitution table (and easier). b'0 b'1 b'2 b'3 b'4 b'5 b'6 b'7
=
1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1
1 0 0 0 1 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 0 0 0 1
x is the inverse value of the byte b
x0 x1 x2 x3 x4 x5 x6 x7
+
1 1 0 0 0 1 1 0
Y
X
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 ca b7 4 9 53 d0 51 cd 60 e0 e7 ba 70 e1 8c
1 7c 82 fd c7 83 d1 ef a3 0c 81 32 c8 78 3e f8 a1
2 77 c9 93 23 2c 0 aa 40 13 4f 3a 37 25 b5 98 89
3 7b 7d 26 c3 1a ed fb 8f ec dc 0a 6d 2e 66 11 0d
4 f2 fa 36 18 1b 20 43 92 5f 22 49 8d 1c 48 69 bf
5 6b 59 3f 96 6e fc 4d 9d 97 2a 6 d5 a6 3 d9 e6
6 6f 47 f7 5 5a b1 33 38 44 90 24 4e b4 f6 8e 42
7 c5 f0 cc 9a a0 5b 85 f5 17 88 5c a9 c6 0e 94 68
8 30 ad 34 7 52 6a 45 bc c4 46 c2 6c e8 61 9b 41
9 1 d4 a5 12 3b cb f9 b6 a7 ee d3 56 dd 35 1e 99
a 67 a2 e5 80 d6 be 2 da 7e b8 ac f4 74 57 87 2d
b 2b af f1 e2 b3 39 7f 21 3d 14 62 ea 1f b9 e9 0f
c fe 9c 71 eb 29 4a 50 10 64 de 91 65 4b 86 ce b0
d d7 a4 d8 27 e3 4c 3c ff 5d 5e 95 7a bd c1 55 54
e ab 72 31 b2 2f 58 9f f3 19 0b e4 ae 8b 1d 28 bb
f 76 c0 15 75 84 cf a8 d2 73 db 79 8 8a 9e df 16
State 50 60 70 00
10 20 30 C0
D0 4A E1 F7
53 D0 51 63
CA B7 04 BA
81 93 A1 AF
70 D6 F8 68
Sbox( 50 ) Sbox( 60 ) Sbox( 70 ) Sbox( 00 )
0C DC 32 79
Sbox( 10 ) Sbox( 20 ) Sbox( 30 ) Sbox( C0 )
Sbox( D0 ) Sbox( 81 ) Sbox( 4A ) Sbox( 93 ) Sbox( E1 ) Sbox( A1 ) Sbox( F7 ) Sbox( AF )
KeyExpansion(byte key[4*Nk],word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
Simple
routine which performs a left shift rows 1, 2 and 3 by 1, 2 and 3 bytes respectively 53 B7 F8 79
Before Shift Rows
53 D0 51 63
CA B7 04 BA
70 D6 F8 68
CA D6 32 63
70 DC 51 BA
0C D0 04 68
After Shift Rows
0C DC 32 79
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
This
with shift rows provides diffusion The columns are considered polynomials over GF(28) and multiplied modulo x4+1 with a(x) where a(x) = {03}x3 + {01}x2 + {01}x + {02} NOTE: x4+1 is relatively prime to a(x) a’j (aj*a(x))mod(x4+1) This can also be written as matrix multiplication. a’ 0
02 03 01 01
a0
a’ 1
01 02 03 01
a1
2
01 01 02 03
a2
a’ 3
03 01 01 02
a3
a’
=
a’0
02 03 01 01
a0
a’1
01 02 03 01
a1
=
+ 3a11 + aa22 +a3 a’0 = 2a0 a a3’ = a + 2a + 3a + a 1
0
1
2
3
’ = a 2a 3a a ’1 = a0 + a 1 2 3a a + 2a + a 01 01 02 03 2 0 1 2 3 2 2 a3 a’’3 = 3a0 + a1 + a2 + 2a3 a’3 03 01 01 02 a3 a 2 = a0 a1 2a2 3a3 Addition is easy in GF(28) : Addition is just the XOR operation
a’
’ = 3a a a Multiplication by 1 is easy in GF(28) : Multiplicationaby 3 one is 0 the identity 1 2
2a3 Multiplication by 2 in GF(28) takes some work: . If multiplying by a value < 0x80 just shift all the bits left by 1 . If multiplying by a value ≥ 0x80 shift left by 1 and XOR with 0x1b . This prevents overflow and keeps the values within range To Multiply by 3 in GF(28) : a * 0x03 = a * (0x02 + 0x01) = (a * 0x02) (a * 0x01)
KeyExpansion(byte key[4*Nk], word w[Nb* (Nr+1)],Nk) Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb -1]) for round = 1 step 1 to Nr –1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb -1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb -1]) out = state end
Input String
Key
Output String (HEX)
Input String(HEX)
Key
Output String (HEX)
ABCDEFGHIJKLMNOP 11223344556677889900AABBCCDDEEFF
BC4784A37D6F46452656B993D53393F5
00000000000000000000000000000000
00000000000000000000000000000000
66E94BD4EF8A2C3B884CFA59CA342B2E
ABCDEFGHIJKLMNOP 01223344556677889900AABBCCDDEEFF
855866490543FDF6504FC84088FEDCA0
00000000000000000000000000000000
00000000000000000000000000000001
0545AAD56DA2A97C3663D1432A3D1C84
ABCDEFFHIJKLMNOP 11223344556677889900AABBCCDDEEFF
372CCA446C0D391C4381392344630EE1
00000000000000000000000000000001
00000000000000000000000000000001
A17E9F69E4F25A8B8620B4AF78EEFD6F
Encryption
Decryption Cipher Text
PlainText
RoundKey
AddRoundKey
1st Round
RoundKey*
SubBytes ShiftRows MixColumns RoundKey
Repeat Nr -1 Round
InvSubBytes RoundKey*
AddRoundKey InvMixColumns
SubBytes
InvShiftRows
AddRoundKey CipherText
1st Round
InvShiftRows
AddRoundKey
ShiftRows RoundKey
AddRoundKey
Last Round
InvSubBytes RoundKey*
Repeat Nr -1 Round
Last Round
AddRoundKey
Plain Text * RoundKey Added in reverse order
How
to avoid frequency analysis?
Cipher Block Chaining
If
plaintext messages are not divisible by 16 bytes. Padding may be a solution. An easy method is to add a single 1 bit at the end of the message followed by enough 0’s to fill the block.
If the block is filled, encode one more block with a 1 followed by 0’s.
Differential
Cryptanalysis – Study of how differences in input affect differences in output.
Greatly reduced due to high number of rounds.
Linear
Cryptanalysis – Study of correlations between input and output.
SBOX & Mix Columns are designed to frustrate Linear Analysis
Side
Channel Attacks – Attacks based on studying and measuring the actual implementation of the code.
For some implementations of AES the key has been obtained in under 100 minutes.
Computer running AES was 850MHz, Pentium III running FreeBSD 4.8
Timing
Attacks – Watches movement of data in and out of the U or memory.
It is difficult to retrieve an array element in a time that is not dependent on the index value.
Power
Attacks – Watches power consumption by U or memory.
Changing one bit requires considerably less power than changing all bits in a byte.
Avoid
use of arrays. Compute values in SBOX and
rCon. Design algorithms and devices to work with constant time intervals. (independent of key and plaintext.)
Hidden U timing data is a threat.
Use
same memory throughout, Cache is faster than DRAM Compute Key Expansion on the fly. Utilize pipelining to stabilize U power consumption.
Extremely
fast compared to other block ciphers. (tradeoff between size and speed) The round transformation is parallel by design. Important in dedicated hardware. Amenable to pipelining The cipher does not use arithmetic operations so has no bias towards big or little endian architectures.
Fully
Self-ing. Does not use Sboxes of other ciphers, bits from Rand tables, digits of or any other such jokes. Is not based on obscure or not well understood processes The tight cipher design does not leave enough room to hide a trap door.
The
inverse cipher is less suited to smart cards, as it takes more codes and cycles. The cipher and inverse cipher make use of different codes and/or tables. In hardware, The inverse cipher can only partially re-use circuitry which implements the cipher.
About AES AES Proposal : Rijndael Joan Daemen, Vincent Rijmen, 2nd version of document to NIST Polynomials in the Nations Service: Using Algebra to Design the Advanced Encryption Standard Susan Landau The Mathmatical Association of America, Monthly 111 Feb 2004 Page(s):89-117 Selecting the Advanced Encryption Standard Security & Privacy Magazine, IEEE Volume 1, Issue 2, Mar-Apr 2003 Page(s):43 - 52
Title: Introduction to Cryptography Author: Johannes A Buchman Publisher: Springer; 2 edition (July 13, 2004)
Burr, W.E.;
Security and Attacking AES Power-analysis attack on an ASIC AES implementation Ors, S.B.; Gurkaynak, F.; Oswald, E.; Preneel, B.;Information Technology: Coding and Computing, 2004. Proceedings. ITCC 2004. International Conference onVolume 2, 2004 Page(s):546 - 552 Vol.2 Algebraic attacks on cipher systems Penzhorn, W.T.; AFRICON, 2004. 7th AFRICON Conference in Africa Volume 2, 2004 Page(s):969 - 974 Vol.2 Cache-Timing attacks on AES Daniel J Bernstein Preliminary version of report to National Science Foundation, grant CCR9983950
Applications / Implementations: AES A high throughput low cost AES processor Chih-Pin Su; Tsung-Fu Lin; Chih-Tsiun Huang; Cheng-Wen Wu; Communications Magazine, IEEE Volume 41, Issue 12, Dec. 2003 Page(s):86 - 91 An efficient FPGA implementation of advanced encryption standard algorithm Shuenn-Shyang Wang; Wan-Sheng Ni; Circuits and Systems, 2004. ISCAS '04. Volume 2, 23-26 May 2004 Page(s):II - 597-600 Vol.2 High-speed VLSI architectures for the AES algorithm Xinmiao Zhang; Parhi, K.K.; Very Large Scale Integration (VLSI) Systems Volume 12, Issue 9, Sept. 2004 Page(s):957 – 967 Fast implementation of AES cryptographic algorithms in smart cards Chi-Feng Lu; Yan-Shun Kao; Hsia-Ling Chiang; Chung-Huang Yang; Security Technology, 2003. 14-16 Oct. 2003 Page(s):573 - 579
Applications / Implementations : AES
A new VLSI implementation of the AES algorithm Liang Deng; Hongyi Chen; Communications, Circuits and Systems and West Sino Expositions, IEEE 2002 International Conference on Volume 2, 29 June-1 July 2002 Page(s):1500 - 1504 vol.2
by National Institute of Standards and Technology (NIST) on May 26, 2002. AES is a simple design, a high speed algorithm, with low memory costs. AES is a symmetric block cipher.
The same key is used to encrypt and decrypt the message. The plain text and the cipher text are the same size.
AES
has a fixed block size of 128 bits called a state
ABCDEFGHIJKLMNOP A B C D
E F G H
I J K L
M N O P
(ASCII)
41 42 43 44
45 46 47 48
49 4A 4B 4C
4D 4E 4F 50
AES
key is either 128 bits, 192 bits or 256 bits
128 bits (4 words): 11223344556677889900AABBCCDDEEFF 11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
or 192 bits (6 words) 1122334455667788 9900AABBCCDDEEFF 1122334455667788 11 55 99 CC 11 55
22 66 00 DD 22 66
33 77 AA EE 33 77
44 88 BB FF 44 88
or 256 bits (8 words) 1122334455667788 9900AABBCCDDEEFF 1122334455667788 9900AABBCCDDEEFF
11 55 99 CC 11 55 99 CC
22 66 00 DD 22 66 00 DD
33 77 AA EE 33 77 AA EE
44 88 BB FF 44 88 BB FF
Expanded Key Length Key Length Block Size Number of (words) (Nk words) (Nb words) Rounds Nr AES-128 4 44 4 10 AES-192 6 52 4 12 AES-256 8 60 4 14 4 10 Rijndael - 128 4 44 6 12 8 14 4 12 Rijndael - 192 6 52 6 12 8 14 4 14 Rijndael - 256 8 60 6 14 8 14 * DES 256 2 16 2 * of 64 bits, only 56 are used
The
key security feature is the size of the key.
Assuming that one could build a machine that could recover a DES key in a second (i.e., try 255 keys per second), then it would take that machine approximately 149 thousand-billion (149 trillion) years to crack a 128-bit AES key. To put that into perspective, the universe is believed to be less than 20 billion years old.
• Accepting Moore's Law, doubling processor speed every 18 months, AES will be secure for another 109.5 years.
AES
Operates on the binary field GF(28).
This can be represented as a polynomial b(x) with binary coefficients b {0,1}:
b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0
• Multiplication in GF(28) consists of multiplying two polynomials modulo an irreducible polynomial of degree 8. – AES uses the following irreducible polynomial m(x) = x8 + x4 + x3 + x + 1
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
Sample Key: 11223344556677889900AABBCCDDEEFF
The
first 4 (Nk) words are set equal to the key
w[0] w[1] w[2] w[3]
11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
For words 4 through 43
i = Nk // Nk = 4 while (i < Nb*(Nr+1)) { // Nb*(Nr+1)= 4*(10+1)= 44 temp = w[ i –1] If ( i%Nk == 0 ) rotate word left 1 byte process each byte through sbox XOR with RCON[i/Nk-1] // just first byte of w[i] w[ i ] = w[ i-4 ] XOR temp i++}
AES Algorithm Key Expansion w[0] w[1] w[2] w[3]
11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
i=4 i = Nk // Nk = 4 while (i < Nb*(Nr+1)) { // Nb*(Nr+1)= 4*(10+1)= 44 temp = w[ i - 1 ] temp = w[3] = CC DD EE FF
If ( i%Nk == 0 ) temp = CC DD EE FF temp = DD EE FF CC rotate word left 1 byte process each byte through sbox temp = sbox[DD] sbox[EE] sbox[FF] sbox[CC] = C1 28 16 4B XOR with RCON[i/Nk-1] RCON[0] = 01 temp = (C1 temp = C0
01) 28 16 28 16 4B
4B
i xi
0 0x01
i xi
1 0x02
8 0x1b
Powers of x = 0x02 2 3 4 0x04 0x08 0x10
5 0x20
Powers of x = 0x02 9 A B C 0x36 0x6c 0xd8 0xab
6 0x40
D 0x4d
7 0x80
E 0x9a
rCon can be implemented with a look-up-table 2i in GF(28) Removes symmetry and linearity from key expansion.
For words 4 through 43
i = Nk // Nk = 4 i=4 while (i < Nb*(Nr+1)) {// Nb*(Nr+1)= 4*(10+1)= 44 temp = W[i-1] If (i%Nk == 0) rotate word left 1 byte process each byte through sbox XOR with RCON[i] // just first element of w w[i] = w[i-4] XOR temp temp = C0 28 i++}
w[i] = w[i-4] XOR temp
16
4B
w[0] w[1] w[2] w[3] w[4]
11 55 99 CC D1
22 66 00 DD 0A
33 77 AA EE 25
44 88 BB FF 0F
i=4 temp = C0 28 16 4B w[i] = w[i-4] XOR temp w[4] = (11 C0) (22 28) (33 16) w[4] = D1
0A
25 0F
(44
4B)
For words 4 through 43
i = Nk // Nk = 4 i=5 while (i < Nb*(Nr+1)) { // Nb*(Nr+1)= 4*(10+1)= 44 temp = w[i1] If (i%Nk == 0) temp = w[4] = D1 0A 25 0F rotate word left 1 byte process each byte through sbox XOR with RCON[i/Nk-1] // just first element of W w[i] = w[i-4] XOR temp i++}
w[0] w[1] w[2] w[3] w[4]
11 55 99 CC D1
22 66 00 DD 0A
33 77 AA EE 25
44 88 BB FF 0F
i=5 temp = D1 0A 25 0F w[i] = w[i-4] XOR temp w[5] = (55 D1) (66 0A) (77 25) w[5] = 84
C6
52 87
(88
0F)
Beginning Key Expansion for: 11 22 33 44 55 66 77 88 99 00 AA BB CC DD EE FF i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
subword
rCon
C1 28 16 4B
C0 28 16 4B
C8 47 2E 3E
CA 47 2E 3E
B0 A9 3B ED
B4 A9 3B ED
92 D2 D3 F8
9A D2 D3 F8
76 27 C5 B1
66 27 C5 B1
90 66 40 A9
B0 66 40 A9
B8 68 E1 11
F8 68 E1 11
9C 0B 6C D4
1C 0B 6C D4
F2 D1 66 D6
E9 D1 66 D6
A0 D5 49 58
96 D5 49 58
w[i-4]XORtemp w[i] 11 55 99 CC D1 84 1D D1 1B 9F 82 53 AF 30 B2 E1 35 05 B7 56 53 56 E1 B7 E3 B5 54 E3 1B AE FA 19 07 A9 53 4A EE 47 14 5E 78 3F 2B 75
22 66 00 DD 0A 6C 6C B1 4D 21 4D FC E4 C5 88 74 36 F3 7B 0F 11 E2 99 96 77 95 0C 9A 1F 8A 86 1C 14 9E 18 04 C5 5B 43 47 10 4B 08 4F
33 77 AA EE 25 52 F8 16 0B 59 A1 B7 30 69 C8 7F E3 8A 42 3D 26 AC EE D3 66 CA 24 F7 87 4D 69 9E EB A6 CF 51 8D 2B E4 B5 C4 EF 0B BE
44 88 BB FF 0F 87 3C C3 31 B6 8A 49 DC 6A E0 A9 24 4E AE 07 95 DB 75 72 3C E7 92 E0 2D CA 58 B8 F9 33 6B D3 2F 1C 77 A4 77 6B 1C B8
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
41 42 43 44
41 11 42 22 43 33 44 44
45 46 47 48
45 55 46 66 47 77 48 88
State 49 4A 4B 4C
4D 4E 4F 50
49 99 4D CC 4A 00 4E DD 4B AA 4F EE 4C BB 50 FF
Expanded Key w[0] w[4] 11 55 99 CC
22 66 00 DD
33 77 AA EE
44 88 BB FF
After AddRoundKey 50 60 70 00
10 20 30 C0
D0 4A E1 F7
81 93 A1 AF
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
SubBytes
is the SBOX for AES This make AES a non-linear cryptographic system. For every value of b there is a unique value for b’
It is faster to use a substitution table (and easier). b'0 b'1 b'2 b'3 b'4 b'5 b'6 b'7
=
1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1
1 0 0 0 1 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 0 0 0 1
x is the inverse value of the byte b
x0 x1 x2 x3 x4 x5 x6 x7
+
1 1 0 0 0 1 1 0
Y
X
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 ca b7 4 9 53 d0 51 cd 60 e0 e7 ba 70 e1 8c
1 7c 82 fd c7 83 d1 ef a3 0c 81 32 c8 78 3e f8 a1
2 77 c9 93 23 2c 0 aa 40 13 4f 3a 37 25 b5 98 89
3 7b 7d 26 c3 1a ed fb 8f ec dc 0a 6d 2e 66 11 0d
4 f2 fa 36 18 1b 20 43 92 5f 22 49 8d 1c 48 69 bf
5 6b 59 3f 96 6e fc 4d 9d 97 2a 6 d5 a6 3 d9 e6
6 6f 47 f7 5 5a b1 33 38 44 90 24 4e b4 f6 8e 42
7 c5 f0 cc 9a a0 5b 85 f5 17 88 5c a9 c6 0e 94 68
8 30 ad 34 7 52 6a 45 bc c4 46 c2 6c e8 61 9b 41
9 1 d4 a5 12 3b cb f9 b6 a7 ee d3 56 dd 35 1e 99
a 67 a2 e5 80 d6 be 2 da 7e b8 ac f4 74 57 87 2d
b 2b af f1 e2 b3 39 7f 21 3d 14 62 ea 1f b9 e9 0f
c fe 9c 71 eb 29 4a 50 10 64 de 91 65 4b 86 ce b0
d d7 a4 d8 27 e3 4c 3c ff 5d 5e 95 7a bd c1 55 54
e ab 72 31 b2 2f 58 9f f3 19 0b e4 ae 8b 1d 28 bb
f 76 c0 15 75 84 cf a8 d2 73 db 79 8 8a 9e df 16
State 50 60 70 00
10 20 30 C0
D0 4A E1 F7
53 D0 51 63
CA B7 04 BA
81 93 A1 AF
70 D6 F8 68
Sbox( 50 ) Sbox( 60 ) Sbox( 70 ) Sbox( 00 )
0C DC 32 79
Sbox( 10 ) Sbox( 20 ) Sbox( 30 ) Sbox( C0 )
Sbox( D0 ) Sbox( 81 ) Sbox( 4A ) Sbox( 93 ) Sbox( E1 ) Sbox( A1 ) Sbox( F7 ) Sbox( AF )
KeyExpansion(byte key[4*Nk],word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
Simple
routine which performs a left shift rows 1, 2 and 3 by 1, 2 and 3 bytes respectively 53 B7 F8 79
Before Shift Rows
53 D0 51 63
CA B7 04 BA
70 D6 F8 68
CA D6 32 63
70 DC 51 BA
0C D0 04 68
After Shift Rows
0C DC 32 79
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)],Nk) Cipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
This
with shift rows provides diffusion The columns are considered polynomials over GF(28) and multiplied modulo x4+1 with a(x) where a(x) = {03}x3 + {01}x2 + {01}x + {02} NOTE: x4+1 is relatively prime to a(x) a’j (aj*a(x))mod(x4+1) This can also be written as matrix multiplication. a’ 0
02 03 01 01
a0
a’ 1
01 02 03 01
a1
2
01 01 02 03
a2
a’ 3
03 01 01 02
a3
a’
=
a’0
02 03 01 01
a0
a’1
01 02 03 01
a1
=
+ 3a11 + aa22 +a3 a’0 = 2a0 a a3’ = a + 2a + 3a + a 1
0
1
2
3
’ = a 2a 3a a ’1 = a0 + a 1 2 3a a + 2a + a 01 01 02 03 2 0 1 2 3 2 2 a3 a’’3 = 3a0 + a1 + a2 + 2a3 a’3 03 01 01 02 a3 a 2 = a0 a1 2a2 3a3 Addition is easy in GF(28) : Addition is just the XOR operation
a’
’ = 3a a a Multiplication by 1 is easy in GF(28) : Multiplicationaby 3 one is 0 the identity 1 2
2a3 Multiplication by 2 in GF(28) takes some work: . If multiplying by a value < 0x80 just shift all the bits left by 1 . If multiplying by a value ≥ 0x80 shift left by 1 and XOR with 0x1b . This prevents overflow and keeps the values within range To Multiply by 3 in GF(28) : a * 0x03 = a * (0x02 + 0x01) = (a * 0x02) (a * 0x01)
KeyExpansion(byte key[4*Nk], word w[Nb* (Nr+1)],Nk) Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb -1]) for round = 1 step 1 to Nr –1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb -1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb -1]) out = state end
Input String
Key
Output String (HEX)
Input String(HEX)
Key
Output String (HEX)
ABCDEFGHIJKLMNOP 11223344556677889900AABBCCDDEEFF
BC4784A37D6F46452656B993D53393F5
00000000000000000000000000000000
00000000000000000000000000000000
66E94BD4EF8A2C3B884CFA59CA342B2E
ABCDEFGHIJKLMNOP 01223344556677889900AABBCCDDEEFF
855866490543FDF6504FC84088FEDCA0
00000000000000000000000000000000
00000000000000000000000000000001
0545AAD56DA2A97C3663D1432A3D1C84
ABCDEFFHIJKLMNOP 11223344556677889900AABBCCDDEEFF
372CCA446C0D391C4381392344630EE1
00000000000000000000000000000001
00000000000000000000000000000001
A17E9F69E4F25A8B8620B4AF78EEFD6F
Encryption
Decryption Cipher Text
PlainText
RoundKey
AddRoundKey
1st Round
RoundKey*
SubBytes ShiftRows MixColumns RoundKey
Repeat Nr -1 Round
InvSubBytes RoundKey*
AddRoundKey InvMixColumns
SubBytes
InvShiftRows
AddRoundKey CipherText
1st Round
InvShiftRows
AddRoundKey
ShiftRows RoundKey
AddRoundKey
Last Round
InvSubBytes RoundKey*
Repeat Nr -1 Round
Last Round
AddRoundKey
Plain Text * RoundKey Added in reverse order
How
to avoid frequency analysis?
Cipher Block Chaining
If
plaintext messages are not divisible by 16 bytes. Padding may be a solution. An easy method is to add a single 1 bit at the end of the message followed by enough 0’s to fill the block.
If the block is filled, encode one more block with a 1 followed by 0’s.
Differential
Cryptanalysis – Study of how differences in input affect differences in output.
Greatly reduced due to high number of rounds.
Linear
Cryptanalysis – Study of correlations between input and output.
SBOX & Mix Columns are designed to frustrate Linear Analysis
Side
Channel Attacks – Attacks based on studying and measuring the actual implementation of the code.
For some implementations of AES the key has been obtained in under 100 minutes.
Computer running AES was 850MHz, Pentium III running FreeBSD 4.8
Timing
Attacks – Watches movement of data in and out of the U or memory.
It is difficult to retrieve an array element in a time that is not dependent on the index value.
Power
Attacks – Watches power consumption by U or memory.
Changing one bit requires considerably less power than changing all bits in a byte.
Avoid
use of arrays. Compute values in SBOX and
rCon. Design algorithms and devices to work with constant time intervals. (independent of key and plaintext.)
Hidden U timing data is a threat.
Use
same memory throughout, Cache is faster than DRAM Compute Key Expansion on the fly. Utilize pipelining to stabilize U power consumption.
Extremely
fast compared to other block ciphers. (tradeoff between size and speed) The round transformation is parallel by design. Important in dedicated hardware. Amenable to pipelining The cipher does not use arithmetic operations so has no bias towards big or little endian architectures.
Fully
Self-ing. Does not use Sboxes of other ciphers, bits from Rand tables, digits of or any other such jokes. Is not based on obscure or not well understood processes The tight cipher design does not leave enough room to hide a trap door.
The
inverse cipher is less suited to smart cards, as it takes more codes and cycles. The cipher and inverse cipher make use of different codes and/or tables. In hardware, The inverse cipher can only partially re-use circuitry which implements the cipher.
About AES AES Proposal : Rijndael Joan Daemen, Vincent Rijmen, 2nd version of document to NIST Polynomials in the Nations Service: Using Algebra to Design the Advanced Encryption Standard Susan Landau The Mathmatical Association of America, Monthly 111 Feb 2004 Page(s):89-117 Selecting the Advanced Encryption Standard Security & Privacy Magazine, IEEE Volume 1, Issue 2, Mar-Apr 2003 Page(s):43 - 52
Title: Introduction to Cryptography Author: Johannes A Buchman Publisher: Springer; 2 edition (July 13, 2004)
Burr, W.E.;
Security and Attacking AES Power-analysis attack on an ASIC AES implementation Ors, S.B.; Gurkaynak, F.; Oswald, E.; Preneel, B.;Information Technology: Coding and Computing, 2004. Proceedings. ITCC 2004. International Conference onVolume 2, 2004 Page(s):546 - 552 Vol.2 Algebraic attacks on cipher systems Penzhorn, W.T.; AFRICON, 2004. 7th AFRICON Conference in Africa Volume 2, 2004 Page(s):969 - 974 Vol.2 Cache-Timing attacks on AES Daniel J Bernstein Preliminary version of report to National Science Foundation, grant CCR9983950
Applications / Implementations: AES A high throughput low cost AES processor Chih-Pin Su; Tsung-Fu Lin; Chih-Tsiun Huang; Cheng-Wen Wu; Communications Magazine, IEEE Volume 41, Issue 12, Dec. 2003 Page(s):86 - 91 An efficient FPGA implementation of advanced encryption standard algorithm Shuenn-Shyang Wang; Wan-Sheng Ni; Circuits and Systems, 2004. ISCAS '04. Volume 2, 23-26 May 2004 Page(s):II - 597-600 Vol.2 High-speed VLSI architectures for the AES algorithm Xinmiao Zhang; Parhi, K.K.; Very Large Scale Integration (VLSI) Systems Volume 12, Issue 9, Sept. 2004 Page(s):957 – 967 Fast implementation of AES cryptographic algorithms in smart cards Chi-Feng Lu; Yan-Shun Kao; Hsia-Ling Chiang; Chung-Huang Yang; Security Technology, 2003. 14-16 Oct. 2003 Page(s):573 - 579
Applications / Implementations : AES
A new VLSI implementation of the AES algorithm Liang Deng; Hongyi Chen; Communications, Circuits and Systems and West Sino Expositions, IEEE 2002 International Conference on Volume 2, 29 June-1 July 2002 Page(s):1500 - 1504 vol.2
Related Documents 3h463d
Aes g4j2j
October 2021 0
Aes g4j2j
April 2021 0
Aes-telasi u14x
December 2019 35
Aes Computacion 6d6l1p
April 2022 0
Aes Ecc 1u3n4
August 2021 0
Aes Catalog 38h19
December 2019 180More Documents from "irshad17" 6p102