0x00 题目概述

这是一道密码学题目,实现了一个基于LFSR的流密码算法。题目提供了加密程序和2048字节的加密输出,要求恢复128位的初始状态。

核心信息:

• 算法: LFSR + Feedforward函数

• 状态长度: 128位

• 输出长度: 16384位 (2048字节)

• Flag: flag{ce2980ad9763b8468882f292dbe9f365}

• SHA-256校验: 825c3637fb99400d7d132f80e379db5982cfaf0eb73b47c1cfdfd9c03aceebac

0x01 算法分析

1.1 LFSR (线性反馈移位寄存器)

def lfsr(R, mask):
    degree = 128
    f_skr = (1 << degree) - 1
    tmp = ((R << 1) & mask)
    lastbit = 0
    while tmp != 0:
        lastbit ^= (tmp & 1)
        tmp = tmp >> 1
    return ((R << 1) ^ lastbit) & f_skr

工作原理:

1. 将128位状态左移1位

2. 根据mask选择特定位进行异或

3. 结果作为新的最低位

4. 这是一个线性变换,可以用转移矩阵表示

数学表示:

S[t+1] = T · S[t]  (mod 2)

其中T是由mask决定的128×128转移矩阵。

关键参数:

MASK = 0x16c9c9a7f51ce6637b0e3f461a8da9b75

1.2 Feedforward函数

def feedforward(r):
    x = [int(i) for i in list('{0:0b}'.format(r))][::-1]
    x += [0] * (128 - len(x))
    box = [78, 65, 90, ...]  # 63个索引

    out = x[127]
    for i in range(0, 63):
        out ^= (x[i] ^ x[box[i]]) & 1
    out ^= x[11] & x[22] & x[33] & x[53] & 1           # 4次项
    out ^= x[1] & x[9] & ... & x[59] & 1                # 16次项
    tmp = 1
    for i in range(0, 63):
        tmp &= x[i]
    out ^= tmp & 1                                      # 63次项
    return out

组成部分:

1. 线性部分:

   • x[127]

   • Σ(x[i] ⊕ x[box[i]])for i in range(63)

   • 覆盖了127个互不重复的比特(缺x[126])

2. 非线性部分:

   • 4次项: x[11] & x[22] & x[33] & x[53]

   • 16次项: x[1] & x[9] & ... & x[59]

   • 63次项: x[0] & x[1] & ... & x[62]

1.3 关键观察 - 识别稀疏噪声

为什么非线性项可以视为噪声?

让我们计算非线性项为1的概率:

• 4次项x[11] & x[22] & x[33] & x[53]: 概率 = 1/16 = 0.0625

• 16次项: 概率 = 1/65536 ≈ 0.0000153

• 63次项: 概率 ≈ 1/10^19 (几乎为0)

因此,实际输出中:

• 约93.75%的输出位只受线性部分影响

• 约6.25%的输出位受非线性项干扰(视为"噪声")

这就形成了一个带噪声的奇偶学习问题(LPN)!

0x02 LPN问题建模

2.1 什么是LPN?

Learning Parity with Noise (带噪声的奇偶学习):

给定:

• 矩阵 A ∈ GF(2)^(m×n)

• 向量 y ∈ GF(2)^m

• 秘密向量 s ∈ GF(2)^n

满足:

y[i] = <A[i], s> ⊕ noise[i]

其中 noise[i] = 1 的概率约为 η (噪声率)

目标: 从(A, y)恢复s

LPN问题被认为是量子安全的,但在η较小时可以用统计方法求解。

2.2 本题的LPN建模

对于第t个输出位,可以表示为:

y[t] = <a[t], s> ⊕ noise[t]

其中:

• s: 128位初始状态(未知)

• a[t]: 第t个系数向量(已知)

• y[t]: 第t个输出位(已知)

• noise[t]: 非线性项产生的噪声

直观理解: 输出的每一比特,几乎等于"当前128位状态里除了x[126]外的全部异或",偶尔被非线性项翻转。

2.3 系数向量a[t]的计算

