충돌 회피성 (=충돌 저항성)

충돌회피성(=충돌저항성) 이란?

뭐 충돌 저항성과 같은 말이다. birthday attack에 대해 언급한적이 있는데, 이게 해시 충돌에 관련된 공격이다.

해시는 일방향성을 가지므로 이론적으로는 함수 반환값으로 입력값을 알 수 없어야 한다.

근데 해시 충돌이 일어나는 가능성이 존재한다. (당근.. 해시값이 뭐 무에서 유를 창조한 그런 값이 아니므로)

그 해시 충돌에 대한 성질을 말한다. 여기엔 두가지가 있다.

 

* 강한 충돌회피성

H(X) = H(Y) 인 서로 다른 임의의 두 입력 X, Y 를 찾는 것은 계산적으로 어려워야 한다.

 

* 약한 충돌회피성

X가 주어졌을 때 H(X) = H(Y) 인 X!=Y 것을 찾는 것은 계산적으로 어려워야 한다.

 

두개 차이는 값이 하나 주어지냐 안주어지냐 그 차이인듯.

하나 주어졌는데 충돌 찾기어려우면 약한 충돌회피, 둘다 모르는데 찾기 어려우면 강한 충돌회피