Tài liệu Kỹ thuật lập trình - Chương 11: Hàm hash

Ch ng 11 ươ

HÀM HASH

11.1 T ng quan v hàm Hash ề ổ

ộ ả Đây là hàm có tham s đ u vào là văn b n có chi u dài b t kỳ và chi u ra là m t b n ố ầ ề ề ả ấ

tóm l t có chi u dài c đ nh. ượ ố ị ề

Nh đã nói trong ph n ch ký s , hàm hash có vai trò r t quan tr ng, ngoài tránh ư ữ ấ ầ ố ọ

đ c s gi ượ ự ả ạ ở m o ch ký, nó còn giúp cho quá trình ký di n ra nhanh h n r t nhi u, b i ơ ấ ữ ễ ề

ề hàm hash có t c đ l n, nh ng quan tr ng nh t là nó làm ch ký ng n đi r t nhi u đi u ố ộ ớ ư ữ ề ấ ắ ấ ọ

này có vai trò r t quan tr ng trong th c t khi làm vi c v i s l ng l n các ch ký. ự ế ấ ọ ệ ớ ố ượ ữ ớ

Đ t o ra hàm Hash thì hàm hash ph i th a mãn các yêu c u sau : ể ạ ả ầ ỏ

1. Đ i s c a hàm hash là b n tin có chi u dài b t kỳ; ố ố ủ ề ả ấ

2. Giá tr c a hàm hash có chi u dài không đ i; ị ủ ề ổ

ệ 3. Hàm H(x) c n ph i có tính toán hi u qu , t c là thu t toán Hash khi th c hi n ả ứ ự ệ ậ ầ ả

trên ph n c ng và ph n m m c n ph i có công su t l n. Ph i đ m b o đ ả ầ ứ ả ả ấ ớ ả ượ c ề ầ ầ

r ng quá trình ký và ki m tra lên giá tr c a hàm hash nhanh h n so v i quá ằ ị ủ ể ơ ớ

trình ký và ki m tra trên b n thân b n tin; ể ả ả

4. Cho y là giá tr c a hàm hash, thì khó v m t tính toán đ tìm đ ề ặ ị ủ ể ượ ỏ c x th a

5. Hàm hash là hàm không va ch m, t c là khi cho tr

h(x)=y, t c là hàm hash ph i là hàm m t chi u; ứ ề ả ộ

ứ ạ ả ể

th c hi n đ c v m t tính toán đ tìm đ c b n x’ c b n tin x, không th ướ „ x sao cho h(x)=h(x’). ệ ượ ề ặ ự ể ượ ả

6. Hàm hash là hàm không va ch m m nh, khi không th th c hi n đ ể ự „ x mà h(x)=h(x’).

ạ ạ ệ ượ ề ặ c v m t

c hai b n tin x và x’, v i x’ tính toán đ tìm đ ượ ể ả ớ

1. Cho tr

: C u trúc chung c a hàm băm Hash g m các ph n sau ủ ầ ấ ồ

c m t thông đi p ướ ệ M có đ dài b t kỳ. Tùy theo thu t toán đ ấ ậ ộ ộ ượ ử c s

d ng, chúng ta có th c n thêm thông đi p các bit đ nh n đ ụ ể ầ ệ ể ậ ượ ệ c thông đi p

có đ dài là b i s c a chi u dài c đ nh cho tr c đ ph c v cho vi c tính ộ ố ủ ố ị ề ộ ướ ể ụ ụ ệ

toán. Chia thông đi p thành t ng kh i có kích th c b ng nhau t c là M=( M1, ừ ệ ố ướ ằ ứ

M2, …Ms).

2. G i ọ Hi là tr ng thái có kích th ạ

c ướ n bit, n là chi u dài c a giá tr hàm băm, F ủ ề ị

là hàm nén th c hi n thao tác tr n kh i d li u v i tr ng thái hi n hành: ố ữ ệ ớ ạ ự ệ ệ ộ

0, b ng véc t

• Kh i t o H ở ạ

kh i t o nào đó. ằ ơ ở ạ

i=F(Hi-1,Mi), i˛

• Th c hi n tr n: H ệ

3. Giá tr c a H

s là giá tr c a hàm băm.

[1,s]. ự ộ

ị ủ ị ủ

N u hàm hash đ c cho là b n v ng, khi có m t s thay đ i b t kỳ đ i s c a nó ế ượ ố ố ủ ổ ấ ộ ự ữ ề

( t c là b n tin đ u vào) thì giá tr c a nó cũng thay đ i ng u nhiên, t c là m i bít trong ị ủ ứ ứ ẫ ả ầ ổ ỗ

n bít có xác su t b thay đ i là ½. M t ph ấ ị ổ ộ ươ ộ ng pháp t n công đ n gi n trên hàm m t ơ ấ ả

chi u hash là l a ch n b n tin sao cho giá tr hàm hash c a nó b ng v i giá tr hàm hash ị ự ủ ề ằ ả ọ ớ ị

đã cho hay nói cách khác đây là ph ng pháp véc c n, chúng ta g i s l ươ ọ ố ượ ạ ầ ng b n tin c n ả

ch n là N mà th a mãn đ ỏ ọ ượ ủ c đi u trên. Chúng ta th y xác su t đ giá tr hàm hash c a ấ ể ề ấ ị

- 21

m t b n tin b t kỳ không trùng v i giá tr H đã cho b ng , n là chi u dài c a giá tr ộ ả ằ ấ ớ ị ủ ề ị

N b n tin khác nhau mà giá tr hàm hash. Nh th xác su t đ không m t b n tin nào t ấ ể ư ế ừ ả ị

) Nn

