2026 磐石行动 Crypto wp

思路

根据题目信息，阈值k=5所以$$deg(f)<5，目标secret=f(0)=a_0$$

由于有两份错误份额故不能直接插值，又$$9=n\geq k+2t=5+4$$满足Berlekamp-Welch 条件

构造错误多项式：$$E(x)=x^2+bx+c \quad 令Q(x)=E(x)f(x) \quad def(Q)<7$$

$$那么Q(x_i)=y_iE(x_i)\Rightarrow Q(x_i)-y_i(x_i^2+bx_i+c)=0$$

9个方程9个未知数可解

解答

from sage.all import *

shares=[
    (
      4,
      "1756507252888966302421944697206841956143152140868019425423436826040417874090358810282666628353861959194519032644153396178974087251656200520090451446037558616"
    ),
    (
      5,
      "291079203062482778164854164602169614214941906034816769921809749669038694270141709535829730588575563957368793945410386647770027583595565500385787765396679943"
    ),
    (
      6,
      "3353657858949220467189251132108794571872371959480001695994095692465794840483860565226874775451906223213941455607156170032589978963502693390308711679147462790"
    ),
    (
      3,
      "3036190474984169590950378504231555599054858759783145166750792797321971974661532479326963124473761720145245595100028856413919438990575098181766312281016449474"
    ),
    (
      2,
      "6194143121566534075891262449799030938599380831596361229544817695037620824633497487483944493077767373997778397971319267160293299864167417885508691584631990890"
    ),
    (
      1,
      "3190833648678294242003969261324345442368829714246140188627248466512581507880823091610739631577934516878443539932340272490275059447848911907619478425588241928"
    ),
    (
      7,
      "4068614300385897042736163548231103545434345847425657360978335306252159948463803163273112788447249335566556829589208573516328678189557514426677386978479001619"
    ),
    (
      8,
      "2524499628636075408730372448736615895921954107928295154192144197934845731982899262196954960370286591718071680967232201013594469797728189493226395106754824275"
    ),
    (
      9,
      "356348046654628493758686606367279817347683022998832017496460398267415288329999382120255439055531110457018951780523102517824504770874348953756247733306681596"
    )
]

p=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
F=GF(p)
points=[(F(x),F(y)) for x,y in shares]
M=[]
Y=[]
for x,y in points:
    row=[]
    for i in range(7):
        row.append(x^i)
    row.append(-y*x)
    row.append(-y)
    M.append(row)
    Y.append(y*x^2)

M=matrix(F,M)
Y=vector(F,Y)
sol=M.solve_right(Y)
q=sol[:7]
b=sol[7]
c=sol[8]
R.<x>=PolynomialRing(F)
Q=sum(q[i]*x^i for i in range(7))
E=x^2+b*x+c
print(E)
f=Q//E
secret=f(0)
print(secret)
flag=int(secret).to_bytes(
    (int(secret).bit_length()+7)//8,
    'big'
)
print(flag)

nonce_again

题目

#!/usr/bin/env python3
import json
import secrets
from pathlib import Path

from Crypto.Cipher import AES

OUTPUT = Path(__file__).with_name("records.json")
AAD = b"telemetry-v1"
PLAINTEXTS = [b"role=user;uid=01", b"role=user;uid=02"]
TARGET = b"admin=true;uid=0"

def encrypt_record(key: bytes, nonce: bytes, plaintext: bytes) -> dict[str, str]:
    cipher = AES.new(key, AES.MODE_GCM, nonce=nonce, mac_len=16)
    cipher.update(AAD)
    ciphertext, tag = cipher.encrypt_and_digest(plaintext)
    return {
        "plaintext": plaintext.hex(),
        "ciphertext": ciphertext.hex(),
        "tag": tag.hex(),
    }

