简介
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://segmentfault.com/a/1190000040064372