. Xác su t đ t n t c a b n tin đó không trùng v i H b ng ủ ả ằ ớ ấ ể ồ ạ i m t b n tin ộ ả ộ ả ( -= 21

-= 1

-= Nn )21(1'

c là: mà giá tr hàm hash c a nó b ng H cho tr ủ ằ ị ướ - - .

S d ng công th c Niut n, chúng ta nh n đ c giá tr g n đúng sau: ử ụ ậ ượ ứ ơ ị ầ

( NN

x N )

-= 1

...

( NN !2

)(1 !3

- - - - » - - , n u nh x nh , ỏ ư ế

2(cid:215)

n 2 và

- (cid:215) » » Nên chúng ta có: .

12 -

» Khi p=1/2, chúng ta có . V i k thu t tính toán hi n nay thì n=64 thì t n công ệ ớ ỹ ậ ấ

có th th c hi n đ c n u có tài nguyên đ l n cho tính toán. N u nh n > 96 thi ể ự ệ ượ ủ ớ ư ế ế

128

đ c xem là an toàn đ i v i cách t n công này, th nh ng còn nhi u cách tân công ượ ố ớ ư ế ề

ấ ‡n . khác, nên khuy n cáo ch n giá tr ị ế ọ

11.2 Hàm băm MD4

Hàm hash MD4 đ c Rivest đ xu t năm 1990. Chúng ta xem miêu t ượ ề ấ ả thu t tóan ậ

MD4.

64.

Đ u vào ầ : B n tin M có chi u dài nh h n 2 ề ỏ ơ ả

ộ ủ 1. M r ng b n tin: Thêm các bít vào b n tin đ b n tin có chi u dài là b i c a ả ể ả ở ộ ề ả

512. Quá trình thêm di n ra nh sau. Thêm bít 1 vào cu i b n tin, sau đó thêm ố ả ư ễ

vào m t s bít 0 đ nh n b n tin có chi u dài là đ ng d v i 448 modulo 512, ề ể ậ ộ ố ư ớ ả ồ

và cu i cùng thêm vào 64 bít, 64bít này bi u di n chi u dài c a b n tin ban ủ ả ể ễ ề ố

c thêm vào bao g m các kh i M đ u. B n tin đ ả ầ ượ ồ ố ỗ 1, M2, … , Mn, chi u dài m i ề

kh i là 32 bít. ố

2. Kh i t o các bi n: ở ạ ế

A=67452301 B=EFCDAB89 C=98BADCFE D=10325476

3. i=1

4. for j=1 to 16 do X[j]=M[16i+j]

5. AA=A;BB=B;CC=C;DD=D;

6. round1

7. round2

round3

9. N u i < n/16 thì i=i+1 và quay v b c 4. ề ướ ế

10. A=A+AA;B=B+BB;C=C+CC;D=D+DD;

: 128 bít là liên k t c a 4 t 32 bít:A|B|C|D. Đ u raầ ế ủ ừ

Trong 3 vòng “round1”, “round2”,”round3” s d ng 3 hàm bool sau: ử ụ

f(X,Y,Z)=(X^Y)v(( (cid:216) X)^Z).

g(X,Y,Z)=(X^Y)v(X^Z)v(Y^Z). h(X,Y,Z)=X ¯ Y ¯ Z.

Round1 đ c miêu t nh sau: ượ ả ư

1. A=(A+f(B,C,D)+X[1])<<3

2. D=(D+f(A,B,C)+X[2])<<7

3. C=(C+f(D,A,B)+X[3])<<11

4. B=(B+f(C,D,A)+X[4])<<19

5. A=(A+f(B,C,D)+X[5])<<3

7. C=(C+f(D,A,B)+X[7])<<11

6. D=(D+f(A,B,C)+X[6])<<7

8. B=(B+f(C,D,A)+X[8])<<19

9. A=(A+f(B,C,D)+X[9])<<3

10. D=(D+f(A,B,C)+X[10])<<7

11. C=(C+f(D,A,B)+X[11])<<11

12. B=(B+f(C,D,A)+X[12])<<19

13. A=(A+f(B,C,D)+X[13])<<3

14. D=(D+f(A,B,C)+X[14])<<7

15. C=(C+f(D,A,B)+X[15])<<11

16. B=(B+f(C,D,A)+X[16])<<19

Round2 đ c miêu t nh sau: ượ ả ư

1. A=(A+g(B,C,D)+X[1]+5A827999)<<3

2. D=(D+g(A,B,C)+X[2] +5A827999)<<5

3. C=(C+g(D,A,B)+X[3] +5A827999)<<9

4. B=(B+g(C,D,A)+X[4] +5A827999)<<13

5. A=(A+g(B,C,D)+X[5] +5A827999)<<3

6. D=(D+g(A,B,C)+X[6] +5A827999)<<5

8. B=(B+g(C,D,A)+X[8] +5A827999)<<13

7. C=(C+g(D,A,B)+X[7] +5A827999)<<9

9. A=(A+g(B,C,D)+X[9] +5A827999)<<3

10. D=(D+g(A,B,C)+X[10] +5A827999)<<5

11. C=(C+g(D,A,B)+X[11] +5A827999)<<9

12. B=(B+g(C,D,A)+X[12] +5A827999)<<13

13. A=(A+g(B,C,D)+X[13] +5A827999)<<3

14. D=(D+g(A,B,C)+X[14] +5A827999)<<5

15. C=(C+g(D,A,B)+X[15] +5A827999)<<9

16. B=(B+g(C,D,A)+X[16] +5A827999)<<13

Round3 đ c miêu t nh sau: ượ ả ư

1. A=(A+h(B,C,D)+X[1]+6ED9EBA1)<<3

2. D=(D+h(A,B,C)+X[2] +6ED9EBA1)<<9

3. C=(C+h(D,A,B)+X[3] +6ED9EBA1)<<11

4. B=(B+h(C,D,A)+X[4] +6ED9EBA1)<<15

5. A=(A+h(B,C,D)+X[5] +6ED9EBA1)<<3

7. C=(C+h(D,A,B)+X[7] +6ED9EBA1)<<11

6. D=(D+h(A,B,C)+X[6] +6ED9EBA1)<<9

8. B=(B+h(C,D,A)+X[8] +6ED9EBA1)<<15

9. A=(A+h(B,C,D)+X[9] +6ED9EBA1)<<3

10. D=(D+h(A,B,C)+X[10] +6ED9EBA1)<<9

11. C=(C+h(D,A,B)+X[11] +6ED9EBA1)<<11

12. B=(B+h(C,D,A)+X[12] +6ED9EBA1)<<15

13. A=(A+h(B,C,D)+X[13] +6ED9EBA1)<<3

14. D=(D+h(A,B,C)+X[14] +6ED9EBA1)<<9

15. C=(C+h(D,A,B)+X[15] +6ED9EBA1)<<11

16. B=(B+h(C,D,A)+X[16] +6ED9EBA1)<<15

Chúng ta th y MD4 ch y u th c hi n nh các phép toán logic và m t phép công ủ ế ự ệ ấ ờ ộ

theo modulo 232 nên thu t toán ch y r t nhanh, thích ng v i vi c s lý b n tin có đ ệ ử ạ ấ ứ ả ậ ớ ộ

i m t s h n ch . C th là có th tìm th y va l n. Tuy nhiên thu t toán MD4 t n t ậ ớ ồ ạ ế ụ ể ộ ố ạ ể ấ

ch m n u s d ng 2 vòng. Vì đi m y u này mà MD5 ra đ i thay th cho MD4. ế ử ụ ể ế ế ạ ờ

11.3 Hàm băm MD5

Thu t toán MD5 ra đ i năm 1992. Nó có c u trúc thu t toán gi ng v i MD4. Ch có ấ ậ ậ ờ ố ớ ỉ

ổ ữ khác là MD5 s d ng 4 vòng, trong khi MD4 s d ng 3 vòng, và có m t s thay đ i n a. ộ ố ử ụ ử ụ

C th nh sau: ụ ể ư

i đ m t tính đ i x ng: ố ứ

Hàm g thi t k tr l ế ế ở ạ ể ấ g(X,Y,Z)=(X^Z) v (Y^( (cid:216) Z))

ộ

S d ng thêm m t hàm i: ử ụ (X v ( (cid:216) Z)) i(X,Y,Z)=Y ¯

T 4 hàm f,g,h và i ta đi đ nh nghĩa 4 hàm FF,GG,HH và II nh sau: ừ ư ị

FF(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<

GG(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<

HH(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<

II(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<

Chúng ta đ nh nghĩa các h s d ch trái: ệ ố ị ị

S11= 7; S12= 12; S13= 17; S14= 22

S21= 5; S22= 9; S23= 14; S24= 20

S31= 4; S32= 11; S33= 16; S34= 23

S41= 6; S42= 10; S43= 15; S44= 21

4 vòng t ng ng đ c miêu t nh sau: ươ ứ ượ ả ư

Round

1. FF (a, b, c, d, X[1], S11, 0xd76aa478);

2. FF (d, a, b, c, X[2], S12, 0xe8c7b756);

3. FF (c, d, a, b, X[3], S13, 0x242070db);

4. FF (b, c, d, a, X[4], S14, 0xc1bdceee);

5. FF (a, b, c, d, X[5], S11, 0xf57c0faf);

6. FF (d, a, b, c, X[6], S12, 0x4787c62a);

7. FF (c, d, a, b, X[7], S13, 0xa8304613);

8. FF (b, c, d, a, X[8], S14, 0xfd469501);

9. FF (a, b, c, d, X[9], S11, 0x698098d8);

10. FF (d, a, b, c, X[10],S12, 0x8b44f7af);

11. FF (c, d, a, b, X[11],S13, 0xffff5bb1);

12. FF (b, c, d, a, X[12],S14, 0x895cd7be);

13. FF (a, b, c, d, X[13],S11, 0x6b901122);

14. FF (d, a, b, c, X[14],S12, 0xfd987193);

15. FF (c, d, a, b, X[15],S13, 0xa679438e);

16. FF (b, c, d, a, X[16],S14, 0x49b40821);

Round 2

1. GG (a, b, c, d, X[2], S21, 0xf61e2562);

2. GG (d, a, b, c, X[7], S22, 0xc040b340);

3. GG (c, d, a, b, X[12],S23, 0x265e5a51);

4. GG (b, c, d, a, X[1], S24, 0xe9b6c7aa);

5. GG (a, b, c, d, X[6], S21, 0xd62f105d);

6. GG (d, a, b, c, X[11],S22, 0x2441453);

7. GG (c, d, a, b, X[16],S23, 0xd8a1e681);

8. GG (b, c, d, a, X[5], S24, 0xe7d3fbc8);

9. GG (a, b, c, d, X[10],S21, 0x21e1cde6);

10. GG (d, a, b, c, X[15],S22, 0xc33707d6);

11. GG (c, d, a, b, X[4], S23, 0xf4d50d87);

12. GG (b, c, d, a, X[9], S24, 0x455a14ed);

13. GG (a, b, c, d, X[14],S21, 0xa9e3e905);

14. GG (d, a, b, c, X[3], S22, 0xfcefa3f8);

15. GG (c, d, a, b, X[8], S23, 0x676f02d9);

16. GG (b, c, d, a, X[13],S24, 0x8d2a4c8a);

Round 3

1. HH (a, b, c, d, X[6], S31, 0xfffa3942);

2. HH (d, a, b, c, X[9], S32, 0x8771f681);

3. HH (c, d, a, b, X[12],S33, 0x6d9d6122);

4. HH (b, c, d, a, X[15],S34, 0xfde5380c);

5. HH (a, b, c, d, X[2], S31, 0xa4beea44);

6. HH (d, a, b, c, X[5], S32, 0x4bdecfa9);

7. HH (c, d, a, b, X[8], S33, 0xf6bb4b60);

8. HH (b, c, d, a, X[11],S34, 0xbebfbc70);

9. HH (a, b, c, d, X[14],S31, 0x289b7ec6);

10. HH (d, a, b, c, X[1], S32, 0xeaa127fa);

11. HH (c, d, a, b, X[4], S33, 0xd4ef3085);

12. HH (b, c, d, a, X[7], S34, 0x4881d05);

13. HH (a, b, c, d, X[10],S31, 0xd9d4d039);

14. HH (d, a, b, c, X[13],S32, 0xe6db99e5);

15. HH (c, d, a, b, X[16],S33, 0x1fa27cf8);

16. HH (b, c, d, a, X[3], S34, 0xc4ac5665);

Round 4

1. II (a, b, c, d, X[1], S41, 0xf4292244);

2. II (d, a, b, c, X[8], S42, 0x432aff97);

3. II (c, d, a, b, X[15],S43, 0xab9423a7);

4. II (b, c, d, a, X[6], S44, 0xfc93a039);

5. II (a, b, c, d, X[13],S41, 0x655b59c3);

6. II (d, a, b, c, X[4], S42, 0x8f0ccc92);

7. II (c, d, a, b, X[11],S43, 0xffeff47d);

8. II (b, c, d, a, X[2], S44, 0x85845dd1);

9. II (a, b, c, d, X[9], S41, 0x6fa87e4f);

10. II (d, a, b, c, X[16],S42, 0xfe2ce6e0);

11. II (c, d, a, b, X[7], S43, 0xa3014314);

12. II (b, c, d, a, X[14],S44, 0x4e0811a1);

13. II (a, b, c, d, X[5], S41, 0xf7537e82);

14. II (d, a, b, c, X[12],S42, 0xbd3af235);

15. II (c, d, a, b, X[3], S43, 0x2ad7d2bb);

16. II (b, c, d, a, X[10],S44, 0xeb86d391);

11.4 Hàm băm SHS

Thu t toán SHS (Secure Hash Standard) do NIST và NSA xây d ng và công b trên ự ậ ố

Federal Register ngày 31/01/1992 và tr thành chu n t ngày 13/05/1993. ẩ ừ ở

Thu t toán đ c miêu t nh sau: ậ ượ ả ư

ộ ủ 1. M r ng b n tin: Thêm các bít vào b n tin đ b n tin có chi u dài là b i c a ể ả ở ộ ề ả ả

512. Quá trình thêm di n ra nh sau. Thêm bít 1 vào cu i b n tin, sau đó thêm ố ả ư ễ

vào m t s bít 0 đ nh n b n tin có chi u dài là đ ng d v i 448 modulo 512, ề ộ ố ư ớ ể ả ậ ồ

ầ và cu i cùng thêm vào 64 bít, 64bít này bi u di n chi u dài c a b n tin ban đ u. ủ ả ề ễ ể ố

B n tin đ c thêm vào bao g m các kh i M ả ượ ố ồ 1, M2, … , Mn, chi u dài m i kh i là ề ỗ ố

32 bít.

2. Kh i t o các bi n: ở ạ ế

A=67452301 B=EFCDAB89 C=98BADCFE D=10325476 E=C3D2E1F0

i=1 3.

6. AA=A;BB=B;CC=C;DD=D;EE=E;

for j=1 to 16 do X[j]=M[16i+j] for j=16 to 80 do X[j]=(X[j-3] ¯ X[j-8] ¯ X[j-14] ¯ X[j-16])<<<1

7. for j=1 to 80 do temp=(AA<<<5)+F(t,BB,CC,DD)+EE+K[t]

EE=DD

DD=CC

CC=BB<<<30

BB=AA

8. A=A+AA;B=B+BB;C=C+CC;D=D+DD;E=E+EE;

AA=temp

9. N u i < n/16 thì i=i+1 và quay v b c 4. ề ướ ế

t c a b n tin có chi u dài 160 bít là n i c a 5 t 32 bít:A|B|C|D|E 10. B n tóm l ả ượ ủ ả ố ủ ề ừ

V i F(t,X,Y,Z) đ ớ ư ượ

£ £

£ £ c cho nh sau: F(t,X,Y,Z)=(X^Y)v(( (cid:216) X)^Z), khi F(t,X,Y,Z)=X ¯ Y ¯ Z, khi

£ £

£ £ F(t,X,Y,Z)=(X^Y)v(X^Z)v(Y^Z), khi F(t,X,Y,Z)=X ¯ Y ¯ Z, khi

Và K[t] đ c xác đ nh nh sau: ượ ư ị

£ £ K[t]=5A827999, khi

£ £ K[t]=6ED9EBA1, khi

£ £ K[t]=8F1BBCDC, khi

£ £ K[t]=CA62C1D6, khi

11.5 Hàm băm SHA

Thu t toán hàm băm an toàn SHA (Secure Hash Algorithm) đ ậ ượ c ch m nh n trong s ậ ấ ố

c ng d ng cùng v i thu t toán chu n ch ký s các chu n c a M năm 1992 và nó đ ỹ ẩ ủ ượ ứ ụ ữ ẩ ậ ớ ố

DSS. Khi đ u vào là m t b n tin M có chi u dài b t kỳ, đ u ra là là 160 bít rút g n. ề ộ ả ấ ầ ầ ọ

Chúng ta xem làm vi c c a thu t toán chi ti t h n. ệ ủ ậ ế ơ

Trong SHA-1 s d ng hàm f(t, B, C, D), v i 0 32 bít. ử ụ ớ £ t£ 79; B, C và D –là các t ừ

f(t, B, C, D) = (B (cid:217) C) (cid:218) (((cid:216) B) (cid:217) D) khi 0£ t£ 19

f(t, B, C, D) = B ¯ C ¯ D khi 20£ t£ 39

f(t, B, C, D) = (B (cid:217) C) (cid:218) (B (cid:217) D) (cid:218) (C (cid:217) D) khi 40£ t£ 59

f(t, B, C, D) = B ¯ C ¯ D khi 60£ t£ 79

và s d ng các h ng s : ố ử ụ ằ

khi 0£ t£ 19 Kt = 5A827999

khi 20£ t£ 39 Kt = 6ED9EBA1

khi 40£ t£ 59 Kt = 8F1BBCDC

khi 40£ t£ 79 Kt = CA62C1D6

Thu t toán Hash SHA-1 đ c mi u t b i các b c sau: ậ ượ ể ả ở ướ

64 bít.

1) M r ng b n tin: thêm vào bít đ chi u dài b n tin là b i c a 512. Quá trình thêm

Đ u vào : b n tin có chi u dài <2 ầ ề ả

ộ ủ ở ộ ể ề ả ả

di n ra nh sau. Thêm bít 1 vào cu i b n tin, sau đó thêm vào m t s bít 0 đ ố ả ộ ố ư ễ ể

nh n b n tin có chi u dài là đ ng d v i 448 modulo 512, và cu i cùng thêm vào ư ớ ề ậ ả ồ ố

64 bít, 64bít này bi u di n chi u dài c a b n tin ban đ u. B n tin đ c thêm vào ủ ả ể ễ ề ầ ả ượ

1, M2, … , Mn, chi u dài m i kh i là 512 bít.

bao g m các kh i M ố ồ ề ố ỗ

2) Kh i t o các bi n ế ở ạ

H0 := 67452301, H1 := EFCDAB89, H2 := 98BADCFE,

H3 := 10325476, H4 := C3D2E1F0

3) i := 1

i thành 16 t

0, w1, …, w15.

4) Chia kh i Mố

5) Đ i v i các t: 16

32 bít w ừ

đây l nh “<<

l nh d ch trái x bít. ệ ị

6) A := H0, B := H1, C := H2, D := H3, E := H4.

