Số hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
–––––––––––––––––
ĐỖ THU HOÀI

NGHIÊN CỨU VỀ HÀM BĂM TRÊN CƠ SỞ MẠNG
HOÁN VỊ THAY THẾ ĐIỀU KHIỂN ĐƯỢC VÀ ỨNG
DỤNG TRONG MÃ HÕA XÁC THỰC VĂN BẢN

Chuyên ngành: Khoa học máy tính
Mã số : 62.48.01
LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

DANH MỤC BẢNG BIỂU 7
CHƢƠNG 1 TỔNG QUAN VỀ HÀM BĂM 10
1.1 Giới thiệu về hàm băm 10
1.1.1 Định nghĩa về hàm băm 10
1.1.2 Lịch sử phát triển của hàm băm 11
1.1.3 Thuộc tính an toàn của hàm băm 13
1.1.4 Các quan niệm an toàn 15
1.2 Ứng dụng của hàm băm 16
1.3 Xu hƣớng thiết kế 17
1.3.1 Hàm băm không khóa và có khóa 17
1.3.2 Hàm băm lặp 18
1.3.3 Hàm băm dựa trên hình cây 28
1.3.4 Hàm nén 29
CHƢƠNG 2 KIẾN TRÚC MẠNG CHUYỂN VỊ THAY THẾ ĐIỀU KHIỂN ĐƢỢC 30
2.1 Các phần tử mã hóa cơ bản điều khiển đƣợc dựa trên mạng chuyển vị thay thế 30
2.1.1 Phần tử điều khiển cơ bản 30
2.1.2 Phân loại các phần tử cơ bản. 32
2.1.3 Nhóm phụ của các phần tử U
2/1
với một đầu ra tuyến tính 37
2.2 Tô pô đối xứng 41
CHƢƠNG 3 XÂY DỰNG VÀ CÀI ĐẶT CHƢƠNG TRÌNH MÔ PHỎNG 51
3.1 Bài toán ứng dụng 51
3.2 Thiết kế CSDL, thuật toán và giao diện chƣơng trình hàm băm 51
3.2.1 Thiết kế cơ sở dữ liệu 51
3.2.2 Thuật toán thực hiện 53
3.2.3 Phân tích các modul chƣơng trình chính 54
3.2.4 Giao diện chƣơng trình 58
3


Controlled Element
Phần tử điều khiển đƣợc
CSPN
Controlled Substitution
Permutation Network
Mạng Hoán vị-Thay thế điều khiển
đƣợc
DES
Data Encrypt Standar
Chuẩn mã hóa dữ liệu
DDP
Data Dependent Permutation (data-
driven permutation)
Hoán vị phụ thuộc vào dữ liệu
FPGA
Field Programmable Gate Array
Thiết bị lập trình có khá năng tái
cấu hình.
HMAC
Hashed Message Authentication
Code
Xác thực thông điệp bằng hàm băm
NIST
National Institute of Standards and
Technology
Viện Tiêu chuẩn và Công nghệ
Quốc gia của Mỹ
NMAC
Non-Message Authentication Code
Không mã xác thực thông điệp

Truth Table
Bảng giá trị chân lý của các phép
toán logic
UOWHFs
Universal One -Way Hash
Functions
Hàm băm 1 chiều phổ dụng
5
Số hóa bởi Trung tâm Học liệu

DANH MỤC HÌNH ẢNH
Hình 1.1. Hoạt động của một hàm băm 11
Hình 1.2. Sơ đồ biểu diễn các thuộc tính khả năng chống đụng độ, ngăn sự nghịch ảnh và nghịch
ảnh thứ 2. 14
Hình 1.3. Thuật toán bƣớc đệm Merkle-Damgard. 20
Hình 1.4. Cấu trúc Merkle-Damgard 20
Hình 1.5. Tấn công đa đụng độ 21
Hình 1.6. Cấu trúc kim cƣơng. 24
Hình 1.7. Cấu trúc NMAC (a) và HMAC (b) 27
Hình 1.8. Cấu trúc MDP. 28
Hình 1.9. Cấu trúc cây mẫu 29
Hình 2.1. Phần tử cơ bản F
2/1
: a. Sơ đồ tổng quát; b. Sơ đồ dạng hàm Logic với 3 biến vào; c. Sơ
đồ dạng 2 phép thế; d,e. Biểu diễn CE thuộc loại P
2/1
; f. Đặc trƣng vi phân của F

