[암호학] 해시함수 Hash Function

Hash Function은 우리말로 해시함수 또는 해쉬함수라고도 하는데 저는 해시함수라고 부르겠습니다. (암호학 수업시절 "해쉬가 아니라 해시라고!" 라는 말이 머리에 박혀있어서 저도 이제는 해시가 아니면 거슬리긴 합니다ㅎㅎ)
 
해시함수는 임의의 입력값에 대해 고정된 길이의 값을 출력하는 함수입니다. (해시함수를 왜 사용하는지는 아래에서 다루겠습니다.)
 
예를 들어, MD5(Messsage Digest Algorithm 5)라는 해시함수는 임의의 길이의 입력 데이터를 받아 128비트(16바이트)의 고정된 길이의 해시 값을 생성합니다. 
 
마지막으로, 항상 같은 입력값에 대해 같은 출력값을 생성합니다

저는 아래 온라인 사이트에서 MD5로 해시 값을 생성해 보겠습니다. 프로그램을 이용한 해싱방법은 맨 아래에서 다루겠습니다.
https://semalt.tools/ko/md5-hash-generator

MD5 해시 생성기

 

짧은 길이의 입력 값이 주어졌을 때

입력값: ABCDEF

MD5 해시값: 8827a41122a5028b9808c7bf84b9fcf6

 

---

긴 길이의 입력값이 주어졌을 때

입력값:
ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF
ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF
ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF
ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF

MD5 해시값: f3fab029dc4bdfcc9656a83483e8b156

 
입력 값에 따라 MD5 해시 값은 변하지만 그 길이는 변함이 없습니다. 즉, 해시함수는 입력값이 아무리 크던 작던 항상 출력되는 길이는 고정입니다.

---

이제부터 저희는 일반적인 해시함수가 아닌 암호학적 해시함수를 가정하고 설명하겠습니다. 

 
해시함수는 데이터나 파일이 변조되지 않았는지 확인하고 싶을 때 사용됩니다. 예를 들어, 파일의 해시 값을 계산하여 원본 파일과 비교하여 변조 여부를 확인할 수 있습니다. 즉, 데이터의 변조여부를 체크할 때 사용됩니다.

일방향성 (One-way): 해시 함수는 입력값에서 출력값을 계산하는 것은 간단하지만, 출력값에서 입력값을 계산하는 것은 매우 어려워야 합니다. 즉, 해시 함수는 단방향입니다. 그래서 해시함수 같은 것을 one-way function 이라고도 합니다. 이와 대비되는 것이 바로 암/복호화입니다. 입력값과 암호화 함수를 이용해 출력값을 얻을 수 있고 출력값과 복호화 함수를 이용하여 다시 원본값(입력값)을 복원할 수 있습니다. 하지만 해시 값을 통해 원본 데이터를 역으로 추론하는 것은 매우 어렵습니다.

충돌 저항성 (Collision Resistance): 충돌은 서로 다른 입력값에 대해 동일한 해시값이 생성되는 상황을 말합니다.
왜 이런 일이 발생할 수 있을까요? 아까 어떠한 길이의 입력에 대해서도 해시함수는 고정된 길이의 출력값을 가진다고 했습니다. 지금 상황은 입력값의 범위는 무한한데 출력값은 10 ~ 99 까지만 있는 상황과 동일합니다. 어떤 입력값이 주어지든 10 ~ 99 값 중 하나를 출력해줘야 합니다. 이를 수학적으로는 비둘기집의 원리라고 합니다. 중학생도 당연하다고 생각하는 만큼 당연한 법칙이라 한번 읽어보시길 추천합니다.

즉, 두 개의 다른 입력값이 동일한 해시 값을 가질 확률은 매우 낮아야 합니다.

 

여기서 문제를 하나 내겠습니다.

생일 문제(birthday problem) 또는 생일 역설 (birthday paradox)이라고도 하는 확률적 문제입니다.

비둘기 집의 원리에 의하면, 1년이 365일이라고 가정한다면 366명이 모여있을 때 생일이 같은 사람이 반드시(100% 확률로) 1쌍 이상 존재합니다.

 

그렇다면 몇 명이 모여야 생일이 같은 사람이 1쌍 이상일 확률이 50% 정도 될까요?

 

 

답: 23명

 

사람이 n명 있을 때 생일이 같은 사람이 한 쌍이상 있을 확률은 1에서 그 사람들이 모두 생일이 다를 확률을 빼면 됩니다. 즉, 확률은 1 - (364/365)*(363/365)*…*(365-n+1/365) 입니다. 

 

아마 단순하게 생각했을 때는 "한 100명은 모여야하는거 아니야?" 라고 생각할 수 있는데 수학적으론 23명입니다. 생일 역설 (birthday paradox)이라고 부르는 이유가 바로 이것입니다. 참고로 70명 정도 모이면 확률이 90%를 넘어갑니다.

 

이 이야기를 왜 하는 것이냐면 출력이 n비트인 해시 함수는 출력 값의 경우의 수가 2^n 개입니다. 그런데 실제로는 그보다 훨씬 적은 2^(n/2) 개 정도 선에서 충분히 해시 충돌을 찾을 수 있습니다. 이를 생일공격이라고 합니다.

역상 저항성 (Preimage Resistance): 해시 값으로부터 원본 입력 값을 찾는 것은 불가능에 가까워야 합니다. 즉, 해시 값만을 가지고서는 원본 데이터를 복원하는 것이 어렵습니다.

키 없음 (Keyless): 일반적인 해시 함수는 별도의 키를 사용하지 않습니다. 하지만 일부 해시 함수들은 키를 사용하여 더 강력한 보안을 제공하기도 합니다.

---

OpenSSL을 이용한 해시함수 사용법

저는 example.txt 파일을 하나 만들어서 아무 내용이나 적겠습니다. 이후 아래 명령어를 실행시키겠습니다. SHA256 해시함수를 사용합니다.
 

$ openssl dgst -sha256 example.txt

파일 해싱결과

Windows에서 해시함수 사용법

 
일반적으로 Windows에는 OpenSSL이 설치되어있지 않습니다. 그런데 잘 몰라서 그렇지 Windows도 웬만한 기능은 다 제공합니다. 저는 새롭게 example.txt 파일을 만들었습니다. 그리고 Windows PowerShell을 켜고 아래 명령어를 입력해 줍니다.

PS> certutil -hashfile example.txt sha256

파일 해싱결과