4주차_암호학

AES(Advanced Encryption Standard)

2001년에 새롭게 표준으로 선정된 블록 암호 알고리즘이다. AES는 전세계에서 암호 알고리즘을 공모받고, 전문가들의 심사를 거쳐 그 중에서 가장 뛰어난 알고리즘이 선정됐다.

 

혼돈(Confusion)과 확산(Diffusion)

클로드 섀넌이 제시한 대칭키 암호가 갖추어야 할 요건이다. 초기 정의에서 발전되어 현대 대칭키 암호에 맞추어 정형화된 요건은 다음과 같다

	기존 정의	현대에서의 정의
혼돈	키와 암호문 사이의 관계가 가능한 한 복잡하여야 한다.	암호문의 모든 비트는 키의 여러 부분에 의존해야 한다.
확산	평문이 암호문 대부분에 걸쳐 분산되어야 한다.	평문을 1비트만 바꿔도, 암호문은 절반 비트 가량이 바뀌어야 한다.

 

SPN

 

AES는 SPN (Substitution Permutation Network)이라는 암호 구조를 사용한다. SPN은 S-Box를 사용하는 치환(Substitution)과 P-Box를 사용하는 순열(Permutation)을 여러 라운드에 걸쳐 반복한다. SPN 구조에서는 라운드마다 입력 전체에 라운드 함수를 적용하므로 같은 수의 라운드를 사용할 때 SPN이 페이스텔 구조에 비해 두 배의 암호학적 안전성을 갖는다고 이야기다.

AES 구조

AES는 128비트 크기의 블록을 암호화하는 블록 암호이다. 키의 길이는 128, 192, 256비트 중 하나를 선택할 수 있고, 라운드 수는 키의 길이에 따라 10, 12, 14로 결정된다.  AES는 암호화를 할 때 가장 먼저 각 블록을 4행 4열의 상태 배열로 재구성합니다. 상태 배열의 각 칸에는 8비트가 저장된다. 후에 재구성된 입력에 대해 AddRoundKey 함수를 적용하고, 마지막 라운드 전까지 매 라운드마다 SubBytes, ShiftRows, MixColumns, AddRoundKey 함수를 반복하여 적용한다. 마지막 라운드에서는 MixColumns를 제외한 나머지 함수들만 적용한다.

AES 라운드 함수

SubBytes

SubBytes는 상태 배열의 각 바이트를 S-Box를 참조하여 치환하는 함수다. 치환 과정은 암호의 선형성을 망가뜨려서 분석 난이도를 까다롭게 만들어, 대칭키 암호에서의 혼돈 요건을 충족시다.

ShiftRows

상태 배열의 각 행을 구성하는 바이트들을 쉬프트하는 함수다. 유일하게 순열의 역할을 수행합니다. 2행은 왼쪽으로 1칸, 3행은 왼쪽으로 2칸, 4행은 왼쪽으로 3칸을 민다. 복호화할 때는 반대로 2행, 3행, 4행을 각각 오른쪽으로 1칸, 2칸, 3칸씩 민다.

MixColumns

열 단위로 치환을 수행하는 함수다. 이 치환은 유한체(Finite field) 내에서의 행렬 연산으로 구해지며, 일반적으로 최적화를 위해 lookup table을 만들어 사용한다. 예를 들면 아래와 같다. 

AddRoundKey

키 생성 함수(Key Schedule)로 생성된 라운드 키의 상태 배열를 각 바이트별로 XOR한다. 복호화할 때는 XOR의 성질을 이용하여 동일한 키를 상태 배열에 XOR다.

Key Schedule

입력된 키로부터 각 라운드에 쓰일 라운드 키를 생성합니다

 

chall.py

from AES import AES_implemented
import os

# For real AES without modification, this challenge is unsolvable with modern technology.
# But let's remove a step.
ret = lambda x: None
AES_implemented._sub_bytes = ret
AES_implemented._sub_bytes_inv = ret
# Will it make a difference?

secret = os.urandom(16)
key = os.urandom(16)

