Tại sao hàm băm quá nhanh không an toàn?

Tôi hiểu tại sao chúng ta cần các hàm băm đủ nhanh để xử lý nhưng đủ chậm để bảo mật. Nhưng tôi không hiểu tại sao hàm băm rất nhanh có thể gây ra xung đột. Tôi đoán là một hàm băm rất nhanh tạo ra một số lượng nhỏ bit làm đầu ra, điều đó có nghĩa là xác suất va chạm cao hơn. Ai đó có thể sửa tôi?

Câu trả lời hiện được chấp nhận là tốt, nhưng tôi muốn thêm một số thứ. "bảo mật" là một thuật ngữ rộng trong ngữ cảnh này và bạn nên hỏi bạn muốn chống lại mối đe dọa nào. Trong hầu hết các cuộc thảo luận, "va chạm" là tìm kiếm một đầu vào khác với một đầu ra giống hệt nhau.Nhưng đối với trường hợp mật khẩu, "băm nhanh" là vấn đề chỉ đối với việc cưỡng bức vũ phu cũ đơn thuần. Với hàm băm nhanh, kẻ tấn công dễ dàng tấn công từ điển nhiều đầu vào có thể, tìm kiếm kết quả khớp với hàm băm.

Đây không phải là trường hợp "băm nhanh == quá ít bit đầu ra" như OP đã hỏi. Chỉ là nếu hàm băm quá nhanh, thì cũng dễ dàng tìm thấy đầu vào ban đầu (không phải xung đột), điều đó khiến nó không an toàn.

Đưa ra một hàm băm có thể điều chỉnh theo "tốc độ", (có lẽ là lặp lại), việc tăng tốc độ băm của nó không tạo ra nhiều va chạm hơn. Vấn đề bảo mật với hàm băm quá nhanh là trong khoảng thời gian X cho trước, hàm băm nhanh hơn sẽ tạo ra số lượng đầu ra lớn hơn, vì vậy kẻ tấn công có cơ hội cao hơn Phát hiện một sự va chạm.

OP lấy ý tưởng từ một bài đăng trên YouTube điều đó tranh luận xung quanh MD5.

Đây là lập luận đơn giản nếu có ai xem video.

Tốc độ không ngụ ý rằng hàm băm không an toàn, thiết kế giúp nó an toàn.

Qua nhiều năm, các nhà nghiên cứu đã tìm ra điểm yếu trong thiết kế của MD5 và cải tiến theo thời gian. Sau khi MD5 được phát hành, năm 1992, các cuộc tấn công bắt đầu, và vào năm 2010 Xie và Dengguo Feng tuyên bố xung đột MD5 đơn khối (512-bit) đầu tiên được xuất bản. Tất nhiên, sự cải tiến của CPU và các chu kỳ của chúng đang giúp cuộc tấn công diễn ra nhanh hơn, tuy nhiên, đóng góp chính là các phương pháp tấn công. Hãy xem xét điều đó, cuộc tấn công va chạm chung (cuộc tấn công sinh nhật) yêu cầu $2^{64}$ Băm MD5 với xác suất thành công là 1/2. Thậm chí ngày nay, không một CPU thông thường nào có thể tạo ra $2^{64}$ Trong một thời gian hợp lý. Mặt khác, hiện tại chúng ta có xung đột tức thì đối với MD5, xem corkami.

Mặt khác, Blake2 là một hàm băm rất nhanh, nhanh hơn MD5 và SHA-1 và không có cuộc tấn công kéo dài do nó sử dụng cấu trúc HAIFA, sửa lỗi thiết kế MD. Nó nhanh hơn MD5 và an toàn ít nhất là trong một tính năng có thể thấy trước. Kích thước đầu ra của nó đủ an toàn cho các cuộc tấn công song song lớn hoặc thậm chí cho Thuật toán tìm kiếm lượng tử của Grover. Dòng Blake hiện có BLACK3, nó là một hàm băm song song và rất nhanh.

Điều quan trọng về tốc độ và mối quan hệ của nó với bảo mật là kích thước thông báo. Các cuộc tấn công chung cho tấn công trước hình ảnh, tấn công trước hình ảnh thứ cấp và xung đột chung là $2^n$,$2^n$, và $2^{n/2}$, tương ứng. Nếu bạn có đầu ra 256 hoặc 512 bit, bạn sẽ ổn với các cuộc tấn công chung. Hãy nhớ rằng không gian đầu vào ngắn là một vấn đề đối với các cuộc tấn công trước hình ảnh và HMAC được khuyên dùng.

PS: băm mật khẩu (không yêu cầu khả năng chống va chạm), nơi chúng tôi muốn tốc độ có thể kiểm soát được, độ cứng bộ nhớvà số lượng luồng của hàm băm mật khẩu. Người ta nên đọc câu hỏi kinh điển từ trang web đáng kính của chúng tôi, bảo mật thông tin.. Cũng thế, giấy Argon2, người chiến thắng cuộc thi băm mật khẩu năm 2015, là một lựa chọn tốt để đọc.

Lưu ý cuối cùng: Người ta nên xác định cẩn thận vấn đề của mình để có thể đạt được một thiết kế an toàn. Không có bảo mật thực sự nếu bạn không biết rủi ro của mình.

Hãy xem xét việc sử dụng hàm băm để bảo vệ mật khẩu và lấy một vài ví dụ.

• Trường hợp đầu tiên: chúng ta có một hàm băm cần 1 giây để thực hiện trên một máy tính bình thường. Nếu kẻ tấn công có quyền truy cập vào 1 triệu máy tính (ví dụ: qua mạng botnet), chúng có thể thực hiện 1 triệu lần thử mỗi giây, 86 tỷ lần thử mỗi ngày. Nhưng mật khẩu gồm 8 ký tự sử dụng chữ hoa, chữ thường, chữ số và ký hiệu là khoảng 50 bit entropy, do đó, ở hiệu suất hiện tại, nó vẫn sẽ chiếm trung bình khoảng 18 năm để bẻ khóa mật khẩu đó, ngay cả với mạng botnet khổng lồ đó (tất nhiên trong 18 năm nữa, mọi thứ có thể sẽ tăng tốc khá nhiều nên nó sẽ ngắn hơn thế, nhưng vẫn vậy). Trường hợp xấu nhất sẽ mất 36 năm.

• Trường hợp thứ hai: chúng ta có một hàm băm cần 1 phần triệu giây để thực thi. Cùng một kẻ tấn công sử dụng cùng một mạng botnet triệu máy tính giờ đây có thể thực hiện thêm một triệu lần thử mỗi giây. Bây giờ mất 1125 giây (ít hơn 20 phút) để thử từng và tất cả mọi người trong số khoảng 2^50 mật khẩu 8 ký tự có thể có. Vì vậy, trung bình khoảng một nửa thời gian.

Nếu bạn nghĩ một mạng botnet với một triệu máy tính là điều viển vông, nghĩ lại.

Vì vậy, vấn đề không phải là tạo ra nhiều xung đột hơn (đối với bất kỳ hàm băm tốt nào, điều này được liên kết trực tiếp với kích thước của đầu ra, không phải tốc độ của hàm băm), mà là vấn đề có thể tìm thấy các xung đột (hoặc thực tế là bản gốc đầu vào, nhưng bạn không nhất thiết phải biết điều đó), đánh bại mục đích của hàm băm.