해시 함수란 (22.11.02 TIL)

  <인크립션 실용주의 암호화> 를 읽던 중 해시 함수의 개념 정리 하는 겸 쓰는 오늘의 TIL!

---

 해시 함수는 임의의 길이를 가진 데이터를 '특정 길이의 데이터'로 변환하는 과정을 의미한다. 블록 암호화는 원래 값을 각 블록으로 나눠 전체 데이터를 온전히 (원본 데이터와 같거나 더 큰 크기로) 암호화했다. 하지만 해시 함수는 원본 데이터 값이 얼만큼 길든 상관없이 정해진 길이로 줄여서 변환해 버린다. 원본 일부가 손실되는 '압축'과 비슷한 형태라고 생각하면 된다.

해시 함수의 개념 모델

고정된 해시 값을 출력하는 해시 함수

 위 그림에서 입력 값(M)의 길이는 상관없지만, 출력되는 해시 값(H)의 길이는 고정한다. 암호화 알고리즘과 달리 해시 함수에는 키가 없다. 그 대신에 해시 값의 길이가 암호화 알고리즘에서 키 길이와 동일한 역할을 한다.

 해시 함수와 블록 암호화 알고리즘은 난수처럼 보이는 결과물을 생성한다는 공통점이 있다. 또 둘 다 입력 값의 비트 하나라도 바뀌면 결과물이 반 이상 바뀌는 '쇄도 효과'를 갖도록 설계되었다. 하지만 블록 암호화 알고리즘이 암호화된 결과물을 복호화할 수 없는 것과 달리, 해시 함수는 암호화된 결과 값을 복호화할 수 없다. 이는 해시 함수의 '일정한 길이로 일종의 압축을 수행하는' 특성 때문이다. 해시 함수의 입력과 출력은 일대일로 유일한 쌍을 이루지 않기 때문에 되돌아갈 수 없다. 알고리즘의 안전성과는 별개로 암호화된 결과 값에 원본 데이터 전부를 복원할 수 있는 정보가 없어서 애초에 복호화를 할 수 없는 것이다. 복원할 수 있는 정보가 없는 이유는 길이가 고정된 결과물로 변환되는 과정에서 원본 데이터의 정보 일부가 사라지므로 복호화를 하려고 해도 할 수 없기 때문이다. 

 해시 함수의 3가지 특성은 아래와 같다.

1. 역상 저항성

역상 저항성

 역상 저항성은 해시 값이 주어졌을 때, 그 해시 값을 생성하는 입력값을 알아내기가 불가능하다는 특성이다. 즉, 주어진 해시 값이 H가 있다면, 그 해시 값을 생성하는 (H=Hash(M)) M 을 계산하기가 어려워야 한다.

2. 제2 역상 저항성

제2 역상 저항성

 제2 역상 저항성은 어떤 입력값과 동일한 해시 값 (결과값)을 가지는 다른 입력 값을 찾을 수 없어야 한다는 특성이다. 즉, 어떤 입력값 M1 에 대해 M1 != M2 이며, Hash(M1) = Hash(M2) 인 M2 를 찾기가 어려워야 한다.

3. 충돌 저항성

충돌 저항성

 충돌 저항성은 해시 값 (결과값)이 같은 입력 값 두 개를 찾을 수 없다는 특성이다. 역상 저항성과 비슷해 보이지만 의미는 다르다. 충돌 저항성은 해시 값이 무엇이든 (그 값을 알든 모르든) 특정하게 같은 해시 값을 생성하는 값 두 개를 찾는 과정이 문제이고, 역상 저항성은 해시 값을 알고 있을 때 원래 값을 찾아내는 것이 문제이다.

 보통 비밀번호를 해시 함수로 암호화하면 로그인을 할 때 입력하는 비밀번호의 해시 값과 저장된 해시 값을 비교하여 사용자를 확인한다. 역상 저항성은 비밀번호의 해시 값이 저장된 데이터 베이스가 공격을 당해 해시 값이 유출되었을 때 의미가 있다. 다른 사용자가 유출된 해시 값으로 해당 서비스에 로그인할 수 있는 것도 문제이지만, 해시 값의 원본 값인 비밀번호만 알면 동일한 비밀번호를 사용하는 다른 서비스까지도 위험할 수 있다는 것이 더 큰 문제이다. 그래서 해시 함수로 비밀번호를 암호화할 때 일반 대칭 키 암호화 알고리즘보다 키 길이를 두 배로 설정하라고 권고한다.

 

 

참고 : 

인크립션: 실용주의 암호화: 키 길이의 중요성과 해시 함수의 안전성 - 3