2021-10-04-현대암호학-5주차.md

5. Advanced Encryption Standard (AES)

---

AES (Advanced Encryption Standard)

• AES (Advanced Encryption Standard) 탄생 배경
  • 1990년대 당시 56 비트 안전성을 제공하는 DES는 더 이상 안전하지 않음
  • TDES의 약점
    • DES를 순차적으로 3번 사용해야 하기 때문에 속도가 느림
    • 블록 암호를 이용하는 응용분야에 적합하지 않음. DES를 이용한다면 64비트 블록을 사용하게 되고 안전성도 이에 의존함
    • 양자컴퓨터를 환경에서 비밀키는 적어도 256비트 크기를 가지는 것이 바람직함
• NIST의 AES 공모(1997)
  • 요구사항
    • 128비트 블록 크기의 대칭키 암호
    • 비밀키의 크기는 128비트, 192비트, 256비트 중 하나로 사용할 수 있어야 함
    • 소프트웨어 & 하드웨어 모두 효율적으로 구현할 수 있어야함
    • 전수 키 조사 외 알려진 공격(차분공격, 선형공격 등)에 대하여 안전해야 함
• AES 기술 개요
  • 혼돈과 확산의 곱 암호
  • 비페이스텔(Non-Feistel) 구조
  • 128비트 블록 암호: $M=C= \{0,1\}^{128}$
  • 3종류 키 지원: 128 / 192 / 256 비트
    • $K \in \{ \{0,1\}^{128}, \{0,1\}^{192}, \{0,1\}^{256} \}$
  • AES 구성
    • N라운드(10, 12, 14): 비밀키의 크기로 결정
      • {SubByte, ShiftRow, MixColumn, AddRoundKey}
      • SubByte와 MixColumn은 수학적인 원리로 작동함
    • 키확장함수
      • {RotWord, SubWord, RCons}

Mathematical Background

• 확장체 (Extension Field)
  • 체(Field): 덧셈 연산 $+$와 곱셈 연산 $\times$가 정의되어 있는 집합
  • 확장체는 다항식(polynomial)으로 구성된 집합
• 확장체 $GF(2^n)$
  • 성질 1. 다항식의 계수(coefficient)가 0이나 1로 구성
  • 성질 2. 다항식의 최고차항은 $n-1$이고 최대 $n$개의 항이 존재
  • 성질 1&2에 의하여 다항식의 곱셈에 대한 역원을 구할 수 있음
• $𝐺𝐹(2^8)$ in AES
  • $n$차 다항식은 $n$비트로 표현 가능
  • AES에서 사용하는 SubByte와 MixColumns은 한 바이트(=8비트)를 처리하고 있음

State

• 128비트(16바이트) 블록 표현 방법
  • 원소가 한 바이트인 $4×4$ 행렬로 표현하며 이를 상태(state)라고 함

AES Rounds

• AES 라운드 구성

  • SubBytes : 상태의 한 바이트를 치환함. 혼돈(Confusion)

  • ShfitRows : 상태의 행(row) 안에서 바이트 단위로 자리바꿈. 확산(Diffusion)

  • MixColumns : 상태의 열(column) 안에 혼합이 수행. 확산(Diffusion)

    • 마지막 라운드에서는 MixColmums을 제외함

  • AddRoundKey : 비밀키에서 생성된 라운드 키와 상태가 XOR연산
    - AddRoundKey만 수행하는 0-라운드 존재

    

AES Components

• SubBytes 계층 (Substitute Bytes)
  • 상태의 원소(1바이트)를 16진수 XY로 표현할 경우
    • 상위 4비트를 나타내는 X가 S-Box의 행을 결정
    • 하위 4비트를 나타내는 Y가 S-Box의 열을 결정
  • AES의 S-Box는 $x^8 +x^4 + x^3 + x + 1$의 $GF(2^8)$상의 연산으로 설계되었음
    • 상태의 원소에 대한 역원을 구하고 이를 비트 벡터 $b = (b_0 b_1 ... b_7)$로 표현
    • $s = M \times b \oplus y$
