언제 해시가 충돌합니까?

Question

비둘기 원칙에 따라 항목 수가 컨테이너 수보다 많으면 적어도 하나의 컨테이너에 두 개 이상의 항목이있는 것으로 알고 있습니다. 어떤 컨테이너가 될 것인가가 중요합니까? 이것이 MD5, SHA1, SHA2 해시에 어떻게 적용됩니까?

Answer 1

아니요 컨테이너가 무엇이든 상관 없으며, 사실 이것은 암호화 해시에 중요하지 않습니다. 많이 더은 birthday paradox이며 충돌을 발견하기 전에 평균적으로 sqrt(numberNeededByPigeonHolePrincipal) 값을 해싱하면됩니다.

따라서 해시는 검색 공간의 제곱근이 너무 많아서 무차별 대항력을 발휘할 수 없을 정도로 커야합니다. SHA1에 대한 제곱근 검색 공간은 2 이며 2012 년 3 월 현재 동일한 SHA1 해시로 두 값을 찾지 못했습니다 (내년이나 내 2 년 내에 발생할 것으로 예상되지만 ..); 모두 더 큰 검색 공간을 가진 해시 제품군 인 SHA2와 동일합니다. MD5는 broken for a while입니다.

Answer 2

해시 함수의 핵심은 항목을 컨테이너에 무작위로 배포하는 것입니다. 어떤 좋은 해시 함수에 대해서도, 어느 컨테이너가 어느 것을 구별 할 수 없으므로 "중요하지"않다.

이것은 언급 한 알고리즘과 달리 무작위 배포보다 나은 "완벽한 해시"구현에는 적용되지 않습니다.

마이클이 언급했듯이 슬롯과 같은 항목이 많아지기 전에 충돌이 오래 걸립니다. birthday paradox을 처리하려면 우아한 충돌 처리 (또는 완벽한 해시)가 필요합니다.

Answer 3

슬롯이있는 것보다 해시 할 항목이 더 많은 경우 해시 충돌이 발생합니다. 그러나 해시 알고리즘이 좋지 않은 경우 아이템/슬롯 비율이 매우 낮을 때도 충돌이 표시됩니다. 좋은 해싱 알고리즘 (야생에서 볼 수있는 대부분의 알고리즘 포함)은 결과 출력 해시를 가능한 한 균등하게 전체 출력 공간에 분산시키고 충돌을 최소화하려고 시도합니다.

해시 충돌이 세계의 끝이 아니라는 점에 유의하십시오. 예를 들어, 해시 테이블에서 사용되는 경우, 하나 이상의 항목이 슬롯에 저장되고 대상 항목을 찾거나 추가하기 위해 테이블 ​​코드가 조금 더 이동해야하므로 조회 시간이 약간 늘어납니다.

사람들은 MD5를 "깨진"해싱 알고리즘이라고 말합니다. 실제로 암호화 해시로 사용하기에는 좋지 않습니다. 너 자신을 만드는 것보다 낫겠 네.

Answer 4

해쉬 함수를 사용하는 응용 프로그램이 중요한 차이라고 생각합니다. 예를 들어 해싱 컨테이너에서 충돌이 자주 발생하면 성능이 저하 될 수 있습니다. 암호 해독에서 잦은 충돌은 훨씬 더 치명적인 결과를 낳습니다 (참조 : cryptographic hash function on Wikipedia).

"괜찮은"해시 알고리즘을 사용하는 경우에도 충돌이 상대적으로 쉽게 발생합니다. 예를 들어, 자바,

String s = new String(new char[size]); 

는 항상에 0입니다, 자바 0 만 \0 해시를 포함하는 모든 문자열을 해시.

---

"어떤 컨테이너가 될 것인가?"에 대해서는 다시 응용 프로그램에 따라 다릅니다. "유사한"객체를 가까운 값에 해시하는 해시 함수를 설계 할 수 있습니다. 예를 들어, 유사한 오브젝트를 검색하려는 경우에 유용합니다. 그들 모두를 해시하고 그들이 떨어지는 곳을보십시오. 이 경우 유사한 개체를 그룹화하기 때문에 충돌 또는 거의 충돌이 바람직합니다.

다른 응용 프로그램에서는 개체가 조금만 변경 되어도 해시 값이 완전히 달라지기를 원합니다. 예를 들어 암호가 변경되지 않은 것을 가능한 한 확실하게하려는 경우와 같은 암호화의 경우입니다. 이 경우 동일한 값으로 해시하는 다른 개체를 찾는 것이 훨씬 어렵습니다.

Answer 5

MDA, SHA1/2 등의 암호화 해시는 응용 프로그램에 따라 이상적인 선택이 아닐 수 있습니다. 정확하게 완전 무작위로 표시되기 때문에 생일 패러독스에 의해 미리 예측 된대로 충돌이 발생합니다. 전통적으로 나머지 연산에 기반한 간단한 해시를 사용하는 한 가지 이유는 키가 일련 번호 또는 이와 유사 할 것으로 예상 되었기 때문에 나머지 작업은 무작위 적으로 예상보다 적은 충돌을 유지할 수 있다는 것입니다. 예 : 키가 정수 인 경우 1.000입니다. 해시 함수가 키 mod 1009 인 경우 크기가 1009 인 컨테이너에서 충돌이 전혀 없을 수 있습니다. 사람들은 때로는 컨테이너 크기와 해시 함수를 신중하게 선택하여 시스템을 손으로 조정할 수 있습니다. 균등 분할.

물론 어려운 문제를 일으킬 수있는 키를 악의적으로 선택하는 사람이나 매우 편향된 키를 보내는 업스트림 시스템 (예 : 자체 해시 테이블이있어서 해시 키를 모두 처리하기로 결정했기 때문에)에 대해 걱정해야한다면 X). 이를 막기 위해 암호화 된 해시 함수에 기반한 해시를 사용할 수 있습니다.