banner

[Rule] Rules  [Home] Main Forum  [Portal] Portal  
[Members] Member Listing  [Statistics] Statistics  [Search] Search  [Reading Room] Reading Room 
[Register] Register  
[Login] Loginhttp  | https  ]
 
Forum Index Thảo luận bảo mật Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ?  XML
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 19/03/2013 07:14:47 (+0700) | #1 | 274184
[Avatar]
invalid-password
Member

[Minus]    0    [Plus]
Joined: 09/03/2010 21:22:46
Messages: 161
Offline
[Profile] [PM]
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 ?
Spam thêm một bài là góp một viên gạch xây diễn đàn lớn mạnh
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 20/03/2013 13:58:00 (+0700) | #2 | 274229
breakoflove
Member

[Minus]    0    [Plus]
Joined: 07/03/2012 18:55:52
Messages: 24
Offline
[Profile] [PM]
Bắt cái vô hạn nằm trong cái hữu hạn thì làm sao được smilie.
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 21/03/2013 07:30:05 (+0700) | #3 | 274257
[Avatar]
invalid-password
Member

[Minus]    0    [Plus]
Joined: 09/03/2010 21:22:46
Messages: 161
Offline
[Profile] [PM]

breakoflove wrote:
Bắt cái vô hạn nằm trong cái hữu hạn thì làm sao được smilie

Không hiểu lắm ?
Spam thêm một bài là góp một viên gạch xây diễn đàn lớn mạnh
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 21/03/2013 09:34:27 (+0700) | #4 | 274263
n2tforever
Member

[Minus]    0    [Plus]
Joined: 01/07/2011 15:39:51
Messages: 92
Offline
[Profile] [PM]

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 smilie

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
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 21/03/2013 09:49:30 (+0700) | #5 | 274264
[Avatar]
invalid-password
Member

[Minus]    0    [Plus]
Joined: 09/03/2010 21:22:46
Messages: 161
Offline
[Profile] [PM]

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 ?
Spam thêm một bài là góp một viên gạch xây diễn đàn lớn mạnh
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 21/03/2013 11:34:27 (+0700) | #6 | 274269
n2tforever
Member

[Minus]    0    [Plus]
Joined: 01/07/2011 15:39:51
Messages: 92
Offline
[Profile] [PM]
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ể.

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 độ.

câu 3 : để hoàn toàn tránh được collision theo em thì số lượng hash có thể phải là vô hạn => chiều dài xâu hash phải là vô hạn => bất khả thi.

[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 21/03/2013 12:12:55 (+0700) | #7 | 274272
[Avatar]
invalid-password
Member

[Minus]    0    [Plus]
Joined: 09/03/2010 21:22:46
Messages: 161
Offline
[Profile] [PM]

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 smilie

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.
Spam thêm một bài là góp một viên gạch xây diễn đàn lớn mạnh
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 26/03/2013 08:04:41 (+0700) | #8 | 274396
vutrongtandng
Member

[Minus]    0    [Plus]
Joined: 21/03/2013 02:07:34
Messages: 1
Offline
[Profile] [PM]
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é
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 26/03/2013 21:57:08 (+0700) | #9 | 274421
Mr.Khoai
Moderator

Joined: 27/06/2006 01:55:07
Messages: 954
Offline
[Profile] [PM]

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
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 28/03/2013 16:29:27 (+0700) | #10 | 274462
[Avatar]
K4i
Moderator

Joined: 18/04/2006 09:32:13
Messages: 635
Location: Underground
Offline
[Profile] [PM]

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
Sống là để không chết chứ không phải để trở thành anh hùng
[Up] [Print Copy]
  [Question]   Khi xảy ra MD5 collision thì mã hash nào khác không bị collision ? 29/03/2013 08:24:19 (+0700) | #11 | 274486
monday1010
Member

[Minus]    0    [Plus]
Joined: 13/12/2008 23:18:55
Messages: 33
Offline
[Profile] [PM]
quăng bom nào, phương pháp giảm thiểu collision bằng cấu trúc Merkle–Damgård

http://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction
[Up] [Print Copy]
[digg] [delicious] [google] [yahoo] [technorati] [reddit] [stumbleupon]
Go to: 
 Users currently in here 
1 Anonymous

Powered by JForum - Extended by HVAOnline
 hvaonline.net  |  hvaforum.net  |  hvazone.net  |  hvanews.net  |  vnhacker.org
1999 - 2013 © v2012|0504|218|