ví dụ của người mà tôi đã đưa ra trong câu hỏi của tôi ở trên có đúng trong khẳng định của họ không - rằng ví dụ 2 sẽ làm cho va chạm, nói theo xác suất, xảy ra ít thường xuyên hơn?
Nhiều khẳng định được đưa ra ở đó:
Một khẳng định là chức năng 1 của mật khẩu + muối năng suất băm Được định nghĩa bởi
hàm băm = sha512(mật khẩu + muối);
for (i = 0; i < 1000; i++) {
băm = sha512(băm); // <-- KHÔNG làm điều này!
}
có nhiều khả năng va chạm hơn chức năng 2 của mật khẩu + muối năng suất băm Được định nghĩa bởi
hàm băm = sha512(mật khẩu + muối);
for (i = 0; i < 1000; i++) {
băm = sha512(băm + mật khẩu + muối);
}
Điều đó đúng về mặt lý thuyết và có thể quan sát được trong thực tế đối với hàm băm hẹp, ví dụ: 80 bit.
Một cách để thấy nó là
- tập đầu ra của hàm ngẫu nhiên cố định $H$ lặp đi lặp lại $n$ thời gian có xu hướng thu hẹp như $n$ phát triển (lập luận: nó không bao giờ có thể tăng lên khi $n$ và một số kết quả thu hẹp do va chạm của hàm băm lặp lại, ở đây SHA-512);
- xác suất va chạm của một hàm ngẫu nhiên đối với hai đầu vào riêng biệt ngẫu nhiên là nghịch đảo của kích thước của tập hợp đầu ra của nó.
Do đó, điều này có thể hiểu được (mặc dù lặp lại một chức năng ngẫu nhiên $n$ lần có thể không hoàn toàn mang lại một hàm ngẫu nhiên đối với phần còn lại của tập đầu ra) mà xác suất va chạm của $H^n(x)$ cho hai phân biệt ngẫu nhiên $x$ tăng với $n$.
Điều đó hạn chế khả năng chống va chạm của chức năng 1 mà vì vòng lặp lặp đi lặp lại $H: h\mapsto\operatorname{SHA-512}(h)$. Trong khi ở 2, chức năng lặp lại thay đổi khi đầu vào mật khẩu + muối thay đổi, do đó bộ đầu ra thu hẹp lại với $n$ phụ thuộc vào đầu vào đó. Theo mô hình hàm băm dưới dạng hàm ngẫu nhiên, 2 cũng là một hàm ngẫu nhiên có khả năng đạt đến toàn bộ và đó là xác suất va chạm đối với các đầu vào khác nhau mật khẩu + muối không tăng như $n$ làm.
Người ta cũng khẳng định rằng vì lý do này, trong thực tế, chúng ta nên sử dụng 2 thay vì 1 và điều đó không chính xác vì một số lý do:
- Ít nhất là đối với bất kỳ hàm băm nào có khả năng chống va chạm, chẳng hạn như SHA-512, chúng ta hoàn toàn không cần lo lắng về va chạm hoặc chu kỳ.
- Trong ngữ cảnh (ứng dụng băm mật khẩu), chống va chạm của chức năng lặp tổng thể không phải là một vấn đề. sức đề kháng trước Là. Và ngay cả đối với SHA-1, không có khả năng chống va chạm và bất kỳ thực tế nào $n$, chúng ta không cần lo lắng rằng việc phá vỡ 1 sẽ yêu cầu đánh giá hàm băm ít hơn đáng kể so với phá vỡ 2, kể cả với tính toán trước thực tế.
Ưu điểm của 2 là: khó triển khai hơn một chút trong phần cứng vì phần cứng cần sử dụng mật khẩu và muối ở mỗi lần lặp, do đó phải được lưu trữ. Do đó, ASIC để tăng tốc 2 sẽ phức tạp hơn so với 1. Đó là lý do duy nhất tôi thấy 2 ít tệ hơn 1 trong thực tế. Nó vẫn tệ, bởi vì $n=1000$ các lần lặp lại không đủ chậm đối với ASIC hoặc GPU khi thực hiện tìm kiếm mật khẩu; và bởi vì toàn bộ điều này không đưa bộ nhớ vào sử dụng, do đó mất khả năng bảo vệ bổ sung chống lại tìm kiếm mật khẩu vũ phu mà các hàm băm mật khẩu khó nhớ hiện đại (như mật mã hoặc Argon2) cho.
Băm nhiều lần sẽ an toàn hơn băm một lần
Điều này phụ thuộc chủ yếu vào mục tiêu, điều này chỉ ra hàm băm để sử dụng
- Nếu chúng ta đang băm cho mục đích kéo dài phím, đó thường là khi băm mật khẩu hoặc cụm mật khẩu, vâng: bảo mật chống lại tìm kiếm vũ phu tăng tuyến tính theo số vòng. Nhưng một lần nữa, chúng ta nên sử dụng hàm băm mật khẩu khó nhớ.Đối với thời gian sử dụng như nhau, ngay cả lỗi thời bcrypt sẽ mang lại sự bảo mật cao hơn so với các công trình hoàn toàn lặp lại một hàm băm, như PBKDF2 hoặc các chức năng 1 và 2, vốn không được khuyến nghị trong thời đại của ASIC, FPGA và GPU cho bẻ khóa mật khẩu.
- Nếu chúng tôi đang băm nhiều lần để củng cố một số hàm băm mật mã có khiếm khuyết (chẳng hạn như khả năng chống va chạm của nó bị hỏng), thì có thể là có. Ví dụ. chức năng 2 (với
mật khẩu + muối được thay thế bằng thông báo thành hàm băm) sẽ khắc phục tất cả các lỗi bảo mật đã biết của MD5 hoặc SHA-1 bên cạnh chiều rộng đầu ra của chúng, ngay cả khi chúng tôi chỉ thực hiện thêm một vòng thay vì 1000. Tuy nhiên, đó là một cái giá rất lớn về hiệu suất và khả năng sử dụng, bởi vì chúng tôi cần băm tin nhắn hai lần, do đó, trong một số trường hợp, hãy lưu trữ nó.
- Đối với các mục đích mật mã khác bao gồm chữ ký và dẫn xuất khóa từ khóa rộng bằng cách sử dụng hàm băm hiện đại, không. Chúng tôi có thể sử dụng SHA-2 hoặc SHA-3 (để đặt tên cho những câu hỏi trong câu hỏi) cho những mục đích này. Băm lặp đi lặp lại là không cần thiết và thậm chí có thể giảm nhẹ khả năng chống va chạm (nếu được thực hiện như trong 1), với một ngoại lệ: nếu hàm băm có thuộc tính mở rộng chiều dài (giống như SHA-2 có, nhưng SHA-3 thì không), và nếu điều đó là không mong muốn, thì việc băm lại một lần đầu ra của hàm băm là hợp lý (không yêu cầu lưu trữ thông báo hai lần).
