信息安全原理與實踐-第二版05-哈希函數(shù)及其他課件

1、1信息安全原理與實踐Information Security: Principles and Practice, 2nd Edition美Mark Stamp著張 戈譯第5章 哈希函數(shù)及其他25.1 引言本章內(nèi)容加密哈希函數(shù)加密哈希函數(shù)的標準應(yīng)用哈希函數(shù)的高級應(yīng)用加密相關(guān)的副作用問題35.2 什么是加密哈希函數(shù)一個加密哈希函數(shù)h(x)，必須滿足下列所有條件：壓縮對于任何長度的輸入值x，輸出值y = h(x)的長度都比較小。在實際使用中，通常輸出值是固定長度的(比如160位長度的二進制值)，而無論輸入值的長度是多少。高效對于任何的輸入值x，必須能夠很容易地計算出h(x)。當然，伴隨著輸入值x的長

2、度增加，計算h(x)所需要的計算量也會隨之增加，但是，這不能增長得太快。單向給定任意值y，要想找到一個值x，使得h(x) = y，將是計算不可行的。換一種不同的說法，即對于哈希運算，沒有行之有效的逆運算?？谷跖鲎残越o定x和h(x)，要想找到任意y，滿足yx，并且h(y) = h(x)，這是不可能的?？箯娕鲎残砸胝业饺我獾膞和y，使得xy，并且h(x) = h(y)，這是不可能的。也就是說，我們不能夠找到任何兩個輸入，使得它們經(jīng)過哈希后會產(chǎn)生相同的輸出值。4哈希函數(shù)在數(shù)字簽名上的應(yīng)用以前Alice對一條消息M實施簽名，是通過使用她自己的私鑰進行“加密”計算得到的，即要計算S = MAlice。

3、如果Alice發(fā)送消息M和簽名S給Bob，Bob就能夠通過執(zhí)行驗證過程M = SAlice來驗證該簽名的有效性。但是，如果消息M很大，MAlice就是一個成本很高的計算，更不用提發(fā)送消息M和簽名S的帶寬需求了，這兩者都會很大。相比之下，在計算一個MAC時，加密的速度會很快，而且在發(fā)送時，我們也僅僅需要伴隨著消息發(fā)送少量附加的校驗位(比如MAC)而已。使用哈希函數(shù)之后假設(shè)Alice有一個加密哈希函數(shù)h。那么，h(M)可以被看做文檔M的一個“指紋”，也就是說，h(M)比M小得多，但是它能夠標識出M。如果M不同于M，那么即使僅僅相差一個單獨的二進制位，哈希函數(shù)執(zhí)行的結(jié)果也幾乎肯定會不同。而且，哈希函

4、數(shù)的抗碰撞特性意味著，想要將消息M替換為任何不同的消息M，使得h(M) = h(M)是不可能的 1. 一旦哈希值發(fā)生相同的情況，該怎么辦呢？好的，這說明你已經(jīng)發(fā)現(xiàn)了一個碰撞，也就意味著你已經(jīng)攻破了這個哈希函數(shù)，于是你就成為一個著名的密碼破解專家了。所以，這是個雙贏的好事。5簽名的正確方法假設(shè)沒有碰撞，那么對h(M)簽名和對消息M實施簽名的效果一樣好。事實上，對哈希值實施簽名比起僅僅對消息本身實施簽名，實際上會更加安全。現(xiàn)在數(shù)字簽名的安全性不僅依賴于公鑰系統(tǒng)的安全性，而且也依賴于哈希函數(shù)本身的安全性如果二者中有任何一個比較弱，簽名體制就可能會被破解。65.3 生日問題假如你和其他N個人同在一個房

5、間里。那么，N必須多大，你才有指望找到至少一個人和你有相同的生日呢？或者說：N必須多大，才會使得“有某個人與你生日相同”的概率大于1/2呢？你的生日是在一年中特定的一天。如果一個人和你的生日不同，那么他或她的生日必定是在其他364天中的一天。假設(shè)所有的生日都是概率相等的，那么“一個隨機選擇的人不與你的生日相同”的概率就是364/365。這樣，所有的N個人都跟你的生日不同的概率就是(364/365)N，于是，至少有一個人與你的生日相同的概率就是：設(shè)置這個表達式等于1/2，并解出N，得到N = 253。7真正的生日問題我們給房間里的N個人分別編上號碼1，2，3，N。編號為1的人的生日是一年365天

