해시에서 많은 반복 : 엔트로피를 줄이지 않습니까?

Question

이 기술은 여러 위치 (스택 포함)에서 권장되는 것으로 보입니다.이 기술이 내 머리에서 빠져 나와 엔트로피가 줄어들지 않습니다. 결국, 당신은 이미 해싱되어 충돌 기회가있는 무언가를 다시 해싱합니다. 충돌 기회에 대한 충돌 기회가 더 많은 충돌 기회를 초래하지 않을까요? 조사한 후에, 내가 틀렸어 보이지만 왜?

Answer 1

md5 태그를 추가 했으므로 예제로 사용하겠습니다. wikipedia에서 : 동일한 해시 두 접두사를 구축 할 수있는 경우

는 공통의 접미사를 사용하여 응용 프로그램에 의해 유효한 데이터로 인정 될 가능성이 충돌을 만들기 위해 모두에 추가 할 수 있습니다. 게다가, 현재 충돌 발견 기술은 임의의 접두어를 지정할 수있게 해줍니다 : 공격자는 두 개의 충돌 파일을 생성 할 수 있습니다. 충돌 파일은 모두 동일한 내용으로 시작됩니다. 침입자는 충돌 검색 알고리즘에 의해 자유롭게 변경 될 수있는 64 바이트 경계에 정렬 된 데이터의 128 바이트 블록이있는 템플릿 파일을 두 개의 충돌 파일로 생성해야합니다. 예를 들어, 6 비트가 다른 두 메시지가있는 MD5 충돌은 다음과 같습니다.

그런 다음 제공 한 일반 텍스트의 길이는 256 바이트입니다. 충돌 공격은 128 바이트 데이터 블록을 사용하고 해시 다이제스트는 128 비트뿐이므로 첫 번째 반복을 넘어 충돌 공격의 위험이 증가하지 않습니다. 즉, 첫 번째 해시를 넘어서는 충돌 가능성에 실제로 영향을 줄 수는 없습니다.

또한 해시의 엔트로피가 앞에서 설명한 128 비트라고 가정합니다. 총 충돌 확률이 2^20.96 (다시 wikipedia) 일지라도 두 입력이 충돌하게하려면 많은 반복이 필요합니다. 제 생각에 당신이 희생양이 될 것이라고 생각하는 이유는 다음과 같습니다.

• 두 임의 입력은 충돌 가능성 x %를가집니다.
• 첫 번째 해시의 출력은 이러한 입력 자체입니다.
• 따라서 모든 반복은 충돌 가능성을 x %만큼 증가시킵니다.

이것은 반례로 매우 쉽게 반박 할 수 있습니다. 다시 MD5를 고려

• 두 입력의 충돌의 기회를 1 :
• 해싱 다시 복잡하게하는 충돌의 가능성이 동일 기회가 발생합니다 (MD5의 위키 백과의 암호 분석에서 최악의 시나리오를 복용) 2^(21) 따라서 두 번째 라운드에서 충돌 가능성은 1 : 2^20입니다.
• Therfore, 임의의 두 입력에 대해 다이제스트의 엔트로피와 동일한 횟수가 해시되고 충돌이 보장됩니다.

MD5 두 개의 입력을 128 번 연속으로 입력하면 이것이 사실이 아님을 알 수 있습니다. 아마도 그들 사이에 하나의 반복 된 해시를 찾지는 않을 것입니다. 결국 가능한 2^128 해시 값 중에서 256 개만 생성하여 2^120의 가능성을 남깁니다. 각 라운드 간의 충돌 확률은 다른 모든 라운드 중 independent입니다.

이유를 이해하는 데는 두 가지 방법이 있습니다. 첫 번째는 각 반복이 본질적으로 움직이는 표적을 공격하려고한다는 것입니다.난 당신이 하나의 입력에서 하나의 해시 다이제스트가 다른 입력의 해시 다이제스트와 일치하는 것을 볼 수있는 해싱의 반복 횟수가 놀라 울 정도로 낮다는 생일 패러독스에 근거한 증명을 만들 수 있다고 생각합니다. 그러나 그들은 거의 확실하게 에서 발생했을 것입니다. 단계가 반복됩니다. 한 번 발생하면 해시 알고리즘 자체가 결정적이기 때문에 같은 반복에서 동일한 결과를 얻을 수 없습니다.

다른 접근법은 해시 함수가 실제로 실행되는 동안 엔트로피를 추가한다는 것을 인식하는 것입니다. 빈 문자열에는 다른 입력과 마찬가지로 128 비트 다이제스트가 있다고 가정합니다. 알고리즘 단계에서 엔트로피가 추가되지 않으면 발생하지 않습니다. 이것은 실제로 암호화 해시 함수의 필연적 인 일부입니다. 즉, 데이터를 파괴해야합니다. 그렇지 않으면 입력을 다이제스트에서 복구 할 수 있습니다. 다이제스트보다 긴 입력에 대해서는 엔트로피가 전체적으로 손실됩니다. 다이제스트 길이에 맞춰야합니다. 그러나 일부 엔트로피도 추가됩니다.

다른 해시 알고리즘에 대한 정확한 숫자는 없지만 다른 해시 함수 및 단방향/매핑 함수로 일반화 한 모든 점을 생각합니다.

Answer 2

엔트로피가 줄어 듭니다. Flajolet 및 Odlyzko하는 정리 (정리 2)에 의해 Random Mapping Statistics라는 논문에서

것을 보여준다 :

N가 K 번 영상 점의 예상 된 수를 반복되는 임의의 함수를 비트 경우

" 인 (1 - t_k) * 2^N (대형 N 위해), 여기서, t_k 만족 점화식 t_0 = 0 및 t_ {K + 1} = E^{- 1 + t_k}. 이것으로부터, 화상 점의 예상 개수임을 나타낼 수 2^{N-I + 1} 랜덤 함수 K = 2^I 번 반복된다. "

또한 참조 같다 다음과 같습니다...

• Gligoroski, D.와의 Klima, V. 2010 년 9 월 이상적인 랜덤 기능에서 좁은 파이프 해시 디자인의 수차의 실제 결과 국제 회의에서 ICT 혁신에 (PP 81- 93). Springer Berlin Heidelberg.

• Bhaum Guan, J., Jean, J., Mouha, N. and Nikolić, I., 2015. More Rounds, Less Security?

• Dinur, I. and Leurent, G., 2014, 팔월. 해시 기반 MAC 및 HAIFA에 대한 향상된 일반 공격. International Cryptology Conference (pp. 149-168). Springer Berlin Heidelberg.

  마지막 참조 용지에서

, 하나는 다음과 같은 두 가지 보조 정리를 찾을 수 : Two lemmas on entropy loss합니다. 따라서 k 독립 임의 함수가 사용되는 경우 엔 엔트로피 손실에 대한 관찰이 유지됩니다.이 경우 임의의 함수는 k 번 반복됩니다.