La Croix、八元数和Second Life有何共同点？- 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的数学基础不是格或同源，而是八元数！八元数是八维超复数，用于理论物理，具有许多反直觉的特性。

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

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

然而，Cayley-Dickson过程不能保留我们可能想要的数字系统的每个属性。复数与实数不同，不可排序（它们不能简单地端对端排列在一条线上）。四元数也不可排序，但与实数或复数不同，具有不可交换的乘法！如果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 Scripting Language（Second Life的官方脚本语言）中定义我们的系统。我一直有点编程语言势利眼。有一段时间，我认为PHP是绝对的底层。没有什么可能比那个主要由意外创建的糟糕设计的分形更糟。后来我开始从事区块链安全，并了解了语言Solidity。 suffice to say，我的想法从此改变了。然而，这两种语言都无法与Linden Scripting Language的绝对轮胎火相比。 seriously， just read how you parse JSON.

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

这就是名字的由来。最后一部分被称为“Holywater 2: La Croix”， specifically 为了吸引Dan“Pamplemousse”Hlavenka，我的一个朋友，他比我知道的任何人都更爱LSL和La Croix。他愿意帮助Second Life部分的每个部分，但 only if 我们尽我们所能使挑战La Croix主题，向下一代传播福音。

竞争对手被下面的离合诗 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”和“Click here to die instantly”。

这些标签是准确的。然而，这并没有阻止许多人反复点击“die instantly”球体， perhaps 试图某种基于转世的密码分析。相比之下，“everything you need”球体给玩家一个IBM Selectric typeball。由于单位四元数描述旋转，我们选择通过物理旋转一个这样的typeball（如正常Selectric操作）来编码消息，通过Second Life的聊天框中的HK17密钥交换商定旋转。用户可以看到附加到type ball的脚本，概述了整个 process， though again，一些尝试了其他策略（见下文）。

尽管如此，数学大致相同，如果更难应用。这次只有两个团队（MIT和CMU）找到了最终标志（另一个聪明的La Croix参考）， first blood 赢得每个团队成员一箱La Croix作为（异常高的）600点的奖金（通常，挑战如果是极其容易的100点，如果是极其困难的500点）。通过逆向脚本和抓取聊天，资格赛有效的相同过程在这里也有效。剩下的就是旋转你的typeball并观察哪个字母在底部。

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

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