6、中的一天。如果所有人的生日各不相同，那么編號為2的人必須與編號為1的人的生日不相同，也就是說，編號為2的人的生日只能是剩余的364天中的任意一天。同樣，編號為3的人的生日只能是再剩余的363天中的任意一天，依此類推。假設(shè)所有的生日都是概率相等的，考慮上述情況的補集，其最后的概率計算如下式所示設(shè)置這個表達式等于1/2，并解出N，我們得到N = 238生日悖論延伸 對于一個生成N位二進制長度輸出的安全哈希函數(shù)來說，一個計算開銷大約以2N /2為因子的強力破解方式，就能夠?qū)ζ浒l(fā)起有效的攻擊。 相比較而言，對于一個密鑰長度為N位二進制數(shù)的安全對稱密鑰加密方案來說，對其強力破解的計算開銷的因子是2N-l

7、。 所以，安全哈希函數(shù)的輸出必須是對稱加密密鑰二進制位數(shù)的大約兩倍長，才能夠獲得與后者基本相當?shù)陌踩健?5.4 生日攻擊假設(shè)哈希函數(shù)h生成一個n位二進制長的輸出。Trudy原則上能夠發(fā)起一次生日攻擊，具體如下：Trudy選擇一條“惡意”消息E，這是她想讓Alice簽名的消息，但是Alice并不想對其簽名。Trudy也創(chuàng)建了一條無害的消息I，她有信心Alice愿意對這條消息簽名。然后，Trudy通過對消息實施較小的編輯性修改，生成2n/2條該無害消息I的變體。這些無害的消息，我們分別標識為Ii，其中i = 0,1, . ,2n/2 1，所有消息都與I的含義相同，但是既然消息本身不同，那么它們

8、的哈希值也不一樣。同樣，Trudy創(chuàng)建出2n/2個惡意消息E的變體，分別標識為Ei，其中i = 0,1, . ,2n/2 1。這些消息也都與原始的惡意消息E表達同樣的含義，但是它們的哈希值不一樣。Trudy對所有的惡意消息Ei以及所有的無害消息Ii實施哈希運算。根據(jù)上述生日問題的討論，她就有希望找到一個碰撞，比方說，h(Ej) = h(Ik)?；谶@樣的一個碰撞，Trudy將Ik發(fā)送給Alice，并請Alice對其進行簽名。既然這條消息看起來沒有問題，Alice就對其進行簽名，并將Ik和h(Ik)Alice返回給Trudy。既然h(Ej) = h(Ik)，那么由此可以得出h(Ej)Alice

9、= h(Ik)Alice，于是，Trudy實際上就已經(jīng)獲得了Alice對惡意消息Ej的簽名。10在這個攻擊中，Trudy獲得了Alice對于一條Trudy自選消息的簽名，但是并沒有以任何方式攻擊潛在的公開密鑰加密系統(tǒng)。這個攻擊是一個針對哈希函數(shù)h的強力攻擊，而哈希函數(shù)h是用于計算數(shù)字簽名的。為了防止此類攻擊，我們可以選擇一個哈希函數(shù)，使得該哈希函數(shù)的輸出值的長度n足夠大，以至于Trudy無法完成2n/2個哈希值的計算。 115.5 非加密哈希非加密哈希運算的例子（1）其中，每個Xi是一個字節(jié)，定義哈希函數(shù)h(X)為：這毫無疑問提供了壓縮功能，因為任何長度的輸入都被壓縮為8位二進制的輸出。但是，

10、這個哈希很容易被破解，因為生日問題的結(jié)論告訴我們，只需對24 = 16個隨機選擇的輸入執(zhí)行哈希運算，我們就有望找到一個碰撞。 對兩個字節(jié)進行互換，就總是能夠產(chǎn)生一個碰撞，類似如下這種情況：（2）我們將哈希函數(shù)h(X)定義為：雖然該函數(shù)在交換輸入字節(jié)順序的情況下能夠輸出不同的結(jié)果，但是仍然逃不過生日問題帶來的麻煩。12循環(huán)冗余校驗，或簡稱為CRC循環(huán)冗余校驗碼的計算本質(zhì)上是長除法，將余數(shù)作為CRC計算的“哈?！敝?。與常規(guī)的長除法不同，CRC在計算中使用XOR運算替代了減法。在一個CRC的計算過程中，除數(shù)被指定作為算法的一部分，數(shù)據(jù)作為被除數(shù)。例子假設(shè)給定的除數(shù)是10011，而有趣的是數(shù)據(jù)恰好是1