如何计算a[t]?

由于LFSR是线性的,第t时刻的状态可以表示为:

State[t] = T^t · s

而线性部分的输出为:

linear_output[t] = c · State[t+1] = c · T^(t+1) · s = <(T^T)^(t+1) · c, s>

因此:

a[t] = (T^T)^(t+1) · c

其中c是线性组合系数:

c = 1 << 127  # x[127]
for i in range(63):
    c ^= (1 << i)       # x[i]
    c ^= (1 << box[i])  # x[box[i]]

0x03 高效的系数向量生成

3.1 为什么不显式构造128×128矩阵?

直接存储128×128的转移矩阵T:

• 内存占用: 128×128/8 = 2KB (可接受)

• 计算开销: 矩阵乘法 O(128^2) (较慢)

• 代码复杂度高

3.2 位运算优化 - O(1)转移矩阵应用

注意题目LFSR是"左移一位 + 选位异或注入",其转置在位级别可以O(1)更新:

FULL = (1 << 128) - 1
MASK_SHIFTED = MASK >> 1

def apply_Tt(v, mask_shifted):
    """对行向量v施加一次T^T"""
    u = (v >> 1) & FULL
    if v & 1:
        u ^= mask_shifted
    return u

原理解析:

• 列向量左移 → 行向量右移

• 反馈位注入 → 条件异或mask

• 时间复杂度: O(1)

3.3 系数向量序列生成

def build_c(box):
    """构造线性部分系数"""
    c = 1 << 127
    for i in range(63):
        c ^= (1 << i)
        c ^= (1 << box[i])
    return c

def gen_rows(n, c_vec, mask_shifted):
    """生成系数向量序列"""
    rows = []
    v = apply_Tt(c_vec, mask_shifted)  # a[0] = T^T · c
    for _ in range(n):
        rows.append(v)
        v = apply_Tt(v, mask_shifted)  # a[t+1] = T^T · a[t]
    return rows

性能优势:

• 时间复杂度: O(n) 而不是 O(n · 128^2)

• 空间复杂度: O(n) 存储结果

• 无需显式矩阵,仅需位运算

0x04 RANSAC求解算法

4.1 为什么不能直接高斯消元?

虽然我们有16384个方程和128个未知数,但由于:

1. 有噪声: 约6.25%的方程是错的

2. 矛盾方程: 直接求解会失败(无解)

标准高斯消元要求方程组完全一致,而带噪声的系统会导致矛盾。

4.2 RANSAC原理

RANSAC (Random Sample Consensus)是一种鲁棒的参数估计算法:

核心思想:

1. 随机选择最小子集(128个方程)

2. 用这个子集求解得到候选解s

3. 用候选解预测所有输出,计算准确率

4. 重复多次,取准确率最高的解

为什么有效?

假设噪声率η = 6.25%,随机选择128个方程:

• 全部正确的概率: (1-η)^128 ≈ 0.0001

• 但只要大部分正确,解就接近真实值

• 通过准确率筛选,可以找到最优解

与传统方法对比:

4.3 GF(2)高斯消元 - 放宽一致性检查

def parity(x: int) -> int:
    """计算奇偶性"""
    return x.bit_count() & 1

def gf2_gauss_solve(A_rows, b_bits, n=128):
    """GF(2)上的高斯消元(放宽一致性检查)"""
    A = A_rows[:]
    b = b_bits[:]
    m = len(A)
    row = 0
    piv = [-1] * n

    # 前向消元
    for col in range(n):
        # 找主元
        pivot = None
        for r in range(row, m):
            if (A[r] >> col) & 1:
                pivot = r
                break
        if pivot is None:
            continue

        # 交换行
        A[row], A[pivot] = A[pivot], A[row]
        b[row], b[pivot] = b[pivot], b[row]
        piv[col] = row

        # 消元
        for r in range(m):
            if r != row and ((A[r] >> col) & 1):
                A[r] ^= A[row]
                b[r] ^= b[row]

        row += 1
        if row == m:
            break

    # 回代(自由元设为0)
    s = 0
    for col in range(n - 1, -1, -1):
        r = piv[col]
        if r == -1:
            continue
        above = (A[r] >> (col + 1)) & ((1 << (n - col - 1)) - 1)
        val = b[r] ^ parity(above & (s >> (col + 1)))
        if val:
            s |= (1 << col)

    return (True, s)

