第二十個知識點：Merkle-Damgaard hash函數如何構造

這裡講的是MD變換,MD變換的全稱為Merkle-Damgaard變換.我們平時接觸的hash函數都是先構造出一個防碰撞的壓縮函數.然後先證明這個小的,固定長度的壓縮函數是安全的,然後再用它構造一個任意長度的雜湊演算法.雖然存在很多其它的構造方法,MD是迄今為止最常用的(至少是被用到最多的),例如MD5,SHA1,SHA2.是以是時候來了解一下它了.

安全的哈希函數?

一般來說,一個安全的哈希函數\(h\)應該是:

• 抗原象攻擊(Pre-image Resistant).給定\(h(x)\)很難計算出\(x\)
• 第二抗原象攻擊(Second Pre-image Resistant).給定\(x\),很難找出\(y\),使得\(h(x) = h(y)\).
• 抗碰撞:很難找出\(x,y\)使得\(h(x) = h(y)\)

如果一個哈希函數是防碰撞的.它一定是第二抗原象攻擊的.是以,這就是我們集中的碰撞一緻性.

壓縮函數

一個壓縮函數\(f:\{0,1\}^n * \{0,1\}^r \rightarrow \{0,1\}^n\)是函數.就像名字一樣"壓縮",它會将\(n+r\)bit寬的輸入壓縮成\(n\)bit的輸出.正如您可能期望的那樣,抗沖突壓縮函數是一種抗沖突的壓縮函數.是以它可能是一個固定長度的hash函數,但是如果我們想讓這個函數變成長度可變的,我們應該怎麼辦.

MD哈希函數的構造

MD構造函數提供一個方法擴充一個固定長度的壓縮函數變成一個可變長度的壓縮函數.使用一個壓縮函數\(f\),我們會用\(n\)bit的值作為我們的内部狀态,同時每次疊代給定\(r\)bit的值.為了做這件事,我們首先使用一個初始的值(IV),然後分割消息\(M\)成每塊\(r\)bit,\(M= M_0M_1...M_m\).然後簡單的疊代構造:

\[S_0 := IV,i = 0,...,m-1:S_{i+1} = f(S_i,M_i),h(M) := S_m

\]

MD構造方法中最重要的就是如果壓縮函數抗碰撞的,是以整個構造就是抗碰撞的(已經被Merkle證明了).這給了我們一個安全的方法從一個小的簡單的密鑰原語構造hash函數.

長度擴充

你可能注意到這個圖有一個我沒有描述的階段:這個Finalisation階段.這就是組織長度擴充攻擊.例如,如果\(N\)是一個單一的塊(ie,\(N \in \{0,1\}^r\)).如果攻擊者知道\(h(M) = x\),然後我們很容易計算\(h(M||N)\).因為\(h(M||N) = f(M,N)\).是以一些finalisation函數能被用于打破這個關系.

實際上這裡說的啥我沒懂,但是我翻看了别的書

look!這裡就是真正的過程,如果它的倍數不對,就是用PB,即padding.

padding的格式是:

\[PB = 100...000||<s>

s是塊的數量,s是64bit長,也就是說最多有\(2^{64}\)個塊.如果不夠s那麼就在後面再補一個塊.

安全證明可以搜一搜,網上都能搜到.