64/256
46
Hình 3.1: Kết quả thử nghiệm với file *.doc 52
Hình 3.2 : Kết quả thử nghiệm với file *.txt 53
Hình 3.3. Các phần tử cơ bản (a,e), (e,g), (f,i), (p,h), (x,d). 55
Hình 3.4. Phần tử CP F
8/12
55
Hình 3.5. Phần tử CP F
-1
8/12
56
Hình 3.6. Phần tử F
96/1
56
Hình 3.7. Phần tử F
32/96
(a), F
-1
32/96
(b)
.
57
Hình 3.8. Phần tử F
32/32
57
Hình 3.9. Giao diện chƣơng trình 58
Hình 3.10. Xây dựng thƣ viện HashDLL.dll 59
Hình 3.11. Giao diện sử dụng Add-In “Ez Hash Function” trong word 2007. 60
Hình 3.12. Phần tử (a) đƣợc biểu diễn thành một cặp hàm logic 4 biến (b) hoặc thành 4 phép


Số hóa bởi Trung tâm Học liệu

MỞ ĐẦU
Mật mã (Cryptography) là ngành khoa học nghiên cứu các nội dung về toán
học, kỹ thuật nhằm cung cấp các dịch vụ bảo vệ thông tin trong quá trình tuyền tin.
Khoa học mật mã đã ra đời và phát triển từ rất sớm, các kết quả nghiên cứu của lĩnh
vực này đƣợc sử dụng nhiều trong lĩnh vực quân sự, chính trị, ngoại giao Ngày
nay, khi công nghệ thông tin phát triển các ứng dụng mã hóa và bảo mật thông tin
đang đƣợc sử dụng rộng rãi sang nhiều lĩnh vực khác nhƣ kinh tế, thƣơng mại điện
tử, ngân hàng…
Với sự phát triển của công nghệ truyền thông và các mạng giao dịch toàn cầu,
việc trao đổi thông tin ngày càng đơn giản và thuận tiện hơn, bên cạnh đó cũng nảy
sinh nhiều yêu cầu cao hơn về bảo mật thông tin trong các hệ thống và các ứng
dụng điện tử. Xã hội càng phát triển, nhu cầu sử dụng các dịch vụ mạng ngày càng
lớn và chúng không ngừng đƣợc nâng cao về mọi mặt để có thể đáp ứng xu thế thời
đại. Trong môi trƣờng mạng, việc truy nhập, lƣu giữ và trao đổi thông tin (trong đó
có các thông tin rất nhạy cảm) đƣợc phát triển với tốc độ cao. Điều này đã tạo điều
kiện cho các hoạt động phi pháp trên mạng ngày càng gia tăng. Việc xâm phạm
dƣới các hình thức khác nhau có thể gây ra các hậu quả nặng nề cho các cá nhân và
tổ chức xã hội. Và trên thực tế đã hình thành mâu thuẫn giữa nhu cầu phát triển các
ứng dụng mạng với các nguy cơ an toàn về thông tin.
Do nhu cầu thực tế, khoa học mật mã không ngừng đƣợc nghiên cứu, phát
triển và ứng dụng. Trên thực tế, mật mã có thể phân chia hình thức thành ba hƣớng
chính - mật mã khóa bí mật, mật mã khóa công khai, hàm băm mật mã. Trong đó
các hàm băm mật mã đóng một vai trò vô cùng quan trọng trong các ứng dụng bảo
vệ an toàn thông tin (xác thực, kiểm tra tính toàn vẹn, chữ ký số, …).
Trong những năm qua vấn đề nghiên cứu về mật mã tại Việt Nam cũng còn
nhiều hạn chế bởi nhiều lý do hoặc có những kết quả nghiên cứu chỉ mang nội dung
cơ bản, đặc thù áp dụng trong những tình huống cụ thể của mỗi đơn vị sử dụng. Còn

