AES(Advanced Encryption Standard)

<AES(Adavanced Encryption Standard)>
- 2001년 미국 국립기술표준원에서 공표한 대칭키 암호 알고리즘
- AES의 선정 기준은
  1. 안정성(security)
  2. 비용(cost)
  3. 구현 효율성(implementation)

- AES는 128비트 평문을 128비트 암호문으로 출력하는 알고리즘으로 non-Feistel 알고리즘(모든 구성요소가 역이 존재)에 속한다

- 10. 12, 14 라운드를 사용하며
  각 라운드에 대응하면 키 크기는 128, 192, 256비트이다
  그러나 마스터 키(128, 192, 256)의 크기가 달라도 라운드 키는 모두 128비트이다
  Nr 10 <- Key size 128
  Nr 12 <- Key size 192
  Nr 14 <- Key size 256
  Pre-round transformation : Rounds KEy 128bits

- Block : 128bits/8bits
- State : 4 by 4

- S(i mod4, i/4) <- block(i)
- block(i+4j) <- S(i,j)





<라운드 함수 구조>
- State -> subBytes -> State -> ShiftRows -> State -> MixColumns -> State -> AddRoundKey -> State

Note
1. One AddRoundKey is applied before the first round
2. The third transformation is missing in the last round




<Transformations>
- AES 알고리즘은 안전성을 제공하기 위해 
  대치(substitution)
  치환(permutation)
  뒤섞음(mixing)
  키덧셈(key-adding)
  과 같은 4가지 형태의 변환을 사용





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

- 체 GF(2^8)를 이용한 변환 방법(Transformation Using the GF(2^8) Field)
  기약다항식(x^8+x^4+x^3+x+1)를 가진 체 GF(2^8)을 이용하여 
  대수적인 변환으로 S-박스를 정의할 수 있다

- SubBytes 변환과 InSubByte변환은 서로 역변환 관계이다
  - InSubByte = SubByte^(-1)




<치환(Permutation)>
- 라운드에서 발견되는 또 다른 변환으로 순환이동변환(shifting)이 있는데, 
  이는 바이트 단위의 치환(permutation)이다

- ShiftRows
  - ShiftRows는 암호화 과정에서 사용하고, 왼쪽으로 순환이동을 수행한다  
    - Row 0 : no shift
    - Row 1 : 1-byte shift
    - Row 2 : 2-byte shift
    - Row 3 : 3-byte shift
 

- InvShiftRows
  - InShiftRows는 복호화 과정에서 사용하고 오른쪽으로 순환이동을 수행한다
 
- ShiftRows와 InvShiftRows는 서로 역변환 관계이다




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

- MixColums와 InvMixColumns에 사용하는 상수 행렬
  C < - Inverse -> C^(-1)

- MixColumns 
  - MixColumns는 열 단위 연산을 수행한다
  즉 각각의 열을 계산하여 새로운 값을 갖는 열을 출력한다

- InvMixColumns 
  - InvMixColumns 변환은 기본적으로 MixColumns 변환과 동일하다




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


<키 확장(Key Expansion)>
- 각 라운드에 사용하는 라운드 키를 생성하기 위해 AES는 키 확장 과정을 사용한다
- Nr을 라운드 수라 하면 키 확장 과정을 통해 하나의 128비트 암호키로부터 Nr+1개의 128비트 라운드 키를 생성한다
- 128bit = 16bytes = 4word

  Words for each round
  Round : Pre-round / Words : w0, w1, w2, w3
  Round : 1            / Words : w4, w5, w6, w7
  ...
  Round : Nr          / Words : w(4Nr), w(4*(Nr)+1), w(4*(Nr)+2), w(4*(Nr)+3) 



- 체 GF(2^8)을 이용하여 상수들의 최상위 바이트들을 계산하여 얻을 수 있다
  여기서 prime은 기약다항식을 의미한다

- AES의 각 라운드에서 쓰이는 라운드 키는 이전 라운드에서 사용한 라운드 키를 이용하여 생성된다
  그러나 키 확장 과정의 SubWord는 라운드 키들 사이에 '비선형성'을 제공하고 상수 덧셈 연산을 통과하면서
  이전 단계의 라운드 키와 그 다음으로 생성되는 라운드 키는 다르게 될 것이다