7) Đ i v i t t c các t t ố ớ ấ ả ừ 0 đ n 79 ế

TEMP := (A <<< 5 + f(t, B, C, D) + E + wt + Kt) mod 232;

8) H0 := H0 + A, H1 := H1+B, H2 := H2 + C, H3 := H3 + D, H4 := H4 + E,

E := D; D := C; C := B <<< 30; B := A; A := TEMP.

T t c các l nh c ng theo modulo 2 ộ ấ ả ệ

9) N u i

: b n băm rút g n có chi u dài 160 bít là liên k t c a các t 32 bít H0 | H1 | Đ u raầ ế ủ ề ả ọ ừ

H2 | H3 | H4.

Chú ý: Ngoài SHA-1 chúng ta v a xem, còn có nh ng thu t toán có chi u dài khác ừ ữ ề ậ

đây không đ c miêu t nhau, nh ng v c b n thu t toán là gi ng SHA-1, nên ậ ề ơ ả ư ố ở ượ ả ụ c

th mà ch nêu ra b ng tóm t t so sánh c a các bi n d ng khác nhau c a SHA. ể ả ỉ ắ ế ạ ủ ủ

Algorithm

Rounds

Operations

Collision

Output size (bits)

Internal state size (bits)

Block size (bits)

Max message size (bits)

