SASCTF 2025 - bigbabycode (crypto) write-up

 

task.py

import numpy as np
import itertools

R = 6
N = 2**R - 1
K = N - R

def string_to_bits(s):
    bits = []
    for ch in s:
        bits.extend(int(b) for b in format(ord(ch), '08b'))
    return bits

def pad_and_split(bits, k):
    bb = bits.copy()
    bb.append(1)
    pad_len = (-len(bb)) % k
    bb.extend([0] * pad_len)
    return [bb[i:i+k] for i in range(0, len(bb), k)]

def p2(x):
    return x != 0 and (x & (x - 1) == 0)

def check(r):
    n = 2**r - 1
    H = np.zeros((r, n), dtype=int)
    for j in range(1, n+1):
        H[:, j-1] = [(j >> i) & 1 for i in range(r)]
    return H 

def gen(r):
    H = check(r)
    n = H.shape[1]
    posd   = [j for j in range(1, n+1) if not p2(j)]
    posp = [j for j in range(1, n+1) if p2(j)]
    k = len(posd)
    H_data = H[:, [j-1 for j in posd]]
    A = H_data.T                        
    G_h = np.zeros((k, n), dtype=int)
    for i, j in enumerate(posd):
        G_h[i, j-1] = 1
    for p, j in enumerate(posp):
        G_h[:, j-1] = A[:, p]
    return G_h

def bm(k):
    S = np.eye(k, dtype=int)
    for _ in range(k):
        i, j = np.random.choice(k, 2, replace=False)
        if np.random.rand() < 0.5:
            S[[i,j], :] = S[[j,i], :]
        else:
            S[i, :] ^= S[j, :]
    return S

def keygen(r=6):
    G_h = gen(r)
    k, n = G_h.shape
    S = bm(k)
    perm = np.random.permutation(n)
    G_pub = (S.dot(G_h) % 2)[:, perm]
    return (S, perm), G_pub, G_h

def enc(m_bits, G_pub, t):
    k, n = G_pub.shape
    assert len(m_bits) == k
    m = np.array(m_bits, dtype=int).reshape(1, k)
    c0 = (m.dot(G_pub) % 2).flatten()
    e = np.zeros(n, dtype=int)
    idx = np.random.choice(n, size=t, replace=False)
    e[idx] = 1
    return (c0 ^ e).tolist(), e.tolist()


