Điểm:1

Làm cách nào để kẻ tấn công giải mã hàm băm bằng cách tìm kiếm tuyến tính?

lá cờ tn

Đọ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ì?

kelalaka avatar
lá cờ in
Tôi không nghĩ rằng bạn có thể tìm thấy một cuộc tấn công đơn giản như vậy.Ví dụ: MD5 đã tấn công bằng [đường dẫn khác biệt](https://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf), Bạn phải tạo một số phương trình đại số để thấy điều này. Nó cần có thời gian...
Morrolan avatar
lá cờ ng
Lĩnh vực đại số tuyến tính có [bộ công cụ phong phú](https://en.wikipedia.org/wiki/System_of_linear_equations#Solving_a_linear_system) để giải các hệ phương trình tuyến tính một cách hiệu quả, ví dụ: Phép loại trừ Gaussian. Vì vậy, nếu một người có thể biểu thị mối quan hệ giữa đầu vào và đầu ra của hàm băm dưới dạng một hệ thống tuyến tính, thì việc phá vỡ nó là điều dễ dàng.
kelalaka avatar
lá cờ in
@Morrolan, vấn đề không phải là giải các hệ phương trình tuyến tính một cách hiệu quả, mà là làm thế nào để xây dựng chúng cho một hàm băm. Giải thì dễ, tìm hàm băm giải được mới khó. Ngoài ra, thay vì các quan hệ tuyến tính, nếu một người nhận được các phương trình cấp thấp thì một cuộc tấn công đại số có thể hữu ích.[Tuyến tính hóa](https://crypto.stackexchange.com/q/75357/18298), XLS, v.v...
Morrolan avatar
lá cờ ng
@kelalaka Nhận xét của tôi liên quan đến khía cạnh câu hỏi của OP tại sao hàm băm tuyến tính thuần túy không khả thi - cụ thể là vì có các công cụ để giải quyết nó một cách tầm thường.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.