Word size (bits)

SHA-0

160

512

264 − 1

+,and,or,xor,rotfl

Yes

SHA-1

160

512

264 − 1

+,and,or,xor,rotfl

263 attack

256/224

256

512

264 − 1

+,and,or,xor,shr,rotfr None

SHA- 256/224

512/384

512

1024

2128 − 1

+,and,or,xor,shr,rotfr None

SHA- 512/384

11.6 Xây d ng hàm băm trên c s m t mã đ i x ng ơ ỡ ậ ố ứ ự

M t trong các ph ng pháp hi u qu đ xây d ng hàm hash là xây d ng trên c s ộ ươ ả ể ơ ở ự ự ệ

hàm m t mã kh i. Gi s E là hàm mã kh i an toàn (có th s d ng hàm m t mã là hàm ậ ố ả ử ể ử ụ ậ ố

MMM = (

,...,

)

bi n đ i m t chi u) v i kích th c kh i là m bít, cho b n tin đ u vào đ c chia ra n ế ề ộ ớ ổ ướ ả ầ ố ượ

MHEH (

)

kh i m bít: i d ng sau: ố . Hàm tính giá tr băm có th vi ị t d ể ế ướ ạ

- ,i=1,2,…,n.

0 là giá tr ban đ u đ c bi

đây H t. Giá tr băm c a hàm H=H ở ặ ầ ị ệ ủ ị

