TinyNTRU

解题思路

将公钥关系变形：

构造 NTRU 格：$$\begin{bmatrix} qI & 0\ H & I \end{bmatrix}$$

其中 (H) 为由多项式 (h) 构造的循环矩阵。

真实私钥对应格中的短向量：(f,g)

因此使用 LLL/BKZ 约减恢复短向量。

解题步骤

  1. 读取题目给出的公钥参数。
  2. 根据 (h) 构造 NTRU 格。
  3. 使用 LLL 进行格基约减。
  4. 从短向量中筛选满足：$$f_h \equiv g \pmod q$$

的候选。 5. 利用恢复出的私钥解密密文。 6. 得到 flag。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
from ast import literal_eval
from pathlib import Path
import re

N = 127
p = 3
q = 12289
chunk_bytes = 24


def trim(poly, n):
    return (poly + [0] * n)[:n]


def mod_center(x, modulus):
    x %= modulus
    if x > modulus // 2:
        x -= modulus
    return x


def center_lift(poly, modulus):
    return [mod_center(x, modulus) for x in poly]


def poly_add(a, b, n, modulus=None):
    a = trim(a, n)
    b = trim(b, n)
    out = [a[i] + b[i] for i in range(n)]
    if modulus is not None:
        out = [x % modulus for x in out]
    return out


def poly_mul(a, b, n, modulus=None):
    a = trim(a, n)
    b = trim(b, n)
    out = [0] * n
    for i, ai in enumerate(a):
        if ai == 0:
            continue
        for j, bj in enumerate(b):
            if bj:
                out[(i + j) % n] += ai * bj
    if modulus is not None:
        out = [x % modulus for x in out]
    return out


def decrypt(ciphertext, f):
    lifted = center_lift(poly_mul(f, ciphertext, N, q), q)
    return [x % p for x in lifted]


def poly_blocks_to_bytes(blocks, chunk_bytes):
    raw = bytearray()
    for block in blocks:
        value = 0
        for coeff in reversed(block):
            value = value * 3 + (coeff % 3)
        raw.extend(value.to_bytes(chunk_bytes, "little"))
    size = int.from_bytes(raw[:2], "big")
    return bytes(raw[2:2 + size])


# 读取公钥和密文
pub_text = Path("public_key.txt").read_text()
out_text = Path("output.txt").read_text()

h = literal_eval(re.search(r"h = (\[.*\])", pub_text).group(1))
ciphertexts = literal_eval(re.search(r"ciphertexts = (\[.*\])", out_text).group(1))

# 构造 NTRU 格
B = Matrix(ZZ, 2 * N, 2 * N)

for i in range(N):
    B[i, i] = q

for i in range(N):
    for j in range(N):
        B[N + i, j] = h[(j - i) % N]
    B[N + i, N + i] = 1

# LLL 规约
L = B.LLL(delta=0.99)

f = None
candidate_g = None

for row in L.rows():
    vec = [int(x) for x in row]
    a = vec[:N]
    b = vec[N:]

    ones = [i for i, x in enumerate(b) if abs(x) == 1]
    threes = [i for i, x in enumerate(b) if abs(x) == 3]

    # f 的形态：唯一 ±1，加上 7 个 ±3
    if len(ones) == 1 and len(threes) == 7:
        idx = ones[0]
        s = b[idx]

        # 调整符号并旋转，使得 f[0] = 1
        f_try = [s * b[(j + idx) % N] for j in range(N)]
        g_try = [s * a[(j + idx) % N] for j in range(N)]

        # 验证 f*h == g mod q
        if poly_mul(f_try, h, N, q) == [x % q for x in g_try]:
            f = f_try
            candidate_g = g_try
            break

if f is None:
    raise ValueError("failed to recover private key")

print("[+] recovered f nonzero:")
print([(i, x) for i, x in enumerate(f) if x])
print("[+] recovered g nonzero:")
print([(i, x) for i, x in enumerate(candidate_g) if x])
print("[+] verify f*h == g mod q:", poly_mul(f, h, N, q) == [x % q for x in candidate_g])

blocks = [decrypt(c, f) for c in ciphertexts]
flag = poly_blocks_to_bytes(blocks, chunk_bytes)
print("[+] flag:", flag.decode())

bea9f3dc926de084b0afb048feca908f.png

Cold Forge

思路

  1. FROST nonce 泄露恢复 share

FROST 签名份额满足：$$z_i=k_i+c\lambda_i s_i \pmod q$$

其中：

  • $s_i$ 为 signer 私钥 share
  • $\lambda_i$ 为拉格朗日系数
  • c 为 challenge
  • $k_i$ 为 nonce

泄露信息：$$k_i=(nonce_msb_i<<104)+\epsilon_i$$

代入：$$z_i-(nonce_msb_i<<104)=c\lambda_i s_i+\epsilon_i\pmod q$$

