使密码哈希攻击变得不经济

Question

考虑到内存和运行时之间的权衡，这也许是一个关于复杂性的抽象问题，我想知道是否有可能只限制两个极端的方法来达到最佳的效率，从而降低对散列的攻击的经济性。

背景

我参加了最近出版的一次研讨会，题为“最大记忆--硬的1”，作者集中讨论了由Percival设计并在RFC 7914中描述的一种简单的候选内存硬功能(MHF)。

从摘要来看：

在并行随机甲骨文模型中，它的累积内存复杂度(cmc)为$\Omega(n^2 cdot w)$，其中$w$和$n$分别是底层哈希函数的输出长度和调用次数。

此外，在导言中：

在本工作的第五节中，我们还证明了抽象scrypt的游戏在并行累积鹅卵石复杂度上的一个最优$\Omega(n^2 \cdot w)下界:我们考虑长度$n$的一条路径，而对手必须在该图上随机选择的节点上鹅卵石$n$，其中第一个挑战节点只有在挑战$i−1$的节点被鹅卵形时才会显示出来。这已经在$cc_{mem}$上给出了一个最优的$cc_(n^2 \cdot w)$下限，用于只允许存储整个标签而不存储任何函数的敌人。

据我理解，对手可能会制定一种在内存和运行时复杂性之间进行适当折衷的策略，例如，存储用于$X_0、X_1、\dots、X_{n−1}$的鹅卵石只为偶数$i$存储，从而将最坏的情况内存使用率减半，同时也具有最坏的情况运行时，但总内存·时间成本仍与以前相同。

问题

对于单个系统，我认为硬件成本与CPU性能或星载内存大小有关是非线性的，也就是说，代表任一频谱极限的组件可能会以指数级方式昂贵。因此，为了降低回报率或增加攻击者所期望的必要的资本投资，我们可能希望降低中档硬件的可用性，否则使用这些硬件将是最经济的。

为了可视化我的基本想法，我在下面包含了一个粗略的图表，其中x和y轴是内存和时间使用。在绿点处与紫色线相交的橙色矩形的体积表示任何配置的总内存·时间成本，例如，如果您有足够的内存，就可以以$\frac{1}{2}$ time单元计算散列。我想知道是否可以提出这样一个问题，使内存·时间成本与红色曲线相反，从而使对手进一步走向硬件极值，以达到最佳的内存·时间成本，同时损害硬件成本。

https://www.desmos.com/calculator/rpjseuy0sj

也许有一些研究，你们中的一些人可能知道，从经济的角度来看，最优的有效结果，即考虑硬件投资，运营成本，每个解决方案的预期回报。当使用需要工作证明的密码货币时，我想这听起来像是矿工优化问题，但我对激励攻击者或骗子的经济学更感兴趣。

@misc{cryptoeprint:2016:989,
author = {Jo\"el Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro},
title = {Scrypt is Maximally Memory-Hard},
howpublished = {Cryptology ePrint Archive, Report 2016/989},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/989}},
}

基本

是否有任何函数使内存或运行时的线性组合变得比单独提交内存或计算速度优化的效率更低，从而总是使中程硬件不适合进行有利可图的攻击？

Answer 1

我想这个问题已经有一段时间了，但没有一个令人满意的答案:这似乎是一个在文献中从未真正考虑过的问题(至少在理论密码界是如此)。

顺便说一句，我今天早上刚刚检查了ePrint归档文件，无意中发现了今天添加到归档中的本论文，它完全集中在您的问题上。它引入了一种新的复杂性度量，它解释了时间-内存交换不与硬件成本成线性关系的事实。我还没有详细阅读(我打算读)，但作者是记忆硬功能方面的领先研究人员之一(作者的子集开发了分析MHFs的理论模型，描述了对Argon和Balloon最著名的攻击，给出了新的构造，并证明了氪的最大记忆硬度)。应该值得一读。