重新审视客户端谜题难度概念与DoS抗性

### 重新审视客户端谜题难度概念与DoS抗性 #### 1. 引言 密码学谜题是一类适度困难的问题，需要投入大量的计算和/或存储资源才能解决。其典型用途是在某些协议执行过程中平衡参与者的成本，例如在SSL/TLS、TCP/IP、通用认证协议、反垃圾邮件等场景中防止资源耗尽。此外，谜题还可作为其他应用中的工作量证明，如时间戳服务，或者用于未来加密等。 目前，大多数与谜题相关的文献主要集中在提供各种谜题构造，这些构造往往具有额外的创新特性。比如，不可并行化的谜题能防止攻击者利用分布式计算来求解；为缓解求解者之间的计算差异，有些谜题依赖内存使用而非CPU速度。 然而，令人惊讶的是，为谜题设计正式的安全概念这一工作至今较少受到关注。此前有两项相关研究：Chen等人首次对谜题的安全属性进行了正式研究，提出了谜题难度和谜题不可伪造性两个属性；Stebila等人注意到单谜题难度在实际应用中可能不足以保证安全，因为在实际场景中可能需要限制攻击者同时解决多个谜题的速度，于是提出了一个考虑同时解决多个谜题的谜题难度概念，并证明了HashInversion和HashTrail两种构造满足该概念。但本文认为，Stebila等人提出的安全定义存在问题，其定义不完整，未考虑边界的紧密度，且严格来说，现有方案无法满足该定义，相关的安全证明也存在错误。 本文的主要贡献在于提出了新的谜题难度安全概念，区分并形式化了两种不同类型的谜题安全（最优和理想），并正确定义了解决单个谜题与解决多个谜题之间的关系。同时，通过分析两种流行的谜题构造（HashTrail和HashInversion），展示了这些概念的适用性。此外，还研究了现有的DoS安全定义，发现其不够严格，并提出了一个替代定义。 #### 2. 现有定义和证明的不足 ##### 2.1 现有谜题难度定义的弱点 Stebila等人定义，若谜题满足攻击者的成功概率小于等于ϵk,d,n(·)，且ϵk,d,n(t) ≤ ϵk,d,1(t/n)，则该谜题为ϵk,d,n(·)-强难度谜题。但这个定义存在多个问题： - **边界紧密度问题**：“强难度”实际上是关于函数ϵ的性质，而ϵ只是谜题难度的上界，不一定是最紧的上界。可能会出现找到一个使谜题满足强难度的边界，但对于更紧的边界，谜题却不满足强难度的情况。例如时间锁谜题，设定一些参数后，按照一个宽松的边界，谜题是强难度的，但使用更精确的边界时，谜题实际上并非强难度。 - **条件必要性问题**：即使边界是紧的，Stebila等人提出的条件也不是使谜题具有难度保持性的必要条件。令人惊讶的是，HashTrail和HashInversion谜题都不满足该条件，但它们都可以被证明具有难度保持性。 - **定义的一般性问题**：在多谜题安全游戏中，挑战谜题可能包含两个相同的谜题，此时解决n个谜题所需的努力应小于n倍解决单个谜题的努力。因此，定义应允许一定的松弛，即|ϵk,d,n(t) - ϵk,d,1(t/n)| ≤ k−ω(1)。时间锁谜题似乎满足这一标准，但基于哈希的谜题（如HashTrail和HashInversion）通常不满足。 ##### 2.2 现有安全证明的缺陷 通过检查Stebila等人的安全证明发现，HashTrail谜题的难度边界过于宽松，HashInversion谜题的难度边界是错误的。以HashInversion谜题为例，假设解决两个3位的谜题，按照Stebila等人给出的边界，攻击者在最多11步内解决谜题的概率上限约为0.66，但实际使用朴素算法解决两个谜题的成功概率约为0.76，这表明原证明存在缺陷。 下面用表格展示不同情况下的对比： | 谜题类型 | 原定义边界 | 实际情况 | | ---- | ---- | ---- | | HashTrail | 过于宽松 | - | | HashInversion | 错误 | 朴素算法成功率更高 | #### 3. 谜题难度 为了形式化谜题难度及相关概念，我们按以下步骤进行： - 定义解决多个谜题的常规游戏，并将攻击者的优势限制在ϵk,d,n(t)。 - 定义谜题最优性，即除了一些可忽略的因素外，没有攻击者能比谜题自带的求解算法更有优势地解决一个或多个谜题。如果一个谜题是最优的，且按照常规方式对每个谜题运行求解算法来解决多个谜题，那么该谜题具有难度保持性，即解决n个谜题的难度是解决一个谜题的n倍。 - 定义理想谜题，即除了一些可忽略