Tạo các va chạm MD5 của riêng bạn

Question

Tôi đang trình bày về các xung đột MD5 và tôi muốn cho mọi người biết có khả năng xảy ra xung đột.

Sẽ tốt nếu có hai khối văn bản được băm giống nhau và giải thích cần bao nhiêu kết hợp [a-zA-Z] trước khi tôi va chạm.

Câu trả lời rõ ràng là băm mọi kết hợp có thể cho đến khi đạt được hai lần băm. Vì vậy, làm thế nào bạn sẽ đi về mã hóa này. Như một thử nghiệm nhanh, tôi đã thử băm tất cả các kết hợp của 5 cột [A-Z], lưu trữ trong một .net hashtable và bắt ngoại lệ xung đột. Hai vấn đề với điều này - hashtable cuối cùng lần ra, và tôi khá chắc chắn tôi sẽ cần A LOT nhiều nhân vật hơn.

Rõ ràng cấu trúc dữ liệu này quá lớn để xử lý trong bộ nhớ, vì vậy bây giờ tôi sẽ phải lấy một cơ sở dữ liệu liên quan. Ngoài ra âm thanh như một dự án tốt để kiểm tra ra azure - một chút như these guys.

Có ai có thể chỉ cho tôi theo hướng hiệu quả cách thực hiện việc này không?

Answer 1

Hai khác nhau 128 chuỗi byte sau băm với cùng:

MD5 Hash: 79054025255fb1a26e4bc422aef54eb4

Sự khác biệt dưới đây được đánh dấu (đậm). Xin lỗi, thật khó để xem.

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 

và

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 

Các trực quan của vụ va chạm/block1 (Nguồn: Links.Org)

Các trực quan của vụ va chạm/block2 (Nguồn: Links.Org)

Answer 2

Tôi sẽ xem Hashcash. Với một thuật toán băm hiệu quả, như md5, thời gian để tính toán một va chạm với hàm mũ với số bit. Những gì Hashcash làm là tính toán các va chạm một phần. Đó là, một kết hợp của nói 16 bit thấp hơn của băm. Để có được 16 bit thấp hơn để phù hợp, người ta sẽ phải thử băm 2^15 kết hợp khác nhau trên trung bình. Nếu bạn biết phải mất bao lâu để có được một vụ va chạm 16, 24 hoặc 32 bit, thì bạn có thể dễ dàng tính toán thời gian cho số bit cao hơn.

Answer 3

Nếu bạn đang nói về khả năng xảy ra va chạm đơn giản - một nơi không có nỗ lực cố ý gây ra - sau đó bạn sẽ thất vọng: Bạn cần tạo trung bình 2^64 plaintexts trước bạn có thể mong đợi để xem một vụ va chạm, và đó là đáng kể hơn bạn sẽ có thể làm trong một thời gian hợp lý (hoặc thực sự, ngay cả một _un_reasonable).

Nếu bạn đang tìm cách chứng minh sự khó khăn của việc cố tình tạo ra một vụ va chạm, các câu trả lời khác đã chứng minh điều đó. Hạn chế thêm của việc yêu cầu các chuỗi là hoàn toàn văn bản làm cho ngay cả những cách tiếp cận phần lớn là không thực tế, mặc dù.

Answer 4

Toàn bộ điểm của băm như vậy là các va chạm rất khó xảy ra.Bạn sẽ không tạo ra một cơ hội - máy của bạn gần như chắc chắn sẽ chết vì tuổi già trước khi bạn thành công. Toàn bộ điểm sử dụng một băm sẽ biến mất nếu bạn có thể tạo ra các va chạm hợp lý!

Answer 5

Thật khó để làm điều đó chỉ với các tệp văn bản, AFAIK. Bạn có thể nhận được một số vụ va chạm nhưng việc nhận chúng cũng chỉ từ [a-zA-Z] là không dễ dàng (chưa). Mặt khác, nếu bạn chỉ muốn hai tập tin “có ý nghĩa” với cùng một băm, bạn có thể làm điều đó với một cái gì đó giống như, nói, PostScript: có các đốm màu nhị phân khác nhau gây ra va chạm, và sử dụng một biểu thức có điều kiện để hiển thị đầu ra khác nhau cho phù hợp.

Xem ví dụ: this problem (phần H2) và solution. Ví dụ: this PS file và this one có cùng MD5sum nhưng chúng đều là các tệp PostScript được định dạng tốt có văn bản hoàn toàn khác trong chúng khi bạn mở chúng.