해시 충돌 H (x) = H (y)와 x! = y는 H (x + z) = H (y +

Question

H가 (MD5 나 SHA256 등의) 일부 해시 함수이고이 해시에 충돌이 있다고 가정합니다. 두 개의 다른 데이터 x와 y는 동일한 해시를가집니다.

즉, x ≠ y이지만 H (x) = H (y)입니다.

이제 임의의 데이터 z를 연결하면 H (x + z)가 H (y + z)와 같습니까?

아이디어는 다음과 같습니다. x와 y는 충돌이므로 동일한 상태에서 H 함수를 가져 오는 것을 의미 할 수 있습니다 (따라서 동일한 해시가 발생 함). 이 시점부터 우리가 추가하는 다른 데이터는 중요하지 않으며 해시도 동일하게 유지됩니다.

나는 위의 내용을 this MD5 collision으로 테스트했으며 거기에서 작동하는 것으로 보입니다. 그러나 이것이 일반적으로 사실인지 나는 모른다.

Answer 1

has 기능에 따라 다릅니다. 해시 함수는 homomorphic이 아니기 때문에 (즉, f(x) = f(y)은 x = y을 의미) f(x + z)과 f(y + z)은 동일한 항목에 매핑됩니다. 해쉬 함수

f(x) = (x * 3) + 1 mod 6 

다음

f(2) = 1 및 f(6) = 1을 감안할 때

: 카운터 예를 생각해 보자. Let z = 1. 그런 다음 :

f(2 + z) = 4 and f(6 + z) = 1 

따라서 f(2) = f(6)하지만 f(2 + z) ≠ f(6 + z). 해시 함수는 호모 모르 픽한다면

그러나, 다음 이체 동형의 정의 :

f(p + q) = f(p) + f(q) 

따라서 :

f(x + z) = f(x) + f(z) 
f(y + z) = f(y) + f(z) 

하지만 f(x) = f(y) 이후 처음 언급 한 바와 같이 어떤 :

f(x) + f(z) = f(y) + f(z) 

이므로 해시는 동일합니다.

Answer 2

이 특정 기술은 length extension attack이라고합니다. 해시 함수가 취약한 지 여부는 분명히 특정 해시 함수에 따라 다릅니다. MD5 및 SHA-1과 같은 Merkle–Damgård construction을 기반으로하는 해시 함수는 취약합니다. SHA-3은 취약하지 않으며 HMAC constructions도 취약하지 않습니다.

Answer 3

(그것은 내 첫 번째 대답 관대하시기 바랍니다 : D) 반드시 하지 :

x = [8 0 4] 
y = [8 1 0] 
z = [5] 

및 해싱 함수 (숫자의 나열로) 다음과 같은 데이터를 고려

H([a b c]) = a + b*c 
H([a b c d]) = H([b c d]) + H([a b c]) 

그러면 x와 y에 대한 충돌이 발생합니다.

H(x) = H([8 0 4]) = 8 + 0*4 = 8 
H(y) = H([8 1 0]) = 8 + 1*0 = 8 

그러나 데이터를 추가 할 때, 해시는 동일하지 :

H(z + x) = H([5 8 0 4]) = H([5 0 8]) + H([8 0 4]) = 5 + 8 = 13 
H(z + y) = H([5 8 1 0]) = H([5 8 1]) + H([8 1 0]) = 13 + 8 = 21