11、0101011。那么，我們先對數(shù)據(jù)附加上4個0(附加的位數(shù)要比除數(shù)的二進制位數(shù)少1)，然后執(zhí)行如下長除法運算：CRC校驗和就是長除法運算的余數(shù)在這個例子中，就是1010。135.6 Tiger HashMD5MD指的是消息摘要(Message Digest)，它的前身是MD4，而MD4本身又繼承自MD2。所有的MD系列算法都是由加密領(lǐng)域的大師級人物Ron Rivest所發(fā)明。MD5算法生成128位的輸出值。SHA-1算法SHA表示安全哈希算法(Secure Hash Algorithm)，是美國政府的一個標準。SHA-1算法實際上非常類似于MD5算法。兩個算法在實踐中的主要不同在于SHA-1生

12、成160位二進制長的輸出值，比MD5提供了更可觀的安全邊際。14所謂雪崩效應(yīng)，是所有加密哈希函數(shù)都會追求的一個理想特性。其目標是：在輸入值中任何小的變化，都應(yīng)該級聯(lián)傳遞并導致輸出結(jié)果較大的變化就像雪崩一樣。理想情況下，任何輸入值的變化引發(fā)的輸出值變化都是不相關(guān)的，這樣，攻擊者將不得不實施窮舉式檢索來尋找碰撞。Tiger算法特點算法的輸入先被分成512位二進制長度的分組，如果需要的話，就對輸入值進行附加填充位，以補足成512的倍數(shù)位的長度。算法輸出192位二進制長度的哈希值。算法實現(xiàn)中使用了4個S-box，這4個S-box的每一個都將8位二進制位映射為64位。算法還使用了一個“密鑰調(diào)度”的算法，

13、不過由于這里沒有密鑰的概念，該算法實際是施加到了輸入分組上。15Tiger算法的過程首先對輸入值X進行附加填充位，使其長度滿足512位二進制長的倍數(shù)，表示為： ，其中每一個Xi都是一個512位二進制長的分組。對每一個Xi使用一個外層的輪運算。假設(shè)a，b和c都是64位二進制長的值。對于第一輪運算，(a, b, c)的初始值以16進制形式表示如下：16一輪運算之后，輸出的(a, b, c)就成為后續(xù)下一輪運算的初始三元組。最后一輪運算之后，最終輸出的(a, b, c)就是192位二進制長的哈希值。首個外層輪函數(shù)F5的輸入是(a, b, c)，如果我們標記F5的輸出為(a, b, c)，那么F7的輸

14、入為(c, a, b)。同樣地，如果我們標記F7的輸出為(a, b, c)，那么F9的輸入為(b, c, a)。上圖的每一個函數(shù)Fm都包含了8個下圖所示的內(nèi)層輪運算。我們再令W表示內(nèi)層輪運算的512位二進制的輸入值，其可以表示如下17對于函數(shù)fm,i，當i = 0,1,2, . ,7時，其各自的輸入值分別如下 其中各自對應(yīng)的函數(shù)fm,i-1的輸出標記為(a, b, c)。每一個fm,i都依賴于a，b，c，wi和m，其中wi是512位二進制輸入值W的第i個64位子分組。c寫作： ，其中每一個ci都是一個單獨的字節(jié)。 fm,i由下式給定：每一個Si都是一個S-box(即查找表)，將8位二進制映射為

15、64位二進制。18密鑰調(diào)度算法假設(shè)令W為密鑰調(diào)度算法的512位二進制輸入值。同上，我們將W寫作W= (w0, w1, w7)，其中每一個wi都是一個64位二進制值，我們再令 為wi的二進制補數(shù)。密鑰調(diào)度算法如下，其中最后的計算結(jié)果W= (w0, w1, w7)給出了該算法的輸出值。19小結(jié)Tiger哈希算法共包含24輪運算，這24輪運算可以看成是3個外層輪運算，而這每一個外層運算都包含了8個內(nèi)層輪運算。該算法所有的中間步驟產(chǎn)生的哈希值都是192位二進制值。該算法中S-box的設(shè)計使得僅僅經(jīng)過24輪運算中的3輪計算，每一個輸入的二進制位就會影響到a，b和c三者中的每一個。而且，在消息中任何小的變