关键改进:

• 不检查矛盾行(0...0 = 1)

• 自由元默认设为0

• 允许子系统有少量错误

4.4 RANSAC主循环

def predict(rows, s):
    """预测输出"""
    return [parity(r & s) for r in rows]

def ransac_solve(rows, y_bits, trials=2000, subset=128, seed=2):
    """RANSAC求解LPN问题"""
    rnd = random.Random(seed)
    N = len(rows)
    best_s, best_acc = 0, -1.0
    idx_all = list(range(N))

    for _ in range(trials):
        # 1. 随机抽取subset个方程
        idx = rnd.sample(idx_all, subset)
        A = [rows[i] for i in idx]
        b = [y_bits[i] for i in idx]

        # 2. GF(2)高斯消元求解
        ok, s = gf2_gauss_solve(A, b)
        if not ok:
            continue

        # 3. 用全体样本验证
        yp = predict(rows, s)
        hits = sum(1 - (a ^ b) for a, b in zip(yp, y_bits))
        acc = hits / N

        # 4. 更新最优解
        if acc > best_acc:
            best_acc, best_s = acc, s
            if acc > 0.92:  # 93.75%理论上限
                break

    return best_s, best_acc

参数说明:

• trials: 迭代次数(1200-2000)

• subset: 子集大小(128-256)

• seed: 随机种子(可复现)

0x05 完整攻击流程

5.1 步骤总结

[1] 读取output文件 → 16384个输出比特
[2] 从babystream.py解析mask和box
[3] 计算线性部分系数向量c
[4] 生成系数矩阵: a[t] = (T^T)^(t+1) · c
[5] RANSAC求解:
    - 2000次迭代
    - 每次随机选128个方程
    - 高斯消元求解
    - 全局验证打分
[6] 获得准确率93.854%的解
[7] 输出flag{ce2980ad9763b8468882f292dbe9f365}

5.2 比特流处理

def bits_be(bs):
    """字节序列 → 比特(高位在前)"""
    out = []
    for b in bs:
        for j in range(7, -1, -1):
            out.append((b >> j) & 1)
    return out

注意: 题目使用大端序(高位在前),这一点很关键!

5.3 运行结果

$ python3 solve.py
[+] Loaded output: 2048 bytes (16384 bits)
[+] Parsed mask: 0x16c9c9a7f51ce6637b0e3f461a8da9b75
[+] Parsed box[63] from babystream.py
[+] RANSAC accuracy: 93.854%
flag{ce2980ad9763b8468882f292dbe9f365}

准确率分析:

• 理论上限: 93.75% (1 - 1/16)

• 实际达到: 93.854%

• 略高于理论值,因为16次和63次项的噪声极低

0x06 严格验证 - 100%复现

6.1 为什么需要验证?

仅凭93.854%的准确率,我们如何确定找到的是真正的初始状态而不是某个"近似解"?

答案: 用恢复的初态代回原始生成器,逐字节复现题目output!

6.2 验证脚本

def lfsr_step(R):
    """LFSR单步演化"""
    degree = 128
    f_skr = (1 << degree) - 1
    tmp = ((R << 1) & MASK)
    lastbit = parity(tmp)
    return ((R << 1) ^ lastbit) & f_skr

def feedforward_bit(r):
    """完整的feedforward函数(含非线性项)"""
    x = [(r >> i) & 1 for i in range(128)]

    # 线性部分
    out = x[127]
    for i in range(63):
        out ^= (x[i] ^ x[BOX[i]]) & 1

    # 非线性部分
    out ^= x[11] & x[22] & x[33] & x[53] & 1
    out ^= x[1] & x[9] & x[12] & x[18] & x[20] & x[23] & x[25] & x[26] & x[28] & x[33] & x[38] & x[41] & x[42] & x[51] & x[53] & x[59] & 1
    tmp = 1
    for i in range(63):
        tmp &= x[i]
    out ^= tmp & 1
    return out & 1

