AES? — Step by Step 정리

이번 포스트에서는 AES 알고리즘이 어떤 방식으로 진행되는지 살펴보고 python AES 모듈을 이용해서 어떻게 메세지를 암호화하고 복호화 할 수 있는지에 대해서 알아보려고 합니다.

Background

AES의 등장 배경에는 DES가 있습니다. Data Encryption Standard(DES)를 간단하게 소개하자면 1970년 초 IBM에서 Horst Feistel의 디자인을 기초로 고안되었습니다. 그래서 DES는 Feistel-structure라고 불리기도 합니다. AES와 마찬가지로 대칭키 암호화 방식의 block cipher이고 56-bits 길이의 키를 가지고 있습니다. block cipher는 plaintext를 몇 개의 블럭으로 나누어서 암호화하는 방식을 말하는데 뒤에 가서 좀 더 설명하도록 하겠습니다.

그런데 지금은 DES가 중요한 정보를 암호화하는데는 적합하지 않다고 알려져있습니다. 1999년 초 DES Challenge III에서 DES로 암호화된 메세지가 brute force attack에 의해 해독되는데 22시간밖에 걸리지 않았습니다! 이렇게 DES가 안전하지 않은 주요한 원인 56-bits의 짧은 key size 때문입니다.

이와 같은 문제때문에 좀 더 안전한 cryptosystem이 필요했고, 2001년 Vincent Rijmen과 Joan Daemon에 의해서 AES가 만들어졌습니다. AES의 주요 강점은 DES보다 훨씬 긴 키 사이즈를 가진다는 것인데 AES는 128-bit, 192-bit, 256-bit 키를 가질 수 있고 이것은 DES의 56-bit key보다 기하급수적으로 더 강력합니다.

또한 AES는 DES보다 encryption 속도가 빠르기 때문에 낮은 레이턴시(latency)와 높은 처리율(thorughput)을 요구하는 소프트웨어 어플리케이션이나 펌웨어에 적합합니다. 그래서 다양한 프로토콜에 사용되고 있는데 SSL/TLS에도 사용되고 있고 방화벽이나 라우터 등에도 사용되고 있습니다.

Algorithm

AES algorithm overview

AES 알고리즘의 큰 흐름은 위와 같습니다.

• Add round key
• Substitute bytes
• Shift rows
• Mix columns
• Add round key

이제부터 각 단계에서 어떤 식으로 동작하는지 살펴보도록 하겠습니다.

Represent data as metrixes

block cipher represents data as metrixes

먼저 알고리즘에 대해서 설명하기 전에 위에서 언급했던 block cipher에 대해서 짚고 넘어가려고 합니다. block cipher란 데이터 bit마다 알고리즘을 적용하는 것이 아니라 몇 개의 bit들을 묶어 하나의 block으로 만들고 block에 대해서 알고리즘과 키를 적용하는 cryptosystem을 말합니다.

AES도 block cipher로 평문, 암호문 그리고 키와 같은 데이터들을 위와같이 block들의 집합으로 나타냅니다. 한 블럭은 1byte (8bit)이고 총 16×8=128bit입니다. 키 길이가 128bit이기 때문에 평문 128bit 에 대해서 AES를 적용하게 됩니다. 그리고 p0, p1 … 순서를 확인하면 알 수 있겠지만 컬럼(column)별로 데이터를 나타내고 한 컬럼은 1word(32bits) 사이즈를 가집니다.

Add round key

add round key is XOR operation

먼저 AES를 진행하면 평문과 키를 가지고 add round key operation을 진행하게되는데 이는 XOR operation을 말합니다. 128bit 길이의 평문과 128bit의 키를 가지고 bit 별로 XOR operation을 진행합니다. 위의 다이어그램을 보면알 수 있지만 output 각각의 bit가 0 또는 1 될 확률은 50%입니다. 따라서 add round key operation을 진행하고 나면 평문값은 0과 1을 비슷한 비율로 가지게 됩니다.

Round function

전체 알고리즘 다이어그램에서 여러 개의 박스를 묶어서 Round function으로 나타낸 부분이 있습니다. DES와 마찬가지로 AES에서도 round라는 개념을 가지는데 묶어 놓은 알고리즘을 한 번 실행하는 것을 1 round가 진행된 것이라고 이해할 수 있습니다. 보통 128-bit key를 대상으로는 10 round 동안 알고리즘이 진행되고 192-bit key를 대상으로는 12 rounds, 256-bit keys를 대상으로는 14 rounds 동안 진행됩니다.

S-BOX: substitute bytes

S-BOX overview

https://en.wikipedia.org/wiki/Rijndael_S-box