def main() -> None:
    key = secrets.token_bytes(16)
    nonce = secrets.token_bytes(12)

    records = [encrypt_record(key, nonce, plaintext) for plaintext in PLAINTEXTS]
    instance = {
        "nonce": nonce.hex(),
        "aad": AAD.hex(),
        "records": records,
        "target_plaintext": TARGET.hex(),
    }
    OUTPUT.write_text(json.dumps(instance, indent=2) + "\n", encoding="utf-8")

if __name__ == "__main__":
    main()
#!/usr/bin/env python3
import hashlib

R = 0xE1000000000000000000000000000000
IDENTITY = 1 << 127

def gf_mul(x: int, y: int) -> int:

    z = 0
    v = y
    for bit in range(127, -1, -1):
        if (x >> bit) & 1:
            z ^= v
        v = (v >> 1) ^ (R if v & 1 else 0)
    return z

def ghash(h: int, aad: bytes, ciphertext: bytes) -> int:
    def blocks(data):
        padded = data + b"\0" * ((-len(data)) % 16)
        return [int.from_bytes(padded[i:i + 16], "big") for i in range(0, len(padded), 16)]

    value = 0
    for block in blocks(aad) + blocks(ciphertext):
        value = gf_mul(value ^ block, h)
    lengths = ((len(aad) * 8) << 64) | (len(ciphertext) * 8)
    return gf_mul(value ^ lengths, h)

def submission_flag(nonce: bytes, ciphertext: bytes, tag: bytes) -> str:
    return "flag{" + hashlib.sha256(nonce + ciphertext + tag).hexdigest()[:32] + "}"

思路

题目给出的两条消息使用同一个key和nonce进行加密，aad是telemetry-v1，目标明文是admin=true;uid=0 伪造目标管理员消息，而不是恢复AES key

GCM认证标签是：$$T=E_k（J_0)⊕GHASH_H(A,C)$$同一个key+nonce对应的E_k相同

两条消息的AAD相同，对应密文长度也相同，那么：$$T_1⊕T_2=(C_1⊕C_2)\cdot H^2 \Rightarrow H^2=(T_1⊕ T_2)\cdot (C_1⊕C_2)^{-1}$$

那么：$$E_k(J_0)=T_1⊕GHASH_H(A,C_1)$$

然后计算：$$T_{target}=E_K(J_0)⊕GHASH_H(A,C_{target})$$

解答

import json
import hashlib

R = 0xE1000000000000000000000000000000
IDENTITY = 1 << 127
def gf_mul(x: int, y: int) -> int:

    z = 0
    v = y
    for bit in range(127, -1, -1):
        if (x >> bit) & 1:
            z ^= v
        v = (v >> 1) ^ (R if v & 1 else 0)
    return z
def gf_pow(x,e):
    res=IDENTITY
    while e:
        if e&1:
            res=gf_mul(res,x)
        x=gf_mul(x,x)
        e>>=1
    return res

def gf_inv(x):
    return gf_pow(x,IDENTITY-2)
def gf_sqrt(x):
    for i in range(127):
        x=gf_mul(x,x)
    return x

def ghash(h, aad, ciphertext):
    def blocks(data):
        data += b"\0" * ((-len(data)) % 16)
        return [int.from_bytes(data[i:i+16], "big") for i in range(0, len(data), 16)]

    value = 0
    for block in blocks(aad) + blocks(ciphertext):
        value = gf_mul(value ^ block, h)

    lengths = ((len(aad) * 8) << 64) | (len(ciphertext) * 8)
    return gf_mul(value ^ lengths, h)

with open("records.json", "r", encoding="utf-8") as f:
    data = json.load(f)

nonce = bytes.fromhex(data["nonce"])
aad = bytes.fromhex(data["aad"])

r1, r2 = data["records"]
p1 = bytes.fromhex(r1["plaintext"])
c1 = bytes.fromhex(r1["ciphertext"])
t1 = bytes.fromhex(r1["tag"])

p2 = bytes.fromhex(r2["plaintext"])
c2 = bytes.fromhex(r2["ciphertext"])
t2 = bytes.fromhex(r2["tag"])

