簡介

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)倍。

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

mathcal{E}_{max }=max _{alpha} frac{1}{alpha D(alpha)}

如果上式中，當a趨近於0的時候， D(a) > 1/a。 也就是說隻要使用的內存變小，那麼內存和時間的乘積就要比之前的要大，對於這樣的函數，我們就叫做memory-hard函數。

memory-hard在MHF中的應用

考慮MHF中的memory-hard的應用，需要在計算密碼hash之前，通過內存準備一些初始數據，這些初始化的工作就是memory-hard的本質。

可以將內存數組B[i]的初始化簡單概括為下面的步驟：

初始值：B[0]=H(P, S)

對於內存數組中從1到t的index j,我們通過下面的方式來初始化：

B[j]=Gleft(Bleft[phi_{1}(j)right], Bleft[phi_{2}(j)right], cdots, Bleft[phi_{k}(j)right]right)

其中G是壓縮函數，phi(j) 是index函數。

根據phi(j) 的不同，我們可以將MHF分成兩種類型，一種是數據獨立類型，也就是說phi(j) 的值不依賴於輸入的密碼P和鹽S，那麼整個的內存數組B值可以在得到密碼和鹽之前來構建，並且可以借助於並行運算功能，同時進行計算。

假設一個運算核G占用的內存是總內存的beta倍，那麼這一種情況下時間和內存的乘積就是：

mathcal{E}(alpha)=frac{1}{alpha+C(alpha) beta}

如果phi(j) 的值依賴於輸入的密碼P和鹽S，那麼我稱這種情況叫做數據獨立型。這種情況下，不能進行並行計算，假如最終計算的次數是一個平均深度為D的樹，那麼這種情況下時間和內存的乘積可以表示為：

mathcal{E}(alpha)=frac{1}{(alpha+C(alpha) beta) D(alpha)}

上面就是MHF的密碼學意義。