<![CDATA[Latest posts for the topic "Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?"]]> /hvaonline/posts/list/8.html JForum - http://www.jforum.net Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? /hvaonline/posts/list/44431.html#274184 /hvaonline/posts/list/44431.html#274184 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? /hvaonline/posts/list/44431.html#274229 /hvaonline/posts/list/44431.html#274229 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?

breakoflove wrote:
Bắt cái vô hạn nằm trong cái hữu hạn thì làm sao được :D. 
Không hiểu lắm ?]]> /hvaonline/posts/list/44431.html#274257 /hvaonline/posts/list/44431.html#274257 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?

invalid-password wrote:

breakoflove wrote:
Bắt cái vô hạn nằm trong cái hữu hạn thì làm sao được :D. 
Không hiểu lắm ? 
số lượng các string là vô hạn, số lượng các giá trị hash là có hạn nên tất yếu có hai string cùng hash]]> /hvaonline/posts/list/44431.html#274263 /hvaonline/posts/list/44431.html#274263 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?

n2tforever wrote:
số lượng các string là vô hạn, số lượng các giá trị hash là có hạn nên tất yếu có hai string cùng hash 
Các bác chẳng hiểu em hỏi gì cả ! Em xin nói lại cho rõ hơn: Câu 1: Có tồn tại 2 chuỗi s1 và s2 nào có chiều dài bằng nhau và hash MD5 giống nhau ? (MD5 giống nhau nhưng chiều dài khác nhau thì em biết là có rồi). Nếu điều này không tồn tại thì em chỉ cần kiểm tra vừa hash vừa chiều dài thì đảm bảo tránh được collision, nếu điều này tồn tại thì không thể dùng cách này. Câu 2: (Giả sử không thể thực hiện theo câu 1) Có tồn tại 2 chuỗi s1 và s2 nào mà MD5 giống nhau và SHA1 cũng giống nhau nốt ? Nếu không tồn tại thì em chỉ cần dùng đồng thời MD5 và SHA1 là đảm bảo tránh được collision, còn không thì không thể dùng cách này. Câu 3: (Giả sử không thể thực hiện theo câu 2) Có 2 phương pháp hash nào có thể sử dụng đồng thời để hoàn toàn tránh được collision ? ]]> /hvaonline/posts/list/44431.html#274264 /hvaonline/posts/list/44431.html#274264 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? /hvaonline/posts/list/44431.html#274269 /hvaonline/posts/list/44431.html#274269 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?

n2tforever wrote:
vẫn quy về vô hạn và hữu hạn thôi bác. nếu bác để ý thì số lượng hash md5 tối đa bằng 2^128 và số các string có thể có phụ thuộc vào chiều dài xâu, khi chiều dài xâu tăng lên thì số lượng các xâu có thể có cũng tăng lên theo, đến một độ dài nào đó ví dụ n chẳng hạn thì số lượng các xâu có chiều dài n sẽ vượt quá 2^128 và tất nhiên khi đó sẽ có 2 xâu chiều dài n có cùng hash. => câu trả lời cho câu 1 là có thể. 
Hiểu rồi. Nguyên lý lồng chim :D

n2tforever wrote:
tương tự cho câu 2, nếu bác dùng kêt hợp md5 và sha thì do md5 và sha đều có chiều dài cố định nên chắc chắn số lượng các giá trị hash kết hợp sẽ bị giới hạn còn số lượng string sẽ là vô hạn => chắc chắn cũng có đụng độ. 
Hiểu luôn. Nếu chuỗi đạt đến độ dài n, ta lấy ra 2^128+1 chuỗi thì sẽ có ít nhất 1 cặp bị collision MD5. Sau khi trừ cặp đó ra và thêm 2 chuỗi nữa thì lại bị collision tiếp. Nếu lấy ra 2^128+1+2k chuỗi thì sẽ có k+1 lần bị collision. Và nếu k+1 mà lớn hơn 2^160 nữa thì trong số các MD5 collision sẽ có 1 cặp bị SHA collision. Tuy nhiên cách dùng MD5 và SHA1 sẽ giảm khả năng collision rất nhiều. Trên bài toán thực tế chắc không có bài toán mà số chuỗi lại dài vô hạn, mình phải dựa vào số lượng các chuỗi có thể có và tính được xác suất collision, từ đó quyết định nên dùng hash nào và mấy hash kết hợp.]]> /hvaonline/posts/list/44431.html#274272 /hvaonline/posts/list/44431.html#274272 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? /hvaonline/posts/list/44431.html#274396 /hvaonline/posts/list/44431.html#274396 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?

vutrongtandng wrote:
Bài toán này la quy từ dãy vô hạn các string về tập hữu hạn hash, cho nên chắc chắn sẽ xảy ra collition, tuy nhiên xác xuất không cao, bạn yên tâm sử dụng md5 nhé  
' Trúng, sát xuất không cao thì không nên lo. Hàm băm nào cũng có collision. Tuy nhiên, cụ thể cho MD5 thì đã có nhiều paper hướng dẫn cách tính collision. Từ string s1 có thể tính ra string s2 khác mà có cùng md5 hash. Vậy thì việc bị collision không còn là ngẫu nhiên nữa. Khoai thấy bạn nên sử dụng một hàm hash khác (SHA-1 chẳng hạn). khoai]]> /hvaonline/posts/list/44431.html#274421 /hvaonline/posts/list/44431.html#274421 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?

invalid-password wrote:
Tôi định dùng hash MD5 để kiểm tra sự giống nhau và khác nhau của các string. Nếu MD5(str) khác nhau và len(str) khác nhau thì string khác nhau. Về lý thuyết khi số lượng string rất lớn thì vẫn có thể xảy ra collision. Không biết người ta đã chứng minh được là trong tất cả những chuỗi có cùng độ dài thì không bao giờ xảy ra MD5 collision ? Ngoài ra tôi còn thấy người ta dùng kết hợp kiểm tra MD5 lẫn SHA1. Như vậy người ta đã chứng minh được khi xảy ra MD5 collision thì không thể xảy ra SHA1 collision ? Ngoài ra xin hỏi có những phương pháp đảm bảo nào khác để tránh collision trong bài toán này ? 
Các hàm băm (cryptographic nay non-cryptographic) đều có mục tiêu là biến đổi một data-set lớn về một giá trị nhỏ hơn, có độ dài không đổi. Chính vì điều này thì kiểu gì hàm băm cũng sẽ có collision. Không rõ tập dữ liệu của bạn lớn đến mức nào. Theo hiệu ứng Birthday Paradox thì với MD5 (128 bit) thì điều kiện tối thiểu để có thể xảy ra collision là tập giá trị phải có 2^64 giá trị. Nên tôi nghĩ chỉ cần so sánh giá trị md5 là đủ. Nếu tập dữ liệu của bạn cực lớn thì có thể sử dụng SHA (160bit) hoặc SHA-2 (256bit) hoặc SHA-3]]> /hvaonline/posts/list/44431.html#274462 /hvaonline/posts/list/44431.html#274462 GMT Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? /hvaonline/posts/list/44431.html#274486 /hvaonline/posts/list/44431.html#274486 GMT