해시 함수

해시 함수는 길이가 제각각인 데이터를 짧은 값 하나로 줄여 주는 함수입니다. 같은 데이터를 넣으면 언제나 같은 값이 나옵니다. 그 값으로 데이터를 빨리 찾거나 내용이 바뀌었는지 가려냅니다. 쓰임에 따라 데이터를 여러 칸에 고르게 나눠 담는 쪽과 거꾸로 풀기 어렵게 만든 쪽으로 갈립니다.

상세

이 절은 해시 함수가 무엇을 받아 무엇을 내놓는지부터 봅니다. 그다음 겹침, 곧 충돌이 왜 반드시 생기는지를 자바 문자열 두 개로 확인합니다.

뒤쪽 절은 쓰임을 둘로 가릅니다. 해시테이블에서 키마다 담을 칸을 고르는 해시 함수와 비밀번호·서명에 쓰는 암호학적 해시 함수입니다. 둘은 이름이 같아도 요구하는 성질이 다릅니다.

지문에 빗대면

사람을 확인할 때 그 사람을 통째로 데려오지 않고 지문만 대조합니다. 지문은 작습니다. 같은 사람이면 늘 같습니다.

다만 이 비유는 한 군데서 어긋납니다. 지문은 사람마다 다르다고 여깁니다. 해시 함수의 값은 서로 다른 데이터끼리 겹칠 수 있습니다. 이 겹침이 아래에서 다룰 충돌입니다.

무엇을 받아 무엇을 내놓나

해시 함수의 입력은 아무 길이의 바이트열입니다. 문자열 몇 글자일 수도 있고 수 기가바이트짜리 파일일 수도 있습니다.

출력은 길이가 정해진 값 하나입니다. 이 값을 해시값이라고 부릅니다. 암호 쪽에서는 다이제스트라고도 부릅니다. 입력이 아무리 길어도 출력 길이는 함수마다 하나로 고정입니다.

flowchart TD
    A["짧은 문자열"] --> H["해시 함수"]
    B["긴 문서"] --> H
    C["큰 파일"] --> H
    H --> V["길이가 정해진 해시값"]

세 입력의 길이는 전부 다르지만 나오는 해시값의 길이는 같습니다. 길이를 맞춰 주기 때문에 해시값끼리는 빠르게 비교하고 정렬하고 저장할 수 있습니다.

해시 함수가 지키는 첫째 성질은 결정성입니다. 같은 입력에는 언제 누가 계산해도 같은 값이 나옵니다. 이 성질이 없으면 저장할 때 고른 칸과 찾을 때 고른 칸이 달라져 아무것도 못 찾습니다.

충돌은 피할 수 없다

서로 다른 두 입력이 같은 해시값을 내는 일을 해시 충돌이라고 부릅니다. 해시 함수라면 어느 것이든 충돌이 있습니다.

이유는 개수 차이입니다. 입력으로 올 수 있는 데이터는 끝없이 많습니다. 출력은 길이가 고정이라 가짓수가 정해져 있습니다. 칸보다 넣을 것이 많으면 어느 칸엔가 둘 이상이 들어갑니다. 이것을 비둘기집 원리라고 부릅니다.

자바의 문자열 해시에서 충돌을 직접 볼 수 있습니다. Java 의 hashCode() 는 문자열을 정수 하나로 바꾸는 해시 함수입니다.

"Aa".hashCode()   // 2112
"BB".hashCode()   // 2112

두 문자열은 다르지만 값이 같습니다. 이 함수는 두 글자짜리 문자열이면 앞 글자 코드에 31 을 곱하고 뒤 글자 코드를 더합니다. A·a 는 65·97 이라 65×31+97 입니다. B·B 는 66·66 이라 66×31+66 입니다. 둘 다 2112 가 됩니다.

그래서 해시 함수를 쓰는 쪽은 충돌을 없애려 하지 않습니다. 충돌이 나도 맞게 도는 방법을 붙이거나, 충돌을 찾기 어렵게 만든 함수를 고릅니다. 어느 쪽을 택하는지가 아래 두 쓰임을 가릅니다.

두 갈래의 쓰임

같은 이름 아래 요구가 다른 두 무리가 있습니다. 아래 표가 둘을 견줍니다. 그다음 소절에서 하나씩 다룹니다.

셋째 줄이 갈림의 뿌리입니다. 입력을 공격자가 고를 수 있으면 충돌을 일부러 만들어 낼 수 있습니다. 그래서 그것을 막는 성질이 따로 필요합니다.

해시테이블에서 쓰는 해시 함수

해시테이블은 키로 값을 찾는 자료구조입니다. 값을 담는 칸을 배열로 늘어놓습니다.

그 칸 하나를 버킷이라고 부릅니다. 키마다 어느 버킷에 담을지를 해시 함수가 정합니다. 키를 먼저 해시값으로 바꿉니다. 그 값을 버킷 수로 나눈 나머지가 버킷 번호입니다.