S đ c u trúc đ n gi n nh t xây d ng hàm Hash mang tên Rabin đ c miêu t ơ ồ ấ ự ấ ả ơ ượ ả ư nh

hình 11.1.

M

M 1

M 2

H

H 0

H 1

i-1

n-1

H 2

E

Hình 11.1. S đ t o hàm Hash Rabin

ơ ồ ạ

S đ hàm Hash Rabin có th vi

i d ng công th c:

ơ ồ

t d ể ế ướ ạ

ứ

HEH

(

...,2,1

ng pháp t n công t ng h p lên hàm Hash xây d ng trên s đ Rabin là t n công theo

ươ

ơ ồ

ự

ấ

ợ

ổ

gi a. Cách t n công này không ph thu c vào hàm mã kh i c th nào. Có

ki u g p nhau ặ

ể

ở ữ

ụ

ấ

ộ

128

ố ụ ể ‡m

th tránh đ

c kh i

bít, ví

ể

ượ

c phép t n công này n u ch n hàm mã kh i v i kích th ọ

ố ớ

ế

ấ

ướ

ố

d nh AES, RC6…vv. ụ ư

Chúng ta có th li

ể ệ

t kê m t s s đ khác, ph c v cho vi c xây d ng hàm Hash đ ụ

ộ ố ơ ồ

ụ

ự

ệ

ượ c

miêu t

ả

trong b ng sau: ả

MEH H

i HMEH (

H =

)

i (

i 1) HM

MEH H

i M

( HMEH

)

H i = HEH

(

1 H

¯ Công th cứ = ( ) S th t ố ứ ự 1 - ¯ ¯ ¯ - - 2 - ¯ ¯ - 3 - ¯ ¯ - 4 - ¯ - - 5

i HMEH (

1 HM

1) 1)

M =

¯ ¯ ¯ - - 6

i (

HEH

i 1)

¯ ¯ - - 7

HMEH (

¯ ¯ - - 8

i 1) )

i M

(

HM i

(

HM i

i 1) )

i M

