Có bất kỳ thuật toán băm hiện có nào đủ mạnh không?
Đúng; trên thực tế, bất kỳ thuật toán băm bảo mật bằng mật mã nào (chẳng hạn như SHA-2, SHA-3, Blake2) sẽ đủ mạnh.
Để nhấn mạnh điều này, hãy để tôi chỉ ra rằng MD5 đủ mạnh. Bây giờ, MD5 được coi là khá yếu (và không ai ở đây tán thành việc sử dụng nó); tuy nhiên, ngay cả với những điểm yếu đã biết, nó vẫn đủ mạnh để chống lại cuộc tấn công cụ thể này.
MD5 có đầu ra 128 bit (trái ngược với các hàm băm mật mã mà chúng tôi sử dụng trong thực tế, có đầu ra lớn hơn nhiều). Ngoài ra, có nhiều cách đã biết để tạo "va chạm", tức là các cặp đầu vào mà MD5-băm thành cùng một giá trị. Tuy nhiên, những phương pháp đó giả định rằng cuộc tấn công có quyền kiểm soát đối với cả hai đầu vào - trong trường hợp này, nhà xuất bản hợp lệ tạo ra hình ảnh hợp lệ và kẻ tấn công không thể thay đổi những gì nhà xuất bản ký, do đó, điểm yếu va chạm của MD5 không áp dụng. MD5 không có điểm yếu nào đối với các cuộc tấn công 'tạo ảnh trước thứ hai' hoặc đối với một cuộc tấn công 'tạo ảnh trước thứ hai đa mục tiêu' (chính xác là đây là gì), và do đó, cách tiếp cận duy nhất mà kẻ tấn công có là băm các đầu vào khác nhau cho đến khi hắn tìm thấy kết quả phù hợp.
Bây giờ, chúng tôi giả định rằng có $60.000 \xấp xỉ 2^{16}$ chữ ký hợp lệ; nếu kẻ tấn công băm một phỏng đoán, điều đó có khoảng $2^{-128+16} = 2^{-112}$ xác suất băm đến một trong các mục tiêu. Nói cách khác, để có cơ hội một phần nghìn tìm thấy một hình ảnh băm vào một trong các mục tiêu, anh ta sẽ cần băm khoảng $2^{102}$ hình ảnh.
Bây giờ, người ta ước tính rằng ngành khai thác bitcoin toàn cầu đánh giá khoảng $2^{68}$ băm mỗi giây (thực tế, ít hơn một chút); điều đó có nghĩa là nếu cuộc tấn công có thể dành tất cả quá trình xử lý đó [1] để tấn công hệ thống của bạn, thì chúng sẽ cần phải thực hiện điều đó trong khoảng $2^{34}$ giây (hoặc khoảng 500 năm) để đạt được cơ hội có 1 phần nghìn đó.
Nếu bạn hoán đổi MD5 bằng một hàm băm tiền điện tử thực, thì 500 năm đó sẽ biến thành loại khung thời gian 'cái chết nóng của vũ trụ'.
[1]: Tất nhiên, cơ sở hạ tầng khai thác bitcoin hiện tại được xây dựng xung quanh SHA-256 - Tôi sẽ bỏ qua chi tiết đó.