• Inv-SubBytes 계층
  • 비페이스텔 구조이므로 SubBytes에 대한 역과정이 존재함
    • S-Box의 역변환 테이블
    • 역 변환식: $(M^{-1} \times (s \oplus y))^{-1}$
• ShiftRows 계층, Inv-ShiftRows 계층
  • ShiftRows에서는 상태의 각 행 단위로 정해진 수만큼 순환 쉬프트를 수행
    • {1행: 그대로, 2행: 1바이트, 3행: 2바이트, 4행: 3바이트} 왼쪽 쉬프트
    • 각 바이트의 위치만 변하는 약한 수준의 확산(Diffusion)
• MixColumns 계층
  • 충분한 확산 효과를 위해 각 열을 비트 단위로 섞음
    • ShiftRows의 출력 상태와 미리 정의한 $4 \times 4$ 행렬 $C$를 곱하여 16바이트를 출력
    • 행렬원소와 상태원소의 곱은 앞서 정의한 $GF(2^8)$에서 수행함
• Inv-MixColumns 계층
  • MixColumns 계층에서 사용한 행렬 $C$의 역행렬 $C^{-1}$을 사용
    • $C$의 원소들은 비트 단위에서 1의 개수가 $C^{-1}$의 원소의 개수보다 더 적음
      • 암호화 과정이 복호화보다 더 빠름
      • 암호화만 사용하는 응용환경(e.g. 운영 모드)을 고려한 결과
• AddRoundKey 계층
  • 128비트 라운드 키 또한 상태와 같은 형태로 표현 ($4×4$ 바이트 행렬)
  • 상태의 각 열은 라운드 키의 같은 위치의 열과 XOR 연산을 함
  • XOR 연산을 이용하므로 역과정은 동일함
• 키 확장 (Key Expansion) 함수

  • 비밀키를 입력받아 각 라운드에 사용할 128비트 라운드키를 생성

    • 128비트→11라운드키 / 192비트→13라운드키 / 256비트→15라운드키
    • 0-라운드 키는 평문과 바로 XOR 연산
    • 나머지 라운드 키는 각 라운드의 AddRoundKey에서 연산 후 사용

  • 키 확장은 4바이트 단위로 연산을 수행하고 이 단위를 워드(word)라고 함

    • 128비트 라운드 키 = 4개의 워드
    • AES-128의 경우 44개의 워드 ($w_0, w_1, ..., w_{43}$) 생성

  • 함수 $G$와 XOR 연산을 이용하여 4개의 워드를 계속해서 생성

    • $G: \{0,1\}^{32} \times \{0,1\}^{32}$ (32비트를 입력받아 32비트 출력)
    • RotWord: 1바이트 쉬프트
    • SubWord: SubBytes와 동일한 방법으로 수행
    • RCons: 미리 정의한 라운드 상수 값과 XOR
      • 1라운드→01000000, 3라운드→04000000, ...

  • DES와 다르게 치환 과정이 존재하므로 보수 특성 및 취약 키가 발생하지 않음
    - $G(w_{4i-1}) = SubWord(RotWord(w_{4i-1})) \oplus RCons$

    

AES Encryption and Decryption

• 서로 다른 암/복호화 알고리즘
• 복호화시 라운드키를 역순으로 대입 (DES와 동일)

Analysis

• 안전성
  • 보수특성 및 취약키가 존재하지 않음
  • 알려진 차분분석 방법, 선형분석 방법이 현재까지 없음
  • Biclique 분석 (2011)
    • AES뿐만 아니라 다른 블록 암호에도 공통적으로 적용 가능한 공격
    • 전수 키 조사 공격보다 4배 정도 효율적인 공격
    • AES-128의 경우 $2^{126}$번의 연산이 필요하므로 126비트 안전성으로 하향
    • 56비트 안전성을 제공하는 DES에 대한 전수 조사 공격을 $2^{70}$번 하는 것과 동일
  • 알고리즘이 아닌 하드웨어 특성 들을 이용한 부채널(side chanel) 공격만 보고
  • AES를 대체 암호가 필요한 것은 아니며 라운드 수(비밀키 길이)를 증가시키는 것으로 높은 안전성을 확보할 수 있음