写点什么

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

发布于: 2021 年 05 月 26 日

简介

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/

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

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

发布于: 2021 年 05 月 26 日阅读数: 6
用户头像

关注公众号:程序那些事,更多精彩等着你! 2020.06.07 加入

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧,尽在公众号:程序那些事!

评论

发布
暂无评论
密码学系列之:memory-hard函数