7.1 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 7 Advanced Encryption Standard (AES)

7.2 Objectives □ AES 의 간략한 역사 □ AES 의 기본 구조 □ AES 에 사용하는 변환 함수 □ AES 의 키 확장 과정 □ AES 구현 방법 Chapter 7

INTRODUCTION Advanced Encryption Standard(AES) 는 2001 년 미국 국립기술표준원 (NIST, National Institute of Standards Technology) 에서 공표한 대칭키 암호 알고리즘이다 역사 (History) 기준 (Criteria) 라운드 (Rounds) 데이터 단위 (Data Units) 각 라운드의 구조 (Structure of Each Round) Topics discussed in this section:

History 년 2 월 미국 국립기술표준원은 공개적인 평가와 의견을 받기 위해 연방정보처리기준 (FIPS, Federal Information processing Standard) 의 초안 (draft) 을 발표하였으며, 최종적으로 2001 년 10 월 연방관보 (Federal Register) 에 FIPS 197 로 공표되었다.

선정 기준 ( Criteria) : 미국 국립기술표준원에서 제시한 AES 의 선정 기준은 세 가지이다 : 안전성 (security) 비용 (cost) 구현 효율성 (implementation)

Rounds. AES 는 128 비트 평문을 128 비트 암호문으로 출력하는 알고리즘으로 non-Feistel 알고리즘에 속한다. 10, 12, 14 라운드를 사용하며, 각 라운드에 대응하는 키 크기는 128, 192, 256 비트이다. AES 는 128, 192, 256 비트 키를 사용하고 키 크기에 따라 각각 10, 12, 14 라운드를 갖는 3 가지 버전이 있다. 그러나 마스터 키의 크기가 달라도 라운드 키는 모두 128 비트이다. Note

Continue Figure 7.1 General design of AES encryption cipher

Data Units. Figure 7.2 AES 암호의 구조도

Continue Figure 7.3 AES 에서 스테이트와 블록의 변환

Continue Example 7.1 Figure 7.4 암호문을 스테이트로 변환 Continue

Structure of Each Round Figure 7.5 암호화 과정의 라운드 함수 구조

TRANSFORMATIONS AES 알고리즘은 안전성을 제공하기 위해 대치 (substitution), 치환 (permutation), 뒤섞음 (mixing), 키덧셈 (key-adding) 과 같은 4 가지 형태의 변환을 사용한다 대치 (Substitution) 치환 (Permutation) 뒤섞음 (Mixing) 키 덧셈 (Key Adding) Topics discussed in this section:

Substitution DES 와 같이 AES 에서도 대치 (substitution) 를 사용하지만 메커니즘은 서로 다르다. SubBytes SubBytes 는 AES 의 암호화 과정에서 사용되는 대치 함수이다. 먼저 각 바이트를 4 비트씩 2 개의 16 진수로 계산하여 왼쪽 4 비트를 S- 박스의 행으로 오른쪽 4 비트를 열로 테이블 (table) 을 읽는다. SubBytes 연산은 16 개의 독립된 바이트 단위의 변환을 수행한다. Note

Continue Figure 7.6 SubBytes 변환

Continue

Continue

Continue InvSubBytes

Continue InvSubBytes (Continued)

Continue Example 7.2 그림 7.7 은 SubBytes 변환을 사용하여 하나의 스테이트가 어떻게 변환되는지 보여준다. 또한 InvSubBytes 를 통해서 원래의 값으로 복원할 수 있음을 보여준다. 두 개의 바이트가 동일한 값을 가지면 변환 후의 값 역시 동일하게 된다. Figure 7.7 예 7.2 의 SubBytes 변환

Continue 체 GF(2 8 ) 를 이용한 변환 방법 (Transformation Using the GF(2 8 ) Field) AES 는 그림 7.8 에서 보여주는 것처럼 기약 다항식 (x 8 + x 4 + x 3 + x + 1) 를 가진 체 GF(2 8 ) 를 이용하여 대수적인 변환으로 S- 박스를 정의할 수 있다. SubBytes 변환과 InvSubBytes 변환은 서로 역변환 관계이다. Note

Continue Figure 7.8 SubBytes 와 InvSubBytes 과정

