Giáo trình Đại số hiện đại - Chương 11: Hàm Hash

Chương 11
HÀM HASH
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:
Đối số của hàm hash là bản tin có chiều dài bất kỳ;
Giá trị của hàm hash có chiều dài không đổi;
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;
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 h(x)=y, tức là hàm hash phải là hàm một chiều;
Hàm hash là hàm không va chạm, tức là khi cho trước bản tin x, không thể thực hiện được về mặt tính toán để tìm được bản x’x sao cho h(x)=h(x’).
Hàm hash là hàm không va chạm mạnh, khi không thể thực hiện được về mặt tính toán để tìm được hai bản tin x và x’, với x’x mà h(x)=h(x’).
Cấu trúc chung của hàm băm Hash gồm các phần sau:
Cho trướ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).
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:
Khởi tạo H0, bằng véc tơ khởi tạo nào đó.
Thực hiện trộn: Hi=F(Hi-1,Mi), i[1,s].
Giá trị của Hs là giá trị của hàm băm.
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 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ị hàm hash. Như thế xác suất để không một bản tin nào từ N bản tin khác nhau mà giá trị của bản tin đó không trùng với H bằng . Xác suất để tồn tại một bản tin mà giá trị hàm hash của nó bằng H cho trước là:
.
Sử dụng công thức Niutơn, chúng ta nhận được giá trị gần đúng sau:
, nếu như x nhỏ,
Nên chúng ta có: và .
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 đượ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 khác, nên khuyến cáo chọn giá trị .
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.
Đầu vào: Bản tin M có chiều dài nhỏ hơn 264.
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 M1, M2,  , Mn, chiều dài mỗi khối là 32 bít.
Khởi tạo các biến:
A=67452301 B=EFCDAB89 C=98BADCFE D=10325476
i=1
for j=1 to 16 do X[j]=M[16i+j]
AA=A;BB=B;CC=C;DD=D;
round1
round2
round3
Nếu i < n/16 thì i=i+1 và quay về bước 4.
A=A+AA;B=B+BB;C=C+CC;D=D+DD;
 Đầu ra: 128 bít là liên kết của 4 từ 32 bít:A|B|C|D.
 Trong 3 vòng “round1”, “round2”,”round3” sử dụng 3 hàm bool sau:
