第7章 密碼學(xué)Hash函數(shù)

1、1第七章 Hash函數(shù) 了解Hash 密碼學(xué)的Hash 密碼學(xué)的Hash構(gòu)造 Hash函數(shù)的攻擊 散列算法2安全目標(biāo) 保密性: 怎樣保持明文的秘密性，使得明文只能被某些人閱讀？ 用加密的方法 完整性: 怎樣確定一列信號(hào)在產(chǎn)生后沒(méi)有被篡改？ 用什么方法？3Nave Idea Alice 用密鑰K加密消息 Oscar 不知道K 但是, Oscar能修改密文 Bob能收到什么?AliceBobOscar4散列碼提供了消息結(jié)構(gòu)MAC加密 (明文 + Hash)5Hash函數(shù)應(yīng)用 認(rèn)證 完整性 數(shù)字簽名 保護(hù)口令文件 時(shí)間戳 證書(shū)6第七章 Hash函數(shù) 認(rèn)證 密碼學(xué)的Hash 密碼學(xué)的Hash構(gòu)造 Ha

2、sh函數(shù)的攻擊 散列算法7強(qiáng)無(wú)碰撞Hash函數(shù) 定義：一個(gè)強(qiáng)無(wú)碰撞Hash函數(shù)是一個(gè)滿足下列條件的函數(shù)h: 1) 壓縮 h: * n 多對(duì)一映射 2) 容易計(jì)算 3) 單向 給定y, 求m使得h(m)=y在計(jì)算上不可行 4) 給定算法h，要找兩個(gè)不同的消息m1m2,使其 Hash值h(m1)=h(m2)是困難的8AliceBobJudgeI owe youI owe you一個(gè)用Hash的例子 Alice想給Bob發(fā)送一條消息“I owe you” Bob可以向法官出示消息來(lái)迫使Alice付清欠款9IOU 協(xié)議AliceKUA, KRAMEKRAH(M)JudgeMEKRAH(M)知道KUA知

3、道KUA不知道KRA，Bob 不能偽造(M, EKRAH(M)對(duì) AliceBobJudgeBob 能核實(shí)H(M)10如果沖突存在 假設(shè)我們用: H (char s ) = (s0 a) mod 10 Alice發(fā)給Bob:“I, Alice, owe Bob $2.”, EKRAH (M) Bob發(fā)給Judge:“I, Alice, owe Bob $200000000000.”, EKRAH (M) 法官證實(shí)EKUA EKRAH (M) = H(“I, Alice, owe Bob $200000000000.”) 使Alice付款11第七章 Hash函數(shù) 認(rèn)證 密碼學(xué)的Hash 密碼學(xué)的

4、Hash構(gòu)造 Hash函數(shù)的攻擊 散列算法12Hash定義 定義：一個(gè)強(qiáng)無(wú)碰撞Hash函數(shù)是一個(gè)滿足下列條件的函數(shù)h: 1) 壓縮 h: * n 多對(duì)一映射 2) 容易計(jì)算 3) 單向 給定y, 求m使得h(m)=y在計(jì)算上不可行 4) 給定算法h，要找兩個(gè)不同的消息x1x2,使其 Hash值h(x1)=(x2)是困難的13Hash函數(shù)構(gòu)造 例1: 假設(shè)n是一個(gè)大整數(shù). 設(shè)h (m)=m (mod n) 是介于0到n-1之間的一個(gè)整數(shù) 例2: 明文: “Go now” G 01000111 o 01101111 n 01101110 o 01101111 w 01110111 01011110

5、 不行14Hash函數(shù)構(gòu)造 基于分組密碼 用候選單向函數(shù)構(gòu)造Hash函數(shù) 矩陣單向函數(shù) 基于胞元自動(dòng)機(jī)的算法 以有限域中元素的指數(shù)運(yùn)算構(gòu)造 用流密碼構(gòu)造15基于分組密碼的Hash函數(shù)構(gòu)造塊加密IVM1M2.塊加密塊加密MnH16基于分組密碼的Hash函數(shù)構(gòu)造塊加密MiHi-1Hi塊加密MiHi-1Hi17用候選單向函數(shù)構(gòu)造Hash函數(shù) 選定一候選單向函數(shù)族 - RSA函數(shù)f(N,e) - Rabin函數(shù)fN - 離散對(duì)數(shù)函數(shù)f(p,g) 從單向函數(shù)族中選出一個(gè)函數(shù)進(jìn)行迭代 - 明文: m=m1.mt - hi=f(hi-1+mi),i=1,.t - h(m)=ht18用候選單向函數(shù)構(gòu)造Hash

