MD5 hash Collisions

MD5                                                                                                           

md5 & SHA1  : Collisions for Hash Functions   md5와 SHA1이 깨졌다고 신문기사가 났는데.. 이번 기회에 Hash Function에 대해서 생각해보도록 합시다. 그런데, 깨졌다기 보다는 정확히는 특정한 문장에 대한 md5 해시 값과 똑같은 결과를 리턴하는 md5 값을 수학적으로 찾아낼 수 있음이 증명되었다는 것이랍니다. 참고로, md5로 해시한 문자열의 수학적인 복호화는 불가능하다는것이 이미 증명되어 있습니다. 이론적으로 md5는 16진수의 32비트 문자열의 해시가 리턴되므로, 16^32 가지의 경우의 수가 존재하며, md5에 들어갈 수 있는 문자의 수는 무한하므로 비둘기집의 원리에 따라 같은 결과를 나타내는  두개 이상의 문자열이 반드시 존재합니다.

비둘기집의 원리(pigeonhole principle)
집의 구멍수보다 비둘기가 더 많으면 적어도 한 구멍에는 두 마리 이상이 들어 있다‘라는 원리를 말한다.

 좀더 일반적으로 말하면, ‘비둘기의 수가 구멍수의 k배보다 더 많으면 어떤 구멍에는 적어도 k+1마리가 들어있다’라고 할 수 있다.

 실제로 문제풀이에 많이 쓰이는 경우는, ‘n+1마리의 비둘기가 n개의 구멍에 들어가려면 적어도 한 구멍에는 두 마리 이상 들어가야 한다’는 것이다.

 이 원리의 증명은, 귀류법에 의하여 명백하므로 거의 필요로 하지 않는다. 즉, 모든 구멍에 한 마리 이하가 들어간다면 그 총 비둘기의 수는 n마리 이하이므로 처음에 생각한 n+1마리가 될 수 없기 때문이다.

 쉬운 예로 탁구공 3개를 양손으로 잡으려면 한 손은 2개 이상 잡아야 한다.

 이 원리를 디리클레 서랍 원리, 신장 원리라고도 한다.

여기서는 특정한 문자열 1 (string1) 을 가지고 똑같은 md5 해시값을 가리키는 문자열 2 (string2) 를
 알아낼 수 있다는 것을 증명한 것입니다.

MD5 중복값 예제:

> 예제 1:

첫번째 해시: 2ba3be5aa541006b62370111282d19f5
두번째 해시: 2ba3be5aa541006b62370111282d19f5

첫번째 문장: pmTquIkEwqxIQ0EOCmNCVBZgbIFELdaNQARYPrj7f4lVrTQGCfSzAoPkiIMlcUFaCFEl6PfNyZ/
ZHb3ygDc8W5eevbQOKm4XpiNXJNHfQbRGc/mW8WJK3RApMWfQCbGPdad/eTDZXOsC6K26
eshVXO10yt1fyZNtsZtK2DXMZ+M=

두번째 문장: pmTquIkEwqxIQ0EOCmNCVBZgbAFELdaNQARYPrj7f4lVrTQGCfSzAoPkiIMl8UFaCFEl6PfNyZ/
ZHb1ygDc8W5eevbQOKm4XpiNXJNHfQbRGc/kW8WJK3RApMWfQCbGPdad/eTDZXOsC6K26
ekhVXO10yt1fyZNtsZtKWDXMZ+M=

if (문장1==문장2): false

- 원래 문자열은 바이너리로, 위의 문자열은 base64로 인코드 되어 있습니다.
  디코드 하신후 테스트 하시기 바랍니다.

<Test by Python>

>>> import base64
>>> import md5
>>> string1 = base64.b64decode("pmTquIkEwqxIQ0EOCmNCVBZgbIFELdaNQARYPrj7f4lVrTQGCfSzAoPkiIMlcUFaCFEl6PfNyZ
/ZHb3ygDc8W5eevbQOKm4XpiNXJNHfQbRGc/mW8WJK3RApMWfQCbGPdad/eTDZXOsC6K26
eshVXO10yt1fyZNtsZtK2DXMZ+M=")
>>> string2 = base64.b64decode("pmTquIkEwqxIQ0EOCmNCVBZgbAFELdaNQARYPrj7f4lVrTQGCfSzAoPkiIMl8UFaCFEl6PfNyZ
/ZHb1ygDc8W5eevbQOKm4XpiNXJNHfQbRGc/kW8WJK3RApMWfQCbGPdad/eTDZXOsC6K26
ekhVXO10yt1fyZNtsZtKWDXMZ+M=")

>>> print md5.new(string1).hexdigest()
2ba3be5aa541006b62370111282d19f5
>>> print md5.new(string2).hexdigest()
2ba3be5aa541006b62370111282d19f5

>>> string1 == string2
False