16、化，都將影響到算法中間步驟產(chǎn)生的哈希值的多個二進制位。在fm,i計算過程中，最后一步的乘法也是該算法設(shè)計中的一個關(guān)鍵特性。它的目的是為了確保，對于一輪運算中每個S-box的輸入，都將在下一輪的運算中混入到多個S-box中。205.7 HMACHMAC來源怎么才能將密鑰混入到所謂的HMAC中呢？將密鑰置于消息體之前，即計算h(K, M)假如我們選擇計算h(K, M)來得到HMAC。如果消息M = (B1, B2)，其中每個Bi都是512位二進制長，則如果Trudy選擇了M，使得M = (M, X)，那么，Trudy有可能利用以上燈飾從h(K, M)找到h(K, M) 。因為，對于特定長度的K，M

17、和X，有將密鑰附加于消息體之后，即計算h(M, K)21假如令B為哈希運算的分組長度，以字節(jié)數(shù)表示。對于所有流行的哈希算法B = 64。ipad = 0 x36 重復B次opad = 0 x5C 重復B次那么，消息M的HMAC定義為：這個方案將密鑰徹底地混入到哈希運算的結(jié)果當中。計算一個HMAC值雖然需要執(zhí)行兩遍哈希運算，但是第二次哈希運算僅作用于少量的二進制位并使用了修改的附加填充密鑰。所以，總開銷比起計算h(M)所需要的開銷，僅僅多了少許。更好5.8 哈希函數(shù)的用途標準應(yīng)用身份認證消息完整性保護(使用HMAC)消息指紋錯誤檢測高效數(shù)字簽名等高級應(yīng)用網(wǎng)上競價垃圾郵件減阻225.8.1網(wǎng)上競價

18、假設(shè)有一個物品在網(wǎng)上拍賣，而Alice、Bob以及Charlie都想要出價競拍。每一個競拍者都有一次機會提交一個秘密的報價，只有當所有的報價都接收到之后，競拍價格才會公開。依照慣例，報價最高的競拍者獲勝。前提：Alice、Bob以及Charlie，三人之間必然是互相不信任的，另外，他們也絕對都不會信任和接受競投價格的網(wǎng)上服務(wù)。為了努力消除這些擔心，網(wǎng)上服務(wù)方提出了如下的方案：每一個競拍者將確定他們各自的競拍價格，比方說，Alice出價為A，Bob出價為B，Charlie出價為C，各自確保其報價秘密。然后，Alice將提交h(A)，Bob將提交h(B)，Charlie將提交h(C)。一旦所有三個

19、經(jīng)過哈希運算的報價都已接收到，網(wǎng)上服務(wù)方就在線公開發(fā)布這些哈希值，以供所有人查閱。優(yōu)點：報價的哈希值將競拍者與他們的原始報價綁在了一起，而且無需揭示有關(guān)報價自身的任何信息。如果率先提交一個報價的哈希值并無什么不利因素，并且一旦提交了報價的哈希值，便再沒有任何辦法能夠改變報價，那么這個方案防止了如前所述的欺騙，缺陷：它可能會遭受前向檢索攻擊235.8.2 垃圾郵件減阻假如M為電子郵件消息，T為當前時間。電子郵件消息M包含了發(fā)送方和目標接收方的電子郵件地址，但是并不包含任何其他的地址。消息M的發(fā)送方必須確定一個值R，使得下式成立： 也就是說，發(fā)送方必須找到一個值R，使得上面等式中哈希運算的輸出結(jié)果