다음은 S-BOX를 이용해 각 block의 bit들을 다른 bit들로 바꾸는 과정입니다. S-BOX는 간단히 말해서 lookup table이라고 생각할 수 있습니다. 해당 block의 bit들을 다른 것으로 바꾸는 과정은 다음과 같습니다. 위에서도 말했듯이 한 블럭엔 8-bit의 데이터가 담겨있습니다. 이 때 앞의 4bit를 row index로 보고 뒤의 4bit를 column index로 봐서 해당 S-BOX의 row, column의 값으로 바꾸게 됩니다.

shift rows

how shift rows work

다음은 shift rows 단계입니다. 여기서는 각 row별로 circular left shift을 하는데 shift하는 step을 맨 윗줄 부터 0, 1, 2 그리고 3으로 잡고 위 그림과 같이 바꿉니다. 첫 번째 줄은 왼쪽으로 circular shift를 0만큼 하여 s0, s4, s8, s12이 원래 데이터였다면 shift rows를 마치고 나면 그대로 s0, s4, s8, s12가 되고 두 번째 줄은 왼쪽으로 circular shift를 1만큼 하여 s1, s5, s9, s13이 원래 데이터였다면 결과물은 s1자리에 s5가 오고 s5 자리에 s9가 오고 s9 자리에 s13가 오고 s13자리에 s1이 와서 s5, s9, s13, s1이 됩니다.

mix columns

mix columns 단계에서는 컬럼 별로 행렬곱(matrix-vector multiplication)을 수행합니다. 현재 matrix에서 컬럼을 가져와서 미리 정의된 circulant MD5 matrix에 곱하게됩니다.

mix columns

보다시피 mix columns 단계에서는 bit 수준에서 덧셈과 곱셈을 할 수 있어야 합니다. 이 때 2와 3을 곱하는 연산을 해야하는데 우리는 여기서 2를 곱하는 것은 bit 수준에서 left shift로 생각할 수 있고 두 bit간의 덧셈은 두 bit의 XOR 연산으로 생각할 수 있습니다. 그렇다면 3을 곱하는 것은? 한 번의 left shift와 한 번의 XOR 연산의 조합으로 생각할 수 있습니다.

matrix-vector multiplication

이와 같은 과정을 거쳐서 mix columns 단계를 마치게 됩니다. 이 때 주의해야할 점 중 하나는 mix columns 과정은 마지막 round에서는 시행하지 않습니다.

Add round key

이제 round의 마지막 단계인 add round key입니다. 이 때 첫 번째로 수행했던 add round key에서는 private key로 add round key를 수행했다면 이 때는 private key로부터 subkey를 만들어서 operation을 수행합니다.

subkey generation

subkey generation – 1

1 — 먼저 위와 같이 이차원 배열로 나타난 private key를 가지고 있습니다. 위에서 말했듯이 한 block은 1byte를 가집니다.

subkey generation – 2

2 — 먼저 가장 오른쪽에 있는 컬럼을 골라 컬럼 방향으로 circular upward shift를 수행합니다.

subkey generation – 3

3 — 그리고 substitute bytes에서 사용했던 S-BOX를 이용하여 이전과 똑같은 방식으로 shift한 block byte들을 바꿉니다.

subkey generation – 4

4 — 그리고 이전 단계에서 만든 컬럼의 값들과 Ki-4 컬럼 값들을 XOR 하고 미리 정의되어있는 rcon table에서 현재 round에 해당하는 값을 가져와 다시 XOR 연산을 하게됩니다. 그 결과 값이 다음 subkey의 첫번째 컬럼이 됩니다.

subkey generation – 5

5 — 두 번째, 세 번째 그리고 마지막 column 값을 구하는 것은 간단합니다. Ki-1 컬럼과 Ki-4 컬럼을 XOR하면 끝입니다.

subkey generation – 6

6 — 이와 같은 방식으로 128-bit subkey 생성을 마치고 나면 이제 만든 subkey로 add round key 과정을 진행합니다.

Example code

예제 코드는 python Crypto.Cipher 모듈에서 제공하는 AES를 이용하여 실제로 평문을 encrypt하고 decrypt하는 과정을 살펴보려고 합니다.

Import modules

from Crypto.Cipher import AES
from Crypto import Random
import binascii

Random 모듈은 우리가 간단하게 private key를 만들기 위해 사용할 것이고, binascii 는 나중에 우리가 encrypt한 데이터를 알아보기 쉬운 hexcode로 인코딩하기 위해서 사용할 것입니다.

Solve padding problems

이전에 언급했듯이 평문을 128-bit씩 나눠서 metrix를 만들고 AES 암호화를 진행합니다. 그런데 만약 평문이 128-bit 보다 작으면 어떻게 될까요? (더 큰 경우는 일단 없다고 가정하고 예제를 작성하였습니다) 이렇게 plaintext가 128-bit로 떨어지지 않는 문제가 있을 수 있기 때문에 128-bit로 나누어 떨어질 수 있게 padding value를 붙여줍니다.

