md5는 짧은 문자열 (문자열의 유한 수)에 대해 고유성을 보장합니까?

Question

MD5 해시 문자열보다 우주에 더 많은 문자열이 있기 때문에 MD5가 고유성을 보장 할 수 없다는 증거가 있다는 것을 알고 있습니다. 그러나 한정된 수의 문자열에 대한 역 증명이 있습니까?

기본적으로 최대 길이가 X 인 문자열은 MD5가 고유 한 것으로 보장되는 X가 있습니까? 그렇다면 X는 무엇입니까? X에 대해 하나 이상의 값이있는 경우 X의 최대 값은 무엇입니까?

또는 다른 해싱 알고리즘 인 SHA-1 등과 같은 X가 있습니까?

Answer 1

귀하의 질문에 대한 답변은 '예'입니다. 모든 해시 함수에 대해 고유 한 문자열을 되 찾을 수있는 최대 길이 X가 있습니다. X를 찾는 것은 매우 어려울 수 있습니다. 아이디어는이 프로그램을 실행하는 것입니다 :

X= 0; 
For i = 0 onward 
    For all strings of length i 
     Compute the hash code of that string. 
     If a collision is found, return X. 
    X = i 

아이디어는 해시 충돌을 찾을 때까지 길고 긴 문자열을 나열하는 것입니다. 결과적으로 해시 출력이 가능한 것보다 많은 문자열을 생성 할 것이므로 결국해야 할 것입니다.

예상대로 해시 함수가 실제로 매우 랜덤하다고 가정하면 충돌을 찾기 전에 O (√ U) 개의 다른 문자열을 생성해야합니다. 여기서 U는 해시 함수가 매핑되는 공간의 크기입니다 . 256 비트 해시의 경우이 값은 2 입니다. 이것은 해쉬 함수가 꽤 깨지기 전까지 실제로는 위의 프로그램이 실제로 종료되지 않는다는 것을 의미합니다. 이론적으로 숫자 X가 존재한다는 것을 의미합니다.

희망이 도움이됩니다.

Answer 2

여기 우수한 응답을 요약 : What's the shortest pair of strings that causes an MD5 collision?는

MD5 최단 알려진 공격 2 개 입력 블록을 요구, 즉, 128 바이트 1024 비트.

N 비트를 출력하는 해시 알고리즘의 경우 입력이 대략 임의로 분포한다고 가정하면 sqrt(2^N) 입력에서 충돌이 50 % 이상 발생할 것으로 가정 할 수 있습니다. 예를 들어, MD5는 128 비트로 해시되므로 모든 64 비트 입력 사이에 충돌이 발생할 수 있습니다. 이것은 균일하게 무작위 해시를 가정합니다. 모든 약점은 충돌이 발생할 것으로 예상되기 전에 입력 수를 줄입니다.