[Dreamhack] No sub please!

문제 설명

AES에서 SubBytes 기능을 없애봤어요! 이 암호는 과연 안전할까요?

 

 

소스 코드

#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)}")

 

(AES.py는 코드가 길어서 생략)

 

 

소스 코드 설명

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

• AES_implemented 클래스 안에 있는 _sub_bytes와 _sub_bytes_inv를 작동하지 않게 만듦.
• 즉, AES의 SubBytes 과정을 없앰.

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

• secret과 key 값을 16바이트 랜덤 값으로 할당함.

cipher = AES_implemented(key)

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

• 생성된 키로 AES 암호화 객체를 생성함.
• secret 값을 AES로 암호화해서 secret_enc에 저장함.
• 암호화가 정상적으로 되었으면 secret 값을 출력함.

 

[ ⭐ 암호화 ]

if option == 1:
    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()

• 사용자가 16바이트의 평문을 입력하면 암호문을 생성해서 출력함.
• 만약 입력한 평문이 secret 값과 같으면 flag를 출력함.
• 즉, secret 값을 맞추면 flag를 알 수 있음.

 

[ 복호화 ]

elif option == 2:
    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)}")

• 사용자가 암호문을 입력하면 복호화해서 평문을 알려줌.
• 단, secret_enc 값은 복호화 못하게 막아둠.
• secret_enc을 넣어서 바로 secret 값을 알아내는 꼼수를 차단함.

 

문제 풀이

이 코드의 존재하는 치명적인 취약점은 Subbytes 단계를 제거한 것이다.

 

AES 암호화 가정에서 SubBytes 단계는 S-Box라는 non-linear 치환 테이블을 사용한다.

이는 AES의 전체 암호화 과정을 non-linear로 만들어, 단순한 대수적 공격(ex. 연립방정식 풀이)를 불가능하게 만드는 장치이다

 

SubBytes가 제거되면 AES에 남는 연산은 ShiftRows, MixColumns, AddRoundKey이다.

이 연산들은 모두 linear 연산이다.

 

선형성의 의미: 암호화 함수 $E_k(P)$와 복호화 함수 $D_k(C)$가 선형 (정확히는 아핀 변환, $f(x) = Ax + b$)이 된다.

• $E_k(P_1 \oplus P_2) = E_k(P_1) \oplus E_k(P_2) \oplus E_k(0)$
• $D_k(C_1 \oplus C_2) = D_k(C_1) \oplus D_k(C_2) \oplus D_k(0)$

 

우리는 secret = cipher.decrypt(secret_enc)을 계산하고 싶지만, 복호화 함수가 이를 막고 있다.

하지만, 선형성의 성질을 이용하면 이 값을 알아낼 수 있다.

 

알고 있는 값 :  secret_enc

원하는 값 : secret = cipher.decrypt(secret_enc)

 

1. cipher.decrypt(0) 값 구하기

• decrypt 옵션을 선택한다.
• 입력값으로 16바이트의 0을 전송한다.
• 서버가 반환하는 평문 값을 $P_0$으로 저장한다. ( $P_0$ = cipher.decrypt(0) )

2. 임의의 $C_1$에 대한 cipher.decrypt($C_1$) 값 구하기

• decrypt 옵션을 선택한다.
• 입력값으로 임의의 16바이트 값 $C_1$을 전송한다. ex) 11111111111111111111111111111111
• 서버가 반환하는 평문 값을 $P_1$으로 저장한다. ( $P_1$ = cipher.decrypt( $C_1$ ) )

3. cipher.decrypt( $secret\_enc \oplus C_1$  ) 값 구하기

• $C_1$ 값과 secret_enc 값을 XOR 연산한다.
  • $C_x = secret\_enc \oplus C_1$
• decrypt 옵션을 선택한다.
• 계산된 $C_x$ 값을 서버에 전송한다.
• 서버가 반환하는 평문 값을 $P_x$으로 저장한다. ( $P_x$ = cipher.decrypt( $C_x$ ) = cipher.decrypt($ secret\_enc \oplus C_1$ ) )

4. secret 계산하기

• 이제 복호화 함수의 선형적 성질 $D_k(C_1 \oplus C_2) = D_k(C_1) \oplus D_k(C_2) \oplus D_k(0)$을 이횽한다.
• $P_x$ = cipher.decrypt( $ secret\_enc \oplus C_1$ ) = cipher.decrypt( $ secret\_enc$ ) ⊕ cipher.decrypt( $C_1$ ) ⊕ cipher.decrypt( $0$ )
• $P_x$ = $secret$ ⊕ $P_1$ ⊕ $P_0$
• 이 식을 secret에 대한 식으로 정리하면
  • $secret$ = $P_x$  ⊕ $P_1$ ⊕ $P_0$

5. flag 획득

• encrypt 옵션을 선택한다.
• 4단계에서 계산한 secret의 16진수 값을 입력한다.
• 서버가 flag 값을 출력한다.

 

풀이 코드

from pwn import *

HOST = 'host8.dreamhack.games'
PORT = 20204

def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

r = remote(HOST, PORT)

r.recvuntil(b'enc(secret) = ')
secret_enc = bytes.fromhex(r.recvline().strip().decode())

def decrypt(payload_bytes):
    r.sendlineafter(b"[1] encrypt, [2] decrypt: ", b'2')
    r.sendlineafter(b"Input ciphertext to decrypt in hex: ", payload_bytes.hex().encode())
    r.recvuntil(b'dec(ciphertext) = ')
    plaintext = bytes.fromhex(r.recvline().strip().decode())
    return plaintext

def encrypt(payload_bytes):
    r.sendlineafter(b"[1] encrypt, [2] decrypt: ", b'1')
    r.sendlineafter(b"Input plaintext to encrypt in hex: ", payload_bytes.hex().encode())

C0 = b'\x00' * 16
P0 = decrypt(C0)

C1 = b'\x11' * 16 
P1 = decrypt(C1)

Cx = xor(secret_enc, C1)
Px = decrypt(Cx)

secret = xor(xor(Px, P1), P0)

encrypt(secret)

r.interactive()