flowchart TD
    K1["키 ab"] --> V1["해시값 3105"]
    K2["키 Aa"] --> V2["해시값 2112"]
    K3["키 BB"] --> V2
    V1 --> B1["3105 % 16 → 1번 버킷"]
    V2 --> B0["2112 % 16 → 0번 버킷"]

버킷이 16개인 표에 키 셋을 넣은 그림입니다. ab 는 1번 버킷에 갑니다. 앞에서 충돌한 Aa·BB 는 해시값이 둘 다 2112 라서 둘 다 0번 버킷에 떨어집니다.

찾을 때도 같은 계산을 합니다. 버킷 번호를 바로 얻으니 배열을 훑지 않고 한 번에 찾아갑니다. 해시테이블의 조회가 평균 O(1), 곧 데이터 수와 상관없이 거의 일정한 시간인 까닭입니다.

이 쓰임에서 해시 함수에 바라는 것은 둘입니다. 하나는 빠르기입니다. 조회마다 부르니 계산이 오래 걸리면 모든 조회가 그만큼 늦어집니다.

다른 하나는 균등 분포입니다. 키들이 버킷에 고르게 흩어져야 합니다. 한 버킷에 몰리면 그 버킷 안을 하나씩 훑게 되어 조회에 시간이 더 듭니다.

충돌은 여기서 정상 동작입니다. Aa·BB 처럼 한 버킷에 키가 둘 이상 오면 충돌 해소 방법이 뒤를 받습니다.

대표적인 방법은 둘입니다. 분리 연쇄법은 같은 버킷에 키를 목록으로 매답니다. 개방 주소법은 빈 버킷을 찾아 옆으로 옮겨 갑니다.

암호학적 해시 함수

암호학적 해시 함수는 누군가 일부러 속이려 들어도 버티도록 만든 해시 함수입니다. 파일이 바뀌지 않았는지 확인하거나 비밀번호를 저장할 때 씁니다. 이런 곳에서는 해시값을 맞춘 가짜를 만들 수 있으면 확인이 무의미해집니다.

그래서 성질 셋을 요구합니다. 셋 다 「불가능」이 아니라 「계산으로 찾아내기가 현실적으로 불가능」이라는 뜻입니다.

첫째는 거꾸로 풀기를 막습니다. 둘째는 정해진 파일 하나를 똑같은 해시값의 가짜로 바꿔치기하는 일을 막습니다. 셋째는 가장 센 요구입니다. 공격자가 두 입력을 둘 다 마음대로 고를 수 있어도 겹치는 쌍을 못 찾아야 합니다.

충돌 저항성에는 출력 길이로 정해지는 한계가 있습니다. 생일 문제가 그 한계를 보여 줍니다. 사람 23명만 모여도 그중 생일이 같은 두 사람이 있을 확률이 절반을 넘습니다. 두 사람씩 짝을 짓는 가짓수가 사람 수의 제곱에 가깝게 늘어나기 때문입니다.

해시값에도 같은 일이 생깁니다. 출력이 n 비트면 나올 수 있는 값은 2의 n 제곱 가지입니다. 그런데 입력을 2의 n/2 제곱 개쯤만 해시해 봐도 겹치는 쌍이 나올 가능성이 커집니다.

곧 n 비트 출력이라도 충돌 찾기는 n/2 비트짜리 수고로 끝납니다. 출력이 긴 함수를 고르는 이유가 여기 있습니다.

또 하나 바라는 것이 눈사태 효과입니다. 입력을 한 비트만 바꿔도 출력의 비트가 절반쯤 바뀌어야 합니다. 비슷한 입력이 비슷한 출력을 내면 출력을 보고 입력을 짐작할 실마리가 생깁니다.

널리 쓰는 것은 SHA-256(Secure Hash Algorithm 256)입니다. 이름의 256 이 출력 길이, 곧 256 비트입니다. 예전에 많이 쓰던 MD5(Message-Digest algorithm 5)와 SHA-1(Secure Hash Algorithm 1)은 충돌을 만드는 방법이 알려져 있습니다. 그래서 서명이나 무결성 확인처럼 속임을 막아야 하는 곳에는 쓰지 않습니다.

비밀번호를 해시로 저장할 때

서버는 비밀번호를 그대로 저장하지 않고 해시값을 저장합니다. 데이터베이스가 털려도 공격자가 얻는 것은 해시값입니다. 역상 저항성 때문에 거기서 비밀번호로 곧장 돌아가지 못합니다.

해시만 해서는 모자랍니다. 같은 비밀번호는 같은 해시값을 냅니다. 그래서 흔한 비밀번호의 해시값을 미리 계산해 둔 표가 있으면 털린 해시값을 한꺼번에 맞춰 볼 수 있습니다. 그런 표를 레인보우 테이블이라고 부릅니다.

