각 바이너리 자산에 대해 MD5 해시를 생성합니다. 특정 바이너리 자산이 이미 애플리케이션에 있는지 확인하는 데 사용됩니다. 그러나 두 개의 다른 이진 자산이 동일한 MD5 해시를 생성 할 수 있습니다. 두 개의 다른 문자열이 동일한 MD5 해시를 생성 할 수 있습니까?
답변
수십억 개의 자산 세트의 경우 무작위 충돌 가능성은 무시할 정도로 작습니다 . 걱정할 필요가 없습니다. 고려 생일 역설 , 2 ^ 64 (또는 18,446,744,073,709,551,616) 자원의 집합을 소정의 확률 단일 세트 내의 MD5 충돌은 50 %이다. 이 규모에서는 스토리지 용량 측면에서 Google을 능가 할 것입니다.
그러나 MD5 해시 기능이 손상 되었기 때문에 ( 충돌 공격에 취약 함 ) 결정된 공격자는 CPU 성능에 대해 몇 초 만에 2 개의 충돌 자산 을 생성 할 수 있습니다 . 따라서 MD5를 사용하려면 그러한 공격자가 애플리케이션의 보안을 손상시키지 않도록해야합니다!
또한 공격자가 데이터베이스 의 기존 자산 에 대한 충돌을 위조 할 수 있는 경우의 결과를 고려하십시오 . MD5 (2011 년 현재)에 대한 알려진 공격 ( 사전 이미지 공격 ) 은 없지만 충돌 공격에 대한 현재 연구를 확장하면 가능할 수 있습니다.
이것이 문제로 판명되면 SHA-2 시리즈 해시 함수 (SHA-256, SHA-384 및 SHA-512)를 살펴 보는 것이 좋습니다. 단점은 약간 느리고 해시 출력이 더 길다는 것입니다.
답변
MD5는 해시 함수입니다 . 따라서 두 개의 서로 다른 문자열이 충돌 MD5 코드를 생성 할 수 있습니다.
특히 MD5 코드는 길이가 고정되어 있으므로 가능한 MD5 코드 수가 제한됩니다. 그러나 문자열 (길이에 관계없이)의 수는 확실히 무제한이므로 논리적으로 충돌 이 있어야 합니다.
답변
답변
예, 물론입니다. MD5 해시는 유한 길이이지만 MD5 해시가 될 수있는 가능한 문자열은 무한합니다.
답변
예, 두 개의 다른 문자열이 동일한 MD5 해시 코드를 생성 할 수 있습니다.
다음은 16 진 문자열에서 매우 유사한 바이너리 메시지를 사용하는 간단한 테스트입니다.
$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc -
008ee33a9d58b51cfeb425b0959121c9
$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca -
008ee33a9d58b51cfeb425b0959121c9
그들은 다른 SHA-1 합계를 생성하지만 동일한 MD5 해시 값을 생성합니다. 둘째, 현이 매우 유사하기 때문에 그 차이를 찾기가 어렵습니다.
차이점은 다음 명령으로 찾을 수 있습니다.
$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63 2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62 2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
af
bf
a2
-00
+02
a8
28
4b
@@ -53,7 +53,7 @@
6d
a0
d1
-55
+d5
5d
83
60
위의 충돌 예는 Marc Stevens에서 가져온 것 입니다. MD5의 단일 블록 충돌 , 2012; 그는 자신의 방법을 소스 코드와 함께 설명합니다 ( 논문에 대한 대체 링크 ).
또 다른 테스트 :
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82 -
cee9a457e790cf20d4bdaa6d69f01e41
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb -
cee9a457e790cf20d4bdaa6d69f01e41
다른 SHA-1 합계, 동일한 MD5 해시.
차이점은 1 바이트입니다.
$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63 2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62 2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
03
65
9e
-70
+74
4f
85
34
@@ -41,7 +41,7 @@
a3
f4
15
-5c
+dc
bb
86
07
위의 예는 Tao Xie 및 Dengguo Feng : 단일 메시지 블록을 사용하여 MD5 충돌 구성 , 2010 에서 채택되었습니다 .
관련 :
- MD5 해시 값이 동일한 두 개의 알려진 문자열이 있습니까? Crypto.SE에서
답변
답변
더 많은 정보를 제공합니다. 수학적인 관점에서 해시 함수는 주입 적이 지 않습니다 .
이는 시작 세트와 결과 세트 사이에 일대일 (단방향) 관계가 없음을 의미합니다.
편집 : 완전한 인젝 티브 해시 함수가 존재하려면 Perfect hashing 이라고 합니다.
