On average, against a 256-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^127 x". Câu hỏi viết "256-bit-long key" nhưng ý là giá trị băm dài n = 256 bit. Phá kháng va chạm mạnh (tìm một cặp bất kỳ trùng băm) nhờ nghịch lý ngày sinh cần cỡ 2^(n/2) = 2^128 phép băm, nên x = 2^128. Phá kháng va chạm yếu (cho trước một đầu vào, tìm đầu vào thứ hai cùng băm) không tận 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^256 giá trị băm và trúng sau một nửa, tức 2^(n−1) = 2^255 lần. Tỉ số là 2^255 / 2^128 = 2^127. Chỗ tranh cãi: "2^128 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^(−256) thì số lần thử kỳ vọng là 2^256 và tỉ số là 2^256 / 2^128 = 2^128; đáp án in kèm câu hỏi theo cách tính này, còn ở đây chọn theo quy ước khoá học và chữ "on average". "2^256 x" lấy số lần tuyệt đối của va chạm yếu làm tỉ số. "2^64 x" và "2^63 x" là tỉ số của hàm băm 128 bit (2^128 / 2^64 và 2^127 / 2^64), không phải 256 bit. "1x" coi hai tấn công tốn như nhau, trong khi va chạm yếu khó hơn rất nhiều.