[보안] Hash Function

1. Hash Function

1) 특징

• compression : 어떤 길이의 input에 대해서도 고정된 길이의 output 이 생성됨

• Efficiency : h(x)를 통해 y값을 계산하는 것이 쉬움

• One-way : hx)=y의 역함수를 구할 수 없음. 즉 y로부터 x를 계산하는 함수를 구할 수 없음

• Weak collision resistanc(약한 충돌 저항성) : h(x)와 x를 알고있을 때, 동일한 해시값을 가지는 다른 입력데이터를 찾을 가능성이 매우 낮은 것.

• Strong collision resistance(강한 충돌 저항성) : 동일한 해시값을 가지는 서로 다른 입력데이터를 찾을 가능성이 거의 없는 것

  따라서 약한 충돌 저항성을 가지게 되면 해커입장에서 다른 입력 데이터들을 수동으로 넣어보며 공격할 가능성이 있긴함.

  해시함수는 기본적으로 "약한 충돌 저항성"과 "강한 충돌 저항성"을 모두 가짐

  2) Pre-Birthday problem

  h(x) = y값으로부터 x를 알아내는 것은 어려우나 같은 해시값을 가지는 h(x)=h(z)인 z를 구하는 것이 불가능한 것은 아님을 보여주는 사례.

  Q) 방안에 N명이 존재. 방안에 생일이 같은 누군가가 존재할 확률이 50%이상이기 위한 N의 최소값은?

  • (1) N명의 생일이 모두 다를 확률
    = 1 x $\frac{364}{365}$ x $\frac{363}{365}$ x $\dots$ x $\frac{365-N+1}{365}$
  • (2) N명 중 생일이 같은 사람이 존재 할 확률
    = 1 - 1 x $\frac{364}{365}$ x $\frac{363}{365}$ x $\dots$ x $\frac{365-N+1}{365}$
  • (3) N명 중 생일이 같은 사람이 존재 할 확률이 50% 이상이 되기 위한 N의 최솟값? N =23

  => 23명만 모여도 그 중 생일이 같은 사람이 존재 할 확률이 절반 이상이다. 이를 통해 Hash function에서 h(x)=h(y)인 x와 y를 찾는 것이 가능함(해쉬 함수의 취약점)을 보여준다.

  => hash함수의 output이 N bit라면, $2^N$ 개의 hash 값이 가능하다. 이때 공격자는 약 $2^{2/N}$ 번의 random values를 가지고 collision을 찾아낼 확률이 높아진다. 반면 대칭키 암호화의 경우 N bit 대칭키를 사용하게 되면 공격자는 $2^N$의 시도를 통해서만 뚫을 수 있다. (전수 조사)

  => hash나 symmetric key를 사용 할 때 모두 충분한 길이의 n bit를 사용하여아함

3) Hash function 예시

• MD5
  : 128 bit output, collisions 발생하기 쉬움
  => $2^{64}$ 번의 대입을 통해 충돌을 찾을 수 있어서 현대에는 잘 사용되지 않음
• SHA-1
  : 160 bit out put
  => 2017년에 뚫림
• SHA-2 family
  : SHA-224, SHA-256, SHA-384, SHA-512
• SHA-3 family
  : SHA3-224, SHA3-256, SHA3-384, SHA3-512

4) Application of Hash funtion

• MAC (message authentication code) : 메시지의 변조성(integrity)를 확인하는 용도
• online bidding system : 입찰 후 본인의 입찰가를 변경하지 못하도록 각각의 입찰가를 해쉬하여 저장
• spam reduction
  : spam을 없앨 수는 없으나 공격자가 더 많은 노력(CPU cycles)를 소요하여 공격하도록 함

  M (message)
  R(공격자가 찾아야할 값)
  T (현재 시간)
  R값에 따라 H(M,R,T)의 앞 N bit가 '0'으로 설정된다.
  => 수신자 : N개의 '0'으로 시작되는 메일만 받도록하며 1번의 Hash만 필요로함
  => 공격자 : N개의 '0'으로 시작되는 R을 찾기위해 $2^N$번의 Hash연산을 필요로함