Continue Example 진수 값 를 subbyte 를 통해 로 계산하는 과정을 보이고 역으로 invsubbyte 를 통해 다시 로 계산하는 과정을 설명한다. 1. subbyte : a. GF(2 8 ) 필드에서 0C 의 역원 (multiplicative inverse) 은 B0 이고 이것을 비트 단위로 표현하면 b=( ) 이다. b. 행렬 X 와 곱셈 연산 후 값은 c=( ) 이 된다. c. 이어서 XOR 연산 후의 값은 d=( ) 이 되며, 이는 FE 의 비트 단위 표현이다.

Continue Example invsubbyte : a. XOR 연산 후의 값으로 c=( ) 을 얻을 수 있다. b. 행렬 X -1 를 곱한 이후의 값은 ( ) 또는 B0 가 된다. c. B0 의 역원은 0C 가 된다.

Continue

치환 ( Permutation) 라운드에서 발견되는 또 다른 변환으로 순환이동변환 (shifting) 이 있는데, 이는 바이트 단위 치환 (permutation) 이다. ShiftRows ShiftRows 는 암호화 과정에서 사용하고 왼쪽으로 순환이동을 수행한다. Figure 7.9 ShiftRows 변환

7.26 InvShiftRows InvShiftRows 는 복호화 과정에서 사용하고 오른쪽으로 순환이동을 수행한다 Continue

Continue ShiftRows 와 InvShiftRows 는 서로 역변환 관계이다. Note

Continue Example 7.4 그림 7.10 은 어떻게 하나의 스테이트가 ShiftRows 변환을 사용하여 변환되는지 보여준다. 또한 InvShiftRows 변환이 어떻게 원래의 값으로 복원시키는지도 보여준다. Figure 7.10 예 7.4 에서의 ShiftRows 변환

뒤섞음 ( Mixing) ShiftRows 변환에 의한 치환의 경우, 바이트 안의 비트는 그대로 두고 바이트를 교환한다. 따라서 ShiftRows 변환은 바이트 단위로 교환하는 변환 (byte-exchange transformation) 이라고 말할 수 있다. Figure 7.11 행렬 곱셈을 이용하여 바이트들을 뒤섞는 과정

Continue Figure 7.12 MixColumns 와 InvMixColumns 에 사용하는 상수 행렬

7.31 MixColumns MixCulmns 는 열 단위 연산을 수행한다. 즉 각각의 열을 계산하여 새로운 값을 갖는 열을 출력한다 Continue Figure 7.13 MixColumns 변환

7.32 InvMixColumns InvMixColumns 변환은 기본적으로 MixColumns 변환과 동일하다 Continue MixColumns 와 InvMixColumns 는 서로 역변환 관계이다. Note

Continue

Continue Example 7.5 그림 7.14 는 어떻게 하나의 스테이트가 MixColumns 변환을 이용하여 변환될 수 있는가를 보여준다. 또한 InvMixColumns 변환을 통해 원래의 값으로 복원하는 것 역시 보여준다. Figure 7.14 예 7.5 에서의 MixColumns 변환

키덧셈 ( Key Adding) AddRoundKey AddRoundKey 는 한 번에 한 열씩 수행한다. 이러한 점에 있어서는 MixColumns 와 비슷하다. MixColumns 의 경우에는 각 스테이트 열행렬에 고정된 정방행렬을 곱하고, AddRoundKey 는 각 스테이트 열행렬에 라운드 키 워드를 더한다. AddRoundKey 변환은 자지 자신이 역변환이다. Note

Continue Figure 7.15 AddRoundKey 변환

KEY EXPANSION) 7-3 키 확장 ( KEY EXPANSION) N r + 1 각 라운드에 사용하는 라운드 키를 생성하기 위해 AES 는 키 확장 과정을 사용한다. 을 라운드 수라 하면 키 확장 과정을 통해 하나의 128 비트 암호키로부터 N r + 1 개의 128 비트 라운드 키를 생성한다 Key Expansion in AES Key Expansion in AES-192 and AES Key-Expansion Analysis Topics discussed in this section:

Continued

Key Expansion in AES-128 Figure 7.16 AES 에서 키 확장

Continue

