拉克罗伊、八元数和第二人生有何共同之处？ - Trail of Bits博客

今年在CSAW CTF中，Trail of Bits贡献了两个密码学问题。第一个问题中，你可以结合两个漏洞来破解DSA，就像PlayStation 3固件黑客所做的那样。另一个挑战——更奇怪且更数学化——分为两部分：一部分用于资格赛，一部分用于决赛。这个名为"Holywater"的挑战是我制作CTF问题以来最有趣的经历之一。

资格赛挑战是一个相当经典的CTF密码学挑战。参赛者从一个脚本和一个过去输出的文本文件（保存在Github上）开始，必须恢复一个秘密密码。如果你想自己尝试，请在（极其相关的）图片下方查看剧透。

在深入我自己的解决方案之前，我首先要赞扬Galhacktic Trendsetters他们出色的解析（如果任何Trendsetters成员正在阅读本文，请联系我，我很乐意寄给你们一些纪念品）。他们优雅地涵盖了攻击的数学基础，这个话题我在这里不会深入探讨。这也是一个优秀的思考过程指南，让一个团队从仅有一个Python文件和几个十六进制字符串开始，在不到48小时内开发出有效的攻击。

挑战的Python文件并不容易。它被称为"lattice.py"，这可能立即暗示它与格密码学有关。方法名称包括"isogeny"、“gaussian"和"wobble"等。甚至上述解析也承认对这些术语的含义有些困惑。

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

理解八元数的最简单方法是从头开始构建它们。大多数读者已经熟悉复数，这是一个二维的超实数集，是代数闭的，这一特性使许多数学变得更容易。我们使用凯莱-迪克森构造来构建复数。实际上，我们加倍维度数，并像在直和中那样定义乘法（尽管不完全相同）。

我们可以对复数重复此过程，产生一个四维的数字集，称为四元数。有图形编程经验的读者可能熟悉，因为四元数允许高效计算三维空间中的旋转，因此被许多图形库使用。再次应用凯莱-迪克森过程，我们到达八维；我们用于密码系统的八元数。

然而，凯莱-迪克森过程不能保留我们可能想要的数字系统的每个属性。复数与实数不同，不可排序（它们不能简单地端对端排列在一条线上）。四元数也不可排序，但不同于实数或复数，具有非交换乘法！如果a和b是四元数，a * b和b * a可以产生不同的数字。这种不变性的逐渐丧失在八元数中继续，它们甚至不是结合的；如果d、e和f是八元数，(d * e) * f可能不等于d * (e * f)。

“实数是家庭中可靠的经济支柱，是我们都依赖的完全有序域。复数是一个稍微花哨但仍然可敬的弟弟：不可排序，但代数完备。四元数，由于非交换性，是被重要家庭聚会回避的古怪表亲。但八元数是没人让出阁楼的疯狂老叔叔：它们是非结合的。” – John Baez

就我们选择使用的数字标准而言，这相当棘手，并在一定程度上解释了为什么八元数不常用（保持阁楼门关闭！）。然而，它似乎也允许我们在构建密钥交换系统时想要的那种难题！通过在八元数上使用多项式，HK17作者创建了一个Diffie-Hellman风格的密钥交换系统，他们声称是量子硬的。

然而，在现实生活中，这个系统可以被大学生在周末可靠地破解（九个团队解决了它）。八元数的奇怪乘法规则最终使因式分解变得容易得多！凭借一些八元数恒等式和高中生的线性代数知识，密码系统减少到四个线性方程中的四个变量，并且可以通过一个几乎瞬间运行的Python脚本在O(1)中解决。

敏锐的读者可能会在这里暂停，完全了解问题，并想知道“为什么这个挑战被称为Holywater？”答案与八元数密钥交换无关，而与我对问题后半部分的计划有关。HK17草案不仅定义了八元数上的系统，还定义了单位四元数（模为一的四元数）上的系统！而且，由于四元数被这么多程序员使用（如上所述，用于图形），这打开了一些有趣的门。

具体来说，这意味着我们现在可以在Linden脚本语言（Second Life的官方脚本语言）中定义我们的系统。我一直有点编程语言势利眼。有一段时间，我认为PHP是绝对的最低点。没有什么可能比那个主要由意外创建的糟糕设计的分形更糟。后来，我开始从事区块链安全，并了解了语言Solidity。 suffice to say，我的想法从此改变了。然而，这两种语言都无法与Linden脚本语言的绝对轮胎火相比。 seriously， just read how you parse JSON.

LSL有一个内置的四元数类型，虽然“数学四元数与LSL四元数之间的差异”可能看起来不祥，但它们完全适用于我们的目的。而且，用LSL编写整个挑战意味着竞争对手可以有更多逆向工程的乐趣。然而，我需要帮助来开发Second Life脚本，设计要附加的对象，在Second Life中租赁空间，并 generally do the non-mathy parts of the whole project.

这就是名字的由来。最后一部分被称为“Holywater 2: La Croix”， specifically to entice Dan “Pamplemousse” Hlavenka，一个我的朋友，他比我知道的任何人都更爱LSL和La Croix。他愿意帮助Second Life部分的每一个部分，但 only if we made the challenge La Croix themed in every way we could， to spread the gospel to the next generation.

竞争对手被下面的离合诗 greeted，当空白被填满时，描述了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罐内，水下（并有碳酸化的粒子效果）。Second Life中的位置被更名为“Mud City”， after LaCrosse Wisconsin，饮料的家乡。然后他们被呈现两个发光的球体， reading “Click here for everything you need” and “Click here to die instantly.”

这些标签是准确的。那并没有阻止许多人反复点击“die instantly”球体， however， perhaps in an attempt at some sort of reincarnation-based cryptanalysis。相比之下，“everything you need”球体给玩家一个IBM Selectric typeball。由于单位四元数描述旋转，我们选择通过物理旋转一个这样的typeball（如正常Selectric操作）来编码消息，通过Second Life的聊天框中的HK17密钥交换商定旋转。用户可以看到附加到type ball的脚本，概述了整个过程， though again， some attempted other strategies（见下文）。

尽管如此，数学大致相同，如果更难应用。这次只有两个团队（MIT和CMU）找到了最终标志（另一个聪明的La Croix参考）， first blood winning a case of La Croix for each team member as a bonus on top of the（异常高的）600 points（通常，挑战如果是极其容易的100分，如果是极其困难的500分）。通过逆向脚本和抓取聊天，资格赛有效的相同过程可以在这里工作。所有剩下的就是旋转你的typeball并观察哪个字母在底部。

Dan在Second Life中的土地租约现已到期，所以挑战 unfortunately closed to the public。Dan的La Croix贡献最终比我预期的更受欢迎，所以也许这个挑战不会是最后一个以饮料为特色的挑战。这个挑战可能比资格赛 less applicable，但它的教训仍然有效：如果你在Second Life中保护一个发送La Croix秘密的遥控打字机，不要使用HK17。

附：虽然最后一刻移除csaw.tv意味着这从未见到竞争的光明，但你可以享受Dan和我为仅可从Second Life访问的特殊csaw.tv制作的这个La Croix主题播放列表。

如果你喜欢这篇文章，分享它： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容 最近的帖子 非传统创新者奖学金 在你的PajaMAS中劫持多代理系统 我们构建了MCP一直需要的安全层 利用废弃硬件中的零日漏洞 Inside EthCC[8]: Becoming a smart contract auditor © 2025 Trail of Bits. 用Hugo和Mainroad主题生成。