[컴퓨터 보안] Hash Function

Hash Function

• 가변 길이의 데이터 블록을 input으로 받아 고정된 길이의 hash 값을 출력한다.
  • 데이터 압축의 역할로 사용할 수 있음
  • 가변 길이를 입력받는다고는 하나, 어느 정도 정해져 있어서 보통 padding으로 채움 
• h = H(M)
  • M을 통해 h를 구하기는 쉬워야 하지만, h를 안다고 M을 쉽게 구할 수 있으면 안 된다. -> one-way property
• 두 가지 요구 조건을 만족해야 한다.
  • The one-way property
  • The collision-free property
    • 서로 다른 input을 넣어 같은 hash 결과를 갖는 것 -> collision
    • 이런 collision을 찾기 힘들어야 한다.
    • 즉, The collision-free property는 다른 input이 들어가면 다른 output(hash 값)이 나오는 성질을 말한다.

 

 

데이터의 무결성과 Hash

•  원인: 변조된 데이터에 대해 hash 값을 쉽게 구할 수 있음

 

 

Message Authentiction Code(MAC)

• MAC = keyed hash function
• Keyed hash function: 메시지와 key를 input으로 넣어 hash 값을 출력한다
• key가 없는 공격자는 meet-in-the-middle attack을 못 함.

 

• plaintext와 hash 값(메시지와 key를 넣은)을 전송
• 수신자는 수신한 plaintext만 다시 (같은) 알고리즘으로 돌려보고 C3와 결과가 같다면 무결성(Integrity)을 확인할 수 있다.
• 또한 같은 hash 값이 출력된다는 것은 송신자가 key를 가지고 있다는 것으로 Authentication할 수 있다.

 

 

Digital Signature

• MAC과 역할이 비슷
• hash 값에 서명(private key)
• Authentication & Integrity & Nonrepudation 가능
• 메시지 변조 실질적으로 어렵다.

• 원본 메시지에 [메시지의 hash값을 private key로 encryption(서명)한 것]을 더해 전송 

 

 

Hash Function: Password

• 사용자의 아이디(예: aa) 비밀번호(예: abc)를 저장할 때, 
  • a - abc, b - bcd 이런식으로 저장하는 것이 아니라
  • a - H(abc), b - H(bcd) 이런 식으로 비밀번호의 hash 값만을 저장한다.
• 필요한 성질: One-way & Collision-free property
  • hash 값을 알아도, 그 값을 출력하게한 input 값(비밀번호)을 알게 하면 안 된다. -> one-way property
  • 서로 다른 두 개의 password가 같은 hash 값이 나오는 것을 collision이라고 하는데, 그러지 않도록 만들어야 한다. -> collision-free
• 위 성질을 지키면 안전한가?
  • one-way로 여러 비밀번호들을 입력해보면서 hash 값을 알아내야함.
    • Dictionary attack ( = offline dictionary attack)
      • 비밀번호를 입력해보고 나오는 값을 dictionary 형식으로 쭉 기록함.
      • 순서대로(aaaa~zzzz) 다 입력해보지 않고, 사람들이 많이 쓰는 비밀번호부터 입력해나가면 생각보다 빨리 찾을 수 있음
    • 위 공격을 막기 위해 salt라는 값을 이용해 hash 함
      • hash가 salt와 비밀번호 두 개를 넣어서 값을 출력하는 것
      • 공격자는 먼저 salt 값을 찾아야 하는데, 그러려면 같은 비밀번호를 여러 개의 값(salt)을 넣어보며 다 찾아봐야 함.
      • 이렇게 하면 위의 방법보다 훨씬 많은 리소스를 사용해야 함

 

 

Preimage

• h = H(x) 에서 x는 h의 preimage이다.
• hash는 N:1 mapping이다. 즉, 여러 개의 perimage가 같은 hash 값을 갖는 구조이다.

 

Hash function의 5가지 사용

1. MAC
   • One way & Collision free 성질 필요
   • One-way -> H(D||S) = h
     • h를 안다고 S(key)를 알게 되면, 그 후 다 변조할 수 있음
   • collision free -> 변조했는데 hash 값이 같은 경우 변조 사실을 알 수 없다.
2. Digital Signature
   • collision free 성질이 필요
   • Spriv(H(D))를 하는데 D가 변조되었는데 H(D)=H(D')인 경우 사인이 같아져 문제를 파악할 수 없다.
     • 즉, A가 하나의 데이터에 대해 서명을 했는데, 서로 다른 데이터에 대한 hash 값이 같으면 A는 여러 개의 데이터에 서명한 것이 됨.
3. Password
   • One-way & Collision free 성질 필요
4. Integrity
   • Collision-free 필요
5. PRNG
   • One-way 필요
   • 진짜 random number가 아니라 pseudo random이라 seed에서 시작해서 생성해내는 것. 
     • preimage가 밝혀졌다고 seed가 밝혀지면 안 됨 

 

 

Secure Hash Algorithm(SHA)

• hash function MD4를 기반으로 만듦
• 160-bit hash 값 출력
• 깨진 적 있는 알고리즘
• 이를 보안하여(bit를 늘려서) SHA-2 나옴
  • SHA2는 bit 수만 늘린 거라 내제적인 안전성 문제가 있음
• SHA3 - 구조를 바꾼 알고리즘
  • Message Digest Size(S): 224, 256, 384, 512
  • Collision resistance: $2^{\frac{S}{2}}$

 

 

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]