简介

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/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

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