def append_space_padding(str, blocksize=128):
    pad_len = blocksize - (len(str) % blocksize)
    padding = 'a'*pad_len
    return str + padding
def remove_space_padding(str, blocksize=128):
    pad_len = 0
    for char in str[::-1]:
        if char == 'a':
            pad_len += 1
        else:
        break
    return str[:-pad_len]

그래서 위와 같이 append_space_padding 과 remove_space_padding 함수를 정의했습니다. append_space_padding 은 데이터를 encrypt 하기 전에 padding 값을 붙여주기 위해 필요하고 remove_space_padding 은 decrypt 했을 때 padding value를 없애주기 위해 정의했습니다.

어떤 것을 padding value로 할 지에는 몇 가지 옵션이 있습니다. 임의의 bit를 붙일 수도 있고 공백을 추가할 수도 있습니다. 그러나 이 예제에서 사용할 방법은 “a”라는 CMS(Cryptographic Message Syntax)를 정해서 필요한 padding 갯수만큼 추가하는 것입니다.

Encrypt, Decrypt

def encrypt(plaintext, key):
    aes = AES.new(key, AES.MODE_ECB)
    return aes.encrypt(plaintext)
def decrypt(ciphertext, key):
    aes = AES.new(key, AES.MODE_ECB)
    return aes.decrypt(ciphertext).decode('UTF-8')

encrypt, decrypt 가 이번 예제의 비즈니스 로직이라고 할 수 있습니다. 이 함수에서 MODE_ECB 모드를 가진 새로운 인스턴스를 만들고 인스턴스의 메소드를 사용합니다.

ECB가 무엇인지는 이 포스트에서 자세하게 다루지 않습니다. 간단하게 ECB는 “Electronic Codebook”의 약자이고, ECB는 AES에서 데이터를 block으로 나누어서 알고리즘을 적용할 때 각 block에 대해서 독립적으로 알고리즘을 적용하는 방식을 말합니다. 이와 대조되는 모드 중 하나가 CBC 모드인데요. CBC 모드에서는 체이닝 메커니즘을 하용하여 각 block은 이전의 모든 block들에게 영향을 받아서 알고리즘이 진행됩니다.

Entry point

if __name__ == "__main__":
    # key is 128 bits - 16 bytes
    key = Random.new().read(16)
    print("key: %s" % key.encode('hex'))
    plaintext = "Hello, AES!"
    print("length of plaintext: %d" % len(plaintext))
    print("plaintext: %s" % plaintext)
    paddedtext = append_space_padding(plaintext)
    print("length of paddedtext: %d" % len(paddedtext))
    print("paddedtext: %s" % paddedtext)
    ciphertext = encrypt(paddedtext, key)
    print("hexified ciphertext: %s" % binascii.hexlify(bytearray(ciphertext)))
    decrypted = decrypt(ciphertext, key)
    maybe_plaintext = remove_space_padding(decrypted)
    print("decrypted text: %s" % maybe_plaintext)

Results !

key: 8b5002efbe9cc0830cf1c18ab6237c3e
length of plaintext: 11
plaintext: Hello, AES!
length of paddedtext: 128
paddedtext: Hello, AES!aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
hexified ciphertext: 1baccc35d666124f4109c448799869204c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b
decrypted text: Hello, AES!

결과에서 우리는 paddedtext 의 길이가 a 문자가 붙어서 128로 나누어 떨어지는 숫자가 된 것을 볼 수 있습니다. 그리고 hexified ciphertext 는 AES 결과이고 마지막으로 decrypted text 에서 plaintext 와 동일한 Hello, AES! 문자를 출력하는 것을 확인할 수 있습니다.

Conclusion

지금까지 오늘날에도 다양한 곳에서 사용되고 있는 Advanced Encryption Standard(AES)에 대해서 살펴보았습니다. AES는 DES와 마찬가지로 block cipher이기 때문에 데이터를 block으로 나누어 encryption을 진행합니다. AES 알고리즘은 크게 다음과 같은 순서로 진행됩니다.

• Add round key
• Substitute bytes
• Shift rows
• Mix columns
• Add round key

최근에 미디엄 글을 블로그로 이전하면서 Diffie-Hellman Key Exchange에 대해서도 글을 가져왔는데 혹시 관심있으신 분은 여기에서 확인해주세요.

Reference

• https://en.wikipedia.org/wiki/Data_Encryption_Standard#Brute-force_attack
• https://blog.syncsort.com/2018/08/data-security/aes-vs-des-encryption-standard-3des-tdea/
• https://searchsecurity.techtarget.com/definition/block-cipher
• https://en.wikipedia.org/wiki/S-box
• https://searchsecurity.techtarget.com/definition/Advanced-Encryption-Standard
• https://en.wikipedia.org/wiki/Rijndael_MixColumns
• https://en.wikipedia.org/wiki/MDS_matrix
• https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_Codebook_