严格的内存困难型哈希函数

发表于 更新于 分类于 本文字数： 4.4k 阅读时长 ≈ 4 分钟

原文地址

摘要

本文介绍严格内存困难型函数的概念。严格内存困难型函数是内存困难性函数的一个扩展，当用于实际计算的内存比预定义的最优内存略微减少时，会使函数的计算指数级变慢或根本不可行。严格内存困难型函数的主要应用是证明在一定的时间间隔内或在一定的计算中使用了一定的内存。这反过来可以用来证明设备的内存区域不包含隐藏数据。其他应用场景包括密码散列和工作证明。我们提供了SeqMemoHash和RandMemoHash两个在随机预测模型下的连续内存困难函数

介绍

加密哈希函数易于计算，但很难反推，同时保留了大量源熵。加密哈希函数称为许多其他函数的基石，比如密钥生成函数（KDF）。密钥生成函数使用伪随机函数从密钥(如主密钥)中派生一个或多个密钥。基于密码的KDFs(PKDF)(也称为密码散列函数)使用密码或密码短语作为主密钥。PKDFs通常用于密钥扩展。密钥扩展是用来在网站中实现更安全的密码认证。该网站不存储原始密码，而是利用PKDF产生一个散列密钥。如果攻击者能够访问所有网站用户的派生密钥列表，他可能尝试执行字典攻击或暴力攻击。这需要为每个密码候选项计算PKDF，并将结果与散列值进行比较。为了降低这些攻击的有用性，于是设计了密钥扩展函数，使它们要么需要昂贵的计算，要么需要大量的RAM。通过对密钥进行递归哈希产生的摘要和一个随机变量异或可以实现这种昂贵计算，比如PBKDF2体制（异或是为了尽可能少的减少熵）。scrypt算法是密钥扩展算法的一个例子，该算法可以配置为需要使用一定数量的RAM才能有效地计算，并且每个内存访问都依赖于前一个内存访问。这使得破解机的硬件实现不那么吸引人，因为这种内存访问模式既不能并行化，也不能流水线化。尽管如此，即使计算期间使用的内存小于最优值，scrypt函数仍然可以快速计算。密码散列函数不需要防止用更少的内存计算该函数：它所期望的性能是，用小于最优内存的函数计算会使计算速度足够慢，因此创建具有这种特性的破译机器没有经济效益。在scrypt中，计算时间随着内存减少的数量线性增长，直到剩下一个非常小的内存时，计算将变得不可能。相比之下，在严格的内存困难型函数(SMHF)中，如果从最优值中删除超过一个常数的少量内存，计算会立即变得不可行，甚至不可能。在随机预测模型下，我们给出了SeqMemoHash和RandMemoHash这两个严格的内存困难型函数。这些函数可以用作密码散列函数，但它们可能达不到高的吞吐量，因为它们需要哈希函数来支持严格属性，而scrypt只需要一个一致的强序函数(一种如果按不同的顺序计算运算，其输出很可能不同的函数)。不过可以修改我们的方案，在不影响实际安全性的前提下通过减少哈希函数的轮数来实现更高的吞吐量。例如SHA-256减少到16轮回比比Salsa20/8快4倍。

在软件认证中的应用

假设验证者希望在目标计算机上验证软件，并且已经有一个验证方法来验证正在运行或已安装的软件是否与预定义的条件相同（比如通过哈希）。但是认证过程还必须验证空闲内存中没有隐藏任何内容，无论是在易失性存储还是非易失性存储中。一个简单的但不是最优的方案的是，验证者发送一个真正的随机数序列来填充未使用的内存，然后执行已知的软件验证阶段，最后检查内存中是否存在相同的序列。SMHF可以在没有网络传输随机值的情况下提供相同的功能，这可能会造成非常高的开销。验证器向认证计算机提供种子，然后计算机计算一个伪随机数序列，该伪随机数序列使用多轮SMHF填充未使用的内存。此填充过程将花费比通信延迟更高的量时间。然后目标计算机返回上一轮SMHF的散列摘要，由验证器进行验证。在已知的软件认证阶段结束后，验证者向目标计算机发送一个挑战。计算机必须使用与SMHF的最后一轮输出相连接的挑战的散列进行响应（应该存储在内存中）。如果内存中没有填充此数据，并且目标计算机试图重新计算的话，这种行为将被探测到，因为这样做的延迟会非常大。

严格内存困难型函数

定义1： 针对内存大小为n的随机存取机，如果他在执行T(n)操作时T(n)=O(n)，提出了一种RAM-fast算法

定义2： 如果一个函数可以用随机存取机的RAM-fast算法来计算，那么它就是RAM-fast。

定义3： 随机存取机器上的内存困难型算法是这样一种算法：他使用大小为n的空间和T(n)操作，n=Ω(T(n)^1−ϵ)

定义3： 如果一个函数是RAM-fast而且可以在随机存取机上一n的空间通过内存困难型算法执行，但是不能在并行随机存储机上以小于n-x的空间运行，那么他是一个内存困难型函数。

SeqMemoHash

SeqMemoHash是我们第一个SMHF提议。设H为单向压缩函数。设D为哈希摘要大小。设s是一个大小等于D的主秘密。设M[i]为为内存数组(0≤i< N)，其中内存单元包含D个字节。设R是函数的轮数。该算法就地计算，输出为内存数组M。对于PoW或密码散列，取内存的最后z块(M[N-z]..M[N-1])，再用一个安全的加密哈希函数进行哈希，得到最终结果。

