密码学系列之:memory-hard函数

简介

Memory hard function简称为MHF 在密码学中 内存困难函数(MHF)是一个需要花费大量内存来完成的函数。MHF主要被用在工作量证明中。因为需要花费大量的内存 所以MHF也会被用在密码Hash中 可以防止恶意破解。

和MHF相识的还有一个MBF memory-bound function 叫做内存约束函数 它是通过内存延迟来减慢计算速度 从而产生运算成本。

为什么需要MHF

我们知道应用程序的执行需要两个部分 一个部分是CPU 用来提供计算能力 一个部分就是内存 用来提供存储能力。

以比特币而言 比特币的挖矿其实是反复的计算SHA-2的函数 当其结果足够小的时候 挖矿就成功了。但是对于传统的CPU来说 当任务是反复计算同一个固定函数的时候 效率会非常低。于是矿工们发明了特定了应用集成电路 ASIC 也就是矿机 来大大的提高这种计算效率。从此挖矿就只掌握在矿工或者矿池手里了 因为普通人根本竞争不过他们。

因为SHA-2只是依赖于CPU的 CPU够好 或者使用ASIC针对算法进行优化 就可以超越其他人 获得优势地位。

而随之带来的就是算力无意义的浪费和用电量的激增。这实际上并不是我们想要的。所以需要一种新的算法来改变这个局面。

我们注意到 程序除了CPU之外 还需要使用到内存 而内存相对CPU相比是更加稀缺的资源。举个例子 假如计算一个函数需要1G空间 对于普通人而言 一个8核16G的电脑可以同时计算16个函数。如果你想加快运算 那么就需要提高内存空间 并且速度的提升也不会太明显 所以如果使用内存作为计算的限制 则可以大大减少恶意的运算 从而让加密解密变得相对公平。

所以 我们需要MHF。

Memory hard的评估方法

那么怎么样才叫做Memory hard呢 我们可以从3个方面去衡量 第一个方面就是累计内存复杂度 简称为CMC。在并行模型中 CMC通过将每一步的所有输入相加来衡量内存的难度。

另一个方法就是使用时间和内存的乘积来衡量。还有一个方法就是计算内存总线上内存带宽的消耗 这种类型的函数也叫做bandwidth-hard functions BHF 。

MHF的种类

根据MHF的评估方式 MHF可以分为两个类型 分别是数据依赖型(dMHF)和数据独立型(iMHF)。

数据依赖型(dMHF)指的是后面计算的数据需要依赖于之前的数据 但是到底需要哪些消息是不确定的。

数据独立型(iMHF)是指后面计算依赖的数据是确定的。

dMHFs的例子是scrypt和Argon2d。iMHFs的例子是Argon2i和catena。

由于MHF的内存特性 所以非常适合用来做密码哈希函数。

因为dMHF是数据依赖型的 所以它比iMHF在密码学上具有更强的memory-hard特性。但是dMHF有一个问题 就是容易受到缓存时序等侧通道攻击。由于这个原因 人们倾向于iMHFs来作为密码加密的算法。

MHF的密码学意义

我们知道MHF主要用来进行密码加密的 主要是为了抵御ASIC 应用集成电路 的破解。上面我们提到了3种衡量方式 这里我们使用时间和内存的乘积来表示。

正常来说 我们给定密码P和盐S 通过Hash函数H来生成结果Tag。

但是对于破解者来说 他们得到的是Tag和S 希望通过各种逆向方式来获得P 如下所示

在密码哈希的情况下 我们假设密码创建者为每个密码分配一定的执行时间 如1秒 和一定数量的CPU核 如4核 。然后他使用最大的内存量M对密码进行哈希。

那么对于密码破解者来说 他们使用ASIC来破解 假设需要用到的内存区域是A 运行ASIC的时间T由最长计算链的长度和ASIC内存延迟决定。我希望使得AT的乘积最大。从而达到防破解的意义。

通常来说ASIC机子的内存肯定要比普通内存M要小 假设A aM, 这里 a 1 。 根据时间权衡原理 内存使用的少了 自然相应的计算时间要变长 假设需要计算C(a)次 那么相应的计算时间要延长到D(a)倍。

我们可以得到下面的最大化公式

如果上式中 当a趋近于0的时候 D(a) 1/a。 也就是说只要使用的内存变小 那么内存和时间的乘积就要比之前的要大 对于这样的函数 我们就叫做memory-hard函数。

memory-hard在MHF中的应用

考虑MHF中的memory-hard的应用 需要在计算密码hash之前 通过内存准备一些初始数据 这些初始化的工作就是memory-hard的本质。

可以将内存数组B[i]的初始化简单概括为下面的步骤

初始值

对于内存数组中从1到t的index j,我们通过下面的方式来初始化

其中G是压缩函数 是index函数。

根据 的不同 我们可以将MHF分成两种类型 一种是数据独立类型 也就是说 的值不依赖于输入的密码P和盐S 那么整个的内存数组B值可以在得到密码和盐之前来构建 并且可以借助于并行运算功能 同时进行计算。

假设一个运算核G占用的内存是总内存的beta倍 那么这一种情况下时间和内存的乘积就是

如果 的值依赖于输入的密码P和盐S 那么我称这种情况叫做数据独立型。这种情况下 不能进行并行计算 假如最终计算的次数是一个平均深度为D的树 那么这种情况下时间和内存的乘积可以表示为

上面就是MHF的密码学意义。

本文已收录于 http://www.flydean.com/memory-hard/

最通俗的解读 最深刻的干货 最简洁的教程 众多你不知道的小技巧等你来发现

欢迎关注我的公众号:「程序那些事」,懂技术 更懂你

本文转自网络，原文链接：https://developer.aliyun.com/article/784310
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！