Continue 키 확장 루틴은 상수 값을 얻기 위해 위의 테이블을 이용할 수도 있고, 아니면 다음과 같이 체 GF(2 8 ) 을 이용하여 상수들의 최상위 바이트들을 계산을 통해 얻을 수도 있다. 여기서 prime 은 기약다항식을 의미한다.

Continue

Continue Example 7.6 (24 75 A2 B E AA 54 87) 비트 마스터 키 (24 75 A2 B E AA 54 87) 16 를 이용하여 각 라운드에 사용할 라운드 키를 생성하는 과정을 보인다. 표 7.5 에 각 라운드 키를 계산한 값을 나타내었다.

Continue Example 7.7 AES 의 각 라운드에 쓰이는 라운드 키는 이전 라운드에서 사용한 라운드 키를 이용하여 생성된다. 그러나 키 확장 과정의 SubWord 는 라운드 키들 사이에 비선형성을 제공하고 상수 덧셈 연산을 통과하면서 이전 단계의 라운드 키와 그 다음으로 생성되는 라운드 키는 다르게 될 것이다. Example 7.8 오직 한 비트만 다른 값을 갖는 두 암호키 과 를 이용하여 각각의 라운드 키를 생성한다.

Continue Example 7.8 Continue

Continue Example 장에서 살펴본 DES 의 취약키 성질은 AES 에서 존재하지 않는다. 암호키의 모든 비트들을 0 이라 하면 아래와 같은 라운드 키를 얻을 수 있다. Pre-round 와 첫 번째 라운드에서 모든 라운드 키의 워드가 같은 값을 갖는다. 또한 두 번째 라운드의 첫 번째 워드와 세 번째 워드, 두 번째 워드와 네 번째 워드는 서로 같은 값을 갖는 것을 볼 수 있다. 그러나 두 번째 이상의 라운드에서는 이러한 규칙성이 나타나지 않고 모든 워드가 서로 다른 값을 갖는다.

Key Expansion in AES-192 and AES-256 : AES-192 와 AES-256 에서의 키 확장 과정은 AES- 128 의 연산과 매우 유사하나 아래와 같은 차이점이 있다 : 1. AES-192 의 키 확장 과정은 4 개의 워드 단위가 아닌 6 개의 워드 단위로 계산한다. a. 192 비트 암호키로 처음의 6 개의 워드 w 0,w 1,....,w 5 를 생성한다. b. i mod 6 ≠ 0 일 경우 w i ←w i-1 w i-6 으로, 그 밖의 경우에는 w i ← t w i-6 으로 계산한다.

Key Expansion in AES-192 and AES AES-256 의 키 확장 과정은 4 개의 워드 단위가 아닌 8 개의 워드 단위로 계산한다. a. 256 비트 암호키로 처음 8 개의 워드 w 0,w 1,....,w 7 를 생성한다. b. i mod 8 ≠ 0 일 경우 w i ← w i-1 w i-8 로, 그 밖의 경우에는 w i ← t w i-8 로 계산한다. c. i mod 4=0 이면서 i mod 8 ≠ 0 인 경우 w i =SubWord(w i-1 ) w i-8 로 계산한다.

키 확장 과정 분석 (Key-Expansion Analysis) AES 의 키 확장 과정은 공격자가 분석하기 어렵도록 몇 가지 특징이 있도록 설계되었다. 1. 공격자가 암호키의 일부나 라운드 키의 일부 값을 얻는다 해도 모든 라운드 키를 알기 위해서는 남은 암호하다 전체 값을 복구해야 한다. 이는 키 확장 과정에서 사용된 SubWord 변환에 의해 발생하는 비선형성에 기반한다. 2. 두 개의 암호키가 오직 한 비트만 다른 값을 갖더라도 라운드 키 확장 과정을 통해 적은 수의 라운드 만에 서로 다른 라운드 키를 생성한다. 3. 암호키의 각 비트는 여러 라운드에 영향을 준다. 예를 들어, 암호하다 한 비트를 바꿀 경우 여러 라운드에서 여러 비트가 바뀌게 된다.