def main():
    priv_key, G_pub, G_h = keygen(R)
    np.save('alice_pub.npy', G_pub)

    m = input("Enter your message: ")
    m_bits = string_to_bits(m)
    m_bits_blocks = pad_and_split(m_bits, K)

    c_bits_blocks = []
    for block in m_bits_blocks:
        c_block, e = enc(block, G_pub, 1)
        c_bits_blocks.append(c_block)

    c_bits = list(itertools.chain.from_iterable(c_bits_blocks))
    c_int = int(''.join(map(str, c_bits)), 2)
    c_hex = hex(c_int)[2:].rjust(len(c_bits) // 4, '0')

    print("Your encrypted message is: ", c_hex)

 

 

output.txt

Your encrypted message is:  33b4ba0c3c11ad7e298b79de7261c5dd8edd7b537007b383cad9f38dbcf584e66a07c9808edad6e289516f3c6cc4186686f3a7fc8e1603e80aba601efe82e8cf2f6a28aa405cf7419b9dd1f01925c5

 

---

Analysis

var	val	desc
n	63	해밍코드 길이
k	57	메시지 비트 수
r	6	패리티 비트 수 n = 2^r - 1
t	1	주입되는 오류 비트 수

 

해밍코드 최소 길이 d=3 이므로 오류 1비트 고칠 수 있음

t=1이면 공개키가 아무리 permutation, scramble 되어도 쉽게 복호화 가능

 

행렬 생성과 키 생성만 집중적으로 보겠다.

 

check(r)

def check(r):
    n = 2**r - 1
    H = np.zeros((r, n), dtype=int)
    for j in range(1, n+1):
        H[:, j-1] = [(j >> i) & 1 for i in range(r)]
    return H

j는 strings_to_bits에서 만들어지는 이진 데이터를 열벡터로 H(6x63) 생성

-> little endian으로 쓴 6bit column

 

G_h

def gen(r):
    H = check(r)
    n   = H.shape[1]                 # 63
    posd = [j for j in range(1,n+1) if not p2(j)]   # 데이터 자리 57개
    posp = [j for j in range(1,n+1) if p2(j)]       # 패리티 자리 6개
    k = len(posd)                   # 57

    H_data = H[:, [j-1 for j in posd]]
    A = H_data.T                    # 57 × 6

    G_h = np.zeros((k, n), dtype=int)
    # 데이터 열 -> 단위행렬
    for i, j in enumerate(posd):
        G_h[i, j-1] = 1
    # 패리티 열 → A = H_data^T
    for p, j in enumerate(posp):
        G_h[:, j-1] = A[:, p]
    return G_h                      # 57 × 63

 

G_h = [ I_k | A ] 

 

키 생성

row scrambler

def bm(k):
    S = np.eye(k, dtype=int)         # 57×57 단위행렬
    for _ in range(k):
        i,j = np.random.choice(k,2,False)
        if np.random.rand() < 0.5:   # swap
            S[[i,j],:] = S[[j,i],:]
        else:                        # i ^= j
            S[i,:] ^= S[j,:]
    return S                         # full-rank

 

McEliece류로 바꿀 때 scramble한다.

 

keygen

def keygen(r=6):
    G_h = gen(r)                     # 57×63
    k,n = G_h.shape
    S    = bm(k)                     # 57×57
    perm = np.random.permutation(n)  # 열 랜덤 섞기
    G_pub = (S.dot(G_h) % 2)[:, perm]
    return (S, perm), G_pub, G_h     # priv, pub, original

 

공개키 G_pub = S x G_h x P

비밀키 (S, perm)

 

encryption

def enc(m_bits, G_pub, t):
    k, n = G_pub.shape
    m  = np.array(m_bits).reshape(1,k)
    c0 = (m.dot(G_pub) % 2).flatten()
    e  = np.zeros(n, int)
    idx = np.random.choice(n, t, False)  # t개 오류 위치
    e[idx] = 1
    return (c0 ^ e).tolist(), e.tolist() # ciphertext, error mask

t비트만 1인 오류 벡터 e를 더해 ciphertext 생성

t = 1 로 고정한다는 점에서 취약점 발견

 

 

method

해밍코드 최소거리가 3이므로 모든 1 bit 오류는 syndrome 하나로 위치가 나온다.

행열을 아무리 섞어도 열벡터가 그대로이므로 syndrome <-> 열벡터 매핑이 안 깨진다.

public key만으로 H = ker(G_pub) 계산 후 s = H x c로 오류 위치 잡고, m을 GF(2) 선형으로 연산하면 평문이 복원된다.

 

t가 2이상이라면 McEliece confusion

---

Exploitation

from pwn import *
import numpy as np, os, re, sys

context.log_level = 'error'


def nullspace(A):
    A = A.copy() & 1; m, n = A.shape
    piv, r = [], 0
    for c in range(n):
        p = next((i for i in range(r, m) if A[i,c]), None)
        if p is None: continue
        A[[r,p]] = A[[p,r]]; piv.append(c)
        for i in range(m):
            if i != r and A[i,c]: A[i] ^= A[r]
        r += 1
    free = [c for c in range(n) if c not in piv]
    B = []
    for f in free:
        v = np.zeros(n, dtype=np.uint8); v[f] = 1
        for idx, p in enumerate(piv):
            if A[idx, f]: v[p] ^= 1
        B.append(v)
    return np.asarray(B, dtype=np.uint8)

def solve_kx63(G, c):
    A = np.concatenate([G.T.copy() & 1, c.reshape(-1,1)], 1)
    n, k1 = A.shape; k = k1-1; row = 0; piv = [-1]*k
    for col in range(k):
        p = next((i for i in range(row, n) if A[i,col]), None)
        if p is None: continue
        A[[row,p]] = A[[p,row]]
        for i in range(n):
            if i != row and A[i,col]: A[i] ^= A[row]
        piv[col] = row; row += 1
    x = np.zeros(k, dtype=np.uint8)
    for col in range(k-1, -1, -1):
        r = piv[col]
        if r == -1: continue
        val = A[r, -1]
        for j in range(col+1, k):
            val ^= A[r,j] & x[j]
        x[col] = val
    return x

def bits(h):
    return np.array(list(map(int, bin(int(h,16))[2:].rjust(len(h)*4,'0'))),
                    dtype=np.uint8)

def to_bytes(bs):
    return bytes(int(''.join(map(str, bs[i:i+8])),2)
                 for i in range(0,len(bs),8))

if len(sys.argv) != 3:
    log.error(f"usage: {sys.argv[0]} alice_pub.npy <cipher hex | file>")
G = np.load(sys.argv[1]).astype(np.uint8)
with open(sys.argv[2]) as f if os.path.isfile(sys.argv[2]) else \
     open(os.devnull) as f: pass
raw = open(sys.argv[2]).read() if os.path.isfile(sys.argv[2]) else sys.argv[2]
cipher_hex = ''.join(re.findall(r'[0-9a-fA-F]', raw)).lower()
c_bits = bits(cipher_hex)

H = nullspace(G)

# 0-62 bit bf
for sh in range(63):
    arr = c_bits[sh:]
    pad = (-len(arr)) % 63
    arr = np.concatenate([arr, np.zeros(pad, dtype=np.uint8)])
    k, n, blocks = 57, 63, len(arr)//63
    m_bits = []
    ok = True
    for i in range(blocks):
        c = arr[i*n:(i+1)*n].copy()
        s = (H @ c) & 1
        if s.any():
            pos = next((j for j in range(n)
                        if np.array_equal(H[:,j], s)), None)
            if pos is None: ok=False; break
            c[pos] ^= 1
            if (H @ c).any(): ok=False; break
        m_bits.extend(solve_kx63(G, c))
    if not ok or 1 not in m_bits: continue
    cut = len(m_bits) - 1 - m_bits[::-1].index(1)    # sentinel '1'
    if any(m_bits[cut+1:]): continue
    plain_bits = m_bits[:cut]
    if len(plain_bits)%8: continue
    pt = to_bytes(plain_bits)
    # printable
    if all(9<=b<128 for b in pt):
        print(pt.decode())
        break

 

 

def nullspace(A):
    A = A.copy() & 1 -> GF(2)
    ... -> gaussian elimination
    return np.asarray(B, np.uint8) -> ( n - k ) x n == 6 × 63

McEliece에선 비밀키가 (S, perm)이지만, Hamming + t = 1 환경에서는 ker(G_Pub)으로 복호 가능

pivot, free variable로 기저 벡터 생성 -> H

 

def solve_kx63(G, c): -> G^t * m = c ( n x k ) x ( k ) = ( n )

해밍코드는 c = M x G 관계가 유지됨

G^T를 augment 하여 gaussian elimination -> m(57bit) recover

 

 

 

 

$ python3 ex.py alice_pub.npy output.txt
SAS{y0u_d0nt_r3ally_n33d_S_perm_t0_d3c0d3_Mc_3l1ec3_w1th_H4mm1ng_c0d3s}