AES(Advanced Encryption Standard)

AES(Advanced Encryption Standard) NIST에서 미국 연방정부의 공문서 등을 안전하게 저장하기 위해 전세계를 상대로 공모함 벨기에에서 제안한 Rijndael 알고리즘을 선정함 핵심함수는 수학적 대상인 유한체(finite field)에 기반함 키 길이에 따른 분류 AES-128 : 128비트의 Cipher Key 사용 AES-192 : 192비트의 Cipher Key 사용 AES-256 : 256비트의 Cipher Key 사용

AES Nb Number of columns (32-bit words) comprising the State. For this standard, Nb = 4. Nk Number of 32-bit words comprising the Cipher Key. For this standard, Nk = 4, 6, or 8. Nr Number of rounds Nk 와 고정값인 Nb에 의해 결정됨 For this standard, Nr = 10, 12, or 14. Byte의 덧셈 및 곱셈  Exclusive-OR operation · Finite field multiplication Word의 곱셈  Multiplication of two polynomials (each with degree < 4) modulo x4 + 1

AES Byte와 bits의 배열 Input bytes State array Output bytes in0 in4 in8 Input bit sequence 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 … Byte number in0 in1 Bit Numbers in byte in0 in4 in8 in12 in1 in5 in9 in13 in2 in6 in10 in14 in3 in7 in11 in15 s0,0 s0,1 s0,2 s0,3 s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 out0 out4 out8 out12 out1 out5 out9 out13 out2 out6 out10 out14 out3 out7 out11 out15 Input bytes State array Output bytes

수학적 배경 The finite field GF(28) : 각 Byte를 유한체 원소로 간주하여 계산함 원소의 표현 b = = b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0 ex) ‘57’ = (0101 0111)2 = x6 + x4 + x2 + x + 1 각 byte의 덧셈 : Addition in GF(28) b + c = defined =  b7 b6 b5 b4 b3 b2 b0 b1 c7 c6 c5 c4 c3 c2 c0 c1 b7 b6 b5 b4 b3 b2 b0 b1

수학적 배경 The finite field GF(28) : 각 Byte의 곱셈연산 방법 각 byte는 최고 7차의 다항식이므로,두 byte의 곱셈을 위해서 먼저 다항식 곱셈을 수행한다 계속하여 다음의 고정된 특별 다항식 m(x)로 나눈 나머지값을 곱셈의 결과로 한다. m(x) = x8 + x4 + x3 + x + 1 = 11Bx ex) ‘57’  ’83’ = ‘C1’ (x6 + x4 + x2 + x + 1)(x7 + x + 1) = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 x13+x11+x9+x8+x6+x5+x4+x3+1 (mod x8 + x4 + x3 + x + 1) = x7 + x6 + 1 = ‘C1’

수학적 배경 The finite field GF(28) : 곱셈 구현의 최적화 방법 유한체의 특성상 다음 다항식은 0과 같다. m(x) = x8 + x4 + x3 + x + 1 = 11Bx (irreducible over Z2) x8 = x4 + x3 + x + 1 x9 = x  x8 = x  (x4 + x3 + x + 1) = x5 + x4 + x2 + x x10 = x2  x8 = x2  (x4 + x3 + x + 1) = x6 + x5 + x3 + x2 x11 = x3  x8 = x3  (x4 + x3 + x + 1) = x7 + x6 + x4 + x3 x12 = x4  x8 = x4  (x4 + x3 + x + 1) = x8 + x7 + x5 + x4 = (x4 + x3 + x + 1) + x7 + x5 + x4 = x7 + x5 + x3 + x + 1 and so on.

x  b = b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x = LeftShift[b] 수학적 배경 xtime(b): 곱셈 구현의 최적화 위한 방법 If we multiply b(x) by the polynomial x, we have x  b = b7x8 + b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x IF b7 = 0, then next reduction is identity operation x  b = b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x = LeftShift[b] IF b7 = 1, then x8 = x4 + x3 + x + 1 must be subtracted (i.e., XORed) x  b = b7x8 + b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x = (x4 + x3 + x + 1) + b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x = b6x7 + b5x6 + b4x5 + (b3  1)x4 + (b2  1)x3 + (b0  1)x + 1 = LeftShift[b]  00011011 This operation is denoted by xtime(b) Multiplication by higher powers of x can be implemented by iterations

