SSG Writeup

Mother#

개요#

Mother는 GF(256) 위에서 동작하는 Oil-Vinegar 계열 서명 문제입니다. 문제 코드는 공개키를 출력하고, 타깃이 아닌 메시지에 대한 서명을 만들어 주며, 최종 제출값을 검증하는 구조입니다.

문제의 조건은 다음과 같습니다.

카테고리: crypto
목표: 서명 오라클이 직접 서명해 주지 않는 메시지 b"Vinegar is not an orphan"의 유효한 서명을 만들어 제출합니다.

풀이에서 먼저 확인할 부분은 vinegar 변수입니다. 서명 과정에서 일부 vinegar 좌표가 모든 서명에서 고정되므로, 서명들이 놓이는 affine subspace를 복구할 수 있습니다. 그 뒤에는 이 공간에서 oil space를 찾아 타깃 메시지를 직접 서명합니다.

문제 분석#

제공된 Sage 코드에서 파라미터는 다음과 같습니다.

1
FF = GF(256)
2

3
M = 32
4
V = 46
5
N = M + V
6
K = 30
7
SIGN_LIMIT = 59
8
FLAG = os.environ.get("FLAG", "HS{fake_flag}")

여기서 전체 변수 수는 78, 방정식 수는 32, vinegar 변수 수는 46입니다. 서명할 때는 vinegar를 먼저 고르고, 남은 oil 변수 32개를 선형 방정식으로 구합니다.

central polynomial 생성 부분을 보면 oil-oil 항이 없다는 점도 확인할 수 있습니다.

1
def random_central_polynomial(self):
2
    F = Matrix(FF, self.n)
3
    for i in range(self.v):
4
        for j in range(i, self.v):
5
            F[i, j] = FF.random_element()
6
        for j in range(self.v, self.n):
7
            F[i, j] = FF.random_element()
8
    return F

이 함수는 행 인덱스 i가 self.v보다 작은 경우만 계수를 채웁니다. 즉 숨겨진 좌표계에서는 oil-oil quadratic term이 없습니다. 나중에 oil space를 복구하면 P(o)=0 성질을 이용해 서명 문제를 선형 문제로 바꿀 수 있습니다.

vinegar 샘플링 부분도 중요합니다.

1
self.mother = random_vector(FF, self.v)
2

3
random.seed(str(self.mother[:self.v - k]))

1
def sample_vinegar(self):
2
    vinegar = list(self.mother)
3
    for i in range(self.v - self.k, self.v):
4
        vinegar[i] = FF.from_integer(random.randrange(256))
5
    return vector(FF, vinegar)

mother 전체를 매번 새로 생성하지 않는다는 점이 중요합니다. V=46, K=30이므로 앞의 16개 vinegar 좌표는 그대로 남고, 뒤의 30개 vinegar 좌표만 PRNG로 갱신됩니다.

서명 함수에서는 이 vinegar를 고른 뒤 oil 변수만 선형 방정식으로 구합니다.

1
def sign(self, msg):
2
    H = self.Si * self.hash(msg)
3

4
    while True:
5
        vinegar = self.sample_vinegar()
6
        x0 = vector(FF, list(vinegar) + [0] * self.m)
7
        mat = Matrix(FF, [x0 * F for F in self.F])
8
        A = mat[:, self.v:]
9

10
        if A.rank() != self.m:
11
            continue
12

13
        oil = A.solve_right(H - mat * x0)
14
        x = vector(FF, list(vinegar) + list(oil))
15
        sig = self.vector_to_bytes(self.Ti * x)
16

17
        assert self.verify(msg, sig)
18
        return sig

반환되는 서명은 공개 좌표계의 벡터입니다. 하지만 숨겨진 좌표계로 보면 앞 16개의 vinegar 좌표가 모든 오라클 서명에서 같습니다. 따라서 오라클 서명들은 전체 78차원 공간에 흩어지지 않고, 특정 affine subspace 위에 놓입니다.

좌표계를 먼저 정리해두면 이후 계산이 더 명확해집니다. 숨겨진 좌표계의 벡터를 x, 서명 함수가 반환하는 공개 서명 벡터를 s라고 하겠습니다. 코드에서 Ti는 T의 역행렬이므로 서명 반환값은 다음 관계를 갖습니다.

1
s = T^-1 x
2
x = T s

