Hash Function

$h = H(M)$

일반적인 Hash Function의 경우

• Large input domain -> Small fixed output
• Well distributed: $P(H(x)=i) \approx \frac{1}{N}$

cryptographic hash function에 충분하지 않음.

그렇기 때문에 cryptographic에 맞게 특성을 추가해 줘야한다.

Cryptographic Hash Function

• Cryptographic Hash Function(암호화 해시 함수)는 해시 함수의 일종으로, 해시 값으로부터 원래의 입력값과의 관계를 찾기 어려운 성질을 가지는 경우를 의미한다.
  
  

추가된 성질

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

• $h = H(x)$가 주어졌을 때, $x$를 찾기 어려워야 한다.

2. Weak Collision resistance (약한 충돌 저항성)

• $h = H(x)$가 주어졌을 때, $H(x')=h$를 만족하는 어떤 $x'$를 찾기 어려워야 한다

3. Strong Collision resistance (강한 충돌 저항성)

• $H(x)=H(y)$를 만족하는 $(x,y)$를 찾기 어려워야 한다.

공격 방식

역상 공격(Preimage attack)

1. 제 1 역상 공격(First Preimage attack)

   해시값이 주어져 있을 때, 그 해시값을 출력하는 입력값을 찾는다.

2. 제 2 역상 공격(Second Preimage attack)

   입력값이 주어져 있을 때, 그 입력과 같은 해시값을 출력하는 다른 입력값을 찾는다.

제 2역상 공격은 제 1 역상 공격에서 원본 메시지까지 주어져 있는 경우이다.

충돌 공격(Collision attack)

1. 충돌 공격(Collision attack)
2. 선정 접두어 충돌 공격(Chosen-prefix collision attack)
   
   

역상 공격은 충돌 공격과는 달리 해시 함수의 출력값이 고정되어 있고, 해시 함수의 출력값이 같은 새로운 입력값을 찾는 공격이다.

입력값과 해시 값에 대해서, 해시 값을 망가뜨리지 않으면서 입력값을 수정하는 공격에 대해 안전해야 한다. 원래 입력값을 의도적으로 손상시키지 않았는지에 대한 검증 장치로 사용할 수 있다.

Hash Chain

• 암호화 해시 함수 H의 연속적인 사용을 의미한다.
• 예를 들면, $h(h(h(h(x))))$ or $h^4(x)$.
• 이 함수 값의 변화를 통해, 의도적 손상이 있는지 검증할 수 있다.

응용

• Binary Hash Chain (바이너리 해시 체인)