수학적 배경 Ex) ‘57’  ‘13’ = ‘FE’ ‘57’  ‘02’ = xtime(57) = ‘AE’ ‘57’  ‘08’ = xtime(47) = ‘8E’ ‘57’  ‘10’ = xtime(8E) = ‘07’ ‘57’  ‘13’ = ‘57’  (‘10’  ‘02’  ‘01’) = ‘07’  ‘AE’  ‘57’ = ‘FE’

수학적 배경 Word의 덧셈 및 곱셈 A(y) a0 a1 a2 a3 A(y) = a3y3 + a2y2 + a1y + a0 4개의 byte로 이루어진 word를 3차, 2차, 1차, 상수항 등의 다항식으로 간주함 Byte : x 기호 사용 Word : y 기호 사용 Word의 덧셈은 bitwise XOR 연산임 곱셈은 byte 곱셈과는 다른 방법을 이용함 (y4 = 1) A(y) = a3y3 + a2y2 + a1y + a0 B(y) = b3y3 + b2y2 + b1y + b0 where ai, bi GF(28) i.e., bytes A(y) a0 4Byte Word a1 a2 a3

AES Key-Block-Round Combinations Key Length (Nk words) Block size (Nb words) Number of Rounds (Nr) AES-128 4 10 AES-192 6 12 AES-256 8 14

AES 암호화 과정(Ciphering) 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]) // 초기 키 값이 add 됨 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 AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end

AES 암복호화 과정(Ciphering) 세부사항 SubBytes() Transformation ShiftRows() Transformation MixColumn() Transformation AddRoundKey() Transformation

AES SubBytes() Transformation S-Box sr,c s'r,c 다음 2가지 연산으로 구성 S-1 계산 : 각 byte를 유한체의 원소로 보고 곱셈에 대한 역원 계산 단 ‘00’은 계산 없이 ’00’으로 변환함 Affine 변환 : 각 바이트에 fixed 행렬을 곱하고 fixed 열벡터 XOR 이 모든 과정을 Lookup table 이용할 수 있음 28 Byte array needed S-Box s-1 계산 Affine 변환 s0,0 s0,1 s0,2 s0,3 s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 s'0,0 s'0,1 s'0,2 s'0,3 s'1,0 s'1,1 s'1,2 s'1,3 s'2,0 s'2,1 s'2,2 s'2,3 s'3,0 s'3,1 s'3,2 s'3,3 sr,c s'r,c

AES SubBytes() Transformation Affine 변환 b’0 1 0 0 0 1 1 1 1 b0 1 Right to Left

AES y 1 2 … x 63 7c 77 ca 82 c9 b7 fd 93 SubBytes() Transformation S-box Lookup Table : input ‘xy’-values y 1 2 … x 63 7c 77 ca 82 c9 b7 fd 93

AES ShiftRows() Transformation 각 행을 LeftRotation함 : different offsets No Rotation

AES MixColumn() Transformation a(x) = {03}x3 + {01}x2 + {01}x + {02} 각 열(word)벡터에 다음의 고정된 a(y) 다항식을 곱한 결과로 변환함 Word 곱셈 a(y)  s(y)이 필요함 a(x) = {03}x3 + {01}x2 + {01}x + {02} 다음의 행렬 곱셈과 같은 결과를 얻을 수 있음 s’0,c 02 03 01 01 s0,c s’1,c = 01 02 03 01 s1,c s’2,c 01 01 02 03 s2,c s’3,c 03 01 01 02 s3,c

AES MixColumn() Transformation MixColumn() s0,c s’0,c s1,c s’1,c s2,c Column-by-column 암호화에 a(x)를 곱하는 과정 복호화에서는 다른 다항식 a-1(x)를 곱하게 됨 암.복호화 과정이 different MixColumn() s0,c s0,0 s0,1 s0,2 s0,3 s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 s'0,0 s'0,1 s'0,2 s'0,3 s'1,0 s'1,1 s'1,2 s'1,3 s'2,0 s'2,1 s'2,2 s'2,3 s'3,0 s'3,1 s'3,2 s'3,3 s’0,c s1,c s’1,c s2,c s’2,c s3,c s’3,c ?

AES AddRoundKey() Transformation AddRoundKey() s0,c s’0,c s1,c s’1,c 각 coulmn에 RoundKey를 XOR 하는 과정 암.복호화 과정에 개별적인 비밀인 Key 정보가 추가됨 AddRoundKey() s0,c s0,0 s0,1 s0,2 s0,3 s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 s'0,0 s'0,1 s'0,2 s'0,3 s'1,0 s'1,1 s'1,2 s'1,3 s'2,0 s'2,1 s'2,2 s'2,3 s'3,0 s'3,1 s'3,2 s'3,3 s’0,c s1,c s’1,c s2,c s’2,c s3,c s’3,c