def regenerate(r0, nbytes):
    """重新生成密钥流"""
    r = r0
    out = bytearray()
    for _ in range(nbytes):
        byte_val = 0
        for _ in range(8):
            r = lfsr_step(r)
            bit = feedforward_bit(r)
            byte_val = (byte_val << 1) ^ bit
        out.append(byte_val)
    return bytes(out)

# 验证
r = 0xce2980ad9763b8468882f292dbe9f365
regenerated = regenerate(r, 2048)

with open("output", "rb") as f:
    original = f.read()

print(f"验证: {regenerated == original}")  # True
print(f"匹配率: {sum(a==b for a,b in zip(regenerated, original))}/2048")  # 2048/2048

验证结果:

• 逐字节完全一致: 100% match

• SHA-256校验: 完全相同

• 这是最强的验证!

0x07 关键技术点总结

7.1 转移矩阵的快速计算

传统方法:

# 显式构造128×128矩阵
T = np.zeros((128, 128), dtype=int)
# ... 填充矩阵 ...
# 矩阵乘法: O(128^2)

优化方法:

# 位运算 O(1) 计算
def apply_Tt(v):
    u = (v >> 1) & FULL
    if v & 1:
        u ^= MASK_SHIFTED
    return u

性能对比:

• 传统: O(n · 128^2) ≈ 268M次运算

• 优化: O(n) ≈ 16K次运算

• 加速比: 16,384倍!

7.2 比特级高斯消元优化

使用整数表示行向量,利用位运算:

• 行异或: A[r] ^= A[row](O(1))

• 检查某位: (A[r] >> col) & 1(O(1))

• 设置某位: s |= (1 << col)(O(1))

比矩阵运算快得多!

7.3 RANSAC参数调优

实验结果:

推荐配置:

• 快速测试: trials=1200, subset=128

• 稳定求解: trials=2000, subset=256

