Có thể tạo một tệp giả mạo có cùng tổng kiểm tra bằng hai thuật toán khác nhau không?

Question

Tôi có một chút cảm hứng từ mục nhập blog này http://blogs.technet.com/dmelanchthon/archive/2009/07/23/windows-7-rtm.aspx (tiếng Đức)

Khái niệm hiện tại là md5 và sha1 đều bị hỏng. Không dễ dàng và nhanh chóng, nhưng ít nhất là cho md5 trong phạm vi của một khả năng thực tế. (Tôi không phải là một chuyên gia về mật mã, vì vậy có lẽ tôi sai về những thứ như thế).

Vì vậy, tôi tự hỏi nếu nó sẽ có thể để tạo ra một tập tin A' trong đó có các cùng kích thước, các cùng md5 sum và cùng sha1 tổng như file gốc A.

Đầu tiên, liệu nó có khả thi không?

Thứ hai, có thể thực hiện được với phần cứng/phần mềm hiện tại không?

Nếu không, sẽ không phải là cách dễ nhất để đảm bảo tính toàn vẹn của tệp để luôn sử dụng hai thuật toán khác nhau, ngay cả khi chúng có điểm yếu nào đó?

Cập nhật:

Chỉ cần làm rõ: ý tưởng là để có một tập tin A và một file A' mà fullfills các điều kiện:

size(A) == size(A') && md5sum(A) == md5sum(A') && sha1sum(A) == sha1sum(A')

Answer 1

"Có thể nào không?" - có, nếu tổng kích thước của tổng kiểm tra nhỏ hơn tổng kích thước của tệp, không thể tránh va chạm.

"có thể thực tế với phần cứng/phần mềm hiện tại không?" - nếu có thể xây dựng một văn bản để phù hợp với một tổng kiểm tra cho mỗi lần kiểm tra đang sử dụng, thì có.

Xem wikipedia on concatenation of cryptographic hash functions, cũng là thuật ngữ hữu ích cho google.

Từ trang đó:.

"Tuy nhiên, đối Merkle-Damgård băm chức năng, chức năng nối chỉ mạnh mẽ như các thành phần tốt nhất , không mạnh Joux lưu ý rằng 2-va chạm dẫn tới n-collisions: nếu khả thi là tìm hai thư có cùng mã MD5 băm, có hiệu quả là không có nhiều hơn khó tìm thấy nhiều thư như kẻ tấn công mong muốn với số băm MD5 giống hệt nhau . n thư có số băm MD5 , có khả năng là sự va chạm trong SHA-1. Cần thêm công việc bổ sung để tìm vụ va chạm SHA-1 (ngoài số tìm kiếm sinh nhật theo cấp số nhân) là đa thức. Đối số này là được tóm tắt bởi Finney."

Answer 2

Về lý thuyết bạn có thể làm điều này. Trong thực tế, nếu bạn bắt đầu từ hai tổng kiểm tra được cung cấp bởi MD5 và SHA1 và cố gắng tạo một tệp tạo ra hai checksum giống nhau - nó sẽ rất khó (nhiều lần khó khăn hơn việc tạo một tệp tạo ra MD5 checksum giống nhau, hoặc SHA1 checksum trong sự cô lập).

Answer 3

Vì vậy, tôi tự hỏi nếu nó sẽ là có thể tạo ra một tập tin A' trong đó có cùng kích thước, cùng sum md5, và tổng sha1 giống như tập tin gốc A.

Vâng, tạo một bản sao của tập tin.

khác hơn thế, không phải không có một lượng lớn tài nguyên máy tính để kiểm tra tấn hoán vị (giả định kích thước tập tin là không tầm thường).

Bạn có thể nghĩ về nó như thế này:

Nếu kích thước tập tin tăng n, khả năng xảy ra một sự gia tăng giả càng tốt, nhưng chi phí tính toán cần thiết để kiểm tra kết hợp tăng theo cấp số nhân bằng 2^n.

Vì vậy tệp lớn hơn của bạn, càng có nhiều khả năng ở đó là số bị loại bỏ ở đó, nhưng bạn càng ít có khả năng tìm thấy nó.

Answer 4

Về lý thuyết, bạn có thể có nó, trong thực tế nó là địa ngục của một thông đồng. Trong thực tế không ai thậm chí có thể tạo ra một thông đồng SHA1 cho phép một mình MD5 + SHA1 + Kích thước cùng một lúc. Sự kết hợp này chỉ đơn giản là không thể ngay bây giờ mà không có toàn bộ sức mạnh máy tính trên thế giới và chạy nó trong một thời gian.

Mặc dù trong tương lai gần, chúng tôi có thể thấy nhiều lỗ hổng hơn trong SHA1 và MD5. Và với sự hỗ trợ của phần cứng tốt hơn (đặc biệt là GPU) tại sao không.

Answer 5

Đối với một câu trả lời ngây thơ, chúng ta sẽ phải thực hiện một số (không chính xác) giả định:

• Cả SHA1 và các thuật toán băm MD5 kết quả trong một phân bố các giá trị băm cho một tập hợp các nguyên liệu đầu vào ngẫu nhiên
• thuật toán chi tiết sang một bên - một chuỗi đầu vào ngẫu nhiên có cơ hội đều có khả năng sản xuất bất kỳ giá trị băm

(lĩnh vực cơ bản, không vón cục và phân phối độc đáo.)

Nếu xác suất phát hiện một chuỗi va chạm với hàm băm SHA1 khác là p1, và p2 tương tự cho MD5, câu trả lời ngây thơ là xác suất tìm được một va chạm với cả hai là p1 * p2.

Tuy nhiên, các băm đều bị hỏng, vì vậy chúng tôi biết giả định của chúng tôi là sai.

Các băm có nhiều vón cục, nhạy cảm hơn với những thay đổi với một số dữ liệu so với các thay đổi khác, và nói cách khác, không hoàn hảo. Mặt khác, một thuật toán băm hoàn hảo, không bị phá vỡ sẽ có các đặc tính trên, và đó chính xác là những gì làm cho việc tìm kiếm va chạm trở nên khó khăn. Họ là ngẫu nhiên.

Xác suất thực chất phụ thuộc vào các thuộc tính của thuật toán - về cơ bản, vì giả định của chúng tôi không hợp lệ, chúng tôi không thể "dễ dàng" xác định mức độ khó. Trong thực tế, khó khăn trong việc tìm kiếm đầu vào mà va chạm có thể phụ thuộc rất mạnh vào các đặc tính của chuỗi đầu vào. Một số có thể tương đối dễ dàng (nhưng vẫn có thể không thực tế trên phần cứng ngày nay), và do tính chất khác nhau của hai thuật toán, một số có thể thực sự là không thể.