flag = open("flag.txt", "r").read()

cipher = AES_implemented(key)

secret_enc = cipher.encrypt(secret)
assert cipher.decrypt(secret_enc) == secret
print(f"enc(secret) = {bytes.hex(secret_enc)}")

while True:
    option = int(input("[1] encrypt, [2] decrypt: "))

    if option == 1: # Encryption
        plaintext = bytes.fromhex(input("Input plaintext to encrypt in hex: "))
        assert len(plaintext) == 16

        ciphertext = cipher.encrypt(plaintext)
        print(f"enc(plaintext) = {bytes.hex(ciphertext)}")

        if plaintext == secret:
            print(flag)
            exit()

    elif option == 2: # Decryption
        ciphertext = bytes.fromhex(input("Input ciphertext to decrypt in hex: "))
        assert len(ciphertext) == 16
        
        if ciphertext == secret_enc:
            print("No way!")
            continue
            
        plaintext = cipher.decrypt(ciphertext)
        print(f"dec(ciphertext) = {bytes.hex(plaintext)}")

SubBytes 과정에 해당하는 _sub_bytes 함수를 제거, 복호화 과정에서 SubBytes의 역연산인 _sub_bytes_inv 함수 또한 제거했다.

• 임의의 16바이트 평문 암호화
• secret의 암호문을 제외한 임의의 16바이트 암호문 복호화.

익스플로잇 설계

선형 관계를 가지는 변형 AES 암호의 암호화 함수는 다음과 같은 특징을 가다.

복호화 또한 이 성질을 만족한다. 

차분(Difference) 관점으로 식을 변형하면 다음과 같다. 

선형 관계의 확

from AES import AES_implemented
import os

ret = lambda x: None
AES_implemented._sub_bytes = ret
AES_implemented._sub_bytes_inv = ret

xor = lambda a, b: bytes([i ^ j for i, j in zip(a, b)])

secret = os.urandom(16)
key = os.urandom(16)

cipher = AES_implemented(key)

for _ in range(1000):
    a = os.urandom(16)
    b = os.urandom(16)
    diff = os.urandom(16)

    # 1
    val1 = xor(cipher.encrypt(a), cipher.encrypt(b))
    val2 = xor(cipher.encrypt(xor(a, b)), cipher.encrypt(bytes(16)))
    assert val1 == val2

    # 2
    val1 = xor(cipher.decrypt(a), cipher.decrypt(b))
    val2 = xor(cipher.decrypt(xor(a, b)), cipher.decrypt(bytes(16)))
    assert val1 == val2

    # 3
    val1 = xor(cipher.encrypt(a), cipher.encrypt(xor(a, diff)))
    val2 = xor(cipher.encrypt(b), cipher.encrypt(xor(b, diff)))
    assert val1 == val2

    # 4
    val1 = xor(cipher.decrypt(a), cipher.decrypt(xor(a, diff)))
    val2 = xor(cipher.decrypt(b), cipher.decrypt(xor(b, diff)))
    assert val1 == val2

secret의 복호화

위 등식에서 양변에 dec(b)를 XOR 연산해주면 다음과 같습니다.

솔브 코드

from pwn import *
import os

# io = process(["python3", "chall.py"])
io = remote("host3.dreamhack.games", 20224)

xor = lambda a, b: bytes([i ^ j for i, j in zip(a, b)])

io.recvuntil(b"= ")
secret_enc = bytes.fromhex(io.recvline().decode())

def encrypt(plaintext):
    io.sendline(b"1")
    io.sendline(bytes.hex(plaintext).encode())
    io.recvuntil(b"= ")
    ciphertext = bytes.fromhex(io.recvline().decode())
    return ciphertext

def decrypt(ciphertext):
    io.sendline(b"2")
    io.sendline(bytes.hex(ciphertext).encode())
    io.recvuntil(b"= ")
    plaintext = bytes.fromhex(io.recvline().decode())
    return plaintext

b = os.urandom(16)