20、中前N個二進制位都是0。一旦完成了這一步，發(fā)送方就發(fā)送三元組(M, R, T)。在接收方Alice接受該郵件之前，她需要驗證時間T是否在不久之前，以及驗證h(M, R, T)是否以N個0開始。 平均而言，發(fā)送方就需要執(zhí)行大約2N次哈希計算。而無論N的長度是多少，接收方只需執(zhí)行一次哈希計算便能夠驗證h(M, R, T)是否以N個0開始。為使這個設(shè)計行之有效，我們需要選擇一個N，使得相應(yīng)的計算開銷處于常規(guī)的電子郵件用戶能夠接受的水平，但其成本又高到了垃圾郵件發(fā)送者無法忍受的程度。245.9 其他與加密相關(guān)的主題Shamir的秘密共享機制有關(guān)視覺的加密技術(shù)隨機性問題信息隱藏255.9.1秘密共享問題

21、？假設(shè)Alice和Bob想要共享一個秘密信息S，以實現(xiàn)如下的效果：Alice或者Bob(當然也包括其他的任何人)都不能獨自確定信息S，除了瞎猜，再無更好的辦法。Alice和Bob在一起，就能夠輕松地確定該信息S秘密共享機制因為其中有兩個參與者，而且雙方必須協(xié)同合作才能恢復出秘密信息S。26兩點決定一條直線假設(shè)秘密信息S是一個實數(shù)。通過點(0, S)在平面上畫一條直線L，并給Alice指定直線L上的一點A = (X0, Y0)，給Bob指定直線L上的另一點B = (X1, Y1)。這樣，Alice和Bob各自都不掌握關(guān)于S的任何信息，因為通過一個獨立的點存在無限多的直線。但是，合在一起，兩個點A

22、和B唯一確定了直線L，這樣就能夠確定在Y軸上的截距，于是進而就獲得了值S。27“m out of n”型的秘密共享機制：即對于任何的mn，其中n代表參與者的數(shù)量，那么其中任意的m個參與者合作，就能夠恢復出共享的秘密。一條直線是一個一次多項式，它可以由兩點唯一確定。一條拋物線是一個二次多項式，它可以由三個點唯一確定。一般而言，一個次數(shù)為m 1的多項式可以由m個點唯一確定。對于任意的mn，正是上述基本事實使得我們能夠構(gòu)造出一個“m out of n”型的秘密共享機制。285.9.1.1密鑰托管如何解決密鑰托管機構(gòu)的信任問題？通過擁有多個托管機構(gòu)，并允許用戶將其密鑰在這些托管機構(gòu)中的n個之間進行分割

23、，使得必須得有n個托管機構(gòu)中的m個協(xié)同合作才能恢復出密鑰。Shamir的秘密共享機制可以用于實現(xiàn)這樣的一個密鑰托管方案。假設(shè)N = 3 和 m = 2，Alice的密鑰是S。使用 “2 out of 3”方案即可。比如，Alice可能會選擇讓司法部持有點(X0, Y0)，讓商務(wù)部持有點(X1, Y1)，再讓Fred的密鑰托管公司持有點(X2, Y2),。于是，這三個托管機構(gòu)中必須至少有兩個協(xié)同合作才能確定Alice的密鑰S。295.9.1.2 視覺加密技術(shù)視覺秘密共享機制該機制是絕對安全的。在視覺秘密共享機制(也被稱作視覺加密技術(shù))中，解密潛在的圖像并不需要執(zhí)行任何計算。例子：像素分解30如果

24、某個特定像素是白色，我們可以通過拋硬幣的方式來決定是使用圖中的“a”行還是“b”行。對于一個黑色像素，我們通過拋硬幣來在“c”行和“d”行之間選擇，然后再使用被選定的行來確定相應(yīng)的像素部分。如果原始的像素是黑色的，那么其分解的兩份重疊之后總是生成一個黑色像素。而如果原始的像素是白色的，那么其分解的兩份重疊之后將生成一個半白半黑的像素，這將被視覺感知為灰色。這個結(jié)果會損失一定的對比度(黑和灰相對于黑和白)，但是，原始的圖像仍然可以清晰地辨別。視覺秘密共享的例子是一個“2 out of 2”型的共享方案315.9.2 隨機數(shù)在加密技術(shù)領(lǐng)域，生成對稱密鑰、生成RSA密鑰對(意即隨機選取大素數(shù))以及生

