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

Chia sẻ: | Ngày: | Loại File: DOC | Số trang:17

Thêm vào BST

Báo xấu

74
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ý. Cùng tham khảo tài liệu để nắm kiến thức về hàm hash.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 h(x)=y, tức là hàm hash phải là hàm một chiều; 5. 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’). 6. 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: 1. 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). 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:
• 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]. 3. 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 1 − 2 − n , 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 p ' = (1 − 2 − n ) . Xác suất để tồn tại một bản tin N mà giá trị hàm hash của nó bằng H cho trước là: p = 1 − p ' = 1 − (1 − 2− n ) N . Sử dụng công thức Niutơn, chúng ta nhận được giá trị gần đúng sau: N ( N − 1) 2 N ( N − 1)( N − 2) 3 (1 − x) N = 1 − Nx + x − x ... ≈ 1 − Nx , nếu như x nhỏ, 2! 3! Nên chúng ta có: p ≈ N ⋅ 2 − n và N ≈ p ⋅ 2 n . Khi p=1/2, chúng ta có N ≈ 2n −1 . 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ị n ≥ 128 . 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. Đầu vào: Bản tin M có chiều dài nhỏ hơn 264. 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 M1, 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 8. 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; Đầ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)=X ⊕ Y ⊕ Z. Round1 được miêu tả như sau: 1. A=(A+f(B,C,D)+X[1])
Round2 được miêu tả như sau: 1. A=(A+g(B,C,D)+X[1]+5A827999)
15. C=(C+h(D,A,B)+X[15] +6ED9EBA1)
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 M1, 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 3. i=1 4. for j=1 to 16 do X[j]=M[16i+j] 5. for j=16 to 80 do X[j]=(X[j-3] ⊕ X[j-8] ⊕ X[j-14] ⊕ X[j-16])
K[t]=6ED9EBA1, khi 21 ≤ t ≤ 40 K[t]=8F1BBCDC, khi 41 ≤ t ≤ 60 K[t]=CA62C1D6, khi 61 ≤ t ≤ 80 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á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) ∨((¬ ∧D) B) 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
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
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. M1 M2 Mi Mn H0 H1 H2 H i-1 Hi H n-1 Hn E E E E 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: H i = EM i ( H i −1 ), i = 1,2..., n , 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 m ≥ 128 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 H i = E H i−1 ( M i ) ⊕ M i 2 H i = EH i −1 ( M i ⊕ H i −1 ) ⊕ M i ⊕ H i −1 3 H i = EH i−1 ( M i ) ⊕ M i ⊕ H i −1 4 H i = EH i−1 ( M i ⊕ H i −1 ) ⊕ M i 5 H i = EM i ( H i −1 ) ⊕ H i −1 6 H i = EM i ( M i ⊕ H i −1 ) ⊕ M i ⊕ H i −1 7 H i = EM i ( H i −1 ) ⊕ M i ⊕ H i −1 8 H i = EM i ( M i ⊕ H i −1 ) ⊕ H i −1 9 H i = EM i ⊕ H i−1 ( M i ) ⊕ M i 10 H i = EM i ⊕ H i −1 ( H i −1 ) ⊕ H i −1 11 H i = EM i ⊕ H i −1 ( M i ) ⊕ H i −1 12 H i = EM i ⊕ H i −1 ( H i −1 ) ⊕ M i −1 Dưới đây là biểu diến một số sơ đồ tương ứng với bảng trên …
H0 H i-1 H n-1 M1 H1 Mi Hi Mn Hn E E E a) M1 Mi Mn H0 H1 H i-1 Hi Hn-1 Hn E E E b) M1 Mi Mn H0 H1 H i-1 Hi H n-1 Hn E E E c) 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 m ≥ 128 bít.
a) Mi M i-1 Hi-1 Hi F b) Mi M i-1 Hi-1 Hi F c) Mi Hi-1 Hi F d) Mi Hi-1 Hi 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: F ( X ) = X ⊕ EK ( X ) , ở đâ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 EK. 11.7 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ó n(n − 1) / 2 ≈ n 2 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à p = p ' n 2 / 2 , từ đây p=1/2 thì chúng ta thu được n ≈ 1 / p ' . 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 M ( i ) , i = 1...N , tính toán giá trị băm của các bản tin này, giá trị tương ứng là H (i ) . 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ị H (i ) 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ị H (1) . Xác suất để nó không trùn với các phần còn lại là P (1) ≈ (1 − 2− m ) N −1 . Tiếp tục chọn một số giá trị mới H ( 2 ) . Xác suất để nó không trùng với phần còn lại là P ( 2 ) ≈ (1 − 2− m ) N − 2 . 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à P ( i ) ≈ (1 − 2 − m ) N − i 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à: P ' ≈ (1 − 2− m ) N −1 ⋅ (1 − 2 − m ) N − 2 ⋅ ... ⋅ (1 − 2− m ) N − i ⋅ ... ⋅ (1 − 2− m ) = (1 − 2 − m ) ∑ Với ∑ = 1 + 2 + ... + ( N − 1) = N ( N − 1) / 2 . Xác suất tìm thấy va chạm là p = 1 − p ' = 1 − (1 − 2− m ) ∑ ≈ 1 − (1 − ∑ ⋅ 2 − m ) ≈ N 2 ⋅ 2 − m −1 . Với xác suất va chạm là ½ thì ta có biểu thức: N 2 ⋅ 2−m −1 = 1 / 2 , Từ đây chúng ta xác định gía trị N1/2: N1 / 2 ≈ 2m . 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 H ( i ) , i = 1...N , có thể nhận được bằng cách rất đơn giản sau. Chúng ta chọn H ( 2 ) . Xác suất để H ( 2 ) không trùng H (1) là p ( 2 ) = (1 − 2− m ) . Tiếp tục chọn H ( 3) . Xác suất để H ( 3) không trùng với H ( 2 ) và H (1) , với điều kiện H (1) và H ( 2 ) không trùng nhau là p ( 3) = (1 − 2− m )(1 − 2 ⋅ 2− m ) . Một cách tương tự, chúng ta xác định xác suất p ( N ) để H ( N ) không trùng với một trong các giá trị H (1) , H ( 2 ) ,…, H ( N −1) , với điều kiện là các giá trị H (1) , H ( 2 ) ,…, H ( N −1) khác nhau từng đôi một. Chúng ta nhận được p ( N ) = p ( 2 ) ⋅ p ( 3) ⋅ ... ⋅ p ( N −1) ⋅ [1 − ( N − 1) ⋅ 2− m ] . Như vậy giá trị chính xác của xác suất không có sự va chạm là: N −1 p ' = p ( N ) = (1 − 2− m ) ⋅ (1 − 2 ⋅ 2− m ) ⋅ ... ⋅ [1 − (i − 1) ⋅ 2− m ] ⋅ ... ⋅ [1 − ( N − 1) ⋅ 2− m ] = ∏ (1 − i ⋅ 2− m ) . i =1
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 1 − x ≈ e− x . Chúng ta thu được: N −1 N −1 N −1 p ' = ∏ (1 − i ⋅ 2− m ) ≈ ∏ exp(−i ⋅ 2− m ) = exp(− ∑ i ⋅ 2− m ) = exp[− N ( N − 1) ⋅ 2 − m −1 ] . i =1 i =1 i =1 Xac suất tồn tại ít nhất một va chạm là: p ≈ 1 − p ' = 1 − exp[− N ( N − 1) ⋅ 2 − m −1 ] . Từ đây ta dể dạng nhận được điều sau:  1  N 2 + N ≈ 2 m +1 ln 1 − p  ,    Hay  1  N 2 ≈ 2m +1 ln 1− p  ,     1  N ≈ 2 m +1 ln 1− p  .    Với p=1/2 chúng ta có N1 / 2 ≈ 1.17 2m . 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à 1.17 ⋅ 2m / 2 m bít và cần thực hiện 1.17 ⋅ 2m / 2 tính toán hàm Hash và thực hiện sắp xếp 1.17 ⋅ 2 m / 2 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 m ≥ 128 bít. 11.8 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 M k 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: H k' +1 = EM 'k +1 ( H k' ) = H k +1 . Nếu như cách thám mã tìm được M 'k +1 đã cho thì thay thế khối dữ liệu M k và M k +1 thành M 'k và M 'k +1 , 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 M = ( M 1 , M 2 ,..., M k , M k +1 ,..., M n ) thành hai phần M (1) = ( M 1 , M 2 ,..., M k ) và M ( 2 ) = ( M k +1 ,..., M n ) . 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 H (1) . Giả sử nhận được N1 gía trị H (1) từ N1 phương án của phần thứ nhất (xem hình …). Phần thứ hai của bản tin M ( 2 ) 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ị H ( 2 ) 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ố H (1) và H ( 2 ) vớ xác suất lớn. Giả sử rằng nó tương ứng với hai bản tin là M '(1) và M '( 2) . Rõ ràng rằng bản tin M ' = ( M '(1) , M '( 2 ) ) ≠ M 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 2 m , 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 H (1) từ tập { H (1) } không trùng với một giá trị nào của tập { H ( 2 ) } bằng p1 ≈ (1 − 2 − m ) N 2 . Xác suất để không một giá trị nào của tập { H (1) } trùng với một giá trị của tập { H ( 2 ) } bằng p ' ≈ (1 − 2− m ) N 2 N1
Như vậy xác suất để tìm ra ít nhất một cặp trùng nhau giữa tập { H (1) } và tập { H ( 2 ) } là p ≈ 1 − p ' = 1 − (1 − 2 − m ) N1 N 2 ≈ 1 − (1 − N1 N 2 ⋅ 2 − m ) ≈ N1 N 2 ⋅ 2− m . Bây giờ với điều kiện N1 N 2 ⋅ 2 −m = 1 / 2 đốiv với trường hợp N1 = N 2 = N dễ dàng xác định giá trị N1/2, với xác suất va chạm là ½: N1 / 2 ≈ 2m −1 . Để nhận được đánh giá chính xác hơn khi N1 = N 2 = 2− m / 2 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à 2m 2 m −1 bít, độ khó tấn công là N1 + N 2 ≈ 2 m +1 .