즉 숨겨진 좌표계에서 앞 16개의 vinegar 좌표가 고정된다는 성질은, 공개 좌표계에서는 T^-1로 옮겨진 방향공간으로 나타납니다. 아래에서는 코드 내부의 H = self.Si * self.hash(msg)와 이름이 충돌하지 않도록, 이 62차원 방향공간을 W라고 부르겠습니다.

제출 대상 메시지는 직접 서명할 수 없도록 막혀 있습니다.

1
if msg == b"Vinegar is not an orphan":
2
    print("right!")
3
    continue

따라서 오라클에서 타깃 메시지의 서명을 직접 받는 방식은 사용할 수 없습니다.

핵심 아이디어#

서명 차이를 보면 고정된 좌표가 사라집니다. GF(256)은 characteristic 2이므로 subtraction과 addition이 같습니다.

59개의 오라클 서명을 s_0, s_1, ..., s_58이라고 두고, 차이 공간 D를 다음처럼 잡습니다.

1
D = span(s_i + s_0), 1 <= i <= 58

실제로 수집한 서명에서는 rank(D)=58이 나왔습니다.

숨겨진 좌표계에서 서명 방향으로 움직일 수 있는 변수는 두 종류입니다.

갱신되는 vinegar 좌표 30개
oil 좌표 32개

따라서 실제 서명 방향 공간 W의 차원은 62입니다.

1
W = T^-1({0}^16 x F_256^30 x F_256^32)
2
dim(W) = 30 + 32 = 62

하지만 수집 가능한 차이 벡터는 58개뿐이므로 D만으로는 W를 전부 알 수 없습니다. 부족한 부분은 4차원입니다.

1
D <= W
2
dim(D) = 58
3
dim(W) = 62

이후 목표는 네 단계로 정리됩니다.

D를 포함하는 62차원 공간 W를 복구합니다.
W 안에서 공개 좌표계의 oil space 일부를 찾습니다.
oil vector 일부를 이용해 전체 oil space를 복구합니다.
타깃 메시지의 서명을 선형 방정식으로 만듭니다.

풀이 과정#

Step 1. 공개키와 서명 59개 수집#

프로그램을 실행하면 n, m, v, k, pubkey가 출력됩니다. 이후 1. sign 메뉴에서 타깃이 아닌 메시지의 서명을 받을 수 있습니다.

공개키와 서명은 같은 실행 세션에서 수집했습니다. 여러 실행 세션의 공개키가 같다고 가정할 수 없으므로, 한 번 받은 공개키에는 같은 세션에서 받은 서명만 대응시켰습니다.

1
items = []
2
for i in range(59):
3
    msg = f"msg-{i}".encode()
4
    sig = sign_from_oracle(msg)
5
    if not verify(pub, msg, sig):
6
        raise RuntimeError(f"signature {i} verification failed")
7
    items.append({"msg": msg.hex(), "sig": sig.hex()})

수집한 서명으로 차이 공간 D를 만듭니다.

1
def build_D_and_Q(sigs):
2
    base = sigs[0]
3
    diffs = [list(s + base) for s in sigs[1:]]
4
    Drows = Matrix(F, diffs).row_space().basis_matrix()
5
    if Drows.nrows() != 58:
6
        raise RuntimeError(f"rank(D)={Drows.nrows()}, need 58")
7
    D = Drows.transpose()

s + base는 여기서 서명 차이입니다. characteristic 2에서는 s - base와 s + base가 같습니다.

Step 2. polar form 구성#

공개 quadratic matrix P_i에서 polar form B_i를 만듭니다.

1
def build_polar(Ps):
2
    Bs = []
3
    for P in Ps:
4
        B = P + P.transpose()
5
        for i in range(N):
6
            B[i, i] = F(0)
7
        Bs.append(B)
8
    return Bs

이 과정으로 quadratic form P(x)의 bilinear part를 얻습니다.

1
B_i(x, y) = P_i(x + y) + P_i(x) + P_i(y)

이후 분석은 공개 좌표계에서 B_i들의 무작위 선형결합을 사용합니다.

Step 3. `D`를 보완하는 4차원 공간 복구#

D의 complement Q를 임의로 잡아 전체 공간을 나눕니다.

1
F_256^78 = D direct_sum Q
2
dim(D) = 58
3
dim(Q) = 20

실제 방향 공간 W는 D를 포함하고 차원이 62입니다. 따라서 Q 안의 어떤 4차원 부분공간 E로 W를 표현할 수 있습니다.