令：$$a_i=c\lambda_i$$ $$b_i=z_i-(nonce_msb_i<<104$$

得到：$$b_i=a_i s_i+\epsilon_i\pmod q$$

因为：$$|\epsilon_i|<2^{105}$$

这是 Hidden Number Problem，利用 LLL + Babai 格攻击恢复私钥 share。

  1. LLL 恢复结果

  2. 合成阈值私钥

拉格朗日系数：

$$\lambda_1=2$$

$$\lambda_2=-1$$

FROST 私钥：$$sk=\lambda_1share_1+\lambda_2share_2\pmod q$$

计算公钥与题目 group_public 一致。

  1. 重建 BIP340 签名

使用恢复出的私钥，对消息生成确定性 BIP340 签名：

  1. ChaCha20-Poly1305 解密

密钥派生：$$key=SHA256(b”cold-forge/release/v1”||signature)$$

使用 sealed_release.json 中 nonce、aad、ciphertext 解密：

1
flag{bd9b026e-b58e-416c-bf8f-d815573c35a6}

38aee816cb6d330e6e4f686932ba5179.png

Invalid Echo

思路

题目实现 ECDH：Q=dG

$共享密钥：S=dP，然后：key=SHA256(S_x||S_y)$

$但是服务器接收点时未检查：P\in E，导致可以提交非法曲线点。$

漏洞利用：

目标曲线：$E^2=x^3+7$

构造非法曲线：$E_c^2=x^3+c，寻找小阶点：ord(P)=r，则：dP=(d\bmod r)P$

$服务器 oracle 返回已知明文：m，枚举：k\in[0,r-1]，匹配 AES：k=d\bmod r$

$恢复私钥得到：d\equiv a_i\pmod {r_i}，使用 CRT：d=CRT(a_i,r_i)，恢复服务器私钥。$

$计算：S=dB_{pub}，得到：key=SHA256(S_x||S_y)，AES-CBC 解密得到 flag。$

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
import base64
import hashlib
import json
import sys
import tempfile
import zipfile
from decimal import Decimal, ROUND_HALF_EVEN, getcontext
from pathlib import Path

from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305
from sympy import Matrix

P_FIELD = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
GX = 55066263022277343669578718895168534326250603453777594175500187360389116729240
GY = 32670510020758816978083085130507043184471273380659243275938904335757337482424
G = (GX, GY)

getcontext().prec = 220

def i2b32(x):
    return int(x).to_bytes(32, "big")

def tagged_hash(tag, data):
    h = hashlib.sha256(tag.encode()).digest()
    return hashlib.sha256(h + h + data).digest()

def inv_mod(x, m):
    return pow(x % m, -1, m)

def point_add(A, B):
    if A is None:
        return B
    if B is None:
        return A

    x1, y1 = A
    x2, y2 = B

    if x1 == x2 and (y1 + y2) % P_FIELD == 0:
        return None

    if A == B:
        k = (3 * x1 * x1) * inv_mod(2 * y1, P_FIELD) % P_FIELD
    else:
        k = (y2 - y1) * inv_mod(x2 - x1, P_FIELD) % P_FIELD

    x3 = (k * k - x1 - x2) % P_FIELD
    y3 = (k * (x1 - x3) - y1) % P_FIELD
    return x3, y3

def point_mul(k, point=G):
    k %= N
    R = None
    Q = point

    while k:
        if k & 1:
            R = point_add(R, Q)
        Q = point_add(Q, Q)
        k >>= 1

    return R

def is_even_y(P):
    return P[1] % 2 == 0

def bip340_sign_deterministic(msg, sk):

    P = point_mul(sk)
    d = sk if is_even_y(P) else N - sk
    px = i2b32(P[0])

    aux = b"\x00" * 32
    t = bytes(a ^ b for a, b in zip(i2b32(d), tagged_hash("BIP0340/aux", aux)))

    k0 = int.from_bytes(tagged_hash("BIP0340/nonce", t + px + msg), "big") % N
    R = point_mul(k0)

    k = k0 if is_even_y(R) else N - k0
    rx = i2b32(R[0])

    e = int.from_bytes(tagged_hash("BIP0340/challenge", rx + px + msg), "big") % N
    s = (k + e * d) % N

    return rx + i2b32(s)

def centered_mod(x, q):
    x %= q
    return x if x <= q // 2 else x - q

def gram_schmidt_decimal(B):
    n = len(B)
    m = len(B[0])

    B_star = [[Decimal(0) for _ in range(m)] for _ in range(n)]
    norm = [Decimal(0) for _ in range(n)]

    for i in range(n):
        v = [Decimal(x) for x in B[i]]

        for j in range(i):
            if norm[j] == 0:
                continue

            dot = sum(Decimal(B[i][k]) * B_star[j][k] for k in range(m))
            mu = dot / norm[j]

            for k in range(m):
                v[k] -= mu * B_star[j][k]

        B_star[i] = v
        norm[i] = sum(x * x for x in v)

    return B_star, norm

def babai_closest_vector(reduced_basis, target):

    n = len(reduced_basis)
    m = len(reduced_basis[0])

    B_star, norm = gram_schmidt_decimal(reduced_basis)
    y = [Decimal(x) for x in target]

    for i in reversed(range(n)):
        if norm[i] == 0:
            continue

        c = sum(y[k] * B_star[i][k] for k in range(m)) / norm[i]
        ci = int(c.to_integral_value(rounding=ROUND_HALF_EVEN))

        if ci:
            for k in range(m):
                y[k] -= Decimal(ci) * Decimal(reduced_basis[i][k])

    closest = [target[k] - int(y[k]) for k in range(m)]
    return closest

def recover_share_for_signer(transcripts, signer_id, lagrange, q, low_bits, drift):

    rows = [t for t in transcripts if int(t["signer"]) == signer_id]

    a = []
    b = []

    for t in rows:
        c = int(t["challenge"], 16)
        z = int(t["z"], 16)
        nonce_msb = int(t["nonce_msb"], 16)

        K = nonce_msb << low_bits

        a_j = c * lagrange % q
        b_j = (z - K) % q

        a.append(a_j)
        b.append(b_j)

    m = len(a)

    inv_a0 = inv_mod(a[0], q)
    u = [1] + [(a[i] * inv_a0) % q for i in range(1, m)]

    basis = [u]
    for i in range(1, m):
        row = [0] * m
        row[i] = q
        basis.append(row)

    print(f"[*] signer {signer_id}: LLL on {m}-dim lattice")

    reduced = Matrix(basis).lll(delta=0.99)
    reduced_basis = [[int(reduced[i, j]) for j in range(m)] for i in range(m)]

    closest = babai_closest_vector(reduced_basis, b)

    # closest ≡ share_i * a mod q
    # 所以 share_i = closest[0] * inv(a[0]) mod q
    share = closest[0] * inv_a0 % q

    residuals = [centered_mod(b_j - a_j * share, q) for a_j, b_j in zip(a, b)]
    max_abs = max(abs(x) for x in residuals)
    bound = (drift + 1) * (1 << low_bits)

    print(f"[+] signer {signer_id} share = {share:064x}")
    print(f"    max |eps| = {max_abs} ({max_abs.bit_length()} bits)")
    print(f"    bound     = {bound} ({bound.bit_length()} bits)")

    if max_abs >= bound:
        raise ValueError("share recovery failed")

    return share

def load_challenge(path):
    path = Path(path)

    if path.is_file() and path.suffix.lower() == ".zip":
        tmp = tempfile.TemporaryDirectory()
        with zipfile.ZipFile(path, "r") as zf:
            zf.extractall(tmp.name)
        root = Path(tmp.name)
    else:
        tmp = None
        root = path

    frost_file = list(root.rglob("frost_telemetry.json"))[0]
    sealed_file = list(root.rglob("sealed_release.json"))[0]

    frost = json.loads(frost_file.read_text())
    sealed = json.loads(sealed_file.read_text())

    return frost, sealed, tmp

def main():
    if len(sys.argv) != 2:
        print(f"Usage: python3 {sys.argv[0]} <cold_forge.zip | cold_forge_dir>")
        sys.exit(1)

    frost, sealed, tmp = load_challenge(sys.argv[1])

    q = int(frost["group_order"], 16)
    low_bits = int(frost["leak_model"]["discarded_low_bits"])
    drift = int(frost["leak_model"]["maximum_bucket_drift"])

    participants = [int(x) for x in frost["participants"]]
    lambdas = {int(k): int(v, 16) for k, v in frost["lagrange_coefficients"].items()}

    shares = {}

    for signer_id in participants:
        shares[signer_id] = recover_share_for_signer(
            frost["transcripts"],
            signer_id,
            lambdas[signer_id],
            q,
            low_bits,
            drift,
        )

    sk = sum(lambdas[i] * shares[i] for i in participants) % q

    print(f"[+] group secret sk = {sk:064x}")

    pub = point_mul(sk)

    want_x = int(frost["group_public"]["x"], 16)
    want_y = int(frost["group_public"]["y"], 16)

    assert pub == (want_x, want_y)
    print("[+] public key check passed")

    msg = bytes.fromhex(frost["message_hex"])

    sig = bip340_sign_deterministic(msg, sk)
    print(f"[+] deterministic BIP340 signature = {sig.hex()}")

    key = hashlib.sha256(b"cold-forge/release/v1" + sig).digest()
    print(f"[+] release key = {key.hex()}")

    nonce = base64.b64decode(sealed["nonce"])
    aad = base64.b64decode(sealed["aad"])
    ciphertext_and_tag = base64.b64decode(sealed["ciphertext"])

    plaintext = ChaCha20Poly1305(key).decrypt(nonce, ciphertext_and_tag, aad)

    print("[+] plaintext =", plaintext.decode())

    if tmp is not None:
        tmp.cleanup()

if __name__ == "__main__":
    main()

1903088b073df117938407c81384357d.png

slashKEM

解题思路

1.功耗侧信道恢复部分密钥

题目泄露模型：

$$L(s,u)=HW(Mont(su)\oplus Mont(7u+0x1234))$$

其中： s为 secret coefficient u为公开输入 HW为汉明重量

由于：$$s\in{-2,-1,0,1,2}$$

因此枚举所有可能值，通过 CPA 计算相关系数$$\rho(X,Y)= \frac{Cov(X,Y)} {\sqrt{Var(X)Var(Y)}}$$

选择相关性最高的猜测，即可恢复大部分 secret coefficient。

注意 trace 中 coefficient 顺序经过 bit-reversal，需要根据：

$$order=(0,64,32,96,16,\cdots)$$还原真实位置。

2、LWE 格攻击恢复剩余系数

ML-KEM 公钥关系：$$t=As+e \pmod q$$

其中：$$q=3329$$

并且误差：$$e_i\in{-1,0,1}$$

CPA 得到部分：

$$s=s_{known}+s_{unknown}$$

$$由于误差很小，将问题转化为格上的 CVP。 构造 lattice：$$

$$L= \begin{bmatrix} qI&0\ A_{unknown}^T&I \end{bmatrix}$$

恢复剩余 secret coefficient。

3.密钥派生

恢复完整 secret polynomial 后：

$$K=SHA256(encode(s))$$

得到 AES-GCM 解密密钥。

进行 AES-GCM 解密：

$$flag=AES_GCM^{-1}(K,nonce,ciphertext,tag)$$

得到：

1
flag{708d7b97-0b8d-4d99-aa1a-b23d3b13cc51}

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# solve.py
from sage.all import *
import numpy as np
from hashlib import sha256
from Crypto.Cipher import AES
import json

q = 3329
N = 64

with open("output.json") as f:
    data=json.load(f)

traces=np.load("traces.npz")["traces"]
us=np.load("traces.npz")["u_samples"]

def hw(x):
    return bin(x&0xffff).count("1")
def leak(s,u):
    return hw((s*u)%q ^ ((7*u+0x1234)%q))


def corr(x,y):
    x=x-np.mean(x)
    y=y-np.mean(y)
    return abs(np.dot(x,y)/
        np.sqrt(np.dot(x,x)*np.dot(y,y)))


  b=f"{i:07b}"[::-1]
    order.append(int(b,2))


for pos,idx in enumerate(order):

    best=(-1,0)

    for s in [-2,-1,0,1,2]:

        hyp=[
            leak(
                s,
                int(u[idx])
            )
            for u in us
        ]

        c=corr(
            hyp,
            traces[:,96+pos]
        )

        if c>best[0]:
            best=(c,s)

    if best[0]>0.5:
        secret[idx]=best[1]

print("[+] CPA recovered")


A=data["A"]
t=vector(
    ZZ,
    sum(data["t"],[])
)


def column(i):

    poly=i//N
    pos=i%N

    ret=[]

    for row in range(2):

        v=[0]*N
        v[pos]=1

        ret+=list(
            vector(GF(q),A[row][poly])
            * vector(GF(q),v)
        )

    return vector(ZZ,ret)
known=[i for i in range(128)
       if secret[i]!=None]

unknown=[i for i in range(128)
         if secret[i]==None]
rhs=t
for i in known:
    rhs-=secret[i]*column(i)
M=Matrix(
    ZZ,
    [column(i) for i in unknown]
).transpose()
m=len(unknown)
L=Matrix(
    ZZ,
    128+m,
    128+m
)
for i in range(128):
    L[i,i]=q
for i in range(m):
    for j in range(128):
        L[128+i,j]=M[j,i]

    L[128+i,128+i]=1
L=L.LLL()
v=L.closest_vector(
    vector(ZZ,list(rhs)+[0]*m)
)
for i,x in zip(unknown,v[-m:]):
    secret[i]=int(x)
print("[+] secret:")
print(secret)
key=sha256(
    bytes([x+2 for x in secret])
).digest()
cipher=AES.new(
    key,
    AES.MODE_GCM,
    nonce=bytes.fromhex(data["nonce"])
)
flag=cipher.decrypt_and_verify(
    bytes.fromhex(data["ciphertext"]),
    bytes.fromhex(data["tag"])
)
print(flag.decode())
#flag{708d7b97-0b8d-4d99-aa1a-b23d3b13cc51}