SeqMemoHash(s,R,N):
    Set M[0]:=s
    For i:=1 to N-1 do set M[i]:=H(M[i-1])
    For r:=1 to R do
        For b:=0 to N-1 do 
            M[b]:=H(M[(b-1+N) mod N] || M[b]) //注：||表示拼接

如果设置R≥N+1，那么SeqMemoHash是严格内存困难型函数。现在我们尝试一个非正式的证明。设c为压缩函数的工作状态空间。如果可用内存低于N*D+c，则计算最后一轮时需要存储一个大小为D的临时状态，而且至少计算前一轮两次。第二次计算必须要n*D+c-D的空间。同样的参数也可以随着内存减少应用到前一轮。经过N轮后，由于没有足够的暂存空间来计算压缩函数的工作状态，使得计算变得不可行的。更仔细的分析表明，每轮执行的回溯调用的数量随着回溯深度的增加而增加，因为每轮都需要存储临时散列摘要，从而减少了调用方的轮临时存储空间。这个问题类似于寄存器分配问题，作者找不到求最优解所需哈希数的精确递归式。

RandMemoHash,添加不可预测的内存访问

SeqMemoHash的每个散列步骤的输入都是预先知道的，因此可以使用最优寄存器分配算法重用尽可能多的中间结果。事实上，一个总是删除链中最老块的贪婪算法似乎是最优的。在本节中，我们建议对前面的函数进行一些轻微的修改，以防止任何寄存器分配算法提前知道将来需要哪些寄存器(或内存块)。：我们强制其中一个块的索引依赖于链的最后一个散列。这给出了一个高度均匀的随机分布的索引。当需要重新计算并执行回溯时，仍然有可能将当前块索引预先存储并作为参数传递给回溯子例程，以便在回溯函数返回后动态优化内存状态。然而，下面的问题似乎是np完全的，所以对于一个足够大的N，可能只找到一个次优解。仿真结果表明，当所提供的内存小于最优内存时，贪婪算法执行的哈希步数随着轮数的阶乘增加而增加。如果我们能够证明这对于任何算法都是正确的，那么这就意味着当R≥35，计算对于128位等效安全变得不可行的。

我们定义RandMemoHash如下:

RandMemoHash(s,R,N)：
    Set M[0]:=s
    For i:=1 to N-1 do set M[i]:=H(M[i-1])
    For r:=1 to R do:
        For b:=0 to N-1 do:
            p:=(b-1+N) mod N
            q:=AsInteger(M[p]) mod (N-1)
            j:=(b+q) mod N
            M[b]:=H(M[p] || M[j])

注意，如果输入是按随机顺序而不是按顺序执行的，它会降低CPU缓存的效用，这通常是一个优势。

若要使用RandMemoHash作为密码散列函数，如果最终结果是完全哈希的话可以使用一个降低轮数的版本替换函数H（如SHA-256使用16轮）。此外，种子应该使用一个标准的快速密钥推导函数从密码中得出，而且结果M应该通过另一个密钥推导函数来输出更短的密钥。

性能优化

当使用RandMemoHash作为工作证明时，它可以防止使用gpu或asic发送垃圾邮件或获得比标准计算机更快的速度。通过要求1mb内存，在一个最先进的gpu上计算SeqMemoHash(从2013年开始)会比使用标准电脑要慢。内部哈希函数可以按轮数减少，只需为减少的轮函数找到一个pre-image比完全计算RandMemoHash要困难。

使用RandMemoHash作为PoW的建议配置如下:

  • RandMemoHash使用4轮(R=4)
  • 内部哈希函数是SHA-256，减少到16个循环
  • N = 2^16，所以需要2mb的内存来优化计算SeqMemoHash。
  • 计算SeqMemoHash至少需要2^18次被减少的哈希计算，这相当于2^16次完整的SHA-256计算，在标准计算机中大约需要30毫秒。
  • 假设每个SHA-256轮需要4个步骤，那么RandMemoHash计算的总步骤数为2^24。

对于这种配置，估计用一半内存计算RandMemoHash需要重新计算大约2^60个散列摘要。

在PoW中也不需要隐藏初始种子，不需要隐藏任何中间状态。使用完整的SHA-256哈希最后一个块，可以防止完整的SeqMemoHash原像攻击。：攻击者不会愿意每次都破坏一个内部约简版哈希函数，即使它在计算上是可行的。例如，打破减少到16轮的SHA-2的原像抵抗需要2^32步。然后是计算成本，如果内存比最优内存少32字节的RandMemoHash至少需要执行这2^32个额外步骤，因此RandMemoHash需要的时间比以前多256倍。

逐步验证

当SeqMemoHash或RandMemoHash被用作PoW时，攻击者可以通过欺骗PoW的难度来尝试DoS攻击，并迫使验证者在计算(无效的)MemoHash摘要时投入CPU资源。防止这种攻击的一种方法是创建一个PoW，该PoW由在两个幂为2的步骤中(在哈希步骤1,2,4,8，..)生成的所有中间结果的串联组成最后的结果。对于上一节给出的配置，这需要17个中间散列摘要和最终散列摘要。验证者必须在计算过程中根据给定的值检查每个中间状态。此保护确保攻击者必须执行验证者执行的至少一半操作。

结论

介绍了严格内存困难函数(SMHF)的概念，和现在的两个SMHF候选SeqMemoHash和RandMemoHash，而且我们推测，他们在随机预测模型下是内存困难的。

题图来自unsplash: https://unsplash.com/photos/TAm2z1TOges