Hàm băm (hash function) là một ánh xạ, ánh xạ các chuỗi nhị phân có độ dài
tuỳ ý thành các chuỗi nhị phân có độ dài cố định đƣợc gọi là giá trị băm. Hàm băm
là giải thuật nhằm sinh ra các giá trị băm tƣơng ứng với mỗi khối dữ liệu (có thể là
một chuỗi kí tự, một đối tƣợng trong lập trình hƣớng đối tƣợng, ). Giá trị băm
đóng vai trò gần nhƣ một khóa để phân biệt các khối dữ liệu, tuy nhiên, ngƣời ta
chấp nhận hiện tƣợng trùng khóa hay còn gọi là đụng độ và cố gắng cải thiện giải
thuật để giảm thiểu sự đụng độ. Hàm băm thƣờng đƣợc dùng trong bảng băm nhằm
giảm chi phí tính toán khi tìm một khối dữ liệu trong một tập hợp (nhờ việc so sánh
các giá trị băm nhanh hơn việc so sánh những khối dữ liệu có kích thƣớc lớn).
Trong ngành mật mã học, một hàm băm mật mã học (Cryptographic hash
function) là một hàm băm với một số tính chất bảo mật nhất định để phù hợp việc
sử dụng trong nhiều ứng dụng bảo mật thông tin đa dạng, chẳng hạn nhƣ chứng
thực (authentication) và kiểm tra tính nguyên vẹn của thông điệp (message
integrity). Một hàm băm nhận đầu vào là một xâu ký tự dài, thông điệp có độ dài
tùy ý và tạo ra kết quả là một xâu ký tự có độ dài cố định, đôi khi đƣợc gọi là tóm
tắt thông điệp (message digest) hoặc chữ ký số (digital fingerprint).

11
Số hóa bởi Trung tâm Học liệu

Hình 1.1. Hoạt động của một hàm băm
Nói rộng ra, một hàm băm mật mã học phải hoạt động càng giống với một
hàm ngẫu nhiên càng tốt, trong khi vẫn có tính chất đơn định và xử lý có hiệu quả.
Một hàm băm mật mã học đƣợc coi là không an toàn nếu một trong các việc
sau là khả thi về mặt xử lý:
- Cho một tóm tắt (digest), tìm một thông điệp chƣa biết khớp với tóm tắt đó.
- Tìm các "xung đột băm" (hash collision), trong đó hai thông điệp khác nhau

không đƣợc nhận ra từ thời kỳ đầu của phát triển. Mặt khác, các cấu trúc hiện thời
lại có ƣu điểm là đã đƣợc nghiên cứu và phân tích sâu rộng qua nhiều năm, do vậy
nếu các hàm băm mới không đƣợc thiết kế cẩn thận, chúng có thể sẽ bị tấn công
nhiều hơn là chống lại.
Các hàm băm thƣờng là những hàm nhiều ứng dụng do chúng ánh xạ các đầu
vào có độ dài bất kỳ thành các đầu ra có độ vào cố định và đầu vào thƣờng lớn hơn
đầu ra (hàm băm là các hàm nén). Do đó, các vụ đụng độ (các thông điệp khác nhau
băm thành cùng một giá trị) ở hàm băm thƣờng là không tránh đƣợc do quy luật
ngăn hộc. Yuval là nhà nghiên cứu đầu tiên thảo luận về vấn đề làm thế nào để tìm
ra những vụ đụng độ trong hàm băm bằng sự sử dụng Birthday Paradox, việc này
dẫn đến một hiện tƣợng khá phổ biến hiện nay đó là sự tấn công ngày sinh nhật [6].
Ở kiểu tấn công này, ngƣời ta tìm ra một vụ đụng độ với xác suất là sau khi q
truy vấn đến một hàm băm cho ra các giá trị với độ dài n-bit. Dù khả năng chống
lại sự đụng độ chắc chắn là một thuộc tính rất quan trọng mà hàm băm nên có
nhƣng đó không phải là thuộc tính duy nhất, thậm chí trong một số ứng dụng thì
thuộc tính này là không bắt buộc. Ví dụ nhƣ khả năng chống nghịch ảnh (tính bất
khả nghịch) là một thuộc tính khó có đƣợc và mang tính thực tiễn hơn. Trên thực
tế, ở hầu hết các ứng dụng để có thể nghịch đảo một giá trị băm thì sẽ tổn thất hơn
nhiều là tìm ra một vụ đụng độ giữa hai thông điệp bất kỳ. Do đó, chính ứng dụng
mà sử dụng hàm băm sẽ quyết định các thuộc tính an toàn mà hàm băm cần bảo tồn.
Tuy nhiên điều này đã thay đổi từ năm 2005 khi giáo sƣ Xiaoyun Wang đã
thông báo một tấn công lƣợng sai lên hàm băm SHA-1[4]. Cùng với những cải tiến
tiếp theo của giáo sƣ Wang, tấn công này đƣợc đánh giá là tìm đƣợc một va chạm
13
Số hóa bởi Trung tâm Học liệu

