On average, against a 128-bit-long key, how many more hash computations would an attacker need to perform to break weak collision resistance compared to breaking strong collision resistance? In other words, if it requires x number of hash computations to break strong collision resistance, how many computations would it require to break the weak collision resistance

Đáp án đúng: "2^63 x". Câu hỏi viết "128-bit-long key" nhưng ý là giá trị băm dài n = 128 bit. Phá kháng va chạm mạnh (strong collision resistance, tìm một cặp bất kỳ trùng băm) dùng tấn công ngày sinh (birthday attack), cần cỡ 2^(n/2) = 2^64 lần băm, nên x = 2^64. Phá kháng va chạm yếu (weak collision resistance, cho trước một đầu vào, tìm đầu vào khác cùng băm) không dùng được nghịch lý ngày sinh; theo quy ước của khoá học cho tấn công tiền ảnh thứ hai "trung bình", ta coi như vét cạn 2^128 giá trị băm và trúng sau một nửa, tức 2^(128−1) = 2^127 lần. Tỉ số là 2^127 / 2^64 = 2^63. Chỗ tranh cãi: "2^64 x" có cơ sở theo quy ước khác, vì nếu mỗi lần thử ngẫu nhiên trúng với xác suất 2^(−128) thì số lần thử kỳ vọng là 2^128 và tỉ số là 2^128 / 2^64 = 2^64; ở đây chọn theo quy ước khoá học và chữ "on average". "2^127 x" lấy số lần tuyệt đối của va chạm yếu làm tỉ số, nhân thêm x sẽ ra 2^191. "2^128 x" cũng nhầm số lần tuyệt đối (kỳ vọng của phép thử ngẫu nhiên) với tỉ số. "1x" coi hai việc khó ngang nhau, trái với nghịch lý ngày sinh. "2^256 x" vượt xa cả không gian 2^128 giá trị băm.