MD5 충돌을 일으키는 가장 짧은 문자열 쌍은 무엇입니까?

MD5 충돌을 일으키는 가장 짧은 문자열 쌍은 무엇입니까?

---

충돌 가능성에 대해 걱정할 필요없이 MD5를 해시로 사용할 수있는 문자열 길이는 얼마입니까?

이것은 해시가 두 번째로 나타날 때까지 (충돌) 특정 문자 집합의 가능한 모든 문자열에 대해 MD5 해시를 생성하여 길이를 늘림으로써 계산할 수 있습니다. 충돌이없는 문자열의 가능한 최대 길이는 충돌하는 쌍의 가장 긴 문자보다 한 문자가 적습니다.

MD5, SHA1 등에 대해 이미 테스트 되었습니까?

---

최신 정보

아이러니하게도 이전 답변을 게시 한 지 몇 주 후에 중국 연구원 Tao Xie와 Dengguo Feng 이 MD5에 대한 새로운 단일 블록 충돌을 발표했습니다 . 나는 지금까지 그 논문을 몰랐다. 단일 MD5 블록은 입력 크기가 64 바이트 또는 512 비트임을 의미합니다. 입력은 거의 동일 하며 2 비트 만 다릅니다 .

그들의 방법론은 2013 년 1 월까지 출판되지 않을 것이지만, 논문의 숫자를 사용하여 충돌을 지금 확인할 수 있습니다.

>>> from array import array
>>> from hashlib import md5
>>> input1 = array('I',  [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
    0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])
>>> input2 = array('I', [x^y for x,y in zip(input1,
    [0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])
>>> input1 == input2
False
>>> md5(input1).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'
>>> md5(input2).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'

업데이트 : 이 논문은 2013 년 3 월에 출판되었습니다 : Tao Xie, Fanbao Liu 및 Dengguo Feng-MD5에 대한 빠른 충돌 공격

그러나 놀 수있는 공간이 더 많으면 몇 킬로바이트의 충돌을 계산하는 것이 훨씬 더 빠릅니다. 일반 컴퓨터에서 몇 시간 내에 계산할 수 있습니다.

이전 답변

이전의 최단 충돌은 최소 2 개의 MD5 블록을 사용했습니다 (128 바이트, 1024 비트). 첫 번째 블록의 접두사는 공격자가 임의로 선택할 수 있으며 나머지는 계산되어 횡설수설로 표시됩니다.

다음은 두 가지 충돌 입력의 예입니다. Python에서 직접 시도해 볼 수 있습니다.

>>> from binascii import unhexlify
>>> from hashlib import md5
>>> input1 = 'Oded Goldreich\nOded Goldreich\nOded Goldreich\nOded Go' + unhexlify(
... 'd8050d0019bb9318924caa96dce35cb835b349e144e98c50c22cf461244a4064bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf67c12978647f5af123de3acf844085cd025b956')
>>> len(input1)
128
>>> md5(input1).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'
>>> input2 = 'Neal Koblitz\nNeal Koblitz\nNeal Koblitz\nNeal Koblitz\n' + unhexlify(
... '75b80e0035f3d2c909af1baddce35cb835b349e144e88c50c22cf461244a40e4bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf6fc11978647f5af123de3acf84408dcd025b956')
>>> md5(input2).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'

이 두 가지 특정 입력을 생성하는 데 Mark Stevens 의 215 노드 Playstation 3 클러스터에서 2 일이 걸렸습니다. :)

---

생일 역설 의 수학은 대략 sqrt (N) 주변에서 충돌 확률의 변곡점을 만듭니다. 여기서 N은 해시 함수의 개별 빈 수이므로 128 비트 해시의 경우 약 64 비트를 얻을 수 있습니다. 충돌이 1 회있을 가능성이 보통입니다. 그래서 내 생각에는 8 바이트 문자열의 전체 세트에 대해 다소 충돌이 발생할 가능성이 있고 9 바이트 문자열의 경우 매우 가능성이 높습니다.

편집 : 이것은 MD5 해시 알고리즘이 입력 바이트 문자열에서 "무작위"에 가까운 출력 해시로의 매핑을 유발한다고 가정합니다. (vs. 가능한 해시 세트간에 문자열을 더 균등하게 분배하는 경우, 16 바이트에 더 가깝습니다.)

Also for a more specific numerical answer, if you look at one of the approximations for calculating collision probability, you get

p(k) ≈ 1 - e^{-k(k-1)/(2*2128)} where k = the size of the space of possible inputs = 2^m where the input bytestring is m bits long.

the set of 8 byte strings: p(2⁶⁴) ≈ 1 - e^-0.5 ≈ 0.3935

the set of 9 byte strings: p(2⁷²) ≈ 1 - e^{-2144/(2*2128)} = 1 - e^-215 = 1 - e^-32768 ≈ 1

Also note that these assume the complete set of m/8 byte strings. If you only use alphanumeric characters, you'd need more bytes to get a probable collision.

---

I doubt if there is any useful length where you're not going to have possible collisions. Those algorithms are not really used for that purpose. It's meant to try to be unique for slight changes in the data (like corrupted files) rather than unique over all possible sets of data.

참고URL : https://stackoverflow.com/questions/1999824/whats-the-shortest-pair-of-strings-that-causes-an-md5-collision