băm (hai thông báo có cùng giá trị băm) với khối lƣợng công việc ƣớc tính khoảng


số thuộc tính phụ khác mà hàm băm cần phải có nếu chúng đƣợc sử dụng trong một
ứng dụng cụ thể.
Nhìn chung, khi ta nói rằng một cuộc tấn công phá vỡ đƣợc một hàm băm cụ
thể thì không nhất thiết nó có nghĩa rằng hàm băm đó hoàn toàn bị phá hủy trong
thực tiễn. nếu một cuộc tấn công có thể chứng minh đƣợc rằng một hàm băm có thể
bị phá hỏng bởi cuộc tấn công ngày sinh nhật hay tấn công bạo lực (ví dụ nhƣ: tìm
ra một vụ đụng độ, hay nghịch ảnh, hay nghịch ảnh thứ 2) với khối lƣợng công việc
ít hơn truy vấn; hàm băm đƣợc coi là bị phá vỡ, mặc dù lƣợc công việc truy vấn để
phá vỡ nó vẫn chƣa làm đƣợc trong thực tiễn (đây đƣợc gọi là sự tấn công trên lý
thuyết). Thực vậy, tìm ra các điểm chƣa hoàn chỉnh nhƣ vậy ở một hàm băm là một
bằng chứng cho các yếu điểm về cấu trúc mà có thể bị phá hủy ở phạm vi lớn hơn
để biến sự tấn công trên lý thuyết này trở thành thực tế; mẫu đầu tiên là MD5, thuật
toán này đầu tiên bị phá vỡ trên lý thuyết, sau đó các cuộc tấn công dần dần đƣợc
cải biến và ngày nay các vụ đụng độ thật có thể đƣợc tìm thấy ở MD5.

Hình 1.2. Sơ đồ biểu diễn các thuộc tính khả năng chống đụng độ, ngăn sự nghịch
ảnh và nghịch ảnh thứ 2.
a, Khả năng chống đụng độ
Một vụ đụng độ hàm băm xảy ra khi hai thông điệp khác nhau bất kỳ băm
thành cùng một giá trị. Tức là với một hàm băm chống đụng độ H, thì nó không thể
tính toán để tìm ra hai thông điệp M và M' bất kỳ sao cho trong khi
. Điều này cũng có thể áp dụng cho họ hàm băm (tức là các hàm băm có
khóa, ở đây các thành viên của họ hàm băm đƣợc thống kê bởi các khóa khác nhau).
15
Số hóa bởi Trung tâm Học liệu


Số hóa bởi Trung tâm Học liệu

- Tính không khác biệt.
- Tính không phân biệt đƣợc.
- Tính không thể làm giả đƣợc.
1.2 Ứng dụng của hàm băm
Một ứng dụng điển hình của một hàm băm mật mã học nhƣ sau [3]: Giả sử
Alice đƣa cho Bob một câu đố khó và tuyên bố rằng cô ấy đã giải đƣợc rồi. Bob
muốn tự giải, nhƣng cũng muốn chắc chắn là Alice đúng là đã giải đƣợc. Do đó,
Alice viết đáp án, gắn thêm một khóa ngẫu nhiên, tính giá trị băm của nó, và đƣa
kết quả băm cho Bob (trong khi vẫn giữ bí mật đáp án và khóa). Bằng cách này, khi
Bob tự giải xong, Alice có thể chứng minh rằng cô đã có đáp án từ trƣớc bằng cách
đƣa khóa cho Bob.
Trong thực tiễn, Alice và Bob thƣờng là các chƣơng trình máy tính và bí mật
thƣờng là cái gì đó không dễ lừa bằng một lời giải cho câu đố. Ứng dụng trên đƣợc
gọi là một hệ thống tin cậy (commitment scheme). Một ứng dụng quan trọng khác
của các hàm băm bảo mật là sự kiểm tra tính toàn vẹn của thông điệp. Ví dụ, việc
xác định xem một file hay một thông điệp có bị sửa đổi hay không có thể thực hiện
bằng cách so sánh tóm tắt đƣợc tính trƣớc và sau khi gửi (hoặc một sự kiện bất kỳ
nào đó). Có thể dùng tóm tắt thông điệp làm một phƣơng tiện đáng tin cậy cho việc
nhận dạng file. Một ứng dụng có liên quan là kiểm tra mật khẩu. Mật khẩu thƣờng
không đƣợc lƣu dƣới dạng văn bản rõ (clear text), mà ở dạng tóm tắt. Để xác thực
một ngƣời dùng, mật khẩu do ngƣời đó nhập vào đƣợc băm và so sánh với kết quả
băm đƣợc lƣu trữ.
Do các lý do cả về bảo mật và hiệu năng chƣơng trình, đa số các thuật toán
chữ ký số nói rằng chỉ có tóm lƣợc của thông điệp, chứ không phải toàn văn thông
điệp, đƣợc "ký". Các hàm băm còn có thể đƣợc dùng để tạo các bit giả ngẫu nhiên
(pseudorandom).
17


