简介
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/
最艰深的解读,最粗浅的干货,最简洁的教程,泛滥你不晓得的小技巧等你来发现!
欢送关注我的公众号:「程序那些事」, 懂技术,更懂你!