AES Key Expansion Cipher key 값인 K(128, 192 or 256 bits)로부터 추출 Key 길이가 256 bits인 경우 약간 다른 과정을 수행함 각 round에 필요한 key-words 생성하는 과정 Total Nb(Nr + 1) words가 필요함 SubWord() Input, output : 4 byte word 각 byte를 S-box의 lookup table을 통하여 변환시킴 RotWord() Input : word [a0, a1, a2, a3] Output : word [a1, a2, a3, a0] Rcon[i] Word [xi-1, {00}, {00}, {00}] where xi-1을 byte로 표현함

AES end KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk) begin word temp i = 0 while (i < Nk) w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]) i = i+1 end while i = Nk while (i < Nb * (Nr+1) temp = w[i-1] if (i mod Nk = 0) temp = SubWord(RotWord(temp)) xor Rcon[i/Nk] else if (Nk > 6 and i mod Nk = 4) temp = SubWord(temp) end if w[i] = w[i-Nk] xor temp i = i + 1 end

AES Key Expansion of a 128-bit Cipher Key (Nk = 4) Cipher Key = 2b7e1516 28aed2a6 abf71588 09cf4f3c w0 = 2b7e1516 w1 = 28aed2a6 w2 = abf71588 w3 = 09cf4f3c i (dec) temp After RotWord() SubWord() Rcon[i/Nk] After XOR with Rcon w[i-Nk] w[i] = temp XOR w[i-Nk] 4 09cf4f3c cf4f3c09 8a84eb01 01000000 8b84eb01 2b7e1516 a0fafe17 5 28aed2a6 88542cb1 6 abf71588 23a33939 7 2a6c7605 8 6c76052a 50386be5 02000000 52386be5 f2c295f2 9 7a96b943 …

AES 복호화 과정(Inverse Ciphering) 암호화 과정의 역순과 유사하지만 세부 과정에서 다른 경우가 있음 실제 암호화와 복호화에 속도차이가 나타남 InvShiftRows() InvSubBytes() InvMixColumns() AddRoundKey()

AES 복호화 과정(Ciphering) InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4, Nb] state = in AddRoundKey(state, w[Nr * Nb, (Nr + 1)*Nb - 1]) for round = Nr – 1 step -1 downto 1 InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb - 1]) InvMixColumns(state) end for AddRoundKey(state, w[0, Nb-1]) out = state end

AES InvMixColumn() Transformation 각 열(word)벡터에 다음의 고정된 a-1(y) 다항식을 곱한 결과로 변환함 Word 곱셈 a-1(y)  s(y)이 필요함 a-1(x) = {0b}x3 + {0d}x2 + {09}x + {0e} 다음의 행렬 곱셈과 같은 결과를 얻을 수 있음 Lookup table을 이용하는 경우는 암호화와 동일한 속도 가능 H/W 구현의 경우 항의 수가 많기 때문에 다소 느려질 수 있음 s’0,c 0e 0b 0d 09 s0,c s’1,c = 09 0e 0b 0d s1,c s’2,c 0d 09 0e 0b s2,c s’3,c 0b 0d 09 0e s3,c

AES 응용 분야 3GPP의 가입자 인증(Authentication & Key Agreement) 3GPP의 Network Domain Security(MAPSEC) 제공 3GPP2의 가입자 인증 및 암호화 ESP(Enhanced Subscriber Privacy) 제공 위한 핵심기능 제공 실제 응용에서는 AES 알고리즘의 독립적인 사용보다는 AES 알고리즘을 핵심함수로 이용하며 다양한 변화를 준다. Modes of Operation OCB, CTR-CBC mode 등이 무선랜 보안 알고리즘으로 활용됨

AES Modes of Operation of Block Cipher ECB(Electronic Codebook) mode CBC(Cipher Block Chaining) mode CFB(Cipher FeedBack) mode OFB(Output FeedBack) mode CTR(Counter) mode OCB(Offset Codebook) mode

AES Modes of Operation of Block Cipher CTR(Counter) mode 병렬처리 가능 전처리 가능 수행속도가 블록암호의 속도와 동일 다량의 메시지를 한 개의 Key로 암호화 할 수 있음 OCB(Offset Codebook) mode 하나의 Key로 기밀성과 무결성을 동시에 제공 가능

Q & A