拉克罗伊气泡水、八元数与Second Life有何共同点？ - Trail of Bits博客

今年CSAW CTF中，Trail of Bits贡献了两个密码学题目。第一题可通过组合两个漏洞破解DSA，类似PlayStation 3固件黑客手法。另一个更奇特、数学味更浓的挑战"Holywater"分为资格赛和决赛两部分，这是我设计过最有趣的CTF题目之一。

资格赛是典型的CTF密码题：选手从Python脚本和历史输出文本文件（保存在Github）开始，需恢复秘密口令。下图（极具相关性）之后的内容含剧透，建议自行尝试前勿阅。

在深入我的解法前，首先要称赞Galhacktic Trendsetters团队的精彩题解（若有成员读到本文，请联系我，愿寄送纪念品）。他们优雅地阐述了攻击的数学基础，此处我不再同等深度展开。该题解也完美展示了团队如何在48小时内仅凭一个Python文件和几个十六进制字符串开发出有效攻击。

挑战的Python文件名为"lattice.py"，可能暗示与格密码相关。方法名包含"isogeny"、“gaussian"和"wobble"等术语，连上述题解也承认对这些术语含义存在困惑。

实际上，文件中几乎所有名称都是误导。它实现的是HK17密钥交换——一种被Li、Liu、Pan和Xie证明完全不可行的后量子密钥交换方案。HK17的数学基础并非格或同源映射，而是八元数！八元数是八维超复数，用于理论物理，具有许多反直觉特性。

理解八元数最简单的方式是从头构造。多数读者熟悉复数（实数的二维扩展，具有代数闭包特性）。我们通过凯莱-迪克森构造生成复数：维度翻倍并定义类似直积的乘法（非完全相同）。

对复数重复此过程得到四元数。有图形编程经验的读者可能熟悉四元数，因其能高效计算三维空间旋转，被多数图形库使用。再次应用凯莱-迪克森构造可得八元数（密码系统所用）。

但凯莱-迪克森过程无法保留数系的所有性质。复数不可排序（不能简单排列在线上），四元数不仅不可排序，还有非交换乘法：a * b与b * a可能不同。八元数更丧失结合律：(d * e) * f可能不等于d * (e * f)。

“实数是家族中可靠的养家者，是我们依赖的完备有序域。复数是稍花哨但仍可敬的弟弟：虽无序但代数完备。四元数因非交换性成为被重要聚会排斥的古怪表亲。而八元数则是没人敢放出阁楼的疯癫老叔：它们非结合。” ——John Baez

这解释为何八元数较少使用（锁紧阁楼门！）。但似乎正适合构建密钥交换系统所需的难题！HK17作者通过八元数多项式创建了号称抗量子攻击的Diffie-Hellman式密钥交换。

然而现实中，大学生仅需周末即可破解（九支队伍成功）。八元数的奇特乘法规则使因式分解更简单！结合八元数恒等式和高中线性代数知识，密码系统可简化为四个变量的线性方程组，Python脚本可瞬间O(1)求解。

敏锐读者可能疑惑：“为何挑战叫’Holywater’？“答案与八元数无关，而关乎我对题目的后续计划。HK17草案不仅定义八元数系统，还包含单位四元数（模为1的四元数）系统！由于四元数被更多程序员（如图形领域）使用，这开启了新可能。

这意味着我们可用Second Life的官方脚本语言Linden Scripting Language（LSL）定义系统。我向来对编程语言挑剔，曾认为PHP是设计最糟的语言，后接触区块链安全中的Solidity改变了看法。但两者都比不上LSL这"轮胎火灾"般的语言——看看其JSON解析方式就知。

LSL内置四元数类型，虽与数学四元数存在差异，但仍适用于本目的。用LSL编写挑战让参赛者能享受逆向工程乐趣。但我需要帮助开发Second Life脚本、设计附件对象、租赁虚拟空间等非数学部分。

由此得名：决赛部分称"Holywater 2: La Croix”，专为吸引热爱LSL和La Croix气泡水的Dan “Pamplemousse” Hlavenka。他愿协助Second Life部分，但要求挑战全面采用La Croix主题以传播其福音。

参赛者会见到以下藏头诗，填空后既描述Second Life位置又暗示六种La Croix口味：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

yeah i SMOKE WEED
P    P
E  M A
PA  AOM
UC BNRP
maps.Secondlife.com/secondlife/_______/23/233/1
M                         E PRONE
O                          PRR GM
K                          EIY EO
E                          AC   U
RO   S
W                           T   S
E                               E
E
D

队伍到达后会发现身处水下巨型La Croix罐中（带碳酸粒子特效）。该地点更名为威斯康星州拉克罗塞市（饮料产地）的"Mud City”。两个发光球体显示：“点击获取所需一切"和"点击立即死亡”。

标签准确，但许多人反复点击"立即死亡"球体（或许试图通过转世破解密码）。相反，“所需一切"球体给玩家IBM Selectric打字球。由于单位四元数描述旋转，我们通过Second Life聊天框用HK17密钥交换协商旋转，物理旋转打字球编码信息。用户可查看打字球附着的脚本了解流程（尽管有人尝试其他策略）。

数学原理相同但应用更难。此次仅两支队伍（MIT和CMU）找到最终flag（另一个巧妙的La Croix引用），首杀队伍除600高分（通常极难题目500分）外每人获赠一箱La Croix。通过逆向脚本和抓取聊天记录，资格赛解法仍适用，只需旋转打字球并观察底部字母。

Dan在Second Life的土地租约已到期，挑战遗憾关闭。但他的La Croix设计比预期更受欢迎，未来或再现该饮料主题。此挑战虽比资格赛实用性低，但教训依然有效：若在Second Life保护传输La Croix秘密的远程打字机，勿用HK17。

附：因csaw.tv临时关闭，您可享受Dan与我在Second Life专属频道制作的La Croix主题播放列表。