1
W = D direct_sum E
2
dim(E) = 4

풀이 코드에서는 표준기저를 하나씩 붙여 rank가 증가하는 열만 골랐습니다.

1
full = D
2
qcols = []
3
rank = full.rank()
4
for i in range(N):
5
    col = Matrix(F, N, 1, list(standard_col(i)))
6
    cand = full.augment(col)
7
    new_rank = cand.rank()
8
    if new_rank > rank:
9
        qcols.append(standard_col(i))
10
        full = cand
11
        rank = new_rank
12
        if len(qcols) == 20:
13
            break

남은 일은 D에 붙여 W를 완성할 4차원 공간 E를 복구하는 것입니다. 여기서는 W 위로 제한한 polar form의 rank 제한을 사용합니다.

숨겨진 좌표계에서 W는 active vinegar 30개와 oil 32개로 구성됩니다. oil-oil 항이 없으므로 무작위 polar form B_lambda를 W에 제한하면 다음과 같은 블록 형태가 됩니다.

1
[ A    C ]
2
[ C^T  0 ]

여기서 C는 30 x 32 행렬입니다. 따라서 B_lambda를 W에 제한한 행렬의 rank는 최대 60입니다.

D와 Q의 직합 기준에서 같은 form을 블록으로 쓰면 다음과 같습니다.

1
[ A    C ]
2
[ C^T  G ]

B_lambda를 D에 제한한 부분이 invertible인 경우 Schur complement를 계산할 수 있습니다.

1
S = G + C^T A^-1 C

W가 D와 E의 직합이므로, 위 rank 제한은 Schur complement S를 E에 제한했을 때의 조건으로 내려옵니다.

1
rank(S restricted to E) <= 2

E는 4차원이고 S는 alternating form입니다. 위 조건은 S를 E에 제한한 form의 Pfaffian이 0이라는 조건과 같습니다.

E의 기저를 e1, e2, e3, e4라고 두겠습니다. S를 이 기저 위에 제한하면 4 x 4 alternating matrix가 되고, 이 행렬의 Pfaffian은 S(ea, eb)들의 곱의 합으로 표현됩니다. 이 값을 Q 좌표계에서 전개하면 계수는 S에서 계산되고, 미지수는 E의 4 x 4 minor들입니다. 이 minor들이 바로 Plucker 좌표입니다. 따라서 무작위 B_lambda 하나는 Plucker 좌표들에 대한 선형 방정식 하나를 줍니다.

Q의 좌표를 0..19라고 하면 Plucker 좌표는 4845개입니다.

1
binom(20, 4) = 4845

무작위 B_lambda 하나마다 길이 4845의 행 하나를 만들 수 있습니다.

1
def plucker_row(S):
2
    row = []
3
    for a, b, c, d in I4:
4
        row.append(
5
            S[a, b] * S[c, d]
6
            + S[a, c] * S[b, d]
7
            + S[a, d] * S[b, c]
8
        )
9
    return row

4차원 alternating matrix의 Pfaffian 공식이 그대로 행의 계수가 됩니다. characteristic 2이므로 부호는 따로 처리하지 않습니다.

풀이 코드에서는 이 행을 충분히 쌓은 뒤 right_kernel이 1차원이 되는지 확인했습니다.

1
def recover_E(Bs, D, Q, initial_rows=4500, check_every=64, max_rows=5600):
2
    rows = []
3
    while len(rows) < max_rows:
4
        Mat = random_polar_combo(Bs)
5
        A = D.transpose() * Mat * D
6
        if A.rank() != 58:
7
            continue
8

9
        C = D.transpose() * Mat * Q
10
        G = Q.transpose() * Mat * Q
11
        X = A.solve_right(C)
12
        S = G + C.transpose() * X
13

14
        rows.append(plucker_row(S))
15

16
        if len(rows) >= initial_rows and len(rows) % check_every == 0:
17
            R = Matrix(F, rows)
18
            K = R.right_kernel()
19
            if K.dimension() == 1:
20
                p = K.basis()[0]
21
                Ecoords = recover_E_from_plucker(p)
22
                E = Q * Ecoords
23
                if E.rank() != 4:
24
                    raise RuntimeError(f"rank(E)={E.rank()}, need 4")
25
                return E

