从La Croix、八元数到Second Life：一场CTF密码学挑战的奇幻之旅
今年在CSAW CTF中，Trail of Bits贡献了两道密码学题目。第一道题结合两个漏洞破解DSA，类似于PlayStation 3固件黑客的手法。另一道更奇特、数学性更强的挑战"Holywater"分为两部分：资格赛和决赛环节。这是我设计过最有趣的CTF题目之一。
资格赛：八元数密码系统的破解
资格赛是一个经典的CTF密码学挑战。参赛者从一个Python脚本和包含历史输出的文本文件（保存在Github上）开始，需要恢复秘密口令。Galhacktic Trendsetters团队提供了出色的解题报告，他们优雅地阐述了攻击的数学基础。
挑战中的Python文件名为"lattice.py"，可能暗示与格密码学相关。方法名包括"isogeny"、“gaussian"和"wobble"等术语，但实际上这些名称都是误导——该文件实现的是HK17密钥交换。
HK17是一种提出的后量子密钥交换机制，但被Li、Liu、Pan和Xie证明完全不可行。HK17的数学基础不是格或同源，而是八元数！八元数是八维超复数，用于理论物理，具有许多反直觉的特性。
理解八元数：从复数到八维
理解八元数最简单的方法是从头开始构建。大多数读者已经熟悉复数，这是实数的二维超集，具有代数闭包性质。我们使用Cayley-Dickson构造来构建复数：将维度加倍并定义乘法运算。
对复数重复此过程可得到四维的四元数。有图形编程经验的读者可能熟悉四元数，因为它们可以高效计算三维空间中的旋转，被许多图形库使用。再次应用Cayley-Dickson过程就到达八维：我们密码系统中使用的八元数。
然而，Cayley-Dickson过程无法保留数字系统的所有理想属性。与实数不同，复数不可排序；四元数也不可排序，而且乘法不可交换！对于八元数，情况更糟：它们甚至不满足结合律。如果d、e、f是八元数，(d * e) * f可能不等于d * (e * f)。
“实数是家庭中可靠的养家者，是我们都依赖的完全有序域。复数是一个稍微花哨但仍受尊敬的弟弟：不可排序，但代数完备。四元数由于不可交换，是在重要家庭聚会上被回避的古怪表亲。但八元数是没人让出阁楼的疯狂老叔叔：它们不满足结合律。” – John Baez
HK17的致命缺陷
HK17作者通过八元数上的多项式工作，创建了一种他们声称具有量子抗性的Diffie-Hellman风格密钥交换系统。然而在现实中，大学生在一个周末就能可靠地破解这个系统（九个团队解决了它）。八元数奇怪的乘法规则最终使因式分解变得容易得多！凭借一些八元数恒等式和高中线性代数知识，密码系统可简化为四个线性方程中的四个变量，Python脚本几乎瞬间就能以O(1)复杂度解决。
决赛：Second Life中的四元数挑战
为什么这个挑战叫"Holywater”？答案与八元数密钥交换无关，而与我对问题后半部分的计划有关。HK17草案不仅定义了八元数系统，还定义了单位四元数（模为1的四元数）系统！由于更多程序员使用四元数（如上所述，用于图形），这打开了一些有趣的大门。
具体来说，这意味着我们现在可以在Linden Scripting Language（Second Life的官方脚本语言）中定义我们的系统。LSL有一个内置的四元数类型，虽然"数学四元数与LSL四元数的差异"可能看起来令人担忧，但对于我们的目的完全可行。
La Croix主题的密码学冒险
最终部分名为"Holywater 2: La Croix"，专门为了吸引我的朋友Dan “Pamplemousse” Hlavenka，他比我认识的任何人都更热爱LSL和La Croix。他愿意帮助Second Life部分的每个环节，但前提是我们尽一切可能使挑战具有La Croix主题，向下一代传播福音。
参赛者会遇到下面的离合诗，当空白处填满时，既描述了Second Life中的一个位置，又描述了六种La Croix口味：
|
|
团队到达后，发现自己在一个巨大的La Croix罐内，水下（还有碳酸化的粒子效果）。Second Life中的位置被重命名为"Mud City"，以威斯康星州LaCrosse（该饮料的家乡）命名。然后他们看到两个发光球体，分别写着"点击这里获取所需一切"和"点击这里立即死亡"。
这些标签是准确的。然而，这并没有阻止许多人反复点击"立即死亡"球体，可能是试图进行某种基于转世的密码分析。相比之下，“所需一切"球体给玩家一个IBM Selectric打字球。
由于单位四元数描述旋转，我们选择通过物理旋转这样一个打字球（如正常Selectric操作）来编码消息，通过Second Life聊天框中的HK17密钥交换商定旋转。用户可以看到附加在打字球上的脚本，概述了整个过程。
挑战结果与启示
数学原理大致相同，但应用起来更困难。这次只有两个团队（MIT和CMU）找到了最终flag（另一个聪明的La Croix引用），首杀团队除了（异常高的）600分外，每个团队成员还赢得一箱La Croix作为奖励（通常，如果极其简单，挑战为100分；如果极其困难，为500分）。
通过逆向脚本和抓取聊天记录，资格赛中有效的相同过程在这里也有效。剩下的就是旋转你的打字球并观察底部是哪个字母。
Dan在Second Life中的土地租约现已到期，因此挑战不幸对公众关闭。但Dan的La Croix贡献最终比我预期的更受欢迎，所以这个挑战可能不是最后一个以该饮料为特色的挑战。这个挑战可能比资格赛更不实用，但其教训仍然有效：如果你在Second Life中保护发送La Croix秘密的远程控制打字机，不要使用HK17。
附言：虽然csaw.tv的最后分钟移除意味着这从未见到竞赛的光明，但你可以享受Dan和我为仅可从Second Life访问的特殊csaw.tv制作的这个La Croix主题播放列表。