Hash

Hash function의 목표

Alice가 Bob에게 M을 서명을 해서 보내려고 한다.

서명의 목적을 달성하기 위해서는 Alice가 서명한 [M]Alice와 M을 함께 보내야 한다.

{[M]Alice}Alice 하면 같은 전달 하려는 같은 M이 나오는데도 꼭 함께 보내야 한다.

 

왜냐하면 {[M]Alice}Alice했을때 나온 M이 함께 보낸 M과 같아야 Alice가 보낸것임을 알 수 있기 때문이다.

M을 안보내면 예를들어 Trudy가 [m]Trudy를 Alice인척 Bob에게 보내고

Bob은 {[m]Trudy}Alice 한 결과인 m` 이 정말 원하던 Alice의 M인지 알 방법이 없다.

(Trudy는 Alice의 private key 를 모르기 때문에 {}Alice했을 때 M이 나오도록 하는 M을 구할 방법이 없다)

 

그러므로 서명을 위해서는 꼭 암호화한 M과 원본 M을 함께 보내야 한다.

그러므로 M의 크기가 크면 클수록 중복된 내용의 크기가 커지는것 이므로 매우 비효율적이게 된다.

그래서 ([M]Alice, M) 을 보내는 대신 ([h(M)]Alice, M) 을 보낸다.

그럼 Bob은 {[h(M)]Alice}Alice 해서 h(M)을 얻고, 함께 받은 M을 h(M)해봐서 h(M)=h(M)을 비교하면 이로서 서명을 확인할 수 있다.

- ([h(M)]Alice, M) 대신 ([M]Alice, h(M)) 도 가능할 것이라고 생각했는데 ([h(M)]Alice, M)를 하는 이유는 뭘까 생각해보니 크기가 큰 M을 암호화 하는것 보다 크키가 작은 h(M)을 암호화 하는것이 Alice도 편하겠다고 생각이 들었다

 

그럼 정말 Hash function을 사용한 내용으로 검증을 하는것이 정말 안전한것인가?

분명 크기가 줄어듬으로서 정보 손실이 발생했고 h(M) = h(M`)이 존재 할 수 있다. collision 발생

 

그래서 Crypto Hash Function은 다음을 보장해야 한다.

• Compression - output length is small
  • 해쉬 결과는 작아야 한다.
• Efficiency - h(x) easy to compute for any x
  • 무엇을 해쉬해도 그 과정이 쉬워야 한다.
• One-­way - given a value y it is infeasible to find an x such that h(x) = y
  • 해쉬된 결과로 원본을 찾을 수 없어야 한다.
• Weak collision resistance - given x and h(x), infeasible to find y ≠ x such that h(y) = h(x)
  • 주어진 x 에 대해서 x의 해쉬 결과와 같은 해쉬결과를 내는 y를 찾을 수 없어야 한다. 
  • 약한 공격을 막을 수 있는 약한 보안의 hash
• Strong collision resistance - infeasible to find any x and y, with x ≠ y such that h(x) = h(y)
  
  • 그 어떤 x 에 대해서 x의 해쉬 결과와 같은 해쉬 결과를 내는 y를 찾을 수 없어야 한다.
  • 강한 공격을 막을 수 있는 강한 보안의 hash

 - Lots of collisions exist, but hard to find any 수많은 쫑이 존재해도 찾을 수는 없어야 한다.

 

Birthday paradox

23명의 사람만 모이면 이 사람들 중 생일이 같은 사람이 존재할 확률은 50%를 넘는다.

-> Hash 에도 적용됨

 

만약 h(x) 결과가 N bits면 2^N 의 다른 결과가 나올 수 있는데 

약 2^N/2 (sqrt(N))정도가 collision이 발생한다.

N bit의 키를 알아내기 위해 2^N-1회 시도해야 한다면 h(N bit)는 2^N/2 (sqrt(N))면 뚫린다

 

Crypto Hash Design

avalanche effect(쇄도 효과): 입력값이 1bit 라도 변경된다면 출력값은 절반 이상 변화되어야 한다.

block cipher design 과 유사하다

 

해쉬의 사용

HMAC(hash massage authentication code): hash + key

HMAC(M,K) = h(K ⊕ opad, h(K ⊕ ipad, M))