Tầm quan trọng của xung đột hàm băm

Giả sử một xung đột đã được tìm thấy trong một hàm băm nhất định, sao cho H(x1) = H(x2)

Tuy nhiên, x1 và x2 đều là một tập hợp các bit dường như 'ngẫu nhiên' không truyền tải một thông điệp mạch lạc và không thể được xen kẽ một cách mạch lạc.

Sự va chạm này có làm cho hàm băm H không an toàn không? nếu vậy làm thế nào nó có thể được khai thác, ngay cả khi vụ va chạm đã biết không truyền tải một thông điệp mạch lạc? cảm ơn

Tôi thích nghĩ về mật mã như cơ sở hạ tầng. Chúng ta nên cố gắng phát triển cơ sở hạ tầng giảm thiểu số lần sử dụng.Công việc của mật mã học không phải là xác định thông điệp "có ý nghĩa" trong ứng dụng của bạn là gì. Bạn có thể nhìn vào một vụ va chạm cụ thể $m_1, m_2$ và nói một cách chắc chắn rằng không ứng dụng của một hàm băm sẽ bao giờ gán ý nghĩa cho những $m_1$ và $m_2$?

Bạn muốn sử dụng hàm băm nào hơn, một hàm có bảo đảm "rất khó tìm không tí nào va chạm" hoặc một cam kết "rất khó tìm ra va chạm, ngoại trừ đôi khi giữa các chuỗi là tệp JPG của gerbils và tệp gzip của Shakespeare"? Tôi sẽ không muốn lái một chiếc ô tô có dán nhãn cảnh báo có nội dung "xe có thể phát nổ nếu bạn đang lái xe với tốc độ 88,1 dặm/giờ khi bật tín hiệu rẽ trái và đài đã chỉnh thành 88,1 FM", ngay cả khi cảnh báo đó đã được thu hẹp chính xác và tôi sẽ không bao giờ làm 3 điều đó cùng một lúc.

Đó là lý do tại sao các định nghĩa bảo mật mật mã coi xung đột là không tí nào hai tin nhắn thỏa mãn $H(x_1) = H(x_2)$, giả mạo chữ ký trên không tí nào tin nhắn là một cuộc tấn công, mã hóa của không tí nào bản rõ sẽ trông không thể phân biệt được, v.v. Nếu bạn muốn sử dụng mật mã của mình, hãy đảm bảo rằng bạn cố gắng đảm bảo an ninh đặt mọi người thoải mái.

Lý do thực tế thứ hai để lo ngại về một vụ va chạm "phi cấu trúc" trong $H$, đó là khi một cái được tìm thấy, vấn đề thường là thời gian trước khi các kỹ thuật được mở rộng để tìm các va chạm "có cấu trúc". Ví dụ: tìm các va chạm có cấu trúc trong một hàm ngẫu nhiên (sử dụng tấn công va chạm Yuval cổ điển) có độ khó tương đương với việc tìm các va chạm không có cấu trúc (sử dụng lực lượng vũ phu tiêu chuẩn và giới hạn sinh nhật).

H sẽ không an toàn nếu khi được cung cấp x1, về mặt thuật toán có thể lấy được một x2 khác với cùng một hàm băm. Vì không gian băm nhỏ hơn nhiều so với không gian dữ liệu nên sẽ luôn có các xung đột tiềm ẩn, câu hỏi đặt ra là chúng ta có thể tìm thấy chúng không.

Ngay cả khi va chạm hoàn toàn không có cấu trúc và phát sinh từ hai đánh giá hoàn toàn độc lập, nó vẫn sẽ là mối quan tâm đáng kể đối với hàm băm hiện đại. Trong các cấu trúc mật mã, chúng ta thường giả định rằng đầu ra của hàm băm được phân phối đồng đều một cách ngẫu nhiên. Đối với các hàm băm như SHA256 không có bằng chứng cho điều này và chúng tôi không biết ví dụ như ngay cả khi tất cả các đầu ra đều khả thi.

Bây giờ hãy xem xét rằng ngay cả đối với SHA256 (có lẽ là hàm băm được đánh giá cao nhất mọi thời đại), tôi vẫn ước tính rằng ít hơn so với $2^{90}$ đầu ra đã được tính toán (và hầu hết các giá trị đó bị loại bỏ). Đối với hàm băm tạo ra đầu ra 256 bit một cách ngẫu nhiên để tạo ra xung đột trong $2^{90}$ đầu ra là về một $2^{-77}$ Sự kiện. Chúng tôi sẽ phải kết luận rằng SHA256 không hoạt động như chúng tôi mong đợi hoặc chúng tôi vô cùng xui xẻo (và không ai xui xẻo như vậy).

Một sự kiện như vậy, nếu nó xảy ra, nên được coi là bằng chứng cho thấy SHA256 có ít hơn đáng kể entropy va chạm so với những gì chúng tôi đã giả định và với sức mạnh tính toán ít hơn đáng kể so với những gì chúng tôi đã giả định, mọi người sẽ có thể va chạm các giá trị dữ liệu thú vị chỉ bằng cách nối thêm các khối ngẫu nhiên. Trong một sự kiện giả định như vậy, nó nên được coi là một dấu hiệu cho thấy có gì đó không ổn với hàm băm nhưng chúng tôi không biết tại sao.