0x08 完整可运行代码

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""BabyStream LPN/RANSAC 完整求解器"""

import random

DEG = 128
FULL = (1 << DEG) - 1
MASK = 0x16c9c9a7f51ce6637b0e3f461a8da9b75
MASK_SHIFTED = MASK >> 1
BOX = [78,65,90,99,117,113,87,119,64,69,114,86,72,123,91,103,
       124,93,79,82,76,84,106,73,110,92,118,63,109,101,67,122,
       98,111,80,105,108,107,100,81,125,71,96,83,75,68,95,74,
       104,112,121,115,77,89,85,97,70,120,88,66,94,102,116]

def parity(x: int) -> int:
    """计算奇偶性"""
    return x.bit_count() & 1

def bits_be(bs):
    """字节序列 → 比特(高位在前)"""
    out = []
    for b in bs:
        for j in range(7, -1, -1):
            out.append((b >> j) & 1)
    return out

def apply_Tt(v):
    """施加转移矩阵T^T"""
    u = (v >> 1) & FULL
    if v & 1:
        u ^= MASK_SHIFTED
    return u

def build_c():
    """构造线性部分系数"""
    c = 1 << 127
    for i in range(63):
        c ^= (1 << i)
        c ^= (1 << BOX[i])
    return c

def gen_rows(n):
    """生成系数向量序列"""
    rows = []
    v = apply_Tt(build_c())
    for _ in range(n):
        rows.append(v)
        v = apply_Tt(v)
    return rows

def gf2_gauss_solve(A_rows, b_bits, n=128):
    """GF(2)高斯消元"""
    A = A_rows[:]
    b = b_bits[:]
    m = len(A)
    row = 0
    piv = [-1] * n

    for col in range(n):
        pivot = None
        for r in range(row, m):
            if (A[r] >> col) & 1:
                pivot = r
                break
        if pivot is None:
            continue

        A[row], A[pivot] = A[pivot], A[row]
        b[row], b[pivot] = b[pivot], b[row]
        piv[col] = row

        for r in range(m):
            if r != row and ((A[r] >> col) & 1):
                A[r] ^= A[row]
                b[r] ^= b[row]

        row += 1
        if row == m:
            break

    s = 0
    for col in range(n - 1, -1, -1):
        r = piv[col]
        if r == -1:
            continue
        above = (A[r] >> (col + 1)) & ((1 << (n - col - 1)) - 1)
        val = b[r] ^ parity(above & (s >> (col + 1)))
        if val:
            s |= (1 << col)

    return (True, s)

def predict(rows, s):
    """预测输出"""
    return [parity(r & s) for r in rows]

def ransac_solve(rows, y_bits, trials=2000, subset=128, seed=2):
    """RANSAC求解"""
    rnd = random.Random(seed)
    N = len(rows)
    best_s, best_acc = 0, -1.0
    idx_all = list(range(N))

    for _ in range(trials):
        idx = rnd.sample(idx_all, subset)
        A = [rows[i] for i in idx]
        b = [y_bits[i] for i in idx]

        ok, s = gf2_gauss_solve(A, b)
        if not ok:
            continue

        yp = predict(rows, s)
        hits = sum(1 - (a ^ b) for a, b in zip(yp, y_bits))
        acc = hits / N

        if acc > best_acc:
            best_acc, best_s = acc, s
            if acc > 0.92:
                break

    return best_s, best_acc

# 验证函数
def lfsr_step(R):
    tmp = ((R << 1) & MASK)
    lastbit = parity(tmp)
    return ((R << 1) ^ lastbit) & FULL

def feedforward_bit(r):
    x = [(r >> i) & 1 for i in range(128)]
    out = x[127]
    for i in range(63):
        out ^= (x[i] ^ x[BOX[i]]) & 1
    out ^= x[11] & x[22] & x[33] & x[53]
    idx2 = [1,9,12,18,20,23,25,26,28,33,38,41,42,51,53,59]
    t = 1
    for k in idx2:
        t &= x[k]
    out ^= t
    t = 1
    for i in range(63):
        t &= x[i]
    out ^= t & 1
    return out & 1

def regenerate(r0, nbytes):
    r = r0
    out = bytearray()
    for _ in range(nbytes):
        byte_val = 0
        for _ in range(8):
            r = lfsr_step(r)
            bit = feedforward_bit(r)
            byte_val = (byte_val << 1) ^ bit
        out.append(byte_val)
    return bytes(out)

def main():
    print("="*60)
    print("BabyStream - LPN/RANSAC 求解器")
    print("="*60)

    # 读取output
    with open("output", "rb") as f:
        raw = f.read()
    y_bits = bits_be(raw)
    print(f"[+] 加载输出: {len(raw)} 字节 ({len(y_bits)} 比特)")

    # 生成系数矩阵
    rows = gen_rows(len(y_bits))
    print(f"[+] 生成系数矩阵: {len(rows)} 行")

    # RANSAC求解
    print("[*] 开始RANSAC求解...")
    best_s, best_acc = ransac_solve(rows, y_bits, trials=2000, subset=128)
    print(f"[+] RANSAC准确率: {best_acc:.3%}")

    # 输出flag
    flag = f"flag{{{best_s:032x}}}"
    print(f"[+] Flag: {flag}")

    # 严格验证
    print("[*] 验证中...")
    regenerated = regenerate(best_s, len(raw))
    match = (regenerated == raw)
    print(f"[+] 完整复现匹配: {match}")

    if match:
        print("="*60)
        print("验证通过! 成功恢复初始状态!")
        print("="*60)
    else:
        print("警告: 验证未通过,请检查参数")

if __name__ == "__main__":
    main()

0x09 为什么代数攻击失败了?

9.1 错误的理解

错误假设: 认为所有非线性项都被移除,系统完全线性化

实际情况:

• 非线性项仍然存在

• 导致方程组有噪声

• 直接高斯消元得到"无解"

9.2 正确的理解

1.md说"将乘号改成加号"的真正含义:

• 不是修改代码

• 而是建模时忽略非线性项

• 把非线性项当作噪声处理

• 用鲁棒算法(RANSAC)求解

9.3 失败尝试的教训

尝试1: 传统代数攻击

变量数量: C(128,1) + C(128,2) + C(128,3) ≈ 350,000
结果: 变量爆炸,无法求解

尝试2: 完全线性化

假设: 所有AND替换为XOR
结果: 方程组无解(与真实output不匹配)

正确方法: LPN建模

变量数量: 128
噪声率: 6.25%
结果: RANSAC成功求解

0x10 LPN的密码学意义

10.1 为什么LPN重要?

1. 量子安全: 目前没有有效的量子算法

2. 简单高效: 只需异或和随机数

3. 应用广泛: 认证协议、加密方案

4. 理论基础: 学习理论、复杂性理论

10.2 本题的弱点

噪声率太低: η ≈ 6.25%

安全的LPN通常需要:

• η ≈ 25% ~ 30%

• 或者n(维度)更大(如n=512)

本题的噪声主要来自4次项,16次和63次项几乎没贡献。

10.3 如何增强?

方法1: 增加噪声

• 添加更多低次非线性项(2次、3次)

• 调整box映射增加非线性

• 使用多个非线性函数

方法2: 增加维度

• 使用256位或512位LFSR

• 增加状态空间

• 提高计算复杂度

方法3: 组合方法

• LPN + LFSR的非线性组合

• 多级滤波

• 时变参数

0x11 学习要点总结

11.1 核心技术

1. LPN问题识别- 识别噪声的来源和比例

2. RANSAC算法- 鲁棒估计的经典方法

3. GF(2)线性代数- 位运算优化

4. LFSR数学建模- 转移矩阵的快速计算

11.2 关键洞察

为什么这种攻击有效?

1. 噪声可预测: 非线性项激活概率已知

2. 数据充足: 16384个样本 >> 128个未知数

3. RANSAC鲁棒: 能容忍6.25%的噪声

4. 计算高效: 位运算优化,秒级求解

11.3 实战技巧

1. 识别噪声来源- 计算非线性项的激活概率

2. 评估噪声率- 判断是否适合RANSAC

3. 参数调优- trials、subset大小的权衡

4. 验证准确率- 接近理论上限说明解正确

5. 严格校验- 100%复现是最强验证

11.4 复杂度分析

理论复杂度:

行向量生成: O(N)          N = 16384
单次消元:   O(subset^3)   subset = 128
RANSAC:     O(trials × subset^3)
总计:       O(trials × 128^3) ≈ 4M次运算

实际运行时间:

• 笔记本i5: 5-7秒

• 服务器: 2-3秒

0x12 总结

这道题目巧妙地将流密码的弱点(低噪声)转化为一个可求解的LPN问题。通过RANSAC算法,我们成功从带噪声的线性系统中恢复了128位密钥,并通过100%复现验证了解的正确性。

最终Flag: flag{ce2980ad9763b8468882f292dbe9f365}

准确率: 93.854% (理论上限93.75%)

验证: 100% 逐字节匹配

这个解法展示了:

• 密码分析不仅仅是代数攻击

• 统计方法在处理噪声时的强大能力

• LPN问题在密码学中的重要性

• 优雅的数学建模如何简化复杂问题

• 位运算优化在密码分析中的价值

• 严格验证在CTF中的必要性

参考资料:

• Blum, A., Kalai, A., & Wasserman, H. (2003). Noise-tolerant learning, the parity problem, and the statistical query model

• RANSAC: Random Sample Consensus Algorithm

• Learning Parity with Noise (LPN) - Post-Quantum Cryptography

• Toyocrypt Algorithm Specification

工具要求:

• Python 3.8+ (仅需标准库)

• 运行时间: 5-10秒