kernel 벡터 p는 E의 Plucker 벡터입니다. 이를 실제 4차원 부분공간으로 되돌릴 때는 다음 성질을 사용합니다.

1
x in E  <=>  x wedge p = 0

p가 4차원 부분공간 E에서 온 decomposable Plucker 벡터라면, 어떤 벡터 x가 E에 속할 때만 x를 p에 wedge해도 차원이 늘어나지 않습니다. 따라서 x wedge p = 0이 x in E의 조건이 됩니다. 일반적인 exterior algebra에서는 항마다 부호가 붙지만, 여기서는 GF(2^8) 위에서 계산하므로 -와 +가 같아 부호를 따로 처리하지 않아도 됩니다.

구현에서는 모든 5-tuple J에 대해 이 조건에서 나오는 선형식을 모읍니다.

1
def recover_E_from_plucker(p):
2
    rows = []
3
    for J in I5:
4
        row = [ZERO] * 20
5
        for j in J:
6
            sub = tuple(x for x in J if x != j)
7
            row[j] += p[IDX4[sub]]
8
        rows.append(row)
9

10
    M_wedge = Matrix(F, rows)
11
    K = M_wedge.right_kernel()
12
    if K.dimension() != 4:
13
        raise RuntimeError(f"dim(wedge kernel)={K.dimension()}, need 4")
14
    return K.basis_matrix().transpose()

E를 얻고 나면 W = D.augment(E)로 전체 방향 공간을 복구할 수 있습니다. 실제 실행에서는 rank(W)=62를 확인했습니다.

Step 4. `W` 위 radical에서 oil plane 찾기#

W를 복구한 뒤에는 무작위 polar form을 W에 제한하고 radical을 구합니다.

1
def recover_oil_plane(Ps, Bs, W, max_tries=512):
2
    for t in range(max_tries):
3
        Mat = random_polar_combo(Bs)
4
        RW = W.transpose() * Mat * W
5
        K = RW.right_kernel()
6
        if K.dimension() != 2:
7
            continue
8

9
        UV = W * K.basis_matrix().transpose()
10
        u = UV.column(0)
11
        v = UV.column(1)
12
        if all(public_eval(Ps, z).is_zero() for z in (u, v)):
13
            return [u, v]
14

15
    raise RuntimeError("failed to recover a verified oil plane")

여기서는 radical 차원이 2인 경우만 사용합니다. 얻은 두 벡터가 실제로 P(z)=0을 만족하는지도 공개키로 검증합니다. 검증이 실패하면 다른 무작위 polar form을 선택합니다.

radical이 oil 방향으로 나오는 이유도 앞의 블록 형태에서 확인할 수 있습니다. W를 active vinegar 30차원과 oil 32차원으로 나누면 무작위 polar form은 [A C; C^T 0] 형태입니다. 일반적으로 C의 rank가 30이므로 radical 조건에서 active vinegar 성분은 사라지고, 남는 조건은 C o = 0을 만족하는 oil 방향입니다. C가 30 x 32이므로 보통 이 kernel은 2차원이고, 이 부분공간이 oil plane으로 나타납니다.

초기에는 이 2차원 oil plane을 MQ나 SAT로 직접 찾는 방식도 시도했지만, 제한 시간 안에서 의미 있는 결과를 얻지 못했습니다. 따라서 먼저 W를 복구한 뒤 radical을 보는 방식으로 우회했습니다.

Step 5. 전체 oil space 복구#

공개 좌표계의 oil vector u, v 두 개를 알면 전체 oil space를 선형대수로 복구할 수 있습니다. oil vector끼리는 oil-oil 항을 만들지 않으므로, oil space의 임의 벡터 x는 다음 조건을 만족합니다.

1
B_i(u, x) = 0
2
B_i(v, x) = 0

이를 모든 i에 대해 모으면 64 x 78 선형시스템이 됩니다.

1
def recover_full_oil(Ps, Bs, oil_plane):
2
    rows = []
3
    for z in oil_plane:
4
        for B in Bs:
5
            rows.append(list(z * B))
6

7
    L = Matrix(F, rows)
8
    K = L.right_kernel()
9
    if K.dimension() != 32:
10
        raise RuntimeError(f"dim(full oil)={K.dimension()}, need 32")
11

12
    Oil = K.basis_matrix()
13
    bad = sum(1 for z in Oil.rows() if not public_eval(Ps, z).is_zero())
14
    if bad:
