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, 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: 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