해시 충돌 및 추가 데이터

Question

두 개의 문자열 (또는 바이트 어레이) A와 B가 있다고 가정합니다. 모두 동일한 해시가 있습니다 (해시와 함께 MD5 또는 SHA1과 같은 것을 의미합니다). 그 뒤에 다른 문자열을 연결하면 A+C와 B+C가 동일한 해시 H '도 있습니까? C+A 및 C+B는 어떻게됩니까?

나는 그것을 테스트했다 MD5 그리고 모든 시험에서, 끝까지 무언가를 추가하면 해시가 동일하게 만들었지 만 처음에는 추가되지 않았습니다.

이것은 항상 사실입니까 (모든 입력에 대해)?

이것이 모든 (잘 알려진) 해시 함수에 맞습니까? 그렇지 않은 경우, A+C와 B+C가 충돌하지 않는 (잘 알려진) 해시 함수가 있습니까 (및 C+A와 C+B는 그렇지 않습니까?

(그 외에 MD5(x + reverse(x)) 그리고 다른 구성된 물건은 내 말입니다)

Answer 1

이것은 달라집니다 전적으로 해시 함수에서. 또한, 당신이 충돌 할 확률은 실제로 작습니다.

Answer 2

세부 사항은 해시 기능 H에 따라 다르지만 일반적으로 다음과 같이 작동합니다.

1. 입력 X 블록을 소비합니다 (예 : 512 비트)
2. 입력을 작은 조각 (예 : 32 비트)으로 나누고 입력에 따라 해시 내부 상태를 업데이트하십시오.
3. 입력이 더 많으면 1 단계로 이동하십시오.
4. 결국, 해시 값 h (x)로 내부 상태를 뱉어냅니다.

따라서 A와 B가 IE H (a) = h (b)를 충돌하면 해시는 소비 한 후 동일한 상태에 있습니다. 동일한 입력 C로 상태를 더 업데이트하면 결과 해시 값이 동일하게 만들 수 있습니다. 이것은 왜 H (a+c)가 때때로 h (b+c) 인 이유를 설명합니다. 그러나 A와 B의 크기가 입력 블록 크기에 정렬되는 방식과 해시가 내부적으로 입력 블록을 깨뜨리는 방법에 따라 다릅니다.

C가 해시 블록 크기의 배수이지만 그렇지 않은 경우 C+A 및 C+B가 동일 할 수 있습니다.

Answer 3

여기에서 논의되는 해시 기능은 일반적으로 암호화 (SHA1, MD5)입니다. 이 해시 함수에는 다음과 같습니다 눈사태 효과 - 입력의 약간의 변화로 출력이 급격히 변합니다.

접두사 및 접미사 확장 C 효과적으로 더 긴 입력을 할 것입니다. 따라서 입력의 전면 또는 후면에 무언가를 추가하면 유효 해시 출력이 크게 변경되어야합니다.

나는 당신이 MD5 점검을 어떻게했는지 이해하지 못합니다. 여기 내 테스트가 있습니다.

echo "abcd" | md5sum
70fbc1fdada604e61e8d72205089b5eb

echo "0abcd" | md5sum
f5ac8127b3b6b85cdc13f237c6005d80

echo "abcd0" | md5sum
4c8a24d096de5d26c77677860a3c50e3

당신은 당신이 동일한 MD5 해시를 가진 두 개의 입력을 찾은 다음 입력의 끝이나 시작에 무언가를 추가했으며, 끝에 추가하면 원래 입력에 대한 MD5와 동일한 MD5가 있음을 발견 했습니까?

테스트 결과와 함께 샘플을 제공하십시오.