- 암호키의 모든 비트들을 0이라고 하면, Pre-round와 첫 번째 라운드에서 모든 라운드 키의 워드가 같은 값을 가진다
  또한 두 번째 라운드의 첫 번째 워드와 세 번째 워드, 
  두 번째 워드와 네 번째 워드는 서로 같은 값을 갖는다
  그러나 두 번째 이상의 라운드에서는 이러한 규칙성이 나타나지 않고 모든 워드가 서로 다른 값을 가진다



<Key Expansion in AES-192 and AES-256>
- 1. AES-192의 키 확장 과정은 4개의 워드 단위가 아닌 6개의 워드 단위로 계산 -> 192bits = 24bytes = 5words
    a. 192비트 암호키로 처음의 6개의 워드 w0, w1, ..., w5를 생성
    b. i mod 6 != 0일 경우 w(i) <- w(i-1) +or w(i-6)으로,
       그 밖의 경우에는 w(i) <- t +or w(i-6)

- 2. AES-256의 키 확장 과정은 4개의 워드 단위가 아닌 8개의 워드 단위로 계산한다
    a. 256비트 암호키로 처음의 8개의 워드 w0, w1, ..., w7를 생성
    b. i mod 8 != 0일 경우 w(i) <- w(i-1) +or w(i-8)으로,
       그 밖의 경우에는 w(i) <- t +or w(i-8)
    c. i mod 4 = 0 이면서 i mod 8 != 0인 경우 w(i)=SubWord(w(i-1)) +or w(i-8)로 계산



<Key Expansion Analysis>
- AES의 키 확장 과정은 공격자가 분석하기 어렵도록 몇 가지 특징이 있도록 설계되었다
  1. 공격자가 암호키의 일부나 라운드 키의 일부 값을 얻는다 해도 모든 라운드 키를 알기 위해서는 남은 암호화 키 값을 복구해야한다
  이는 키 확장 과정에서 사용된 SubWord 변환에 의해 발생하는 비선형성에 기반한다

2. 두 개의 암호키가 오직 한 비트만 다른 값을 갖더라도 라운드 키 확장 과정을 통해 적은 수의 라운드 만에 서로 다른 라운드 키를 생성한다
  
3. 암호키의 각 비트는 여러 라운드에 영향을 준다
  예를 들어, 암호화한 비트를 바꿀 경우 여러 라운드에서 여러 비트가 바뀌게 된다

4. 키 확장 과정에서 사용하는 상수 RCons는 다른 변환 과정에서 발생할 수 있는 라운드 키들 사이의 대칭성을 제거한다
  
5. DES와 달리(4+12+48=64개의 취약키 존재) AES에서는 심각한 취약키가 존재하지 않는다

6. 키 확장 과정은 거의 대부분의 환경에서 쉽게 구현할 수 있다

7. 키 확장 과정은 테이블을 저장하지 않고도 모든 계산을 GF(2^8) 또는 GF(2)를 사용하여 표현할 수 있다




<기본 디자인(Original Design)>
Cipher Key(w(0)-w(3)) -> Plaintext(->AddRoundKey) <- Inverse -> Plaintext(Round10 : AddRoundKey, InvSubBytes, InvShiftRows) <- Cipher Key(w(0)-w(3))
...
Cipher Key(w(40)-w(43) -> Plaintext(->AddRoundKey) <- Inverse -> Plaintext(AddroundKey) <- Cipher Key(w(49)-w(45)) 

<대체 디자인(Alternative Design)>
- SubBytes와 ShiftRows 조합의 가역성
  ->SubBytes, ShiftRows <- Inverse -> InvShiftRows, InvSubBytes <-

- MixColumn와 AddRoundKey 조합의 가역성
  ->MixColumns, AddRoundKey(RoundKey) <- Inverse -> InvMixColumns, InvAddRoundKey(RoundKey) ->
  - 암호 : T=CS +or K
  - 역암호 : C^(-1)T +or C^(-1)K = S

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




<AES의 세 가지 특성>
1. 보안성(Security)
- Brute-Force Attack
  - AES는 DES보다 큰 사이즈의 키(비트)를 사용하기 때문에 DES보다 안전
  
- Statistical Attacks 
  - 수많은 테스트들이 암호문의 통계적인 분석에 실패했다

- Differential and Linear Attacks
  - 아직까지 AES에 대한 차분 공격과 선형 공격이 알려지지 않고 있다

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

3. 단순성와 비용(Simplicity and Cost)
- AES에 사용하는 알고리즘은 매우 단순하므로 저렴한 프로세서와 최소 메모리를 이용하여 쉽게 구현 가능하다