15
        raise RuntimeError(f"{bad} recovered oil basis vectors fail P(z)=0")
16
    return Oil

실행 결과 dim(full oil)=32가 나왔고, 모든 basis vector가 P(z)=0 검증을 통과했습니다.

Step 6. 타깃 메시지 서명#

전체 oil space를 알고 나면 서명 생성은 일반적인 Oil-Vinegar 서명과 같습니다. 공개 공간에서 oil space의 complement를 하나 잡고, 그 위의 점 x0를 임의로 고릅니다. 그다음 oil 방향 보정값 o를 찾습니다.

quadratic form에 대해 다음 식이 성립합니다.

1
P(x0 + o) = P(x0) + B(x0, o) + P(o)

o가 oil space에 있으면 P(o)=0입니다. 따라서 타깃 hash h에 대해 다음 선형 방정식을 풀면 됩니다.

1
B(x0, o) = h + P(x0)

구현은 다음과 같습니다.

1
def sign_with_oil(Ps, Bs, Oil, target_msg, max_tries=4096):
2
    h = hash_vec(target_msg)
3
    Vc = complement_rows(Oil, N - Oil.nrows())
4
    oil_rows = list(Oil.rows())
5

6
    for t in range(max_tries):
7
        x0 = vector(F, [ZERO] * N)
8
        for row in Vc:
9
            c = rnd()
10
            if c:
11
                x0 += c * row
12

13
        p0 = public_eval(Ps, x0)
14
        L = Matrix(F, M, M)
15
        for i, B in enumerate(Bs):
16
            xb = x0 * B
17
            for j, o in enumerate(oil_rows):
18
                L[i, j] = xb * o
19

20
        if L.rank() != M:
21
            continue
22

23
        coeffs = L.solve_right(h + p0)
24
        sig = vector(F, x0)
25
        for c, row in zip(coeffs, oil_rows):
26
            if c:
27
                sig += c * row
28

29
        if public_eval(Ps, sig) == h:
30
            return sig
31

32
    raise RuntimeError("failed to sign with recovered oil space")

L이 full rank이면 oil coefficient를 한 번의 선형 방정식 풀이로 구할 수 있습니다. 실패하면 다른 x0를 선택해 다시 시도합니다.

Exploit / Solver#

solver는 공개키와 59개의 서명만 있으면 됩니다. 공개키는 출력된 hex 문자열을 78 x 78 행렬 32개로 파싱하고, 서명은 각각 78바이트 hex 문자열을 GF(256) 벡터로 바꿉니다. 정확한 Sage 버전은 확인하지 못했습니다.

풀이 코드는 다음 순서로 구성됩니다.

1
def solve(data, args):
2
    if args.seed is not None:
3
        random.seed(args.seed)
4

5
    Ps = parse_pub(data)
6
    sigs = parse_sigs(data)
7
    target_msg = bytes.fromhex(data.get("target_msg", TARGET.hex()))
8

9
    Bs = build_polar(Ps)
10
    D, Q = build_D_and_Q(sigs)
11

12
    E = recover_E(
13
        Bs,
14
        D,
15
        Q,
16
        initial_rows=args.initial_rows,
17
        check_every=args.check_every,
18
        max_rows=args.max_rows,
19
    )
20
    W = D.augment(E)
21
    w_rank = W.rank()
22
    if w_rank != 62:
23
        raise RuntimeError(f"rank(W)={w_rank}, need 62")
24

25
    oil_plane = recover_oil_plane(Ps, Bs, W)
26
    Oil = recover_full_oil(Ps, Bs, oil_plane)
27

28
    sig = sign_with_oil(Ps, Bs, Oil, target_msg)
29
    return {
30
        "sig": vec_to_hex(sig),
31
        "target_msg": target_msg.hex(),
32
        "rank_D": D.ncols(),
33
        "rank_W": w_rank,
34
        "dim_oil": Oil.nrows(),
35
    }

실행 결과 확인한 값은 다음과 같습니다.

1
rank(D) = 58
2
dim(Q) = 20
3
Plucker kernel dimension = 1
4
rank(W) = 62
5
dim(full oil) = 32
6
target signature verifies

마지막으로 제출 메뉴에 위조 서명을 입력하면 타깃 메시지 검증을 통과합니다.

결과#

제출 결과 flag를 확인했습니다.

1
HS{I_l0v3_m0th3r_6ut_1_h2te_v1n3gar}