Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions
Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions
复制标题
数据独立的内存硬功能：新的攻击和更强大的结构
DOI：
10.1007/978-3-030-26951-7_20
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zhou, S.
中科院分区：
文献类型：
--
作者：
Blocki, J;Harsha, B;Kang, S;Lee, S;Xing, L;Zhou, S.
难记忆函数 (MHF) 是一种关键的密码原语，是中等昂贵的密码哈希算法和平等工作证明设计的基础。在过去的几年里，人们提出了几个越来越严格的MHF目标，包括要求MHF具有高顺序时空（ST）复杂性、并行时空复杂性、摊销区时（aAT）复杂性和持续空间复杂性。数据独立内存硬函数 (iMHF) 在密码散列上下文中特别受关注，因为它们自然地抵抗侧通道攻击。 iMHF 可以使用具有节点和低入度的有向无环图 (DAG)G 来指定，并且可以使用卵石游戏来分析 iMHF 的复杂性。最近，阿尔文等人。 [ABH17]构建了一个名为 DRSample 的 DAG，其复杂度至少为 aAT。 DRSample 渐近优于所有先前的 iMHF 结构，包括密码散列竞赛的获胜者 Argon2i（aAT 成本），尽管这些边界中的常数人们知之甚少。我们展示了 Boneh 等人的贪婪鹅卵石策略。 [BCS16] 对 DRSample 特别有效，例如 aAT 成本是。事实上，我们的实证分析推翻了Alwen等人先前的结论。 DRSample 对已知的卵石攻击提供了更强的抵抗力，具有实用价值。我们通过使用位反转图扩展 DRSample 来构建新的 iMHF 候选（DRSample+BRG）。然后，我们证明该构造在每个 MHF 标准下都是渐近最优的，并且我们凭经验证明我们的 iMHF 对已知的卵石攻击提供了最佳的抵抗力。例如，我们表明任何并行卵石攻击要么具有 AT 成本，要么至少需要 DAG 上的卵石步骤。这使得我们的构造成为第一个实用的 iMHF，具有强大的持续空间复杂性保证，并立即意味着任何并行卵石都具有 AT 复杂性。我们还证明任何顺序卵石攻击（包括贪婪卵石攻击）都有一个 AT 成本，如果一个合理的猜想成立，任何并行卵石攻击都有一个 AT 成本——iMHF 的最佳可能界限。我们实施了新的 iMHF 并证明它与 Argon2 一样快。在此过程中，我们提出了对 Argon2 轮函数的简单修改，使攻击者的 aAT 成本增加了近一个数量级，而不增加 CPU 上的运行时间。最后，我们给出了一个 pebbling 缩减，证明在并行随机预言模型 (PROM) 中，评估像 Argon2i 或 DRSample+BRG 这样的 iMHF 的成本是由底层 DAG 的 pebbling 成本给出的。先前的鹅卵石减少假设 iMHF 轮函数在散列之前连接输入标签，并且不适用于实际的 iMHF，例如 Argon2i、DRSample 或 DRSample+BRG，其中输入标签被异或在一起。
Memory-hard functions (MHFs) are a key cryptographic primitive underlying the design of moderately expensive password hashing algorithms and egalitarian proofs of work. Over the past few years several increasingly stringent goals for an MHF have been proposed including the requirement that the MHF have high sequential space-time (ST) complexity, parallel space-time complexity, amortized area-time (aAT) complexity and sustained space complexity. Data-Independent Memory Hard Functions (iMHFs) are of special interest in the context of password hashing as they naturally resist side-channel attacks. iMHFs can be specified using a directed acyclic graph (DAG)Gwithnodes and low indegree and the complexity of the iMHF can be analyzed using a pebbling game. Recently, Alwen et al. [ABH17] constructed a DAG called DRSample that has aAT complexity at least. Asymptotically DRSample outperformed all prior iMHF constructions including Argon2i, winner of the password hashing competition (aAT cost), though the constants in these bounds are poorly understood. We show that the greedy pebbling strategy of Boneh et al. [BCS16] is particularly effective against DRSample e.g., the aAT cost is. In fact, our empirical analysisreversesthe prior conclusion of Alwen et al. that DRSample provides stronger resistance to known pebbling attacks for practical values of. We construct a new iMHF candidate (DRSample+BRG) by using the bit-reversal graph to extend DRSample. We then prove that the construction is asymptotically optimal under every MHF criteria, and we empirically demonstrate that our iMHF provides the best resistance toknownpebbling attacks. For example, we show that any parallel pebbling attack either has aAT costor requires at leaststeps withpebbles on the DAG. This makes our construction the first practical iMHF with a strong sustained space-complexity guarantee and immediately implies that any parallel pebbling has aAT complexity. We also prove that any sequential pebbling (including the greedy pebbling attack) has aAT costand, if a plausible conjecture holds, any parallel pebbling has aAT cost—the best possible bound for an iMHF. We implement our new iMHF and demonstrate that it is just as fast as Argon2. Along the way we propose a simple modification to the Argon2 round function that increases an attacker’s aAT cost by nearly an order of magnitude without increasing running time on a CPU. Finally, we give a pebbling reduction that proves that in the parallel random oracle model (PROM) the cost of evaluating an iMHF like Argon2i or DRSample+BRG is given by the pebbling cost of the underlying DAG. Prior pebbling reductions assumed that the iMHF round function concatenates input labels before hashing and did not apply to practical iMHFs such as Argon2i, DRSample or DRSample+BRG where input labels are instead XORed together.
登录
查看更多内容
密码分析攻击的全部成本
影响因子：
3
作者：
M. Wiener
通讯作者：
M. Wiener
DOI：
--
发表时间：
2017
期刊：
Theory of Cryptography Conference
影响因子：
--
作者：
J. Alwen;Björn Tackmann
通讯作者：
Björn Tackmann
DOI：
10.1007/978-3-662-45608-8_16
发表时间：
2014-12
期刊：
--
影响因子：
--
作者：
C. Forler;S. Lucks;Jakob Wenzel
通讯作者：
C. Forler;S. Lucks;Jakob Wenzel
抗 ASIC 的带宽硬函数
DOI：
--
发表时间：
2017
期刊：
Theory of Cryptography Conference
影响因子：
--
作者：
Ling Ren;S. Devadas
通讯作者：
S. Devadas
黑白鹅卵石和图形分离
影响因子：
0.6
作者：
Thomas Lengauer
通讯作者：
Thomas Lengauer