một cuộc tấn công đơn độc vào một hàm và phá hủy hoàn toàn hàm đó). Tuy nhiên
18
Số hóa bởi Trung tâm Học liệu

một yếu điểm rất rõ ràng của hàm băm trong trƣờng hợp khóa chuyên dụng đó là
hiệu quả bị thấp đi vì trong trƣờng hợp này hàm băm ngoài có đầu vào (thông điệp)
phải có thêm đầu vào (khóa).
Xem bảng 1.1 để rõ hơn về các định nghĩa ngắn gọn (không chính thức) của
thuật ngữ về hàm băm đƣợc sử dụng trong toàn bài.
Bảng 1.1. Một số thuật ngữ về hàm băm
Thuật ngữ
Định nghĩa không chính thức
Hàm nén.
Một khối cấu trúc tiêu chuẩn của hàm
băm với miền lớn hơn phạm vi.
Cấu trúc, chuyển đổi, chế độ hoạt động,
chế độ chuỗi, chuyển đổi mở rộng
miền, sơ đồ tổ hợp.
Một thuật toán mà gọi một khối cấu trúc
(thƣờng là một hàm nén) theo tính hệ
thống để băm một thông điệp.
Biến số chuỗi, giá trị chuỗi, sự băm
trung gian, biến số tính trạng bên trong.
Đầu ra của một hàm nén đƣợc sử dụng
nhƣ đầu vào cuộc gọi với hàm nén theo
sau.
Giá trị băm, giá trị băm cuối cùng, mật

thức chứng minh rằng cấu trúc này có thể ngăn chặn sự đụng độ. Trong cấu trúc của
Merkle và Damgard, thông điệp M trƣớc tiên đƣợc chia đều thành các khối có kích
thƣớc nhƣ nhau . Nếu khối cuối cùng có kích thƣớc nhỏ hơn thì
khối này đƣợc đệm lót thêm cho. Để có thể ngăn chặn sự đụng độ, độ dài của thông
điệp đƣợc gắn vào thông điệp (sau khi đã đệm) và nó đƣợc đặt tên là sự củng cố
Merkle-Damgard (đƣợc đặt lần đầu tiên bởi Lai và Massey ở mặc dù đã đƣợc đề
xuất bởi Merkle và Damgard); Hình 1.3 minh họa thuật toán bƣớc đệm, ở đây L là 1
mã hóa 64 bit của độ dài thông điệp và m là độ dài của 1 khối đơn. Tiếp đó thông
điệp này đƣợc lặp lại bằng việc gọi một hàm nén có chiều dài đầu vào cố định (FIL)
chấp nhận hai đầu vào đó là: một khối thông điệp
(của độ dài m) và hoặc là một véc tơ khởi tạo IV (khi băm khối thứ nhất) hoặc là
một biến chuỗi (mà sẽ do đầu vào của hàm f trƣớc đó gọi), cả hai đầu vào đều thuộc
độ dài n; hình 1.4 miêu tả mã làm giả của cấu trúc Merkle-Damgard.
* Algorithm Pad
s
(M)
d = M + 1 +64 mod m
M
64
→
→ M
1
M
L

20
Số hóa bởi Trung tâm Học liệu


