[컴퓨터 보안] AES 개념과 구조

왜 Block Cipher에 대해 Finite Field를 이용하는가?

• AES를 구성하는 함수들
  • Substitution
  • Transposition (permutation)
  • Multiple rounds
  • Simple bit operations (XOR 같은  )
• Bit randomizion effect
  • input에 대해 output이 랜덤하게 나오는 것 같은 느낌을 줌
  • Field multiplication이나 Field inversion이 이런 randomizion effect 역할을 함
  • 덧셈은 그다니 randomizion 효과가 없음
    • 덧셈 반복해도 효과 x
    • 곱셈이나 역연산은 복잡도를 증가시킬 수 있음

 

 

Binary Field의 근거

• 우리는 편의성과 구현 효율성을 위해 낭비되는 비트 패턴이 없는, 주어진 수의 비트에 정확히 맞는 정수로 작업을 하고 싶다.
  • 즉, (mod $2^n$)을 해서 0부터 ($2^n$-1)까지 쓰려고 한다.
• 하지만 $2^n$을 modulus로 쓰게 되면, 이런 modular연산에 대해서는 field를 구성할 수 없다.
• 즉, 이런 수(예: $2^3$=8)를 정수 그대로 쓸 수는 없고, 이거를 binary field로 바꿔서, 모든 원소들을 숫자가 아닌 계수가 2진수인 다항식으로 표현하면 잘 연산할 수 있다.
• GF($2^n$)에 속하는 모든 다항식은 n-bit로 표현할 수 있다.

 

AES에 대한 Finite Field Arithmetic

• Advanced Encryption Standard(AES)를 위해 우리는 GF($2^8$)를 사용한다.
  • 모든 연산은 8-bit bytes 단위이다.
• finite field GF($2^8$)를 쓰기 때문에, irreducible polynomial이 필요하다.
  • irreducible polynomial: $x^8 + x^4 + x^3 + x + 1$
• binary field는 (mod 2)에 대한 연산을 하는 것이다.
  • 예를 들어, $x^2±1$는 irreducible polynomial이 아니다.
    • $x^2 + 2x + 1$ = $(x+1)^2$로 나타낼 수 있기 때문
    • (mod 2)에서는 양수와 음수가 동일하게 작동하기 때문에 $x^2+1$=$x^2-1$이다.

 

AES

-> DES에서 key의 길이가 짧아서 생기는 안전성 문제를 해결하기 위해 나온 방법

 

AES의 구조

• plaintext, ciphertext, intermediate data 모두 4x4 matrix of bytes 구조를 가짐
• 파라미터로 들어오는 key size는 128, 192, 256 bits이다. 
  • 셋 중 하나 선택해서 사용하면 되는데, key 길이가 길어지면 안전해지지만 연산 속도는 느려지게 된다.
• SPN(Substitution-permutation network)
  • 하나의 round에서 4개의 연산이 이루어진다.
    • Permutation: ShiftRows
    • Substitution: SubBytes / MixColumns / AddRoundKey
  • AES는 복호화할 때, 암호화 과정을 역으로 올라간다. 이를 위해 모든 연산은 역연산이 존재한다.

 

 

AES 파라미터

* 1 byte = 8 bits

* 1 word = 4 bytes

 

 

• key size는 128, 192, 256 bits로 3가지.
• Plaintext의 Block size는 128-bytes로 항상 고정

 

• key 길이가 길수록 round 수가 많아짐 -> Subkey(RoundKey) 수도 많아짐 (하나의 size는 똑같고 개수만 많아짐)
• (#subkey) = (#round) +1

 

 

AES Encryption Process

• 44 words의 subkey가 필요하다.
  • state 하나는 4 words이다(16 bytes)
  • 이게 10 round일 때, (각 round에 하나씩) + (final state)해서 11개가 있으므로 총 44 words가 된다.
  • w[0]~w[43]
• DES는 '절반은 유지, 절반은 업데이트'하면서 매 round를 진행했었다. 
  • 순방향으로 복호화를 진행하기 위해서
  • DES 설명
• 하지만 AES는 SPN 방식으로 전부를 업데이트한다.
  • 역방향으로 복호화가 진행됨

 

 

AES에서 사용되는 4개의 stage

• Substitute bytes - S-box를 이용해서 byte끼리의 대치를 수행
• ShiftRows - 간단한 permutation
• MixColumns - GF($2^8$)를 사용하며 행렬을 사용하여 업데이트.
• AddRoundKey - bitwise XOR

 

 

 

 

 

* Encryption의 마지막 round에는 'Mix columns' 단계가 빠져있다.

 

-> 구현상의 편의성을 위한 것으로, 안정성에는 문제가 없는 수준이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. SubBytes

SubBytes

: byte 단위로 치환

 

S-box

: 각 byte를 대치시키는 규칙을 정해 놓은 것

 

*1

: 각 칸은 1byte(8 bits)이다. 이를 4 bits씩 잘라서 S-box의 x값, y값으로 사용하여 대치할 값을 찾는다.

 

ex)

<Encryption>

(0, 0) -> 63

 

<Decryption>

(6,3) -> 00

 

 

 

 

S-box를 사용하는 이유

• input과 output의 상관관계를 줄임 -> 공격하기 힘들어짐
• 어떻게 상관관계를 줄일 수 있을까?
  • input에 대해 linear하지 않은 수학적 함수를 사용하여 output을 낸다.
  • '곱셈에 대한 역원'을 사용할 수 있다.

 

2. Shift Rows

• 입력의 하나의 열이 출력의 모든 열에 영향을 끼치게 됨

 

3. Mix Columns

• 각 열이 행렬 곱 연산을 통해 새로운 값을 가지게 됨

 

4. AddRoundKey

• state의 128 bits가 round key의 128 bits와 XOR 된다.

 

 

AES의 중요 포인트!

• 입력의 일부분이 출력의 여러 부분에 분산해서 영향을 미치게 한다.
• 입출력 사이 관계가 자명하게 드러나지 않도록 한다. Not linear하게 (복잡스~)

 

 

AES Key Expansion

 

• (w[0]~w[3]), (w[4]~w[7]), ... 들이 각각 subkey이다.
• $w_4 =w_0$ XOR $g(w_3)$
• $RC_j$ -> 어떤 상수

 

왜 Key Expansion을 사용하는가?

• xor(substitution), shift(transposition) 연산을 통해 공격에 강함
• round마다 달라지는 상수 값(RC)을 사용해서 규칙성을 없앰
• 이렇게 하면, 공격자가 key의 일부를 알거나, 어떤 round의 key를 알아도 다른 round의 key를 알기 힘들다.
• cipher key의 diffusion이 round key에 적용이 된다.
  • diffusion: 한 bit가 다른 여러 곳에 영향을 줌 (확산)
  • 한 round key의 일부 비트만 바뀌어도 다른 round key들에 영향을 주게 됨.
• 충분히 nonlinearity 하다
  • 특정 bit를 알아서 연립방정식을 하더라도 답을 쉽게 얻을 수 없음

 

bit 하나만 달라져도

• 맨 처음 bit 하지만 다르게 넣어도, 2 round부터 64 bits에 가깝게 변화한다. 
• 많이 바뀔수록 좋은 거 아닌가?
  • 우리는 최대한 randomize하려고 한다. 
  • 총 128 bits에서 절반인 64 bits에 가깝게 변해야 랜덤하다고 할 수 있다.

 

 

 

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]