Microsoft PowerPoint - 讲义08_hash.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 讲义08_hash.ppt"

罔璎焦
5 years ago
Views:

1 Hash 函数王小云 (1966 年 -), 生于中国山东省诸城, 中国密码学家裴士辉 QQ:

2 密码学上的 hash 函数密码学上 Hash 函数, 输入任意长度的明文, 输出固定长度的数值输入的任意变化, 都会引起输出显著的变化输入的数据称为消息 (message) 输出的数据称为消息摘要或摘要 (message digest or simply digest) 2

3 密码学上的 hash 函数 3

4 Hash 函数的应用验证文件和消息的完整性 4

5 Hash 函数的应用口令验证 5

6 Hash 函数的应用口令验证 6

7 Hash 函数的应用数字签名中生成消息摘要 7

8 Hash 函数族定义一个 Hash 族是满足如下条件的四元组 (,,, ): 1. 是所有的可能的消息的集合 2. 是由所有可能的消息摘要构成的有限集 3. 是密钥空间, 是所有可能的密钥构成的有限集 4. 对每个 K, 存在一个 Hash 函数 hk, hk : Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 8

9 Hash 函数的安全性假定 h : 是一个不带密钥的 Hash 函数设 x, 定义 y hx ( ) 如果一个 Hash 函数是安全的, 就应该对如下三个问题都是难解的问题 1 原像 (Preimage) 问题 2 第二原像 (Second preimage) 问题 3 碰撞 (Collision) Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 9

10 已知 :Hash 函数 h : 找出 : x 使得 hx ( ) 问题 1 原像 (Preimage) 和 y y Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 10