target_p = bytes.fromhex(data["target_plaintext"])

Cdiff = int.from_bytes(c1, "big") ^ int.from_bytes(c2, "big")
Tdiff = int.from_bytes(t1, "big") ^ int.from_bytes(t2, "big")

H2 = gf_mul(Tdiff, gf_inv(Cdiff))
H = gf_sqrt(H2)

mask = int.from_bytes(t1, "big") ^ ghash(H, aad, c1)
target_c=bytes(x^y^z for x,y,z in zip(c1,p1,target_p))
target_t=(mask^ghash(H,aad,target_c)).to_bytes(16,"big")
flag="flag{" + hashlib.sha256(nonce + target_c + target_t).hexdigest()[:32] + "}"
print(flag)

echo_lwe

题目

#!/usr/bin/env python3
import hashlib
import hmac
import json
import secrets
from pathlib import Path

N = 256
Q = 12289
OUTPUT = Path(__file__).with_name("output.json")

def derive_seed(master: bytes, label: bytes) -> bytes:

    normalized_label = label[:6]
    return hmac.new(master, normalized_label, hashlib.sha256).digest()

def sample_small(master: bytes, label: bytes) -> list[int]:
    seed = derive_seed(master, label)
    stream = hashlib.shake_256(seed).digest(N)
    return [(byte % 3) - 1 for byte in stream]

def negacyclic_rotate(poly: list[int], amount: int) -> list[int]:

    result = [0] * N
    for index, coefficient in enumerate(poly):
        target = index + amount
        if target >= N:
            result[target - N] -= coefficient
        else:
            result[target] += coefficient
    return result

def negacyclic_mul(left: list[int], right: list[int]) -> list[int]:
    result = [0] * N
    for i, a_i in enumerate(left):
        for j, b_j in enumerate(right):
            target = i + j
            if target >= N:
                result[target - N] -= a_i * b_j
            else:
                result[target] += a_i * b_j
    return [value % Q for value in result]

def add(*polynomials: list[int]) -> list[int]:
    return [sum(values) % Q for values in zip(*polynomials)]

def trim(poly: list[int]) -> list[int]:
    poly = [coefficient % Q for coefficient in poly]
    while len(poly) > 1 and poly[-1] == 0:
        poly.pop()
    return poly

def polynomial_remainder(dividend: list[int], divisor: list[int]) -> list[int]:
    dividend = trim(dividend)
    divisor = trim(divisor)
    inverse_lead = pow(divisor[-1], -1, Q)
    while len(dividend) >= len(divisor) and dividend != [0]:
        scale = dividend[-1] * inverse_lead % Q
        offset = len(dividend) - len(divisor)
        for index, coefficient in enumerate(divisor):
            dividend[index + offset] = (dividend[index + offset] - scale * coefficient) % Q
        dividend = trim(dividend)
    return dividend

def is_unit(poly: list[int]) -> bool:

    left = trim(poly)
    right = [1] + [0] * (N - 1) + [1]
    while right != [0]:
        left, right = right, polynomial_remainder(left, right)
    return len(trim(left)) == 1 and trim(left)[0] != 0