키 확장 과정 분석 (Key-Expansion Analysis) AES 의 키 확장 과정은 공격자가 분석하기 어렵도록 몇 가지 특징이 있도록 설계되었다. 4. 키 확장 과정에서 사용하는 상수 RCons 는 다른 변환 과정에서 발생할 수 있는 라운드 키들 사이의 대칭성을 제거한다. 5. DES 와 달리 AES 에서는 심각한 취약키가 존재하지 않는다. 6. 키 확장 과정은 거의 대부분의 환경에서 쉽게 구현할 수 있다. 7. 키 확장 과정은 테이블을 저장하지 않고도 모든 계산을 GF(2 8 ) 또는 GF(2) 체를 사용하여 표현할 수 있다.

CIPHERS) 7-4 암호 ( CIPHERS) 이제 AES 의 암 · 복호화 과정에서 네 가지 변환이 어떻게 사용되는지 살펴보자. 표준에서 암호 알고리즘을 암호 (cipher) 로, 복호 알고리즘을 역암호 (inverse cipher) 라 표기하고 있다 기본 디자인 (Original Design) 대체 디자인 (Alternative Design) Topics discussed in this section:

Original Design Figure 7.17 암호와 역암호의 기본 디자인

7.53 Algorithm 이 디자인의 AES-128 에 대한 의사코드는 알고리즘 7.6 과 같다 Continue

Alternative Design Figure 7.18 SubBytes 와 ShiftRows 조합의 가역성

Continue Figure 7.19 MixColumns 와 AddRoundKey 조합의 가역성

Continue Figure 7.20 대체 디자인에서의 암호와 역암호

7.57 키 확장 알고리즘의 변경 (Changing Key-Expansion Algorithm) 역암호에서 InvRoundKey 대신, 다른 라운드 키 집합을 생성하도록 키 확장 알고리즘을 변경할 수 있다. 그러나 pre-round 에 대한 라운드 키와 마지막 라운드에 대한 라운드 키는 수정되지 않아야 한다 Continue

Examples 이 절에서는 앞 두 절에서 다뤘던 내용을 강조하기 위해 암 · 복호화, 키 생성에 관한 예제를 살펴본다. Example 7.10 다음은 랜덤하게 선택된 키를 이용하여 평문 블록으로부터 생성된 암호문 블록이다.

Continued Example 7.10Continued

Continued Example 7.10Continued

Continued Example 7.10Continued

Continued Example 7.11 그림 7.21 은 예 7.10 에서 라운드 7 에서의 스테이트 값을 나타낸 것이다. Figure 7.21 한 라운드에서의 스테이트 값

Continued Example 7.12 예 7.10 과 동일한 키를 사용하여 으로 구성된 평문을 암호화하여 생성된 암호문은 다음과 같다.

Continued Example 7.13 한 비트만 다른 두 개의 평문을 암호화한 결과를 비교하여, 6 장에서 다뤘던 쇄도 효과 (avalanche effect) 를 확인해 보자. 마지막 바이트에서 한 비트만 변경한다. 결과값은 혼돈과 확산의 효과를 보여준다. 평문에서 한 비트 차이는 암호문에서 많은 비트에 영향을 주고 있다.

Continued Example 으로 구성된 키를 사용할 경우, 생성된 암호문은 다음과 같다.

ANALYSIS OF AES) 7-6 AES 의 분석 ( ANALYSIS OF AES) 본 절에서는 AES 의 세 가지 특성을 간단히 살펴본다 보안성 (Security) 구현 (Implementation) 단순성과 비용 (Simplicity and Cost) Topics discussed in this section:

Security AES 는 DES 가 설계된 후에 설계되었다. 따라서 DES 에 대한 알려진 대부분의 공격들이 이미 AES 에 적용되었다. Brute-Force Attack AES 는 DES 보다 큰 사이즈의 키 ( 비트 ) 를 사용하기 때문에 DES 보다 더 안전하다. Statistical Attacks 수많은 테스트들이 암호문의 통계적인 분석에 실패했다. Differential and Linear Attacks 아직까지 AES 에 대한 차분 공격과 선형 공격이 알려지지 않고 있다.

Implementation AES 는 소프트웨어, 하드웨어, 펌웨어로 구현할 수 있다. Table lookup 또는 잘 정의된 대수적 구조를 사용하는 루틴을 사용하여 구현될 수 있다.

Simplicity and Cost AES 에 사용하는 알고리즘은 매우 단순하므로 싼 프로세서와 최소 메모리를 이용하여 쉽게 구현 가능하다.