11 问题 2 第二原像 (Second preimage) 已知 :Hash 函数 h : 和 x 找出 : x' 使得 x' x, 并且 hx ( ') hx ( ) Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 11

12 问题 3 碰撞 (Collision) 已知 :Hash 函数 h : 找出 : x,x' 使得 x' x, 并且 hx ( ') hx ( ) Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 12

13 随机预言机模型 (Random Oracle Model) 定义令, 是所有从到的函数集合假定 N, M, 则, N M 任何 Hash 函数族, 被称为一个 (N, M)---Hash 族定理假设 h, 是随机选取的, 令 0 假定当且仅当 x 0时,h( x)( 通过查询 h 的预言机 ) 被确定则对所有的 x \ 0 和 y, 都有 Pr[ hx ( ) y] 1/ M Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 13

14 算法 Find-Preimage(h, y, Q) 选择任意的 for each 0, 0 Q x 0 if hx ( ) y do then return ( x) return (failure) 定理对任意的, 且 0 Q 0 Q 成功率是 1 ( 1 1/ M ) 证明 : 令 E 表示事件 hx ( ) y i i, 上述算法的平均情况 E i 是独立事件, 并且对所有的 1 i Q, Pr[ Ei ] 1/ M Pr[ E1 E2 E Q ] M Q 14

15 算法 Find-Second-Preimage(h, y, Q) y hx ( ) \{ }, 0 Q 1 选择 0 x for each x 0 0 if hx ( 0) y do then return ( x0 ) return (failure) 定理对任意的 0 \{ x}, 且 0 Q 均情况成功率是 Q 1 ( / M ) -1, 上述算法的平 Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 15

16 Birthday Paradox - 生日悖论探讨 k 个人里, 随便选两个人, 生日是同一天的机率问题 ( 同月同日, 但不见得要同年 ) k 要有多大, 才能让机率高于 50% 呢? 这个理论假定有两个前提 : 没有人的生日是二月二十九每个人的生日乃平均分散于一年的 365 天内 16

17 k 个人中至少有两个人的生日相同的概率假定 k 365 k 个数据项中任意两个都不相同的所有取值方式数为 : (365 k 1) 365! (365 k)! k 个数据项中所有取值方式数为 :365 k k 个数据项中任意两个都不相同的概率 Q(365, k) 365! (365 k)! 365 k k 个人中至少有两个人的生日相同的概率 365! P(365, k) 1 Q(365, k) 1 (365 )! 365 k k 17

18 生日悖论推广已知一个在 1 到 n 之间均匀分布的整数型随机变量, 该变量的 k 个取值中至少有两个取值相同的概率 n! Pnk (,) 1 ( )! k n k n 令 P(n, k)>0.5, 可得 : k 1.18 n n 18

19 算法 Find-Collision(h, y, Q) 选择, 0 Q 0 for each x 0 do y hx ( ) x if 对某一 x' x, 有 yx yx' then return(x', x) else return (failure) 定理对任意的功率是 :, 且 0 Q 0 M 1 M 2 M Q 1 1 ( )( ) ( ) M M M, 上述算法的平均情况成 19

20 Merkle Damgård 迭代结构 m[0] m[1] m[2] m[3] ll PB IV (fixed) H h h h h 0 H 1 H 2 H 3 H 4 H(m) 通过压缩函数 h: T X T 得到 Hash 函数 H: X L T. H i - 中间变量 PB: 填充 ll msglen 64 bits 如果 PB 的空间不够, 另加一个分组 Dan Boneh,Online Cryptography Course 20

21 SHA 由美国 NIST 提出,SHS(Secure Hash Standard), 算法为 SHA-1 要求输入小于 2 64 位, 输出为 160 位 (5 个寄存器,A, B, C, D, E) 将明文分成若干 512 位的定长块, 每一块与当前的信息摘要值结合, 产生信息摘要的下一个中间结果, 直到处理完毕 21

22 SHA 的运算过程将消息填充为 512 位的整数倍 5 个 32 位中间变量 a b c d e, 起初值为常数对 5 个 32 位的寄存器 A B C D E, 进行运算 A B C D E 的初值为 0 对每一个 512 位的消息进行如下处理 : 将中间变量 a b c d e 赋给 A B C D E; 进行主循环 4 轮, 每轮 20 次 a=a+a, b=b+b,c=c+c,d=d+d, e=e+e 最后输出为 a b c d e 的级联 22

23 a,b,c,d,e 的初值 a=0x b=0xefcdab89 c=0x98badcfe d=0x e=0xc3d2e1f0 23

24 SHA-1 压缩函数 ( 单步 ) 24

25 非线性函数 F Ch(x, y, z)=(x y) ( x z) 0 t 19 Parity(x, y, z)=x y z 20 t 39 Maj(x, y, z)=(x y) (x z) (y z) 40 t 59 Parity(x, y, z)=x y z 60 t

26 Kt: 常数 Kt=0x5a <=t<20 Kt=0x6ed9eda1 20<=t<40 Kt=0x8f1bbcdc 40<=t<60 Kt=0xca62c1d6 60<=t<80 26

27 Wt: 从当前 512 位输入分组导出的 32 位字消息 :512bit, 16 个 32bit 字 M0~M15 Wt: 32bit 字 0<=t<=15 Wt=Mt 16<=t<=79 W t =(W t-3 W t-8 W t-14 W t-16 )<<<1 27

28 SHA-2 维基百科 28

29 SHA-3 29

30 状态 State y z x 状态的位串表示 :b=1600 S = S[0] S[1] S[b-2] S[b-1] 状态的数组表示 :5 5 w 的数组,w=64 数组中的一位表示为 A[x, y, z] fips_202_draft 30

31 状态 State:plane z x y z x 5 层 plane 每层 plane 包含 5 64=320 位 fips_202_draft 31

32 状态 State:slice y x y z x W=64 层 plane 每层 plane 包含 5 5=25 位 fips_202_draft 32

33 状态 State:sheet y z x 5 层 sheet 每层 sheet 包含 5 64=320 位 fips_202_draft 33

34 状态 State:row,column,lane y z x x fips_202_draft 34

35 状态的两种表示的转换状态的位串表示 :b=1600 S = S[0] S[1] S[b-2] S[b-1] 状态的数组表示 :5 5 w 的数组,w=64 数组中的一位表示为 A[x, y, z] A[x, y, z] = S [w(5y + x) + z]. 例如 : A[0, 0, 0] = S [0] A[0, 0, 1] = S [1] A[1, 1, 62] = S [446] A[2, 1, 62] = S [510] A[4, 0, 63] = S [319] A[2, 1, 63] = S [511] fips_202_draft 35

36 状态的索引关系 Z 2 1 y x fips_202_draft 36

37 KECCAK-p 置换 KECCAK-p[b, nr]: 其中 b 为状态的位数, 为 1600 nr 为迭代次数, 为 24 KECCAK-p[1600, 24] 每一轮的 p 置换由 5 个 step mapping 组成, 依次为 θ, ρ, π, χ, 和 ι. fips_202_draft 37

38 Algorithm 1: θ(a) Input: state array A. Output: state array A. Steps: 1. For all pairs (x, z) such that 0 x < 5 and 0 z < w, let C[x, z] = A[x, 0, z] A[x, 1, z] A[x, 2, z] A[x, 3, z] A[x, 4, z]. 2. For all pairs (x, z) such that 0 x < 5 and 0 z < w let D[x, z] = C[(x 1) mod 5, z] C[(x+1) mod 5, (z 1) mod w]. 3. For all triples (x, y, z) such that 0 x < 5, 0 y < 5, and 0 z < w, let A [x, y, z] = A[x, y, z] D[x, z]. y z x fips_202_draft 38

39 Algorithm 2: ρ(a):input: state array A. Output: state array A. Steps: 1. For all z such that 0 z < w, let A [0, 0, z] = A[0, 0, z]. 2. Let (x, y) = (1, 0). 3. For t from 0 to 23: a. for all z such that 0 z < w, let A [x, y, z] = A[x, y, (z (t + 1)(t + 2)/2) mod w]; b. let (x, y) = (y, (2x + 3y) mod 5). 4. Return A. fips_202_draft 39

40 Algorithm 3: π(a) Input: state array A. Output: state array A. Steps: 1. For all triples (x, y, z) such that 0 x < 5, 0 y < 5, and 0 z < w, let A [x, y, z]= A[(x + 3y) mod 5, x, z]. 2. Return A. fips_202_draft 40

41 Algorithm 4: χ(a) Input: state array A. Output: state array A. Steps: 1. For all triples (x, y, z) such that 0 x < 5, 0 y < 5, and 0 z < w, let A [x, y, z] = A[x, y, z] ((A[(x+1) mod 5, y, z] 1) A[(x+2) mod 5, y, z]). 2. Return A. 41

42 Algorithm 5: rc(t) Input:integer t. Output: bit rc(t). 1. If t mod 255 = 0, return Let R = For i from 1 to t mod 255, let: a. R = 0 R; b. R[0] = R[0] + R[8]; c. R[4] = R[4] + R[8]; d. R[5] = R[5] + R[8]; e. R[6] = R[6] + R[8]; f. R =Trunc8[R]. 4. Return R[0] Algorithm 6: ι(a, ir) Input: state array A; round index ir. Output: A. 1. For all triples (x, y, z) such that 0 x < 5, 0 y < 5, and 0 z < w, let A [x, y, z] = A[x, y, z]. 2. Let RC = 0w. 3. For j from 0 to l, let RC[2 j 1] = rc(j + 7ir). 4. For all z such that 0 z < w, let A [0, 0, z] = A [0, 0, z] RC[z]. 5. Return A. 42

43 KECCAK-p 置换轮函数 : 已知状态数组 A 和轮索引 ir, 轮函数 Rnd 是依次执行 θ, ρ, π, χ, 和 ι, : Rnd(A, ir) = ι(χ(π(ρ(θ(a)))), ir). KECCAK-p[b, nr] 包含 nr 次 Rnd KECCAK-p[1600, 24] fips_202_draft 43

44 Algorithm 8: SPONGE[f, pad, r](m, d) 1. Let P = M pad(r, len(m)). 2. Let n = len(p)/r, c = b r. 3. Let P = P 0 P n 1. len(p i )=r 4. Let S = 0 b. 5. For i from 0 to n 1, let S = f (S (P i 0 c )). 6. Let Z be the empty string. 7. Let Z = Z Trunc r (S). 8. If d Z, then return Trunc d (Z); else continue. 9. Let S = f(s), and continue with Step 7. 44

45 SPONGE[f, pad, r](m, d) KECCAK[c] = SPONGE[KECCAK-p[1600, 24], pad10*1, 1600 c] KECCAK[c] (M, d) = SPONGE[KECCAK-p[1600, 24], pad10*1, 1600 c] (M, d). SHA3-224(M) = KECCAK[448] (M 01, 224); SHA3-256(M) = KECCAK[512] (M 01, 256); SHA3-384(M) = KECCAK[768] (M 01, 384); SHA3-512(M) = KECCAK[1024] (M 01, 512). 45

46 安全性 Security Strengths in Bits Function Output Size Collision Preimage 2nd Preimage SHA < L M SHA min(224, 256 L M SHA-512/ SHA L M SHA-512/ SHA SHA L M SHA SHA SHA SHA fips_202_draft 46

Improved Preimage Attacks on AES-like Hash Functions: Applications to Whirlpool and Grøstl

Improved Preimage Attacks on AES-like Hash Functions: Applications to Whirlpool and Grøstl SKLOIS (Pseudo) Preimage Attack on Reduced-Round Grøstl Hash Function and Others Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian Zou March 20, 2012 Institute. of Software, Chinese Academy