def encode_message(message: bytes) -> list[int]:
    padded = message.ljust(N // 8, b"\0")
    bits = [(byte >> shift) & 1 for byte in padded for shift in range(7, -1, -1)]
    return [bit * (Q // 2) for bit in bits]

def keygen() -> tuple[list[int], list[int], int]:
    master = secrets.token_bytes(32)
    rotation = secrets.randbelow(N - 1) + 1

    secret = sample_small(master, b"secret-key")
    raw_error = sample_small(master, b"secret-noise")
    error = negacyclic_rotate(raw_error, rotation)

    while True:
        public_a = [secrets.randbelow(Q) for _ in range(N)]
        vulnerable_factor = public_a.copy()
        vulnerable_factor[rotation] = (vulnerable_factor[rotation] + 1) % Q
        if is_unit(vulnerable_factor):
            break

    public_b = add(negacyclic_mul(public_a, secret), error)
    return public_a, public_b, rotation

def encrypt(public_a: list[int], public_b: list[int], message: bytes) -> tuple[list[int], list[int]]:

    ephemeral_r = sample_small(secrets.token_bytes(32), b"encrypt-r")
    error_1 = sample_small(secrets.token_bytes(32), b"encrypt-e1")
    error_2 = sample_small(secrets.token_bytes(32), b"encrypt-e2")
    encoded = encode_message(message)

    u = add(negacyclic_mul(public_a, ephemeral_r), error_1)
    v = add(negacyclic_mul(public_b, ephemeral_r), error_2, encoded)
    return u, v

def main() -> None:
    from secret import flag

    public_a, public_b, rotation = keygen()
    u, v = encrypt(public_a, public_b, flag)
    instance = {
        "n": N,
        "q": Q,
        "rotation": rotation,
        "a": public_a,
        "b": public_b,
        "u": u,
        "v": v,
    }
    OUTPUT.write_text(json.dumps(instance, indent=2) + "\n", encoding="utf-8")

if __name__ == "__main__":
    main()

思路

题目给出了Ring-LWE的公钥和密文：$$(a,b)\quad (u,v)$$环为$$R_q=\mathbb Z_q[x]/(x^256+1)$$

关键漏洞在 KDF label 截断：

1	derive_seed(master,label)=HMAC(master,label[:6])\text{derive\_seed}(master,label)=\text{HMAC}(master,label[:6])

所以：

1	b"secret−key"[:6]=b"secret−noise"[:6]=b"secret"b"secret-key"[:6]=b"secret-noise"[:6]=b"secret"

因此：

1	s=secret=raw_errors=\text{secret}=\text{raw\_error}

源码中确实对 label 只取前 6 字节，且 secret 和 raw_error 都由同一个 master 派生。

噪声是secret的旋转：$$erot_r(s)$$，公钥中代入有：$$b=a\cdot s+rot_r(s)=（a+x^r)s \Rightarrow s=b(a+x^r)^{-1}$$

又密文满足：$$u=ar+e_1 \quad v=br+e_2+m\Rightarrow v-us=(br+e_2+m)-(ar+e_1)s \approx m$$

根据编码规则，对每个系数判断即可恢复bit拼成flag

解答

import json

Q = 12289
N = 256

def negacyclic_mul(a, b):
    res = [0] * N
    for i, x in enumerate(a):
        if x == 0:
            continue
        for j, y in enumerate(b):
            if y == 0:
                continue
            k = i + j
            if k >= N:
                res[k - N] -= x * y
            else:
                res[k] += x * y
    return [x % Q for x in res]

def solve_mod(A, b, mod):
    n = len(A)
    M = [A[i][:] + [b[i] % mod] for i in range(n)]
    row = 0
    pivots = []

    for col in range(n):
        pivot = None
        for r in range(row, n):
            if M[r][col] % mod:
                pivot = r
                break
        if pivot is None:
            continue

        M[row], M[pivot] = M[pivot], M[row]
        inv = pow(M[row][col] % mod, -1, mod)
        M[row] = [(x * inv) % mod for x in M[row]]

        for r in range(n):
            if r != row and M[r][col] % mod:
                c = M[r][col] % mod
                M[r] = [(M[r][i] - c * M[row][i]) % mod for i in range(n + 1)]

        pivots.append(col)
        row += 1

    x = [0] * n
    for r, col in enumerate(pivots):
        x[col] = M[r][n] % mod
    return x

def center(x):
    x %= Q
    return x - Q if x > Q // 2 else x

def decode(poly):
    bits = []
    half = Q // 2

    for x in poly:
        d0 = abs(center(x))
        d1 = abs(center(x - half))
        bits.append(1 if d1 < d0 else 0)

    out = []
    for i in range(0, len(bits), 8):
        val = 0
        for bit in bits[i:i + 8]:
            val = (val << 1) | bit
        out.append(val)

    return bytes(out).rstrip(b"\x00")

data = json.load(open("output.json", "r"))
a = data["a"]
b = data["b"]
u = data["u"]
v = data["v"]
r = data["rotation"]
f = a[:]
f[r] = (f[r] + 1) % Q
cols = []
for j in range(N):
    e = [0] * N
    e[j] = 1
    cols.append(negacyclic_mul(f, e))
A = [[cols[j][i] for j in range(N)] for i in range(N)]
s = solve_mod(A, b, Q)
assert negacyclic_mul(f, s) == [x % Q for x in b]

us = negacyclic_mul(u, s)
m = [(v[i] - us[i]) % Q for i in range(N)]
print(decode(m))

time_stream

题目

#!/usr/bin/env python3
import json
import secrets
import time
from pathlib import Path

OUTPUT = Path(__file__).with_name("capture.json")
WINDOW_SECONDS = 6 * 60 * 60

def xorshift32(x: int) -> int:
    x ^= (x << 13) & 0xFFFFFFFF
    x ^= x >> 17
    x ^= (x << 5) & 0xFFFFFFFF
    return x & 0xFFFFFFFF

def stream(seed: int, length: int) -> bytes:
    state = seed & 0xFFFFFFFF
    output = bytearray()
    while len(output) < length:
        state = xorshift32(state)
        output.extend(state.to_bytes(4, "little"))
    return bytes(output[:length])

def encrypt(message: bytes, seed: int) -> bytes:
    keystream = stream(seed, len(message))
    return bytes(left ^ right for left, right in zip(message, keystream))

def main() -> None:
    from secret import flag

    event_timestamp = int(time.time())
    offset_in_window = secrets.randbelow(WINDOW_SECONDS + 1)
    window_start = event_timestamp - offset_in_window
    window_end = window_start + WINDOW_SECONDS
    ciphertext = encrypt(flag, event_timestamp)

    capture = {
        "window_start": window_start,
        "window_end": window_end,
        "ciphertext": ciphertext.hex(),
    }
    OUTPUT.write_text(json.dumps(capture, indent=2) + "\n", encoding="utf-8")

if __name__ == "__main__":
    main()

思路

题目给出：

event_timestamp = int(time.time())
    offset_in_window = secrets.randbelow(WINDOW_SECONDS + 1)
    window_start = event_timestamp - offset_in_window
    window_end = window_start + WINDOW_SECONDS
    ciphertext = encrypt(flag, event_timestamp)

说明加密时的种子为：seed=[time.time()]由于unix时间戳精确到秒，那么只要知道事件发生的大致时间范围，就可以暴力枚举所有可能的种子，并且日志给出了6小时的时间窗口

$$seed \in [1786147200,\ 1786168800]，因此只需要爆破21601个可能的seed$$

$$程序使用xorshift32生成密钥流K，并通过异或加密Flag: \quad C=P\oplus K$$

$$所以对于每个候选seed，重新生成对应密钥流K_{seed}:P_{seed}=C\oplus K_{seed}$$

$$最终得到seed=1786159697$$

$$那么P=C\oplus PRNG(1786159697)$$

解答

import json

def xorshift32(x):
    x ^= (x << 13) & 0xffffffff
    x ^= x >> 17
    x ^= (x << 5) & 0xffffffff
    return x & 0xffffffff

def stream(seed, n):
    out = b""
    while len(out) < n:
        seed = xorshift32(seed)
        out += seed.to_bytes(4, "little")
    return out[:n]

data = json.load(open("capture.json"))
ct = bytes.fromhex(data["ciphertext"])

for seed in range(data["window_start"], data["window_end"] + 1):
    pt = bytes(a ^ b for a, b in zip(ct, stream(seed, len(ct))))
    if pt.startswith(b"flag{"):
        print(seed, pt.decode())

bad_share

思路

解答

nonce_again

题目

思路

解答

echo_lwe

题目

思路

解答

time_stream

题目

思路

解答