25、成Diffie-Hellman的秘密指數(shù)，這些都需要隨機數(shù)。加密技術(shù)中的隨機數(shù)必須不僅是統(tǒng)計上隨機的，而且它們還必須要滿足嚴格得多的條件它們必須是不可預測的。常用的偽隨機數(shù)生成器就是可預測的，即給定足夠大數(shù)量的輸出值，后續(xù)的值將能夠被很容易地確定。所以，偽隨機數(shù)生成器不適用于加密類應(yīng)用。 假設(shè)有個服務(wù)器專門為用戶生成對稱密鑰，并假設(shè)它為一系列用戶生成了如下的密鑰：KA 給Alice使用KB 給Bob使用KC 給Charlie使用KD 給 Dave使用現(xiàn)在如果Alice、Bob和Charlie都不喜歡Dave，他們就可以將他們的這些信息放在一起，看看是否有助于確定Dave的密鑰。即Alice、B

26、ob和Charlie可以利用對于他們自己的密鑰KA、KB和KC的理解，來考慮這些信息是否有助于確定出Dave的密鑰KD。如果能夠根據(jù)對于密鑰KA、KB和KC的了解來預測KD，那么該系統(tǒng)的安全性是有缺陷的。325.9.2.1德州撲克規(guī)則首先給每個玩家發(fā)兩張牌，正面朝下扣起來作為底牌。然后完成一輪投注。接下來，翻開三張公共牌所有玩家都可以看到公共牌，并可以考慮與他們自己手中的牌結(jié)合使用。進行第二輪投注之后，再次翻開一張公共牌，隨后再進行一輪投注。最后，翻開最后的一張公共牌，這之后還可以再加投一次注。在所有保持持續(xù)跟進到最后的玩家中，誰能夠從自己手里的兩張底牌和翻開的5張公共牌中組成最好的一手牌，誰

27、就是獲勝者。ASF公司開發(fā)的撲克牌游戲軟件在運用隨機數(shù)來洗一副牌的時候，隨機數(shù)的使用方式中有一個嚴重的缺陷：這個程序無法產(chǎn)生一個真正隨機的洗牌結(jié)果，于是在游戲中，玩家就有可能實時地確定整副牌的情況。33如何實時地就確定洗牌的結(jié)果呢？對于一幅含有52張牌的撲克來說，共有52! 2225種不同的洗牌結(jié)果。AFS公司的德州撲克程序中使用了一個“隨機的”32位二進制整數(shù)來確定洗牌的結(jié)果。因此，在2225種所有可能的洗牌結(jié)果中，這個程序就不可能產(chǎn)生多于其中232種不同的洗牌結(jié)果。這是一個不可原諒的設(shè)計缺陷！為了生成“隨機的”洗牌結(jié)果，該程序使用了偽隨機數(shù)生成器或簡稱為PRNG。在每次洗牌時，該偽隨機數(shù)生

28、成器都會基于新的種子值，但種子值基于一個已知的函數(shù)，即其值為自午夜0點以來所經(jīng)歷的毫秒數(shù)。因為在一天中包含的毫秒數(shù)為實際上就會使得最后能夠產(chǎn)生的不同洗牌結(jié)果的數(shù)量小于227。攻擊者Trudy將她的時鐘與服務(wù)器進行同步，她就有可能將需要檢測的不同洗牌結(jié)果的數(shù)量降低為小于218。事實上，當?shù)谝惠喌墓才平視灾螅琓rudy就能夠唯一確定洗牌結(jié)果了，于是她就能夠知道其他所有玩家最終整手牌的情況。345.9.2.2 隨機二進制位的生成真正的隨機性不僅非常難以找到，而且非常難以界定。真正的隨機性的來源確實存在。例如，放射性衰變就是隨機的。但是，基于核放射技術(shù)的計算機肯定是不受歡迎的。隨機性的另一個來源是臭名昭著的熔巖燈，可以從其混沌行為中獲得隨機性。因為軟件本身是(也希望是)有確定性的，所以真正的隨機數(shù)必須產(chǎn)生于任何代碼之外。355.9.3 信息隱藏隱寫術(shù)也叫隱藏書寫，就是試圖隱藏特定信息被傳遞這一事實。隱寫術(shù)有很長的歷史，特別是在戰(zhàn)爭中很久之前就已經(jīng)在使用?，F(xiàn)代版本的隱寫術(shù)涉及在各種媒介中隱藏信息，這些媒介包括諸如圖像文件