f(X,Y,Z)=(X^Y)v((X)^Z).
g(X,Y,Z)=(X^Y)v(X^Z)v(Y^Z).
h(X,Y,Z)=XYZ.
Round1 được miêu tả như sau:
A=(A+f(B,C,D)+X[1])<<3
D=(D+f(A,B,C)+X[2])<<7
C=(C+f(D,A,B)+X[3])<<11
B=(B+f(C,D,A)+X[4])<<19
A=(A+f(B,C,D)+X[5])<<3
D=(D+f(A,B,C)+X[6])<<7
C=(C+f(D,A,B)+X[7])<<11
B=(B+f(C,D,A)+X[8])<<19
A=(A+f(B,C,D)+X[9])<<3
D=(D+f(A,B,C)+X[10])<<7
C=(C+f(D,A,B)+X[11])<<11
B=(B+f(C,D,A)+X[12])<<19
A=(A+f(B,C,D)+X[13])<<3
D=(D+f(A,B,C)+X[14])<<7
C=(C+f(D,A,B)+X[15])<<11
B=(B+f(C,D,A)+X[16])<<19
Round2 được miêu tả như sau:
A=(A+g(B,C,D)+X[1]+5A827999)<<3
D=(D+g(A,B,C)+X[2] +5A827999)<<5
C=(C+g(D,A,B)+X[3] +5A827999)<<9
B=(B+g(C,D,A)+X[4] +5A827999)<<13
A=(A+g(B,C,D)+X[5] +5A827999)<<3
D=(D+g(A,B,C)+X[6] +5A827999)<<5
C=(C+g(D,A,B)+X[7] +5A827999)<<9
B=(B+g(C,D,A)+X[8] +5A827999)<<13
A=(A+g(B,C,D)+X[9] +5A827999)<<3
D=(D+g(A,B,C)+X[10] +5A827999)<<5
C=(C+g(D,A,B)+X[11] +5A827999)<<9
B=(B+g(C,D,A)+X[12] +5A827999)<<13
A=(A+g(B,C,D)+X[13] +5A827999)<<3
D=(D+g(A,B,C)+X[14] +5A827999)<<5
C=(C+g(D,A,B)+X[15] +5A827999)<<9
B=(B+g(C,D,A)+X[16] +5A827999)<<13
Round3 được miêu tả như sau:
A=(A+h(B,C,D)+X[1]+6ED9EBA1)<<3
D=(D+h(A,B,C)+X[2] +6ED9EBA1)<<9
C=(C+h(D,A,B)+X[3] +6ED9EBA1)<<11
B=(B+h(C,D,A)+X[4] +6ED9EBA1)<<15
A=(A+h(B,C,D)+X[5] +6ED9EBA1)<<3
D=(D+h(A,B,C)+X[6] +6ED9EBA1)<<9
C=(C+h(D,A,B)+X[7] +6ED9EBA1)<<11
B=(B+h(C,D,A)+X[8] +6ED9EBA1)<<15
A=(A+h(B,C,D)+X[9] +6ED9EBA1)<<3
D=(D+h(A,B,C)+X[10] +6ED9EBA1)<<9
C=(C+h(D,A,B)+X[11] +6ED9EBA1)<<11
B=(B+h(C,D,A)+X[12] +6ED9EBA1)<<15
A=(A+h(B,C,D)+X[13] +6ED9EBA1)<<3
D=(D+h(A,B,C)+X[14] +6ED9EBA1)<<9
C=(C+h(D,A,B)+X[15] +6ED9EBA1)<<11
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ó độ lớn. Tuy nhiên thuật toán MD4 tồn tại một số hạn chế. Cụ thể là có thể tìm thấy va 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.
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:
Hàm g thiết kế trở lại để mất tính đối xứng: 
g(X,Y,Z)=(X^Z) v (Y^(Z))
Sử dụng thêm một hàm i:
 i(X,Y,Z)=Y(X v (Z))
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)<<<s;
GG(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<<s;
HH(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<<s;
II(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<<s;
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); 
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:
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 M1, M2,  , Mn, chiều dài mỗi khối là 32 bít.
Khởi tạo các biến:
	 A=67452301 B=EFCDAB89 C=98BADCFE D=10325476 E=C3D2E1F0
i=1
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
AA=A;BB=B;CC=C;DD=D;EE=E;
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
AA=temp 
A=A+AA;B=B+BB;C=C+CC;D=D+DD;E=E+EE;
Nếu i < n/16 thì i=i+1 và quay về bước 4.
Bản tóm lượ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
Với F(t,X,Y,Z) được cho như sau:
F(t,X,Y,Z)=(X^Y)v((X)^Z), khi 
F(t,X,Y,Z)=XYZ, khi 
F(t,X,Y,Z)=(X^Y)v(X^Z)v(Y^Z), khi 
F(t,X,Y,Z)=XYZ, 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 
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ác chuẩn của Mỹ năm 1992 và nó được ứng dụng cùng với thuật toán chuẩn chữ ký số 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£t£79; B, C và D –là các từ 32 bít. 
	f(t, B, C, D) = (B Ù C) Ú ((ØB) Ù D) 	khi 0£t£19
	f(t, B, C, D) = B Å C Å D 	khi 20£t£39
	f(t, B, C, D) = (B Ù C) Ú (B Ù D) Ú (C Ù 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ố:
	Kt = 5A827999	khi 0£t£19
	Kt = 6ED9EBA1	khi 20£t£39
	Kt = 8F1BBCDC	khi 40£t£59
	Kt = CA62C1D6	khi 40£t£79
Thuật toán Hash SHA-1 được miểu tả bởi các bước sau:
Đầu vào: bản tin có chiều dài <264 bít.
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 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 M1, M2,  , Mn, chiều dài mỗi khối là 512 bít.
Khởi tạo các biến
H0 := 67452301, H1 := EFCDAB89, H2 := 98BADCFE, 
H3 := 10325476, H4 := C3D2E1F0
i := 1
Chia khối Mi thành 16 từ 32 bít w0, w1, , w15.
Đối với các t: 16£t£79 wt := (wt-3 Å wt-8 Å wt-14 Å wt-16)<<<1, ở đây lệnh “<<<x” là lệnh dịch trái x bít.
A := H0, B := H1, C := H2, D := H3, E := H4.
Đố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; 
	E := D; D := C; C := B <<< 30; B := A; A := TEMP. 
H0 := H0 + A, H1 := H1+B, H2 := H2 + C, H3 := H3 + D, H4 := H4 + E,
Tất cả các lệnh cộng theo modulo 232
Nếu i<n, thì i := i+1 và chuyển sang bước 4.
Đầu ra: 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 | 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 nhau, nhưng về cơ bản thuật toán là giống SHA-1, nên ở đây không được miêu tả 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
Output size (bits)
Internal state size (bits)
Block size (bits)
Max message size (bits)
Word size (bits)
Rounds
Operations
Collision
SHA-0
160
160
512
264 − 1
32
80
+,and,or,xor,rotfl
Yes
SHA-1
160
160
512
264 − 1
32
80
+,and,or,xor,rotfl
263 attack
SHA-256/224
256/224
256
512
264 − 1
32
64
+,and,or,xor,shr,rotfr
None
SHA-512/384
512/384
512
1024
2128 − 1
64
80
+,and,or,xor,shr,rotfr
None
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 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 khối m bít: . Hàm tính giá trị băm có thể viết dưới dạng sau:
,i=1,2,,n.
ở đây H0 là giá trị ban đầu đặc biệt. Giá trị băm của hàm H=Hn. 
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.
Hình 11.1. Sơ đồ tạo hàm Hash Rabin
Sơ đồ hàm Hash Rabin có thể viết dưới dạng công thức: 
,
Phươ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 kiểu gặp nhau ở 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ó thể tránh được phép tấn công này nếu chọn hàm mã khối với kích thước khối bít, ví dụ như AES, RC6vv.
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:
Số thứ tự
Công thức
1
2
3
4
5
6
7
8
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ì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ố Hi-1, Mi-1 và Mi có thể xây dựng rất nhiều phương án xây dựng hàm 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 vào phụ. Các phươ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.
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:
,
ở đây K là một số khóa cố định đã biết. Đối với một thuật toán EK 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 EK.
Tấn công hàm Hash theo kiểu ngày sinh nhật
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, tức là có va chạm mà không phụ thuộc vào số lượng biến đổi của hàm, cách tấn công này có 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 trong nhóm gồm n người có cặp khác nhau. Từ đây dể dàng nhận được đánh 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 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 nhau , tính toán giá trị băm của các bản tin này, giá trị tương ứng là . 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ị không tìm được hai như nhau.
Đầ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à đủ nhỏ. Chúng ta chọn một số giá trị. Xác suất để nó không trùn với các phần còn lại là
.
Tiếp tục chọn một số giá trị mới. Xác suất để nó không trùng với phần còn lại là
.
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à
Tất cả chúng ta cần thực hiện N-1 bước kiểm tra không trùng. Xác suất để không một giá trị trong chúng không trùng là:
Với .
Xác suất tìm thấy va chạm là 
.
Với xác suất va chạm là ½ thì ta có biểu thức:
,
Từ đây chúng ta xác định gía trị N1/2:
.
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 , có thể nhận được bằng cách rất đơn giản sau. Chúng ta chọn. Xác suất để không trùng là. Tiếp tục chọn . Xác suất để không trùng với và , với điều kiện và không trùng nhau là. Một cách tương tự, chúng ta xác định xác suấtđể không trùng với một trong các giá trị ,,,, với điều kiện là các giá trị ,,,khác nhau từng đôi một. Chúng ta nhận được . Như vậy giá trị chính xác của xác suất không có sự va chạm là:
.
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 đúng . Chúng ta thu được:
.
Xac suất tồn tại ít nhất một va chạm là:
.
Từ đây ta dể dạng nhận được điều sau:
,
Hay 
,
.
Với p=1/2 chúng ta có. Chúng ta thấy kết quả ở phương án tính này 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 để 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 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 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 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ơ sở mã khối, mà chúng ta tìm hiểu ở phần trước. Phương pháp này cho kết quả tố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 cơ sở sơ đồ Rabin xem hình 11.1.
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ạp xác định khóa khi biết đầu vào và đẩu ra của khối dữ liệu. Khối dữ liệu Mi được sử dụng như khóa tươ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 đế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 Mk thành M’k. Điều này dẫn đến nhận được giá trị mới của vòng hàm hash H’k. Có thể tồn tại một số khóa mã M’k+1, mà chúng ta nhận được đẳng thức sau:
.
Nếu như cách thám mã tìm được đã cho thì thay thế khối dữ liệu vàthành và, tức là ta đã tìm đượ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 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 M’ cũng bằng H. Chúng ta chia bản tin thành hai phần và . Phần đẩu tiên của bản tin được biến dạng nhiều lần và mỗi sự biến dạng đó giá trị hàm Hash được tính bằng. Giả sử nhận được N1 gía trị từ N1 phương án của phần thứ nhất (xem hình ). Phần thứ hai của bản tin cũng biến dạng nhiều lần, từ mỗi biến dạng đó hàm Hash được tính theo thuật toán khác, ở đây chúng ta tính theo thứ tự ngược và sử dụng hàm giải mã D, tương ứng vơi hàm mã hóa E (xem hình). Giả sử thu được N2 giá trị từ N2 phương án của phần hai.
Khi số lượng N1 và N2 đủ lớn thì có thể tìm được cặp giá trị bằng nhau trong số và vớ xác suất lớn. Giả sử rằng nó tương ứng với hai bản tin là và . Rõ 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.
Chúng ta giả sử rằng N1 và N2 tồn tại giá trị nhỏ hơn , m là kích thước của giá trị 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á trị đầu tiên từ tập không trùng với một giá trị nào của tập bằng
.
Xác suất để không một giá trị nào của tập trùng với một giá trị của tập bằng
Như vậy xác suất để tìm ra ít nhất một cặp trùng nhau giữa tập và tập là
.
Bây giờ với điều kiện đốiv với trường hợp dễ dàng xác định giá trị N1/2, với xác suất va chạm là ½:
.
Để nhận được đánh giá chính xác hơn khi có thể nhận gía trị p=0.63. Như vậy cần bộ nhớ cần thiết cho phép tấn công là bít, độ khó tấn công là .