密碼學系列之:memory-hard函數

簡介

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/

最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！

歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！