(

HM i

(

i M

M i = EH i = EH i = EH i = EH i

i 1)

HM i

¯ ¯ 9 - ¯ - - ¯ 10 - ¯ - ¯ 11 - ¯ - - ¯ 12 -

D i đây là bi u di n m t s s đ t ộ ố ơ ồ ươ ứ ng ng v i b ng trên … ớ ả ướ ể ế

H

H 0

i-1

n-1

H

M 1

M i

M n

H 1

H i

E

M

M 1

H

H i-1

H 0

n-1

H 1

H i

E

M 1

M n

M i

H i-1

H n-1

H 0

H 1

H i

H n

E

Hình 11.2.S đ bi u di n hàm Hash t

ng ng v i ph

ng án 1 (a), 5(b) và 10 (c)

ơ ồ ể

ễ

ươ ứ

ớ

ươ

ở

b ng…ả

Trên c s ba tham s H

ng án xây d ng hàm

ơ ở

ố i-1, Mi-1 và Mi có th xây d ng r t nhi u ph ể

ự

ề

ấ

ươ

ự

Hash khác v i vi c s d ng m t thanh ghi có kích th

c l n.

ệ ử ụ

ớ

ộ

ướ ớ

ầ Th nh ng chúng ta quan tâm nh t là xây d ng trên c s hàm m t chi u F không có đ u ự

ơ ở

ế

ề

ấ

ộ

‡m

128

ng án đ

c nêu ra trên hình 11.3, các hàm F ph i có đ u vào

bít.

vào ph . Các ph ụ

ươ

ượ

ả

ầ

M

i-1

Hi-1

H i

F

M

i-1

Hi-1

H i

F

M

Hi-1

H i

F

M

Hi-1

H i

F

Hình 11.3. S đ xây d ng hàm Hash trên c s bi n đ i kh i m t chi u ề

ơ ở ế

ơ ồ

ự

ộ

ổ

ố

Hàm m t chi u có th xây d ng trên c s hàm m t mã kh i b n v ng E, ví d có th

ố ề

ơ ở

ữ

ụ

ự

ể

ề

ậ

ộ

ể

xây d ng F theo công th c sau:

ứ

ự

XF (

)

XE ( K

đây K là m t s khóa c đ nh đã bi

ở

ộ ố

ố ị

ế

t. Đ i v i m t thu t toán E ộ

ố ớ

ậ

K v ng ch c thì hàm đã ắ

ữ

cho là hàm m t chi u, b i vì chúng ta không bi

t véc t

c hình thành b i đ u ra c a E

ề

ộ

ở

ế

đ ơ ượ

ở ầ

ủ

N u kích th

c c a hàm Hash nh , thì có th tìm đ

c 2 văn b n có cùng giá tr hàm băm,

ế

ướ ủ

ể

ỏ

ượ

ả

ị

ng bi n đ i c a hàm, cách t n công này có

t c là có va ch m mà không ph thu c vào s l ứ

ố ượ

ụ

ạ

ộ

ổ ủ

ế

ấ

tên ngày sinh nh t. Ý t

ậ

ưở

ng c a ph ủ

ươ

ầ ng pháp t n d a trên bài toán ngày sinh nh t sau. C n

ự

ấ

ậ

ph i ch n m t nhóm bao nhiêu ng

i đ xác su t hai ng

i có cùng ngày sinh nh t là 0.5?

ả

ọ

ộ

ườ ể

ấ

ườ

ậ

V n đ

ch là xác su t trùng ngày sinh nh t đ i v i m t c p ng u nhiên là p’=1/365, còn

ề ở

ấ

ậ ố ớ

ộ ặ

ẫ

ấ

ổ

11.7 T n công hàm Hash theo ki u ngày sinh nh t ậ ể ấ

nn (

2/)1

trong nhóm g m n ng

i có

c p khác nhau. T đây d dàng nh n đ

c đánh

ồ

ườ

ừ

ể

ặ

ậ

ượ

p =

2np '

giá g n đúng. Xác su t đ t n t

i ít nh t m t c p có cùng ngày sinh là

, t

đây

ấ ể ồ ạ

ầ

ộ ặ

ấ

ừ

n »

/1 p

p=1/2 thì chúng ta thu đ

c ượ

Chúng ta xem s d ng bài toán ngày sinh nh t đ tìm va ch m trong hàm Hash nh th

ậ ể

ử ụ

ư ế

ạ

nào. Gi

s cho H là hàm Hash v i kích th

c đ u ra là m bít. Chúng ta có N b n tin khác

ả ử

ớ

ướ

ầ

ả

,)( iM i

...1

nhau

, tính toán giá tr băm c a các b n tin này, giá tr t

ị ươ

ủ

ả

ị

ng ng là ứ

)(iH . N uế

» -

nh hàm Hash là hàm bi n đ i gi

ng u nhiên thì d dàng tính đ

c xác su t sao cho gi a N

ế

ổ

ả

ễ

ẫ

ượ

ữ

ấ

giá tr ị

ượ

c hai nh nhau. ư

)(iH không tìm đ

Đ u tiên chúng ta xem đánh giá d a trên tính toán g n đúng, sao cho s l

ng va ch m là

ố ượ

ự

ầ

ạ

i là

đ nh . Chúng ta ch n m t s giá tr ủ ỏ

ộ ố

ọ

ị

ấ ể

ầ

ớ

ạ

)1(H . Xác su t đ nó không trùn v i các ph n còn l

)1(

Nm )21(

i là

Ti p t c ch n m t s giá tr m i ị ớ

ế ụ

ộ ố

ọ

ấ ể

ầ

ớ

ạ

)2(H . Xác su t đ nó không trùng v i ph n còn l

- - - »

)2(

Nm )21(

Chúng ta ch n t

ng t

nh v y đ i v i giá tr m i c a hàm Hash, trong b

c th I chúng

ọ ươ

ự ư ậ

ị ớ ủ

ố ớ

ướ

ứ

ta thu đ

c xác su t không trùng là

ượ

ấ

- - - »

iNm

)( iP

)21(

- - - »

c ki m tra không trùng. Xác su t đ không T t c chúng ta c n th c hi n N-1 b ầ ấ ả ự ệ ướ ấ ể ể

m t giá tr trong chúng không trùng là: ộ ị

iNm

Nm )21(

...

)21(

...

m )21(

+++=

- - - - - - - - (cid:229) - (cid:215) (cid:215) - (cid:215) (cid:215) - (cid:215) - »

...

(

NN (

2/)1

V i ớ (cid:229)

Xác su t tìm th y va ch m là ấ

ạ

ấ

- -

-= 1

-= m )21(1'

1(1

m )2

2 2

- - - - (cid:229) (cid:215) » (cid:215) - - » - (cid:229) .

- m

2/1

V i xác su t va ch m là ½ thì ta có bi u th c: ứ ể ấ ạ ớ - (cid:215) ,

1/2:

T đây chúng ta xác đ nh gía tr N ừ ị ị

2/1

» .

,)( iH i

...1

ợ Chúng ta xem tính cách tính chính xác h n xác su t tìm va ch m trong t p h p ơ ạ ấ ậ

)2(H . Xác

, có th nh n đ ể ậ ượ c b ng cách r t đ n gi n sau. Chúng ta ch n ọ ả ấ ơ ằ

)2(

m )21(

. Ti p t c ch n

su t đ ấ ể

ế ụ

ọ

)2(H không trùng

)1(H là

)3(H . Xác su t đ ấ ể

)3(H không

trùng v i

ớ

ệ

ề

ớ

)2(H và

)1(H , v i đi u ki n

)1(H và

)2(H không trùng nhau là

)3(

)

21(

m )221)(

( Np

. M t cách t

ng t

ộ

ươ

ự

, chúng ta xác đ nh xác su t ấ

ị

đ ể

( NH không

(

trùng v i m t trong các giá tr ị

ớ

ộ

, v i đi u ki n là các giá tr ị ệ

ề

ớ

)1(H ,

)2(H ,…,

-NH

)1(H ,

)2(H ,…,

(

khác

nhau

đôi

m t.

Chúng

t ng ừ

ộ

nh n ậ

ượ c

-NH

- - (cid:215) -

(

)

)2(

)3(

(

...

(1[

m ]2)1

. Nh v y giá tr chính xác c a xác su t không có

ư ậ

ủ

ấ

ị

s va ch m là: ự

ạ

- - (cid:215) - - (cid:215) (cid:215) (cid:215) (cid:215)

(

)

m )221()21(

...

i (1[

m ]2)1

...

(1[

m ]2)1

m )2

= 1

- - - - - - (cid:215) - (cid:215) - - (cid:215) (cid:215) (cid:215) - - (cid:215) (cid:215) (cid:215) - (cid:215) (cid:213) .

ứ ầ T đây chúng ta xác đ nh xác su t có s va ch m là p=1-p’. Áp d ng công th c g n ừ ụ ự ạ ấ ị

-1

- » đúng . Chúng ta thu đ c:ượ

m )2

exp(

m )2

exp(

m )2

exp[

NN (

2)1

]

= 1

- - - - - - - - (cid:215) - - (cid:215) - (cid:215) - » (cid:215) - (cid:229) (cid:213) (cid:213) .

-= 1'

exp[

NN (

2)1

]

Xac su t t n t i ít nh t m t va ch m là: ấ ồ ạ ạ ấ ộ - (cid:215) - - - » .

T đây ta d d ng nh n đ ể ạ ậ ượ ừ c đi u sau: ề

+ 2 1 m

(cid:246) (cid:230) (cid:247) (cid:231) » (cid:247) (cid:231) , - ł Ł

Hay

+ 2 1 m

(cid:246) (cid:230) (cid:247) (cid:231) » (cid:247) (cid:231) , - ł Ł

+ 2 1 m

(cid:246) (cid:230) (cid:247) (cid:231) » . (cid:247) (cid:231) - ł Ł

17.1

2/1

» V i p=1/2 chúng ta có ph ng án tính này ớ . Chúng ta th y k t qu ấ ả ở ế ươ

chính xác h n ph ng án đ u tiên. Và t công th c này chúng ta th y, trong s 23 ng ơ ươ ầ ừ ứ ấ ố ườ i

ch n ng u nhiên thì có ít nh t m t c p trùng ngày sinh v i xác su t là ½. Nh v y đ ộ ặ ư ậ ấ ẫ ấ ọ ớ ể

17.1

mm 2/2

17.1

m 2/2

(cid:215) (cid:215) th c hi n t n công thì c n b nh là bít và c n th c hi n tính toán ệ ấ ự ầ ộ ớ ự ệ ầ

17.1

m 2/2

(cid:215) hàm Hash và th c hi n s p x p ự ế ệ ắ s . Và t ố ừ ư đây chúng th y r ng n u nh m ấ ằ ế

‡m

128

không đ l n thì s d dàng tìm ra đ ẽ ễ ủ ớ c s l ượ ố ượ ng b n tin mà có s va ch m. V i công ự ả ạ ớ

11.8

ngh hi n nay thì đòi h i bít. ệ ệ ỏ

T n công hàm hash theo ki u g p nhau gi a ( ể ấ ặ ở ữ meet – in – the –

middle attack)

Ph ng pháp t n công g p nhau gi a áp d ng cho các hàm Hash xây d ng trên c ươ ấ ặ ở ữ ự ụ ơ

c. Ph ng pháp này cho k t qu t s mã kh i, mà chúng ta tìm hi u ở ể ở ố ph n tr ầ ướ ươ ả ố ơ t h n ế

ph ng pháp t n công theo ngày sinh nh t. Trong t n công theo ki u ngày sinh nh t tìm ươ ể ấ ậ ậ ấ

đ c va ch m nh ng giá tr nh n đ c c a hàm Hash đ i v i tìm ki m va ch m là ượ ư ậ ạ ị ượ ủ ố ớ ế ạ

ng u nhiên. T n công đ u tiên đ c đ xu t là t n công trên hàm Hash xây d ng trên ẫ ầ ấ ượ ự ề ấ ấ

S đ này d a trên thu t toán mã kh i an toàn. S đ d a trên ý t

ơ ồ ự

ơ ồ

ự

ậ

ố

ưở

ứ ng v tính toán ph c

ề

t đ u vào và đ u ra c a kh i d li u. Kh i d li u Mi đ

t p xác đ nh khóa khi bi ạ

ị

ế ầ

ố ữ ệ

ủ

ẩ

ượ ử c s

ng ng v i m t vòng tính toán c a hàm Hash. Tìm ki m va ch m liên quan

d ng nh khóa t ư ụ

ươ ứ

ủ

ế

ạ

ớ

ộ

ơ ở ơ ồ Rabin xem hình 11.1. c s s đ

đ n bài toán tính toán khóa. Ví d , t n công có th thay th m t s kh i M ế

ế ộ ố

ụ ấ

ể

ố

k thành M’k. Đi uề

c giá tr m i c a vòng hàm hash H’

i m t s khóa mã

k. Có th t n t

này d n đ n nh n đ ế

ậ

ẫ

ượ

ị ớ ủ

ể ồ ạ

ộ ố

c đ ng th c sau:

M’k+1, mà chúng ta nh n đ

ậ ượ ẳ

ứ

(

)

' k

+ 1

' k

+ 1

' +kM đã cho thì thay th kh i d li u

kM và

1+kM

N u nh cách thám mã tìm đ c ư ế ượ ố ữ ệ ế

kM ' và

' +kM , t c là ta đã tìm đ

thành ứ ượ ớ c b n tin m i, mà có giá tr hàm Hash b ng v i ả ằ ớ ị

ắ ố ớ giá tr hàm Hash c a b n tin ban đ u. N u nh thu t toán mã kh i là v ng ch c đ i v i ủ ả ữ ư ế ậ ầ ố ị

phép t n công trên c s bi t b n tin, thì phép t n công đã cho trên hàm Hash có đ tính ơ ở ế ả ấ ấ ộ

ph c t p cao. ứ ạ

Chúng ta xem c th phép t n công này. Gi ụ ể ấ ả ử ủ s cho b n tin M, giá tr hàm Hash c a ả ị

MMM (

,...,

)

ủ M là H. M c đích c a phép t n công là tìm ra b n tin khác M’ mà gía tr hàm Hash c a ủ ụ ả ấ ị

MM , k

+ 1

)1(

)2(

M =

(

,...,

)

(

,...,

)

M’ cũng b ng H. Chúng ta chia b n tin ả ằ thành hai ph nầ

MM , 1

+ 1

và . Ph n đ u tiên c a b n tin đ ủ ả ầ ẩ ượ ạ c bi n d ng ế

)1(H . Gi

nhi u l n và m i s bi n d ng đó giá tr hàm Hash đ c tính b ng ỗ ự ế ề ầ ạ ị ượ ằ ả ử ậ s nh n

1 gía tr ị

)1(H t

đ c Nượ Nừ 1 ph ươ ủ ng án c a ph n th nh t (xem hình …). Ph n th hai c a ứ ấ ủ ứ ầ ầ

)2(M cũng bi n d ng nhi u l n, t ạ

m i bi n d ng đó hàm Hash đ c tính theo b n tin ả ề ầ ế ừ ỗ ế ạ ượ

thu t toán khác, đây chúng ta tính theo th t c và s d ng hàm gi i mã D, t ậ ở ng ứ ự ượ ử ụ ả ươ ng

2 giá tr ị

)2(H t

ng v i hàm mã hóa E (xem hình…). Gi s thu đ c N ng án ứ ơ ả ử ượ Nừ 2 ph ươ

c a ph n hai. ầ ủ

1 và N2 đ l n thì có th tìm đ

)1(H

Khi s l ng N c c p giá tr b ng nhau trong s ố ượ ủ ớ ể ượ ặ ị ằ ố

)2(H v xác su t l n. Gi

)1('M và

)2('M . Rõ

và s r ng nó t ng ng v i hai b n tin là ấ ớ ớ ả ử ằ ươ ứ ả ớ

MMM

(

)1( '

)2( '

)

„ ràng r ng b n tin mà H(M)=H(M’). V y đã tìm ra đ c s va ằ ả ậ ượ ự

ch m. Gi chúng ta xác đ nh xem c n b nh và đ khó c a ph ạ ờ ủ ầ ớ ộ ộ ị ươ ng pháp t n công này. ấ

1 và N2 t n t

m2 , m là kích th

Chúng ta gi s r ng N i giá tr nh h n c c a giá tr ả ử ằ ồ ạ ỏ ơ ị ướ ủ ị

ư ế ớ ấ ầ

)1(H t

tr đ u tiên băm. Nh th , v i giá tr xác su t g n đúng đ chính xác có th ti p nh n, sao cho giá ị ủ ể ế })1(H không trùng v i m t giá tr nào c a t p ủ ậ { ộ ậ })2(H b ngằ ừ ậ { t p ị ầ ớ ị

Nm 2)21(

- - » .

})2(H

p 1 ủ ậ { Xác su t đ không m t giá tr nào c a t p ộ

ấ ể ị

})1(H trùng v i m t giá tr c a t p ị ủ ậ { ộ

ớ

NNm 2)21(

b ngằ - - »

})2(H

ữ ậ { Nh v y xác su t đ tìm ra ít nh t m t c p trùng nhau gi a t p ấ ấ ể ộ ặ ư ậ

})1(H và t p ậ {

là

NNm

-= )21(1'

1(1

m )2

NN 1

- m

- - - (cid:215) » (cid:215) - - » - - » .

2/1

N 1

NN 1

(cid:215) Bây gi đ iv v i tr ờ ớ v i đi u ki n ề ệ ớ ườ ố ng h p ợ d dàng xác ễ

1/2, v i xác su t va ch m là ½: ấ

đ nh giá tr N ị ị ạ ớ

2 -

2/1

2 m

» .

N 1

Đ nh n đ c đánh giá chính xác h n khi có th nh n gía tr p=0.63. ể ậ ượ ơ ể ậ ị

-mm 12

Nh v y c n b nh c n thi bít, đ khó t n công là ư ậ ầ ộ ớ ầ ế t cho phép t n công là ấ ấ ộ

2 +

N 1

» .