Đọc câu trả lời đã chọn cho Thiết kế hàm băm từ các nguyên tắc đầu tiên thay vì phụ thuộc vào kinh nghiệm là rất sâu sắc.
Phần về "tính phi tuyến tính" gợi ý rằng việc biến mọi phương trình liên quan đến hàm băm thành một phương trình tuyến tính có nghĩa là kẻ tấn công có thể dễ dàng tìm ra cách triển khai hàm băm.
Nếu bạn cố gắng tạo một hàm băm mật mã chỉ sử dụng XOR và dịch chuyển, các phương trình sẽ tuyến tính ngay cả sau vô số vòng, giờ đây nhà phân tích chỉ cần loại bỏ Gauss một lần là có thể giải quyết nó và giờ đây họ có khả năng tạo các tiền ảnh tùy ý .
Để tránh điều đó, bạn cần làm cho các phương trình của mình phi tuyến tính bằng cách sử dụng toán tử AND. Băm thực hiện tất cả các loại dịch chuyển và XOR-ing nhưng bước phi tuyến tính này là thứ giúp chúng an toàn.
Nhưng có các điều khoản phi tuyến tính là không đủ. Bạn phải chắc chắn rằng kẻ tấn công không thể loại bỏ một cách hiệu quả các số hạng phi tuyến tính ra khỏi phương trình của bạn bằng cách sửa một số đầu vào thành 1 hoặc 0. Ngoài ra, bạn cần đảm bảo rằng các số hạng sẽ không bị hủy bỏ nếu những kẻ tấn công lấy hiệu của hai phương trình. Nếu bạn có công thức ++ cho một bit và công thức khác ++ cho bit khác. Thêm hai cái này sẽ cho + hiện là tuyến tính và cho phép kẻ tấn công giải quyết nó để có được mối quan hệ giữa hai bit đầu ra. Mỗi phương trình tuyến tính độc lập mà kẻ tấn công có thể tạo ra sẽ làm giảm tính bảo mật của hàm băm của bạn với 1 bit.
Bạn có thể giải thích chi tiết hơn làm thế nào điều này sẽ làm việc? Với một số hàm băm đã bị hỏng, làm thế nào bạn có thể hiển thị tình huống tuyến tính này trên hàm băm đó? Về cơ bản, giả sử md5 là một ví dụ (không an toàn vì một số lý do). Có phải nó không an toàn vì lý do tuyến tính này? Nếu vậy, điều đó có nghĩa là gì về hàm băm md5? Các phương trình đã được tìm thấy là tuyến tính là gì? Nếu md5 là một ví dụ xấu, một ví dụ tốt là gì? Về cơ bản, làm thế nào để bạn tìm kiếm tuyến tính trong hàm băm từng chút một, các kỹ thuật sử dụng là gì?
Tôi muốn biết các kỹ thuật mà kẻ tấn công có thể sử dụng để "giải quyết" hàm băm chỉ dựa trên đầu vào/đầu ra (mà không cần xem triển khai). Nhưng vì đó có lẽ là một câu hỏi quá chung chung hoặc quá liên quan, nên câu hỏi này chỉ tập trung vào khía cạnh phương trình tuyến tính này. Các kỹ thuật "phương trình tuyến tính" mà kẻ tấn công có thể sử dụng để giải hàm băm là gì?