CodeShell.kr - Obsidian

Posted on 2026-09-22 In ctf Views: Disqus:

Challenge

GF(2) 上的 syndrome decoding，320 列 160 位、目标权重 35。结构已排除、复杂度已实测，本文只写已验证的部分与精确的算力估算。

Find the missing pattern

找到缺失的图案。

1	https://codeshell.kr/challenges/obsidian/

Solution

自带 rules.txt 完整规格：

GF(2); 320 columns of 160 bits, indexed 0..319; hex encoding.
H*e=syndrome; wt(e)=35.
E: 40 bytes; e_i is bit i%8 in byte i//8.
commitment=SHA256(b"WITNESS-V1"||E).
Submit CodeShell{SHA256(b"CODESHELL-GOD-CRYPTO-V1"||E).hexdigest()[:32]}.

本质是 GF(2) 上的 syndrome decoding。结构已全部排除（实测）：

rank(H) = 160（满秩）        320 列互不相同        无单位矩阵列
无旋转/循环关系（前 60 列 0 命中）                  非拟循环（shift×rotation 全扫 0 命中）
列重 64..97、行重 134..188（密度约 0.5）            不是稀疏 LDPC，BP 不可用
1/2/3 列 XOR == s：均无                            答案不在低列数组合里

复杂度精算（三次修正后的准确结论）：① 只算 Prange 迭代次数 2^38 → 判不可行（错）； ② 改成「算工作量」但把每个候选的成本当成 ~1μs → 估 5–13 小时（也错，实际约 70μs/候选）； ③ 实测：写了增量 info-set 版本并测速：

1
2
3

14286 info-set/秒（每个 info-set 枚举全部 160 个 free 位置）
p=1  info-set 2^32.54, 候选 160    -> 1.0e12 候选 ≈ 124 小时
p=2  info-set 2^28.13, 候选 12720  -> 3.9e12 候选 ≈ 480 小时

结论：Lee-Brickell 系列在本实例上需要 100 小时量级（进一步优化 Bcol[] 增量维护可到约 40 小时）。Stern 已验算无效：需 2l+p=w=35，l=8,p=19 与 l=17,p=1 两种取法总代价都超 2^67，比 Prange 还差。

已交付：两个正确的 C 实现（solvers/obsidian_isd.c 全量消元版、 solvers/obsidian_inc.c 增量版），都在合成实例上精确恢复真值并通过 H·e==s 验证。踩过的坑：行变换必须同步变换 RHS（do_swap 里漏了 → selfcheck 从 20/20 掉到 0/20）、新 pivot 必须选在该列上有 1 的行且要均匀随机、p=1 要枚举全部 free 位置、swap 后不能 undo（否则只探索 25600 个 info-set）。

已排除：CryptoMiniSat（35 分钟无输出）、isd 包（其实是气象数据库）、低权重假设（最佳总权重 56）、Sage 的 Lee-Brickell（解释器慢两个数量级）、经典 Stern。

Challenge

Solution

Reversing