해시 함수 선택

Question

해시 함수의 예상 충돌 수를 유지하면서 안전하게 해시 할 수있는 최대 바이트 수는 무엇입니까?

md5, sha- *의 경우 crc32 또는 adler32도 가능합니다.

Answer 1

질문이 명확하지 않습니다. "최대 바이트 수"란 "최대 항목 수"를 의미합니까? 해시되는 파일의 크기는 충돌 수와는 관계가 없습니다 (물론 모든 파일이 다르다고 가정 할 경우).

"예상 충돌 수 유지"란 무엇을 의미합니까? 문자 그대로 말하면 대답은 "무한"이지만 ​​일정한 숫자가 지나면 예상대로 충돌이 발생합니다. 질문에 대한 답변으로

"얼마나 많은 항목 나는 X의 %에서 충돌의 가능성을 유지하면서 해시 수 있을까?", 다음 표를 살펴 걸릴 다음에서

http://en.wikipedia.org/wiki/Birthday_problem#Probability_table

을 링크 :

비교를 위해, 10^-18에서 10^-15는 일반적인 하드 디스크의 정정 할 수없는 비트 오류율입니다 [2]. 이론상으로 MD5 (128 비트)는 가능한 출력이 훨씬 더 많아도 약 820 억 개의 문서까지 해당 범위 내에 있어야합니다.

균일 한 분포를 출력하는 해시 함수를 가정합니다. 해시 할 수있는 충분한 항목과 md5 및 sha와 같은 암호화 해시 함수 또는 Murmur3, Jenkins, City 및 Spooky Hash와 같은 양호한 해시가 있다고 가정 할 수 있습니다.

또한 악의적 인 공격자가 적극적으로 충돌을 일으키지 않는다고 가정합니다. 그런 다음 SHA-2와 같은 안전한 암호화 해시 함수가 필요합니다.

주의 : CRC 및 Adler는 데이터 손상을 감지하고 예상되는 충돌을 최소화하도록 설계된 체크섬입니다. 그것들은 "크기가X 또는> Y 인 모든 비트 영점을"Z KB까지의 입력에 대해 감지하지만 좋은 통계적 특성은 아닙니다 "와 같은 소유권을 가지고 있습니다.

편집 : 이것은 모두 확률에 관한 것입니다. 극히 드물기는하지만 0.5kb보다 작은 두 개의 파일 만 해시하고 동일한 SHA-512를 얻을 수 있습니다 (예 : no collision has ever been found for SHA hashes till this date).

Answer 2

기본적으로 정말 큰 숫자 만보고있는 생일의 역설을보고 있습니다. 데이터의 정상적인 '분포'를 감안할 때, 문제가 발생하기 전에 가능성이 5-10 % 정도 될 수 있다고 생각합니다.

문제가 발생하지 않도록 충분히 긴 해시로 이동하십시오.)