[암호] 해시 함수(hash function), 일방향 함수(one-way function)

보안을 하다보면 많이 접하게 되는 해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)에 대하여 알아보자

해시 함수는 임의의 길이의 데이터를 임의의 고정된 길이의 데이터로 매핑하는 함수이다.

예를 들어 큰 수를 10으로 나눈 나머지를 구하는 함수도 해시 함수라고 할 수 있다.

10001 % 10 = 1

1000000002 % 10 = 2

5 % 10 = 5

1500 % 10 = 0

임의의 큰 수를 입력해도 결과는 항상 1자리수로 나오기 때문이다.

여기서 10으로 나눈 수(해시 함수의 결과)를 해시 값, 해시 코드 등으로 불린다.

조금 더 자세히 설명하기위해 일방향 함수(one-way function)을 먼저 설명하겠다.

일방향 함수 즉 한쪽으로는 쉽고 반때쪽으로 어려운 함수이다.

위에서 예로든 % 가 좋은 예가 된다. 

x % 10 = y        

x를 알떄 y를 구하는건 쉽다. x = 11 이면 y=1, x = 105 이면 y = 5

y를 알때 x를 구하는건 쉬지 않다. y = 1 이면 x = 1, 11, 111, 1111, 11111 등등 중 하나.

반면 + 1 의 경우는 일방향 함수가 아니다.

x + 1 = y

x를 알때 y를 구하는건 쉽다. x = 1 이면 y = 2

y를 알때 x를 구하는것 또한 쉽다. y = 1 이면 x = 0

해시함수는 이러한 일방향 함수에서 몇가지 특성이 추가된다

위에서 예로든 % 의 경우 x가 1, 11, 111, 1111 모두 % 10 을 하면 1 이 된다. 

이를 충돌(collision)이라 한다.

해시함수는 입력이 다르지만 해시 값이 같을 수 있다. 해시 함수는 큰 데이터를 작게 만드는 것이기 때문에 충돌은 피할 수 없다. 

다만 이 충돌을 찾기 힘들어야 한다.

%는 충돌을 찾기 쉽기 때문에 좋은 해시 함수는 아니다.

해시함수는 입렵값이 바뀌면 결과값도 크게 바뀌어야 한다.

1비트라도 달라진다면 해시값이 달라져야 하며 같은 값이 될 수도 있지만 불가능한 수준이여야 한다. 해시 입력1과 해시 입력2가 비슷하더라도 해시 결과1 해시 결과2는 많이 달라야 한다.

요약하자면

1. 일방향 함수

2. 충돌을 찾기 어려움

3. 입력이 바뀌면 결과가 크게 바뀜

이러한 특징이 왜 중요한지 잘 이해가 되지 않을수 있다.

하지만 어떻게 사용되고 있는지 본다면 더 잘 이해가 될 것이다.

로그인 비밀번호를 db에 저장할 경우 그냥 저장한다면 db 관리자는 사용자의 비밀번호를 그냥 확인 할 수 있다. 하지만 해시 함수를 이용하여 해시 값을 저장한다면 db 관리자는 해시 값은 알수 있지만 비밀번호는 알 수 없다. (one-way function + 충돌을 찾기 어려움)

데이터와 데이터의 해시 값을 수신 받았을 경우 누군가 데이터를 변조 하였을 때 해시 값을 비교 하여 데이터가 바뀐 사실을 알수있다.( 입력이 바뀌면 결과도 바뀐다. 물론 해시 값도 바꾸면 어쩔 수 없지만 그에 대한 장치는 다른 방법으로 보완한다)

비밀번호를 해시 하여 저장할때 비밀번호1과 비밀번호2가 비슷하더라도 해시 값1과 해시 값2는 많이 다르기 때문에 db 관리자는 비밀번호1과 비밀번호2가 비슷하다고 유추할 수 없다.

암호화(encrypt)와 차이도 잘 알아두었으면 좋겠다.

암호화는 기본적으로 인증된 사람만 볼수 있게 하는것이 목적이다.

그래서 인증된 사람만 암호문을 만들수 있고 인증된 사람만 복호화 할 수 있다.

반면 해시는 누구나 해시 할수 있고 누구도 해시 결과로 해시 전의 데이터를 알수 없다.

암호학적으로 유명한 해시 함수는 MD5, SHA계열의 해시 함수가 있다.