6、函數(shù) 例1: RSA函數(shù)f(N,e): hi=(hi-1+mi)e mod N, (i=1,.,t) 例2: 背包法: 令M1,.,Ms是二元消息數(shù)字, A=(a1,., as)是一背包向量，ai1,N H(M)=M1a1+.+Msas mod N19矩陣單向函數(shù) 用tt階隨機(jī)矩陣A作為密鑰, 按下述矩陣變換將消息M擾亂: H(M)=MTAM=ijaijmimj20第七章 Hash函數(shù) 認(rèn)證 密碼學(xué)的Hash 密碼學(xué)的Hash構(gòu)造 Hash函數(shù)的攻擊 散列算法21Hash函數(shù)的攻擊 生日攻擊 特殊攻擊 - 中間相遇攻擊 攻擊具有分組鏈接結(jié)構(gòu)的Hash函數(shù) - 差分攻擊 攻擊基于分組加密函數(shù)構(gòu)造

7、的Hash函數(shù) - 修正分組攻擊 攻擊基于模算術(shù)的Hash函數(shù)22結(jié)論 Hash值的長(zhǎng)度必須足夠大，以便使得生日攻擊不能成功 MD5的Hash長(zhǎng)度為128位，M=264；SHA-1的Hash長(zhǎng)度為160位，則M=28023密碼學(xué)的Hash 對(duì)強(qiáng)無(wú)碰撞Hash函數(shù): hash輸出的長(zhǎng)度應(yīng)該是分組密碼密鑰長(zhǎng)度的2倍 64-bits 太短 通常128512 bits SHA-256, SHA-384, SHA-51224第七章 Hash函數(shù) 消息認(rèn)證 密碼學(xué)的Hash 密碼學(xué)的Hash構(gòu)造 Hash函數(shù)的攻擊 散列算法25第七章 Hash函數(shù) 消息認(rèn)證 密碼學(xué)的Hash 密碼學(xué)的Hash構(gòu)造 Has

8、h函數(shù)的攻擊 散列算法26Hash 算法的結(jié)構(gòu) bY0nfbY1nfbYL-1nCVL-1fCV1nnIV = Initial VectorCV = Chain VectorYi = The ith Message Blockf = Compress Functionn = Hash Value Lengthb = Block LengthCVLCV0=IV= initial n-bit valueCVi=f(CVi-1, Yi-1) (1 i L)H(M) = CVLCV027 MessageK bitsL 512 bits=N 32bitsLength of Message (K mod

9、264)1000Y0512 bitsY1512 bitsYq512 bitsYL-1512 bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512128-bit digestpadding(1 to 512 bits)512512512MD528填充舉例 例：消息由 704位組成，則在其末尾添加256位（1后面跟255個(gè)0），消息擴(kuò)展到960位 將消息的原始長(zhǎng)度縮減為mod 264 ，例：704位=1011000000位，將這個(gè)數(shù)書(shū)寫(xiě)為64位（在開(kāi)始位置添加54個(gè)0） 最后結(jié)果是一個(gè)具有1024位的消息29MD5 細(xì)節(jié) Step 1) 填充消息: 10

10、.0, 使消息長(zhǎng)度等于448 mod 512 Step 2) 添加明文長(zhǎng)度(64位) Step 3) 初始化4個(gè)字(128 bits)的寄存器(A, B, C, D) A = 67452301 B = EFCDAB89 C = 98BADCFE D = 10325476 Step 4) 消息由512-bits 數(shù)據(jù)塊(Y0,Y1,YL-1)處理 4 輪，每輪16次迭代 30F,T116,Mi16 stepsG,T1732,M2i16 stepsH,T3348,M3i16 stepsI,T4964,M4i16 steps+ABCDABCDABCDABCDCVq128Yq512CVq+1128+