thêm vào thông điệp M trƣớc khi thông điệp đƣợc băm và , ở đây
m là chiều dài của một khối đơn trong M, thƣờng là |H(M)|; lƣu ý rằng |pad| thực tế
có thể là 0 nếu thông điệp đƣợc đặt thẳng hàng tại ranh giới của các khối. Tuy
nhiên, kiểu tấn công này không tính toán đến việc củng cố cấu trúc Merkle-
Damgard (gắn thêm chiều dài thông điệp vào thông điệp trƣớc khi băm nó).
* Tấn công đụng độ thứ 2.
Trong kiểu tấn công này, có thể dễ dàng tìm đƣợc một vụ đụng độ bằng cách
mở rộng đồng đều kích thƣớc của các thông điệp đụng độ với nhau. Tức là, nếu ta
có H(M) = H(N) trong khi và , có thể tìm đƣợc một vụ đụng độ thứ
hai bằng cách mở rộng M và N với một chuỗi bất kỳ (tiếp tố) S, H(M
. Điều này sẽ đƣợc thực hiện với sự củng cố cấu trúc Merkle-Damgard,
nhƣng nếu không có sự củng cố cấu trúc Merkle-Damgard thì một vụ đụng độ thứ
hai thậm chí còn dễ hơn nhiều vì kích thƣớc các thông điệp đụng độ nhau không bị
chia đều ra nữa.
* Tấn công đa đụng độ
Joux chỉ ra rằng tìm ra nhiều sự đụng độ (nhiều hơn hai thông điệp băm ra
cùng một giá trị) trong một hàm băm Merkle-Damgard không khó hơn việc tìm các
vụ đụng độ đơn lập [5]. Trong tấn công đa đụng độ của mình, Joux cho rằng đƣờng
dẫn đến một máy mà với một biến số tính trạng bên trong cho trƣớc sẽ trả về hai
thông điệp đụng độ nhau ( có thể sử dụng kiểu tấn công ngày sinh nhật hoặc bất
kỳ một kiểu tấn công nào khác để phá các yếu điểm ở hàm băm tƣơng ứng). Hình
1.5 minh họa cuộc tấn công này.

Hình 1.5. Tấn công đa đụng độ
22
Số hóa bởi Trung tâm Học liệu
Số hóa bởi Trung tâm Học liệu

bao gồm l khối, ở đây có l-1 giá trị băm ở giữa). Bây giờ, tìm một khối tại M sao
cho . Giả sử tìm đƣợc (tìm với độ phức tạp ít hơn do M là
một thông điệp rất dài, ở đây n là độ dài của giá trị băm cuối cùng của H) và phù
hợp với (giá trị băm ở giữa thứ j của M), tiếp tục tìm E (nhóm các thông điệp có
thể mở rộng đƣợc) với một thông điệp có độ dài j – 1 sao cho số các khối của
là j. Gọi thông điệp gốc M không có các khối j đầu tiên là thì
. Tấn công này tìm đƣợc một sự nghịch ảnh thứ 2 với một
thông điệp có kích thƣớc trong bƣớc, nhiều so với dự kiến là
. Ví dụ, sử dụng RIPEMD-160 nó sẽ tìm đƣợc một sự nghịch ảnh thứ 2 cho một
thông điệp byte trong khoảng bƣớc, ở đây RIPEMD-160 cho ra một hàng
số kích thƣớc 160bit.
Kiểu tấn công theo nhóm.
Kiểu tấn công này gần giống với kiểu tấn công đa đụng độ và sự nghịch ảnh
thứ 2 đã đề cập ở trên và do Kelsey và Kohno nghiên cứu. Một trƣờng hợp điểm
hình mà có thể sử dụng kiểu tấn công này đó là khi một kẻ tấn công công khai một
giá trị băm D (không phải là ngẫu nhiên) và nói rằng mình biết đƣợc các sự kiện
xảy ra trong tƣơng lai (điều này là giả) và rằng D là giá trị băm của sự kiện đó. Sau
đó, khi các sự kiện tƣơng ứng xảy ra, kẻ tấn công cố gắng nhóm các sự kiện này để
băm D nhƣ đã đƣa ra trƣớc đó. Kiểu tấn công diễn ra trong 2 giai đoạn:
- Giai đoạn 1: Xây dựng một cấu trúc hình kim cƣơng và tính toán giá trị D.
- Giai đoạn 2: Cho trƣớc tiền tố, tìm ra một tiếp tố thích hợp và nhóm chúng vào
D qua cấu trúc kim cƣơng.
24