密碼學系列之:memory-hard函數
目錄
簡介
為什麼需要mhf
memory hard的評估方法
mhf的種類
mhf的密碼學意義
memory-hard在mhf中的應用
memory hard function簡稱為mhf，在密碼學中，記憶體困難函數(mhf)是一個需要花費大量記憶體來完成的函數。mhf主要被用在工作量證明中。因為需要花費大量的記憶體，是以mhf也會被用在密碼hash中，可以防止惡意破解。
和mhf相識的還有一個mbf（memory-bound function ），叫做記憶體限制函數，它是通過記憶體延遲來減慢計算速度，進而産生運算成本。
我們知道應用程式的執行需要兩個部分，一個部分是cpu，用來提供計算能力，一個部分就是記憶體，用來提供存儲能力。
以比特币而言，比特币的挖礦其實是反複的計算sha-2的函數，當其結果足夠小的時候，挖礦就成功了。但是對于傳統的cpu來說，當任務是反複計算同一個固定函數的時候，效率會非常低。于是礦工們發明了特定了應用內建電路（asic）也就是礦機，來大大的提高這種計算效率。從此挖礦就隻掌握在礦工或者礦池手裡了，因為普通人根本競争不過他們。
因為sha-2隻是依賴于cpu的，cpu夠好，或者使用asic針對算法進行優化，就可以超越其他人，獲得優勢地位。
而随之帶來的就是算力無意義的浪費和用電量的激增。這實際上并不是我們想要的。是以需要一種新的算法來改變這個局面。
我們注意到，程式除了cpu之外，還需要使用到記憶體，而記憶體相對cpu相比是更加稀缺的資源。舉個例子，假如計算一個函數需要1g空間，對于普通人而言，一個8核16g的電腦可以同時計算16個函數。如果你想加快運算，那麼就需要提高記憶體空間，并且速度的提升也不會太明顯，是以如果使用記憶體作為計算的限制，則可以大大減少惡意的運算，進而讓加密解密變得相對公平。
是以，我們需要mhf。
那麼怎麼樣才叫做memory hard呢？我們可以從3個方面去衡量，第一個方面就是累計記憶體複雜度，簡稱為cmc。在并行模型中，cmc通過将每一步的所有輸入相加來衡量記憶體的難度。
另一個方法就是使用時間和記憶體的乘積來衡量。還有一個方法就是計算記憶體總線上記憶體帶寬的消耗，這種類型的函數也叫做bandwidth-hard functions（bhf）。
根據mhf的評估方式，mhf可以分為兩個類型，分别是資料依賴型(dmhf)和資料獨立型(imhf)。
資料依賴型(dmhf)指的是後面計算的資料需要依賴于之前的資料，但是到底需要哪些消息是不确定的。
資料獨立型(imhf)是指後面計算依賴的資料是确定的。
dmhfs的例子是scrypt和argon2d。imhfs的例子是argon2i和catena。
由于mhf的記憶體特性，是以非常适合用來做密碼哈希函數。
因為dmhf是資料依賴型的，是以它比imhf在密碼學上具有更強的memory-hard特性。但是dmhf有一個問題，就是容易受到緩存時序等側通道攻擊。由于這個原因，人們傾向于imhfs來作為密碼加密的算法。
我們知道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函數。
考慮mhf中的memory-hard的應用，需要在計算密碼hash之前，通過記憶體準備一些初始資料，這些初始化的工作就是memory-hard的本質。
可以将記憶體數組b[i]的初始化簡單概括為下面的步驟：
初始值：$b[0]=h(p, s) $
對于記憶體數組中從1到t的index j,我們通過下面的方式來初始化：
\(b[j]=g\left(b\left[\phi_{1}(j)\right], b\left[\phi_{2}(j)\right], \cdots, b\left[\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的密碼學意義。
本文已收錄于 http://www.flydean.com/memory-hard/ 最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！