MD5에서 충돌 가능성

Question

최악의 경우, 캐시에 1 억 8 천만 개의 값 (오래된 15 분 경과 전)이 있고 MD5에는 2^128 값이 있습니다. 충돌 할 확률은 얼마입니까? 또는 더 나은 아직, 어딘가에 그 질문 또는 대략적인 견적에 대답하는 웹 페이지가 있습니까? 내 기회를 알기 때문에 그렇게 흔들릴거야.

Answer 1

확률 1 m이다!/(mⁿ (m-N)!)여기서 m = 2¹²⁸및 N = 180,000,000.

온라인 Wolfram을 통해 실행하면 계산 시간이 초과됩니다! 당신이 스몰 토크가 로컬로 설치 한 경우

, 당신은이를 실행할 수 있습니다

이

|m n p| 

m := 2 raisedTo:128. 
n := 180000000. 
p := (1-(m factorial/((m raisedTo:n)*(m-n)factorial)))asFloat. 

Transcript show:p printString;cr. 

생일 문제에 대한 검색가 128 비트 및 2.6 × 10¹⁰ 해시에 대한 나타내는 표를 제공 어디 Wikipedia page, 확률을 제공합니다 충돌의 수는 10¹8에서 1이므로 140 × 해시의 수는 고려중인 것보다 많습니다. 그래서 당신은 당신의 확률이 이것보다 "더 나쁘다"는 것을 알고 있습니다.

는

는 n 개의«분 당신이 미터 이상 N에 연결하면 1-E ^{-n 2/2m}이다 좋은 근사, 당신은 4.76 × 10⁻²³를 얻을 수 충돌 확률로 2.10 × 10²²로 1이됩니다.

충돌 확률이 매우 낮을지라도 FOOBAR 경우에는 신중해야합니다. 문제가 있고 15 분 이상 동안 해시가 누적되는 경우 최소한 이벤트 발생시 어떤 일이 발생하는지 확인하려면 말하십시오. 충돌.