p1 = decrypt(bytes(16))
p2 = decrypt(xor(secret_enc, b))
p3 = decrypt(b)

p = xor(p1, xor(p2, p3))
encrypt(p)

io.interactive()

 

AES의 ShiftRows 단계가 없을 경우

chall.py

from AES import AES_implemented
import os

# For real AES without modification, this challenge is unsolvable with modern technology.
# But let's remove a step.
ret = lambda x: None
AES_implemented._shift_rows = ret
AES_implemented._shift_rows_inv = ret
# Will it make a difference?

secret = os.urandom(16)
key = os.urandom(16)

flag = open("flag.txt", "r").read()

cipher = AES_implemented(key)

secret_enc = cipher.encrypt(secret)
assert cipher.decrypt(secret_enc) == secret
print(f"enc(secret) = {bytes.hex(secret_enc)}")

while True:
    option = int(input("[1] encrypt, [2] decrypt: "))

    if option == 1: # Encryption
        plaintext = bytes.fromhex(input("Input plaintext to encrypt in hex: "))
        assert len(plaintext) == 16

        ciphertext = cipher.encrypt(plaintext)
        print(f"enc(plaintext) = {bytes.hex(ciphertext)}")

        if plaintext == secret:
            print(flag)
            exit()

    elif option == 2: # Decryption
        ciphertext = bytes.fromhex(input("Input ciphertext to decrypt in hex: "))
        assert len(ciphertext) == 16
        
        if ciphertext == secret_enc:
            print("No way!")
            continue
            
        plaintext = cipher.decrypt(ciphertext)
        print(f"dec(ciphertext) = {bytes.hex(plaintext)}")

익스플로잇 설계

 ShiftRows 과정이 없을 시, 각 열들은 독립적인 연산이 진행다.

 

한 비트만 차이나는 평문쌍을 암호화한 결과

[1] encrypt, [2] decrypt: 1
Input plaintext to encrypt in hex: 00000000000000000000000000000000
enc(plaintext) = 25de8dcf447352d4661c7008e4794783
[1] encrypt, [2] decrypt: 1
Input plaintext to encrypt in hex: 00000000000000000000000000000001
enc(plaintext) = 25de8dcf447352d4661c70080192da49

 

다른 비트로도 실험한 결과

[1] encrypt, [2] decrypt: 1
Input plaintext to encrypt in hex: 00000000000000000000000000000000
enc(plaintext) = 25de8dcf447352d4661c7008e4794783
[1] encrypt, [2] decrypt: 1
Input plaintext to encrypt in hex: 00000000000000000000000000010000
enc(plaintext) = 25de8dcf447352d4661c7008deb0c328
[1] encrypt, [2] decrypt: 1
Input plaintext to encrypt in hex: 000000000000000000000000deadbeef
enc(plaintext) = 25de8dcf447352d4661c7008ab3c996a

솔브 코드

from pwn import *
import os

io = process(["python3", "chall.py"])
io = remote("host3.dreamhack.games", 13536)

xor = lambda a, b: bytes([i ^ j for i, j in zip(a, b)])

io.recvuntil(b"= ")
secret_enc = bytes.fromhex(io.recvline().decode())

def encrypt(plaintext):
    io.sendline(b"1")
    io.sendline(bytes.hex(plaintext).encode())
    io.recvuntil(b"= ")
    ciphertext = bytes.fromhex(io.recvline().decode())
    return ciphertext

def decrypt(ciphertext):
    io.sendline(b"2")
    io.sendline(bytes.hex(ciphertext).encode())
    io.recvuntil(b"= ")
    plaintext = bytes.fromhex(io.recvline().decode())
    return plaintext

secret = [0] * 16

for i in range(4):
    c = [0] * 16
    for j in range(4):
        c[4 * i + j] = secret_enc[4 * i + j]
    c = bytes(c)

    p = decrypt(c)
    for j in range(4):
        secret[4 * i + j] = p[4 * i + j]

secret = bytes(secret)

encrypt(secret)

io.interactive()