해시함수의 성질

해시함수(ex-SHA-256)는 어떤 길의 데이터가 입력되더라도 고정된 길이의 전혀 다른 결과값(해시값)을 출력하는 알고리즘이다.

해시함수가 해커의 공격으로부터 안전하다고 인정받으려면 다음 3가지 저항성(내성)을 반드시 만족해야 한다.

 

1. 역상 저항성 (Pre-image Resistance)

• 한 줄 요약: 일방향성(One-way) 보장. 결과값을 보고 원본을 역추적할 수 없어야 한다.
• 개념: 해시값 $H$가 주어졌을 때, $h(X) = H$를 만족하는 원본 데이터 $X$를 찾는 것이 계산적으로 불가능해야 한다는 성질이다.

 

2. 제2 역상 저항성 (Second Pre-image Resistance) = 약한 충돌 내성

• 한 줄 요약: 특정 원본값과 해시값이 주어진 상태에서, 정해진 원본과 똑같은 해시값을 가진 다른 입력값을 찾는 것이 불가능해야 한다.
• 개념: 특정 원본 $X1$과 그 해시값 $h(X1)$이 이미 공개된 상태에서, 동일한 해시값을 가지는 새로운 데이터 $X2$를 찾는 것이 계산적으로 불가능해야 한다는 성질이다. ($h(X1) = h(X2)$를 만족하는 $X2$ 찾기)

 

3. 충돌 저항성 (Collision Resistance) = 강한 충돌 내성

• 한 줄 요약: 임의의 쌍 매칭. 내용이 다르면서 해시값이 똑같이 나오는 데이터 2개를 아무거나 찾아내는 것도 불가능해야 한다.
• 개념: 공격자에게 주어지는 조건이 없다. 해시값이 같은 임의의 서로 다른 두 데이터 쌍($X1, X2$)을 아무거나 찾아내는 것이 계산적으로 불가능해야 한다는 성질이다.
• 특징: '생일 역설(Birthday Paradox)' 원리에 의해, 특정 타겟을 맞추는 제2 역상 저항성 공격보다 아무 쌍이나 찾는 충돌 저항성 공격이 수학적으로 훨씬 쉽다. 따라서 해시함수를 설계할 때 가장 뚫기 어려운 마지막 보루가 된다.