11、是 mod 232512-bit MessageHMD54 輪311輪 每一輪處理16個(gè)子塊。每一輪的輸入如下: 1) 16個(gè)子塊; 2) 寄存器ABCD中的值; 3) 常量T16個(gè)子塊常量T一輪 B A C D32ABCDABCD+移位+gMkTi1輪中的1次迭代步驟7步驟6步驟5步驟4步驟3步驟2步驟1+ 是 mod 232BB + ( A + g(B,C,D) + Mk +Ti)s)33MD5 壓縮函數(shù) 每一輪有16次迭代，每1次迭代形如： BB + ( A + g(B,C,D) + Mk +Ti)s) g：4輪都不同的非線性函數(shù) (F,G,H,I) 第一輪：F(X,Y,Z) = (XY

12、)(X)Z) 第二輪：G(X,Y,Z) = (XZ)(Y(Z) 第三輪：H(X,Y,Z) = XYZ 第四輪：I(X,Y,Z) = Y(X(Z) Mk =第q個(gè)512-bits數(shù)據(jù)塊的第k個(gè)字 Ti = T盒的第i個(gè)32-bits字 (Ti=232abs(sin(i)34第一輪迭代MsT12345678910111213141516M1M2M3M4M5M6M7M8M9M10M11M12M13M14M15M167121722712172271217227121722T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15T1635第二輪迭代MsT12345678910111213

13、141516M2M7M12M1M6M11M16M5M10M15M4M9M14M3M8M13591420591420591420591420T17T18T19T20T21T22T23T24T25T26T27T28T29T30T31T3236第三輪迭代MsT12345678910111213141516M6M9M12M15M2M5M8M11M14M1M4M7M10M13M16M34111623411162341116234111623T33T34T35T36T37T38T39T40T41T42T43T44T45T46T47T4837第四輪迭代MsT12345678910111213141516M1

14、M8M15M6M13M4M11M2M9M16M7M14M5M12M3M106101521610152161015216101521T49T50T51T52T53T54T55T56T57T58T59T60T61T62T63T6438T的取值T(i)值T(i)值T(i)值T(i)值T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15T16D76AA478E8C7B756242070DBC1BDCEEEF57C0FAF4787C62AA8304613FD469501698098D88B44F7AFFFFF5BB1895CD7BE6B901122FD987193A679438E49

15、B40821T17T18T19T20T21T22T23T24T25T26T27T28T29T30T31T32F61E2562C040B340265E5A51E9B6C7AAD62F105D02441453D8A1E681E7D3FBC821E1CDE6C33707D6F4D50D87455A14EDA9E3E905FCEFA3F8676F02D98D2A4C8AT33T34T35T36T37T38T39T40T41T42T43T44T45T46T47T48FFFA39428771F681699D6122FDE5380CA4BEEA444BDECFA9F6BB4B60BEBFBC70289B7E

16、C6EAA127FAD4EF308504881D05D9D4D039E6DB99E51FA27CF8C4AC5665T49T50T51T52T53T54T55T56T57T58T59T60T61T62T63T64F4292244432AFF97AB9423A7FC93A039655B59C38F0CCC92FFEFF47D85845DD16FA87E4FFE2CE6E0A30143144E0811A1F7537E82BD3AF2352AD7D2BBBE86D391Ti=232abs(sin(i)39MD5 分析 Berson (1992): For a single-round MD5, he

17、 finds collision using differential cryptanalysis Attack does not work for 4-round MD5 Boer & Bosselaers(1993): Found a pseudo collision (same message, two different IVs) Dobbertin (1996): Created collisions on MD5 compression function with chosen IV Wang, Feng, Lai, Yu(2005): Works on any IV Ea

18、sy to find multiple collisions40 MessageK bitsL 512 bits=N 32bitsLength of Message (K mod 264)1000Y0512 bitsY1512 bitsYq512 bitsYL-1512 bitsSHAIV160SHACV1160SHACVq160SHACVL-1160512160-bit digestpadding(1 to 512 bits)512512512SHA41SHA1 細(xì)節(jié) Step 1) As in MD5 message is padded such as its length is a mu

19、ltiple of 512 bits Step 2) Initialize 5 word (160 bits) buffer (A, B, C, D, E) A = 67452301 B = EFCDAB89 C = 98BADCFE D = 10325476 E = C3D2E1F0 Step 3) The message is processed in 512-bits data expand 16 words into 80 words by mixing & shifting use 4 rounds of 20 operations on message block and

20、buffer424 輪 SHA4 differentfunctions:Totally 80steps5 32- bit words43SHA1 壓縮函數(shù)From 512-bitinput blockFixed constantCircular left shift 5 bits44SHA1 壓縮函數(shù) Each round consists of 20 steps (A,B,C,D,E) (E+f(t,B,C,D)+(A5)+Wt+Kt),A,(B30),C,D) t is the step number f(t,B,C,D) is a non-linear function for roun

21、d Wt is derived from the message block Wt=S1(Wt-16 Wt-14 Wt-8 Wt-3) Kt is a constant value derived from the sin function Sk is circular left shift by k bits45SHA1: f(t,A,B,C,D)StepFunction ValueComment0 t 19(B C) (B) D)If B then C else D20 t 39B C DParity bit of B,C, and D40 t 59(B C) (B D) (C D)2 or 3 of B,C,D is true60 t 79B C DParity bit of B,C, and D46SHA1 分析 Brute force: Brute force attack is harder (160 vs 128 bits for MD5) Remark of SHA1 operation: SHA1 shuffles using