[🥉 Bronze 2] ShiftRows 하나 빼면 AES가 32비트 암호 네 개로 쪼개진다 — DreamHack No shift please! 풀이

ls -la extracted && file extracted/*.py && wc -l extracted/*.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)}")

grep -n "shift_rows" extracted/chall.py extracted/AES.py

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

#!/usr/bin/env bash
# extracted/AES.py 가 정말 표준 AES-128-ECB 인지 openssl 로 대조한다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
KEY=000102030405060708090a0b0c0d0e0f
PT=00112233445566778899aabbccddeeff
 
MINE=$(python3 -c "
import sys; sys.path.insert(0, 'extracted')
from AES import AES_implemented
print(AES_implemented(bytes.fromhex('$KEY')).encrypt(bytes.fromhex('$PT')).hex())
")
OSSL=$(printf '%s' "$PT" | xxd -r -p | openssl enc -aes-128-ecb -K "$KEY" -nopad | xxd -p)
 
openssl version
echo "key       = $KEY"
echo "plaintext = $PT"
echo "AES.py    = $MINE"
echo "openssl   = $OSSL"
if [ "$MINE" = "$OSSL" ]; then
  echo "-> 일치. 문제의 AES.py 는 손대지 않은 표준 AES-128 이다."
else
  echo "-> 불일치. 구현이 표준과 다르다."
fi

./crosscheck.sh

python3 AES.py && echo "4096 vectors == PyCryptodome  (rc=$?)"

def _transpose(self, m):
    return [m[4 * j + i] for i in range(4) for j in range(4)]

#!/usr/bin/env python3
"""AES 상태 배열의 바이트 배치 확인.
 
AES.py 의 _transpose 가 입력 16바이트를 어떤 4x4 격자로 펴는지, 그래서 "컬럼 하나"가
입력의 어느 바이트들인지 실제 함수를 호출해 확인한다. 이 배치를 잘못 잡으면
뒤집을 4바이트를 엉뚱하게 고르게 된다.
"""
import os
import sys
 
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), "extracted"))
from AES import AES_implemented
 
cipher = AES_implemented(bytes(16))
 
# 입력 바이트를 '자기 인덱스' 로 채워 두면 어디로 갔는지 그대로 읽힌다.
state = cipher._transpose(list(range(16)))
 
print("_transpose(list(range(16))) =", state)
print()
print("state[4*r + c] 로 본 4x4 격자 (칸 값 = 입력 바이트 번호)")
print("        c=0  c=1  c=2  c=3")
for r in range(4):
    row = "  ".join(f"{state[4 * r + c]:3d}" for c in range(4))
    print(f"  r={r}   {row}")
print()
 
for c in range(4):
    idx = [state[4 * r + c] for r in range(4)]
    print(f"  컬럼 {c} = 입력 바이트 {idx}  -> 연속 구간 [{idx[0]}:{idx[-1] + 1}]")
print()
 
# 라운드키도 _expand_key 끝에서 같은 전치를 거친다. 즉 키 바이트도 같은 규칙으로 컬럼에 들어간다.
probe = AES_implemented(bytes(range(16)))
print("round_keys[0] (전치 후) =", probe._round_keys[0])
print("  -> 마스터키 0..15 가 전치돼 들어갔다. 컬럼 c 가 쓰는 키 바이트도 key[4c:4c+4] 다.")

python3 layout.py

#!/usr/bin/env python3
"""ShiftRows 유무에 따른 확산(diffusion) 비교.
 
평문 1바이트를 뒤집었을 때 암호문의 어느 바이트가 따라 바뀌는지 센다.
원본 AES 는 16바이트 전부 바뀌고, ShiftRows 를 뺀 AES 는 같은 4바이트 청크만 바뀐다.
"""
import os
import sys
 
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), "extracted"))
from AES import AES_implemented
 
 
def diff_map(cipher, base_pt):
    """평문 바이트 i 를 뒤집었을 때 바뀌는 암호문 바이트 집합을 i 별로 반환."""
    base_ct = cipher.encrypt(base_pt)
    rows = []
    for i in range(16):
        pt = bytearray(base_pt)
        pt[i] ^= 0xFF
        ct = cipher.encrypt(bytes(pt))
        rows.append([a != b for a, b in zip(base_ct, ct)])
    return rows
 
 
def show(title, rows):
    print(f"== {title} ==")
    print("    " + "".join(f"{j:2d}" for j in range(16)) + "   changed")
    for i, row in enumerate(rows):
        marks = "".join(" #" if x else " ." for x in row)
        print(f"p{i:<2d}{marks}   {sum(row):2d}/16")
    print()
 
 
key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
pt = bytes.fromhex("00112233445566778899aabbccddeeff")
 
show("original AES (ShiftRows 있음)", diff_map(AES_implemented(key), pt))
 
AES_implemented._shift_rows = lambda self: None
AES_implemented._shift_rows_inv = lambda self: None
 
show("patched AES (ShiftRows 제거)", diff_map(AES_implemented(key), pt))

python3 diffusion.py

#!/usr/bin/env python3
"""라운드 연산별 오염(taint) 추적.
 
평문 0번 바이트만 뒤집은 두 입력을 AES.py 의 진짜 코드로 나란히 돌리면서,
각 연산 직후 상태 배열의 어느 칸이 달라졌는지 센다. 재구현이 아니라 원본 메서드를
감싸서 스냅샷만 뜨는 방식이라 실제 구현의 동작 그대로다.
"""
import os
import sys
 
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), "extracted"))
from AES import AES_implemented
 
SNAPS = []
OPS = ("_add_round_key", "_sub_bytes", "_shift_rows", "_mix_columns")
 
 
def install_probe():
    for name in OPS:
        orig = getattr(AES_implemented, name)
 
        def wrapper(self, *args, _orig=orig, _name=name):
            out = _orig(self, *args)
            SNAPS.append((_name, list(self._state)))
            return out
 
        setattr(AES_implemented, name, wrapper)
 
 
def trace(key, pt):
    SNAPS.clear()
    AES_implemented(key).encrypt(pt)
    return list(SNAPS)
 
 
def report(title, key, pt):
    a = trace(key, pt)
    b = trace(key, bytes([pt[0] ^ 0xFF]) + pt[1:])
    print(f"== {title} ==")
    print("  step                     오염된 상태 칸 수   오염된 컬럼")
    rnd = 0
    for (name, sa), (_, sb) in zip(a, b):
        if name == "_add_round_key":
            rnd += 1
        idx = [i for i, (x, y) in enumerate(zip(sa, sb)) if x != y]
        cols = sorted({i % 4 for i in idx})  # state[4r+c] 이므로 컬럼 = 인덱스 % 4
        print(f"  r{rnd - 1:<2d} {name:<20s} {len(idx):>3d}/16          {cols}")
        if len(cols) == 4:
            print("       -> 네 컬럼 전부 오염. 여기서 추적을 끊는다.")
            return
    print("       -> 끝까지 한 컬럼에 갇혔다.")
 
 
key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
pt = bytes.fromhex("00112233445566778899aabbccddeeff")
 
install_probe()
report("original AES — p0 한 바이트를 뒤집었을 때", key, pt)
print()
 
AES_implemented._shift_rows = lambda self: None
AES_implemented._shift_rows_inv = lambda self: None
report("patched AES (ShiftRows 제거) — 같은 입력", key, pt)

python3 taint.py

#!/usr/bin/env python3
"""컬럼이 독립이면 무슨 일이 벌어지나 — 4바이트 단위 ECB.
 
같은 자리에 같은 4바이트를 가진 서로 다른 평문 두 개를 암호화하면, 그 자리 암호문도
같은 값이 나온다. 128비트 블록암호라고 부르지만 실제로는 32비트 블록 넷을 ECB 로
이어붙인 것과 다르지 않다는 뜻이다.
"""
import os
import sys
 
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), "extracted"))
from AES import AES_implemented
 
AES_implemented._shift_rows = lambda self: None
AES_implemented._shift_rows_inv = lambda self: None
 
key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
cipher = AES_implemented(key)
 
pa = b"AAAAsecret!!BBBB"
pb = b"ZZZZsecret!!YYYY"
 
ca, cb = cipher.encrypt(pa), cipher.encrypt(pb)
 
print(f"평문 A     = {pa!r}")
print(f"평문 B     = {pb!r}")
print(f"암호문 A   = {ca.hex()}")
print(f"암호문 B   = {cb.hex()}")
print()
for c in range(4):
    s = slice(4 * c, 4 * c + 4)
    same_pt = pa[s] == pb[s]
    same_ct = ca[s] == cb[s]
    print(
        f"  청크{c} [{4 * c:2d}:{4 * c + 4:2d}]  평문 {pa[s]!r} vs {pb[s]!r} "
        f"{'같음' if same_pt else '다름'}  ->  암호문 {'같음' if same_ct else '다름'}"
        f"  ({ca[s].hex()} / {cb[s].hex()})"
    )
print()
print("평문이 같은 청크는 암호문도 같다 = 4바이트 단위 ECB.")
 
# 같은 청크를 서로 다른 자리에 두면? 컬럼마다 라운드키가 달라 값이 달라진다.
pc = b"secret!!AAAABBBB"
cc = cipher.encrypt(pc)
print()
print(f"평문 C     = {pc!r}   (같은 'secr' 을 청크0 으로 옮김)")
print(f"암호문 C   = {cc.hex()}")
print(f"  A 의 청크1 {ca[4:8].hex()} vs C 의 청크0 {cc[0:4].hex()} -> "
      f"{'같음' if ca[4:8] == cc[0:4] else '다름'} (컬럼마다 라운드키가 다르다)")

python3 chunk_leak.py

#!/usr/bin/env python3
"""No shift please! (Dreamhack, Bronze 2 / crypto)
 
ShiftRows 가 빠진 AES 는 128비트 블록 하나가 아니라 독립적인 32비트 암호 4개다.
평문/암호문의 연속 4바이트 청크가 곧 AES 컬럼 1개이고, 남은 세 연산
(AddRoundKey / SubBytes / MixColumns) 은 전부 컬럼 안에서 끝나기 때문이다.
 
서버는 enc(secret) 을 알려주고 복호화 오라클도 열어 주지만 enc(secret) 자체는 거부한다.
그러나 한 청크만 뒤집은 암호문은 "다른 값" 이므로 통과하고, 건드리지 않은 세 청크는
secret 의 평문 그대로 돌아온다. 서로 다른 청크를 뒤집은 질의 두 번이면 16바이트가 다 모인다.
 
사용법:
    python3 solve.py                       # 로컬 재현(local/chall.py)
    python3 solve.py host3.dreamhack.games 12345
"""
import sys
 
from pwn import context, process, remote
 
context.log_level = "info"
 
MENU = b"[1] encrypt, [2] decrypt: "
 
 
def flip(block: bytes) -> bytes:
    """청크 하나를 통째로 뒤집어 '원본과 다른 암호문' 을 만든다."""
    return bytes(b ^ 0xFF for b in block)
 
 
def decrypt(io, ct: bytes) -> bytes:
    io.sendlineafter(MENU, b"2")
    io.sendlineafter(b"Input ciphertext to decrypt in hex: ", ct.hex().encode())
    io.recvuntil(b"dec(ciphertext) = ")
    return bytes.fromhex(io.recvline().strip().decode())
 
 
def encrypt(io, pt: bytes) -> bytes:
    io.sendlineafter(MENU, b"1")
    io.sendlineafter(b"Input plaintext to encrypt in hex: ", pt.hex().encode())
    io.recvuntil(b"enc(plaintext) = ")
    return bytes.fromhex(io.recvline().strip().decode())
 
 
def main():
    if len(sys.argv) >= 3:
        io = remote(sys.argv[1], int(sys.argv[2]))
    else:
        io = process(["python3", "chall.py"], cwd="local")
 
    io.recvuntil(b"enc(secret) = ")
    secret_enc = bytes.fromhex(io.recvline().strip().decode())
    print(f"[*] enc(secret)  = {secret_enc.hex()}")
 
    # 질의 1 — 마지막 청크만 뒤집는다. 앞의 세 청크는 secret[0:12] 그대로 나온다.
    q1 = secret_enc[:12] + flip(secret_enc[12:])
    p1 = decrypt(io, q1)
    print(f"[*] query#1 ct   = {q1.hex()}")
    print(f"[*] query#1 pt   = {p1.hex()}   <- 앞 12바이트가 secret")
 
    # 질의 2 — 첫 청크만 뒤집는다. 뒤의 세 청크는 secret[4:16] 그대로 나온다.
    q2 = flip(secret_enc[:4]) + secret_enc[4:]
    p2 = decrypt(io, q2)
    print(f"[*] query#2 ct   = {q2.hex()}")
    print(f"[*] query#2 pt   = {p2.hex()}   <- 뒤 12바이트가 secret")
 
    secret = p1[:12] + p2[12:]
    print(f"[+] secret       = {secret.hex()}")
 
    # 겹치는 8바이트(4~11)가 두 질의에서 같아야 한다 — 컬럼 독립성의 자체 검증.
    assert p1[4:12] == p2[4:12], "청크 독립 가정이 깨졌다"
 
    # secret 을 그대로 암호화 요청하면 서버가 flag 를 뱉는다.
    ct = encrypt(io, secret)
    print(f"[*] enc(secret') = {ct.hex()}")
    assert ct == secret_enc, "복구한 secret 의 암호문이 enc(secret) 과 다르다"
 
    io.recvuntil(b"DH{")
    flag = "DH{" + io.recvuntil(b"}").decode()
    print(f"[+] FLAG: {flag}")
    io.close()
 
 
if __name__ == "__main__":
    main()

python3 solve.py

python3 solve.py host3.dreamhack.games 14466

DH{This_is_actually_pretty_safe_for_a_4btye_cipher.._But_unsafe_ofc}