Chapter 11. Cryptographic Hash Function

박병준·2022년 5월 26일

컴퓨터 보안

목록 보기

11/14

가변 길이의 데이터 블록을 input으로 받아 고정된 길이의 hash 값을 출력한다.
데이터 압축의 역할로 사용할 수 있음
가변 길이를 입력받는다고는 하나, 어느 정도 정해져 있어서 보통 padding으로 채움

h = H(M)
M을 통해 h를 구하기는 쉬워야 하지만, h를 안다고 M을 쉽게 구할 수 있으면 안 된다. -> one-way property

두 가지 요구 조건을 만족해야 한다.

변조된 데이터에 대해 hash 값을 쉽게 구할 수 있어 문제가 된다.

MAC = keyed hash function

key가 없는 공격자는 meet-in-the-middle attack을 못 한다.

결과가 같다면 무결성(Integrity)을 확인할 수 있다.
또한 같은 hash 값이 출력된다는 것은 송신자가 key를 가지고 있다는 것으로 Authentication할 수 있다.

MAC과 역할이 비슷하다.

hash 값에 서명(private key)

Authentication & Integrity & Nonrepudation 가능하다.
메시지 변조 실질적으로 어렵다.

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

사용자의 아이디(예: aa) 비밀번호(예: abc)를 저장할 때,
a - abc, b - bcd 이런식으로 저장하는 것이 아니라
a - H(abc), b - H(bcd) 이런 식으로 비밀번호의 hash 값만을 저장한다.

필요한 성질

One-way property
hash 값을 알아도, 그 값을 출력하게한 input 값(비밀번호)을 알게 하면 안 된다.
collision-free property
서로 다른 두 개의 password가 같은 hash 값이 나오는 것을 collision이라고 하는데, 그러지 않도록 만들어야 한다.

위 성질을 지키면 안전한가?

one-way로 여러 비밀번호들을 입력해보면서 hash 값을 알아내야 한다.
Dictionary attack ( = offline dictionary attack)
비밀번호를 입력해보고 나오는 값을 dictionary 형식으로 쭉 기록한다.
순서대로(aaaa~zzzz) 다 입력해보지 않고, 사람들이 많이 쓰는 비밀번호부터 입력해나가면 생각보다 빨리 찾을 수 있음
위 공격을 막기 위해 salt라는 값을 이용한다.
hash가 salt와 비밀번호 두 개를 넣어서 값을 출력하는 것
공격자는 먼저 salt 값을 찾아야 하는데, 그러려면 같은 비밀번호를 여러 개의 값(salt)을 넣어보며 다 찾아봐야 한다.
이렇게 하면 위의 방법보다 훨씬 많은 리소스를 사용해야 한다.

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