이 표를 막으려고 사용자마다 다른 임의 값을 비밀번호에 섞어 해시합니다. 그 임의 값이 솔트입니다. 솔트가 다르면 같은 비밀번호도 다른 해시값을 냅니다. 미리 만든 표가 더는 맞지 않습니다.

sequenceDiagram
    participant 사용자
    participant 서버
    participant 저장소
    사용자->>서버: 가입 · 비밀번호
    서버->>서버: 솔트를 새로 뽑아 비밀번호와 함께 해시
    서버->>저장소: 솔트와 해시값 저장
    사용자->>서버: 로그인 · 비밀번호
    서버->>저장소: 솔트와 해시값 꺼냄
    서버->>서버: 같은 솔트로 다시 해시해 견줌

가입 때 한 계산을 로그인 때 한 번 더 합니다. 저장해 둔 솔트를 꺼내 같은 방식으로 해시합니다. 두 해시값이 같으면 같은 비밀번호로 봅니다. 서버는 비밀번호 원문을 한 번도 저장하지 않습니다.

빠르기도 여기서는 약점이 됩니다. 해시테이블에서는 빠를수록 조회가 빨라집니다. 비밀번호에서는 공격자도 후보를 그만큼 빨리 대입해 볼 수 있습니다.

그래서 일부러 계산이 오래 걸리게 만든 비밀번호 해싱 함수를 씁니다. 계산을 수없이 되풀이하거나 메모리를 많이 쓰게 해서 한 번 맞춰 보는 비용을 올립니다. bcrypt · scrypt · Argon2 · PBKDF2(Password-Based Key Derivation Function 2)가 이 무리입니다.

해시는 암호화가 아니다

암호화는 키가 있으면 원래 데이터로 되돌립니다. 되돌리는 것이 목적입니다.

해시 함수에는 키가 없고 되돌리는 방법도 없습니다. 긴 입력을 짧게 줄이는 순간 정보가 버려지기 때문입니다. 그래서 「해시를 복호화한다」는 말은 성립하지 않습니다. 할 수 있는 것은 후보를 해시해 보고 값이 같은지 맞춰 보는 것뿐입니다.

해시가 원문을 지켜 주는 힘도 여기서 옵니다. 되돌릴 수 없으니 해시값만 흘러도 원문이 드러나지 않습니다. 대신 원문이 필요한 곳에는 해시를 쓸 수 없습니다.

복잡도

해시 함수 한 번의 계산은 대개 입력을 앞에서부터 한 번 훑습니다. 그래서 시간은 입력 길이 n 에 비례하는 O(n) 입니다. 출력 길이는 고정이라 쓰는 공간은 입력 길이와 상관없이 일정합니다.

해시테이블 조회가 O(1) 이라는 말은 키 길이를 짧고 일정하다고 보고 센 것입니다. 키가 긴 문자열이면 해시 계산에 그 길이만큼 시간이 듭니다.

비밀번호 해싱은 이 비용을 일부러 키웁니다. 되풀이 횟수를 늘리면 한 번 계산하는 시간이 그만큼 늡니다. 공격자가 후보 하나를 맞춰 보는 시간도 같이 늘어납니다.

쓸 때와 안 쓸 때

아래 표는 하려는 일마다 해시 함수가 맞는지를 가립니다.

마지막 두 줄이 해시 함수를 쓸 때 가장 자주 헷갈리는 대목입니다. 값이 다르면 입력이 다른 것이 확실합니다. 값이 같으면 입력이 같을 가능성이 높을 뿐입니다.

관련 항목

해시 함수가 키를 흩는 자료구조

해시테이블 · 해시 인덱스 · 블룸 필터 · 일관성 해싱 · 샤딩 · 버킷 · 해시 링

해시 충돌을 뒤처리하는 방법

충돌 해소 · 분리 연쇄법 · 개방 주소법 · 선형 탐사 · 이중 해싱 · 해시 충돌

암호학적 해시 함수가 지키는 성질

역상 저항성 · 제2 역상 저항성 · 충돌 저항성 · 눈사태 효과 · 균등 분포 · 생일 문제

이것을 구현한 해시 알고리즘

SHA-256 · SHA-1 · MD5 · SHA-3 · BLAKE2 · MurmurHash · xxHash · CRC

해시 함수로 지키는 보안 기법

솔트 · 비밀번호 해싱 · 키 유도 함수 · bcrypt · scrypt · Argon2 · PBKDF2 · 메시지 인증 코드 · 전자 서명 · 무결성

해시 함수를 노리는 공격

레인보우 테이블 · 사전 공격 · 무차별 대입 공격 · 생일 공격 · 해시 플러딩

해시 함수와 헷갈리는 이웃

암호화 · 인코딩 · 체크섬 · 난수 생성기

해시 함수가 내놓는 값을 가리키는 다른 이름

해시값 · 다이제스트 · 핑거프린트