宜昌优化网站建设,wordpress 配置文件,wordpress重新设置域名,营销网站结构1. 引言
在 2024 年 11 月 14 日的 Devcon 大会上#xff0c;以太坊基金会、Phantom.zone 和 0xPARC 联合发起了一个 1 万美元悬赏#xff0c;奖励给成功破解他们的 不可区分混淆#xff08;Indistinguishability Obfuscation#xff0c;简称 iO#xff09; 实现的人。详…1. 引言
在 2024 年 11 月 14 日的 Devcon 大会上以太坊基金会、Phantom.zone 和 0xPARC 联合发起了一个 1 万美元悬赏奖励给成功破解他们的 不可区分混淆Indistinguishability Obfuscation简称 iO 实现的人。详情见 obfustopia.io 。
本文简要介绍了什么是不可区分混淆iO、该悬赏的背景以及Killari是如何成功破解它的过程。
2. 何为不可区分混淆
不可区分混淆Indistinguishability ObfuscationiO是一种密码学方案旨在将一个程序转化为**“黑盒”**。这意味着
混淆后的程序可以被自由分享和执行但其内部结构和逻辑对外界完全隐藏。用户可以无限次运行该程序但无法推断出它的内部逻辑或实现细节。
乍一看这个概念似乎不太现实。毕竟如果可以随意运行程序难道不能通过穷举输入并分析输出来反推出它的功能吗但实际上大多数程序的输入空间巨大穷举测试几乎是不可能完成的任务。
iO 最显而易见的应用场景是数字版权管理digital rights managementDRM。如一个游戏可以经过混淆处理后发布用户可以自由游玩但无法逆向工程其代码。
一个不那么显然、但更令人兴奋的用例是
安全地将秘密嵌入到混淆程序中。
举个例子一个私钥可以隐藏在一个经过 iO 混淆的程序中。这个程序可以作为智能合约运行只有满足特定条件的消息才会被签名。这样既能保证密钥的安全又能严格限制其使用条件。进一步来说这甚至使智能合约能够在区块链环境之外运行从而大幅拓展应用边界。
理论上iO 有潜力成为 几乎所有密码学协议的基础见2013年论文How to Use Indistinguishability Obfuscation: Deniable Encryption, and More因此它也被称作 “万能协议God Protocol”见下图。它的通用性和强大能力让它成为密码学领域的革命性概念。但也正因为如此它的“过于美好”引发了不少怀疑。
上图源自0xPARC团队2024年7月30日博客 Programmable Cryptography (Part 1)。
2. iO 真能实现吗
当Killari第一次接触不可区分混淆iO这个主题时——其对iO完全一无所知——对iO的可实现性深感怀疑。从纯粹的理论角度看它几乎不可能实现。当年第一次接触 零知识证明技术 时也有过类似怀疑。然而在深入研究之后Killari相信零知识证明不仅在理论上是可靠的在很多实际场景中也已得到应用验证。
零知识技术已经证明是可行且具有巨大影响力的但Killari仍然不确定 iO 能否真正实现。不过仍然抱有希望因为如果 iO 真能实现将会开启密码学领域的巨大突破。
尽管 iO 潜力巨大但到目前为止尚未出现实用的不可区分混淆实现。学术界已经提出过多种方案但最终都被证明存在缺陷或不安全。
也就是说目前已经有理论证明2020年论文Indistinguishability Obfuscation from Well-Founded Assumptions表明在经过良好验证的密码学假设下iO 是可能存在的。这个证明确认了 iO 在原理上是成立的但它并不保证在实践中可以高效实现。
需要注意的是完全黑盒混淆器即一个可以混淆任意程序且除输入输出行为之外不泄露任何信息的工具已被证明不可能存在见2013年论文How to Use Indistinguishability Obfuscation: Deniable Encryption, and More。不过iO 是一个更狭义、更可实现的目标。
iO 的要求并不是隐藏程序的所有内部细节而是确保两个功能相同的程序在混淆后无法区分。
2. Obfustopia 的 iO 实现悬赏部分
为了这次悬赏项目方创建了一个包含 1024 个操作的随机程序然后对其进行了混淆处理使其膨胀到超过 20 万个操作。 这个悬赏的目标是
将这个混淆程序优化还原为功能相同但包含 1024 个操作或更少的版本。
需要特别说明的是
悬赏的目标并不是找出程序中隐藏的秘密也不是弄清楚它的功能或行为纯粹是为了将程序还原为更高效的表示形式。
当然一旦找到了更小、更优的版本理解程序隐藏部分的内容也会变得容易得多。
该程序是直线代码程序straight-line code即没有循环和分支。执行从第一行开始顺序进行直到最后一行。程序的输入是一个 64 位布尔数组如[true, false, true, false, ...]对其进行一系列变换后输出一个 64 位结果。 这样的设计避免了停机问题halting problem程序也不是图灵完备的。
Obfustopia 的 iO 实现——https://github.com/phantomzone-org/obfustopiaRustPython采用了一种称为 局部混合local mixing 的方法进行程序混淆其原理在2024年论文 Towards general-purpose program obfuscation via local mixing 中进行了描述。 虽然该论文内容较为晦涩但这篇由 Janmajayamall 撰写的摘要Program obfuscation via local mixing提供了更容易理解的解释。
以下为对该协议的简化版总结
1生成随机程序电路2混淆该随机程序
2.1 生成随机程序电路
与其说是对一个已有程序进行混淆不如说这个悬赏任务本质上是生成一个随机程序然后再对它进行混淆处理。 该程序是使用reversible boolean gates可逆布尔门构建的这意味着这些操作可以通过再次执行相同操作来恢复原状。 举个例子
v0 v0 XOR v1这里有两个布尔变量 v0 和 v1。对 v0 和 v1 执行 异或 (XOR) 操作并将结果存回 v0。其对应的真值表如下
v0v1v0 XOR v1000011101110
如果连续执行两次该操作
v0 v0 XOR v1
v0 v0 XOR v1最终结果仍然是原始的 v0。这可以通过以下方式直观理解
v0 (v0 XOR v1) XOR v1 v0 XOR v1 XOR v1 v0 XOR (v1 XOR v1) // XOR operations can be computed in any order v0 XOR (FALSE) // XOR with itself is always false (check above truth table) v0然而如果使用不可逆门——如true gate——直接赋值 true
v0 true则再次执行该操作v0 永远都是 true无法恢复原本的 v0。这种操作属于不可逆操作。 虽然可逆门在破解电路时并不重要但它们对于混淆程序的生成过程来说是至关重要的。
2.2 混淆该随机程序
接下来使用 局部混合Local Mixing 方法对这个随机生成的程序进行混淆。这种方法的核心思想是
选取程序中的一小部分将其改写成不同的样子同时保持功能不变。
一个简单的做法是插入一些对最终结果没有影响的额外操作比如插入两个冗余的门操作
v0 v0 XOR v1
v0 v0 XOR v1由于两次异或操作互相抵消最终不影响程序功能。但这种方法并不理想因为攻击者很容易识别并移除这些冗余操作。
为了实现真正的 iO不可区分混淆需要采用更强健的混淆方式。
局部混淆包含两个阶段
1膨胀阶段Inflationary stage 选择程序中的一个小部分并通过插入冗余逻辑使其 “膨胀”看起来更复杂。2揉捏阶段Kneading stage 将这些局部修改打散、分散到整个程序之中就像揉面团一样使得局部结构与整体深度混合进一步增加混淆难度。
3. 破解Obfustopia 的 iO 实现
当意识到这个悬赏本质上是一个优化问题时立刻想到了一些可能破解混淆的方法。
3.1 攻击思路一 —— 猜测程序功能
Killari对攻击 iO 协议的第一个直觉是这样的 如果给我一个混淆后的程序我可以无限次运行它并观察它的行为那么混淆真的安全吗
举个简单例子 假设这个混淆程序实际上只做了如下简单操作
v0 v1 AND v2那么完全可以运行这个程序上百万次使用各种随机输入最终猜测出它执行的是 AND 操作。
当然这种攻击方式有明显的反驳理由
这是一个概率性的攻击。或许可以“相当有信心”地猜测这个程序是 AND 操作但无法百分之百确认除非穷举所有可能输入并验证所有输出行为。更重要的是即便这个程序看起来像一个简单的 AND 操作也可能存在特定输入时它表现得像 OR 操作。要发现这种情况要么在输入选择上非常幸运要么能够遍历所有可能的输入组合。为了防止这种概率性攻击密码学中提出了穿孔程序Punctured Program的概念。相关原理可参考2013年论文 How to Use Indistinguishability Obfuscation: Deniable Encryption, and More。穿孔程序技术就是用来防御攻击者通过概率性猜测来推断程序行为的。
在 Obfustopia.io 这个悬赏挑战中清楚地知道
穷举完整输入空间是不可能的因为 64 位输入对应的可能组合数量是 2 64 1.8446744 × 10 19 2^{64} 1.8446744 \times 10^{19} 2641.8446744×1019
不过也可以确信
这个随机生成的程序不太可能只是一个简单程序除了极少数特定输入外其行为应该是一致复杂的。
考虑到原始程序包含 1024 个操作如果试图盲目猜测正确的 1024 个操作组合来还原这个程序这显然是不切实际的。虽然没有精确计算过针对 64 位输入的 1024 操作程序可能数量但非常确信这个空间庞大到无法通过穷举方式完成破解。
3.2 攻击思路2 —— 迭代化简
这个被混淆的程序大致看起来像下面这样实际上长度要长得多
1: v20 ^ v51
2: v15 ^ \!v2
3: v1 ^ \!v42
4: v33 ^ (v40 v51) | (\!v40 \!v51)
5: v50 ^ \!v32
6: v60 ^ v29
7: v13 ^ v26
8: v46 ^ \!v43
9: v48 ^ (v13 v19) | (\!v13 \!v19)
10: v12 ^ v6
11: v29 ^ v22
12: v50 ^ \!v32 这里^ 表示异或赋值操作含义是 左边变量 左边变量 ⊕ 右边表达式 \text{左边变量} \text{左边变量} \oplus \text{右边表达式} 左边变量左边变量⊕右边表达式
同时 表示与AND操作| 表示或OR操作\! 表示取反NOT操作。
如果仔细观察会发现有如下情况
5: v50 ^ \!v32
12: v50 ^ \!v32 这两个操作在程序中出现了两次且在这两次操作之间
v50 和 v32 均未被其他操作使用或修改
这意味着可以安全地移除这两条语句。原因是 ( a ⊕ b ) ⊕ b a (a \oplus b) \oplus b a (a⊕b)⊕ba
连续两次对同一个变量进行相同的异或操作等价于无操作identity operation。
移除后程序被简化为
1: v20 ^ v51
2: v15 ^ \!v2
3: v1 ^ \!v42
4: v33 ^ (v40 v51) | (\!v40 \!v51)
5: v60 ^ v29
6: v13 ^ v26
7: v46 ^ \!v43
8: v48 ^ (v13 v19) | (\!v13 \!v19)
9: v12 ^ v6
10: v29 ^ v22 现在这个程序只有 10 条指令相比原来的 12 条明显更简洁。
Obfustopia.io 悬赏项目中的混淆程序包含超过 20万条操作指令。
是否可以采用这种“迭代简化”的方法将整个程序逐步缩减至 1,024 条以内
更有趣的是
可以任意选取程序中连续的一小段作为“子程序”。对这个子程序进行输入输出分析看看能否进一步简化。如果可以简化就将其简化版本替换回原程序中。每次进行这样的操作整个程序就会进一步变小。
这个方法称为 窥孔优化Peephole Optimization是很多编译器都会采用的标准优化技术。
这个迭代过程让Killari开始质疑局部混合Local Mixing方案是否足够稳健。
一个合格的 iO 程序不应允许通过这种方式逐步“拆掉”混淆结构。
iO 的理想状态应与大多数密码学系统的工作原理类似
程序中的每个部分都高度依赖于整体结构移除任何局部片段都会破坏程序整体功能。
换句话说iO 混淆设计应具备“结构紧密耦合性”避免被逐步剥离还原。
3.3 编写窥孔优化Peephole Optimization攻击程序
3.3.1 创建彩虹表Rainbow Table
首先着手编写一个 彩虹表Rainbow Table因为性能对于这个任务至关重要。
这个彩虹表包含了所有可能的、使用不超过三条操作、涉及不超过四个变量的程序组合。 下面是一个非常粗糙但足够用的程序示例它可以枚举所有针对指定变量数量在本例中是 4 个变量的3个操作组合
function* generateAllGates(numberOfVariables: number) {for (let a 0; a numberOfVariables; a) {for (let b 0; b numberOfVariables; b) {for (let target 0; target numberOfVariables; target) {for (let gate_i 0; gate_i 16; gate_i) {yield { a, b, target, gate_i }}}}}
}随后又针对 0 个操作、1 个操作、2 个操作的情况分别做了类似处理。
最终这个彩虹表生成的文件大小超过了 1 GB。
借助这个彩虹表可以高效地回答以下类型的问题 “对于一个输入和输出都最多包含四个变量的程序如何用最少的操作次数来表示它假设最优程序可以用不超过三条操作表示” 3.3.2 利用彩虹表
为了测试这种攻击方法使用该悬赏提供的工具生成了一个简单的 4 位混淆程序。 这一过程帮助极大因为能够访问生成原始混淆程序的源码能更容易理解问题本质同时也帮助测试自己的程序逻辑是否正确。
接下来开始对混淆程序进行迭代简化
每次提取2-10 行代码的子程序如果这个子程序的真值表在彩虹表中存在对应项就用最优版本替换掉原来的子程序。
结果非常成功 Killari成功破解了所有自己生成的这些简单 4 位混淆程序。
3.3.3 破解真实程序
然而仍然面临一个重大挑战悬赏项目的目标程序是 64 位输入的而目前仅能处理 4 位的情况。
如何才能将这种方法推广到更大的程序上呢
这里的关键在于
不需要一次性破解整个 64 位程序而是聚焦于包含较少变量的小型子程序。
实际上大部分混淆程序都由仅使用少数几个变量的小型子程序组成。 此外每个逻辑门最多涉及 3 个变量 —— 比如v0 v1 AND v2。
这种形式正是变量依赖最复杂的逻辑门。
于是对程序做了优化
不再考虑所有 2-10 行的子程序组合只考虑涉及不超过 4 个变量的子程序。
调整完成后开始将这个攻击方法应用于真实目标程序。
出乎意料的是
成功将原始程序从 20 多万个逻辑门压缩到了不足 10 万个逻辑门优化幅度超过 50%
这个阶段的成果极大增强了对于彻底破解这个混淆方案的信心。
3.3.3.1 行顺序Row Order
Killari还意识到一个由顺序执行操作组成的程序可以用多种不同的方式编写。 特别是——可以交换彼此之间没有依赖关系的行顺序。 如
1: v1 ^ v3
2: v60 ^ v29
3: v13 ^ v26和
1: v1 ^ v3
2: v13 ^ v26
3: v60 ^ v29实际上是完全相同的程序但之前的彩虹表实现却把它们视为不同的程序因为只比较连续的代码行。
为了应对这个问题实现了一个行交换器row swapper它会扫描整个程序并随机交换不互相依赖的行。 引入这一机制后重新运行了攻击结果发现——优化效果更进一步了
3.3.3.2 变量缩减攻击Variable Reduction Attack
在应用了彩虹表攻击和行交换器之后Killari意识到还可以针对涉及超过 4 个变量的子程序进一步优化。
Killari想出了一个策略
针对包含 5-8 个变量的子程序可以随机用另一个子集内的变量替换其中的某个变量。
如 如果有一个子程序涉及变量
[v0, v1, v2, v3, v4]可以将 v0 替换成 v4从而让程序只使用变量
[v1, v2, v3, v4]然后可以分别计算两个版本程序的真值表进行对比。 如果两个真值表完全相同说明可以移除这个变量进而简化这个子程序。
⚠️ 这种方法虽然不能减少操作次数但可以减少变量数量。
然而——当子程序只涉及 4 个变量时之前的彩虹表攻击又可以派上用场。 这种变量缩减策略比单纯依赖彩虹表更具可扩展性即使涉及多达 10 个变量真值表也只有 2 10 1024 2^{10} 1024 2101024 行计算起来完全可行。
幸运的是并不需要再进一步增加变量数量因为混淆程序已经被破解了。 Killari成功地将这个程序缩减到了1,023 条操作比原始程序少 1 条
Killari按照悬赏要求的格式打包了这个简化程序并使用悬赏提供的工具将其与去混淆后的参考程序进行对比。
3.3.3.3 程序一致性验证
检查两个程序是否完全一致并不是一件简单的事情。 在悬赏挑战中这一过程通过随机采样输入然后验证两个程序的输出是否相同来完成。
Killari多次运行这一检测并不断增加检测次数。 Killari对破解结果非常有信心于是将结果提交给了悬赏主办方他们也确认混淆已经被破解。
随着后续的优化进行Killari 最终将程序压缩到了不到 800 个逻辑门。
这意味着找到了一个比作者原始伪随机程序还要更优的版本。
4. 后续优化Further optimizations
Killari对这个解混淆器最大的抱怨是
它不是确定性的。 会不断随机打乱程序行顺序然后测试是否能找到更优解接着反复尝试。这种做法非常低效。
事实上Killari还有很多攻击思路根本没来得及实现因为目前这套攻击方案已经足够破解悬赏了。
Killari一直在慢慢优化和改进这个解混淆器可在 https://github.com/KillariDev/cryptopia-deobfuscatorTypeScript 找到最新版代码。 ⚠️ 需要注意的是这个版本的代码不是破解悬赏时用的原始版本而是一个更高效、更智能的后续版本。
5. 展望The Road Ahead
在与悬赏项目的作者交流后他们承认原始的混淆器存在一个漏洞这使得整个挑战更容易被破解。 他们正在开发一个新的版本声称将能够防御本文所采用的这种攻击方法。
有趣的是
在 Devcon 大会期间Barry Whitehat 曾经提出是否存在类似的攻击方法。 当时主办方的回答是——不可能。结果 Barry 是对的。
非常期待测试新的混淆系统并且打算持续不断地尝试攻破它直到要么被彻底反驳要么终于拥有一个真正安全的“不可区分混淆”Indistinguishability ObfuscationiO密码系统。
不过需要强调的是 “我无法破解一个密码系统 ≠ 它就是安全的。” 比如Local Mixing 方法本身并没有被证明是安全的。 即使在正确实现的情况下它也可能存在未被发现的漏洞。
这正是密码学探索道路上最有趣的一部分。
参考资料
[1] Killari 2025年2月5日博客 Breaking the $10,000 iO Bounty: My Journey to Crack an Indistinguishability Obfuscation Implementation
