[Dreamhack] No shift please!

문제 설명

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

 

 

소스 코드 설명

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

• AES_implemented 클래스 안에 있는 _shift_rows 와 _shift_rows _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 값을 알아내는 꼼수를 차단함.

 

문제 풀이

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

이전 문제에서는 SubBytes를 제거하여 비선형성을 없앴지만, 이번 문제에서는 ShiftRows를 제거하여 Diffusion(확산) 속성을 망가뜨렸다.

 

AES는 16바이트 데이터를 4x4 행렬로 처리한다.

ShiftRows 단계는 이 행렬의 2,3,4번째 행의 바이트를 왼쪽으로 일정 칸씩 밀어 섞는 역할을 한다.

SubBytes와 MixColumns가 Column 단위로만 연산을 수행하기 때문에, ShiftRows가 없으면 한 열의 바이트는 다른 열의 바이트에 전혀 영향을 주지 못한다.

ShiftRows는 이 열들을 수평으로 섞어서 한 바이트의 변경이 전체 16파이트에 퍼지도록(확산) 하는 핵심 장치이다.

 

ShiftRows가 사라지면, AES의 모든 라운드 SubBytes, MixColumns, AddRoundKey가 Column 내에서만 독립적으로 수행된다.

즉, 128비트 AES 암호화가 32비트 암호화 4개가 병렬로 동작하는 것과 같아진다.

 

• 1열 (bytes 0, 4, 8, 12)
• 2열 (bytes 1, 5, 9, 13)
• 3열 (bytes 2, 6, 10, 14)
• 4열 (bytes 3, 7, 11, 15)

 

1열의 평문은 1열의 암호문에만, 2열의 평문은 2열의 암호문에만 영향을 준다.

 

이러한 Column의 독립성을 이용하면, secret_enc를 복호화하지 않고도 secret의 각 열을 조각조각 알아낼 수 있다.

 

알고있는 값 : secret_enc : $ C_0, C_1, C_2, C_3, ..., C_15 $

원하는 값 : secret : $P_0, P_1, P_2, P_3, ..., P_15$

 

1. secret의 첫 번째 열 (bytes 0, 4, 8, 12) 찾기

• 서버가 알려준 secret_enc에서 첫 번째 열에 해당하는 바이트 (0, 4, 8, 12번째)만 가져온다.
• 나머지 12개의 바이트에는 secret_enc와 다르게 하기 위해서 모두 0으로 채워서 새로운 16바이트 암호문 C_test_1을 만든다.
  • C_test_1[0] = secret_enc[0]
  • C_test_1[4] = secret_enc[4]
  • C_test_1[8] = secret_enc[8]
  • C_test_1[12] = secret_enc[12]
  • (나머지 인덱스는 0)
• 이 C_test_1은 secret_enc와 다르므로, 서버의 [2] decrypt 옵션으로 복호화할 수 있다.
• 서버가 복호화한 결과 P_result_1을 받는다.
• P_result_1의 첫 번째 열(bytes 0, 4, 8, 12)은 우리가 찾던 secret의 첫 번째 열과 정확히 일치한다.

2. 다음 과정을 나머지 열에 모두 반복한다.

 

3. secret 조합

• 얻는 조각들을 올바른 위치에 합치면 16바이트의 전체 secret이 완성된다.

4. flag 획득

• 서버에 [1] encrypt 옵션을 선택하고, 조합한 secret을 16진수로 입력하여 플래그를 얻는다.

 

풀이 코드

from pwn import *

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

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())

final_secret_list = bytearray(16)

for col_index in range(4):
    test_cipher = bytearray(16)
    
    for row_index in range(4):
        idx = (col_index * 4) + row_index
        test_cipher[idx] = secret_enc[idx]
        
    decrypted_partial = decrypt(test_cipher)
    
    for row_index in range(4):
        idx = (col_index * 4) + row_index
        final_secret_list[idx] = decrypted_partial[idx]

secret = bytes(final_secret_list)

encrypt(secret)

r.interactive()