해시 충돌
해시 충돌은 서로 다른 두 입력이 같은 해시값을 받는 일입니다. 해시 함수를 쓰는 곳에서는 어디서나 일어나고 없앨 수 없습니다. 키로 값을 찾는 표에서는 찾는 속도를 깎습니다. 값만 보고 원본이 같은지 판정하는 곳에서는 다른 것을 같다고 말하게 만듭니다.
쉽고 빠른 이해
무슨 일이 일어나는가 — 서로 다른 두 데이터가 해시 함수를 지나 똑같은 값 하나를 받는 일입니다. 내용이 다른 두 파일이 같은 해시값을 받으면, 값만 보고 판정하는 쪽은 둘을 같은 파일로 봅니다.
왜 없앨 수 없나 — 입력으로 올 수 있는 데이터는 끝이 없습니다. 나올 수 있는 해시값은 가짓수가 정해져 있습니다. 넣을 것이 값의 가짓수보다 많으면 어느 값엔가 둘 이상이 몰립니다.
어떻게 도나
- 서로 다른 두 데이터를 해시 함수에 넣습니다
- 두 데이터가 같은 해시값을 받습니다
- 해시값만 보는 쪽은 둘을 구분하지 못합니다
무엇이 나빠지나 — 키로 값을 찾는 표에서는 두 키가 표의 같은 칸으로 가 찾는 일이 느려집니다. 표에서는 해시값이 겹치지 않아도 칸으로 줄이는 동안 또 겹칩니다. 값을 대조해 원본이 같은지 확인하는 곳에서는 가짜가 진짜로 통과합니다.
상세
학교 사물함이 백 개인데 학생이 천 명이라고 해 봅시다. 이름을 어떤 규칙으로 번호로 바꾸든 같은 번호를 받는 학생이 반드시 생깁니다. 규칙을 잘 고르면 한 사물함에 몰리는 인원은 줄지만 겹침 자체는 남습니다.
해시 충돌은 서로 다른 두 입력이 같은 해시값을 받는 일입니다. 해시 함수는 길이가 제각각인 데이터를 받아 길이가 정해진 값 하나로 바꾸는 함수입니다. 그 결과로 나온 값이 해시값입니다. 해시값은 원본을 대신해 비교하고 저장하는 데 쓰이므로, 값이 같아진 두 입력은 해시값만 보는 쪽에서 구분되지 않습니다.
왜 반드시 생기나
이유는 개수 차이 하나입니다. 입력으로 올 수 있는 데이터에는 끝이 없습니다. 해시값은 길이가 고정이라 나올 수 있는 가짓수가 정해져 있습니다.
flowchart TD
subgraph IN["입력 · 끝이 없다"]
I1["파일 ㄱ"]
I2["파일 ㄴ"]
I3["파일 ㄷ"]
I4["… 나머지 전부"]
end
subgraph OUT["나올 수 있는 해시값 · 가짓수가 정해져 있다"]
V1["값 1"]
V2["값 2"]
V3["값 3"]
end
I1 --> V1
I2 --> V2
I3 --> V2
I4 --> V3
넣을 것이 나올 수 있는 값의 가짓수보다 많으면 어느 값엔가 둘 이상이 몰립니다. 이것이 비둘기집 원리입니다. 비둘기 열 마리를 집 아홉 개에 넣으면 두 마리가 같은 집을 쓰게 된다는 이야기에서 온 이름입니다.
겹침은 생각보다 이르게 찾아옵니다. 나올 수 있는 해시값이 백만 가지여도, 서로 다른 입력을 천이백 개쯤 모으면 그중 둘이 같은 값을 받을 확률이 절반을 넘습니다. 백만 개를 다 채워야 겹치는 것이 아닙니다. 이 셈이 생일 문제입니다.
충돌은 한 층 더 아래에서도 납니다. 해시값을 그대로 쓰는 곳은 드뭅니다. 대개는 표에 늘어놓은 칸 중 어느 칸에 담을지를 정하는 데 씁니다. 칸이 여덟 개라면 해시값을 8로 나눈 나머지를 칸 번호로 씁니다.
15 % 8 # 7
23 % 8 # 7
다른 해시값 둘이 같은 7번 칸을 받았습니다. 해시값이 겹치지 않아도 칸으로 줄이는 동안 또 겹칩니다.
flowchart TD
K1["키 ㄱ"] -->|해시 함수| V1["해시값 15"]
K2["키 ㄴ"] -->|해시 함수| V2["해시값 23"]
V1 -->|8 로 나눈 나머지| S
V2 -->|8 로 나눈 나머지| S
S["7번 칸"]
그래서 충돌은 해시 함수를 잘못 만들어서 생기는 것이 아닙니다. 어떤 해시 함수를 쓰든 있습니다.
키로 값을 찾는 표에서는 속도가 깎인다
해시테이블은 값을 담을 칸을 여러 개 늘어놓고 키마다 갈 칸을 해시값으로 정하는 자료구조입니다. 그 칸 하나가 버킷입니다. 칸을 곧바로 찍어 주기 때문에 키 하나를 찾는 시간이 담긴 개수와 상관없이 일정합니다.
충돌이 나면 그 전제가 흔들립니다. 두 키가 같은 칸을 받으면 칸 하나에 둘이 들어갑니다. 찾을 때는 그 칸 안에서 어느 쪽이 맞는 키인지 하나씩 대조해야 합니다.
한 칸에 쌓인 개수만큼 대조가 늘어납니다. 모든 키가 한 칸으로 몰리면 표를 쓰는 값이 사라져, 목록을 처음부터 끝까지 훑는 것과 시간이 같아집니다.
flowchart TD
subgraph EVEN["고르게 퍼진 표 · 대조 한 번"]
E0["0번 칸"] --> E0K["키 ㄱ"]
E1["1번 칸"] --> E1K["키 ㄴ"]
E2["2번 칸"] --> E2K["키 ㄷ"]
end
subgraph SKEW["한 칸으로 몰린 표 · 대조 세 번"]
S0["0번 칸"]
S1["1번 칸"] --> S1A["키 ㄱ"] --> S1B["키 ㄴ"] --> S1C["키 ㄷ"]
S2["2번 칸"]
end
같은 칸에 든 것을 뒤처리하는 일을 충돌 해소라고 합니다. 방법은 크게 둘입니다 — 칸 안에 목록을 매다는 분리 연쇄법, 빈 칸을 찾아 옮겨 담는 개방 주소법.
바깥에서 키를 넣는 서비스라면 이 몰림을 누가 일부러 만들 수도 있습니다. 같은 칸으로 몰리는 키를 골라 계속 보내면 표가 느려집니다. 그 표를 쓰는 요청 처리가 통째로 밀립니다.
값을 대조하는 곳에서는 신뢰가 깨진다
해시값은 원본 대신 들고 다니는 짧은 표식으로도 쓰입니다. 파일을 받고 나서 해시값이 게시된 값과 같은지 보는 무결성 확인이 그렇습니다. 문서에 서명할 때 문서 전체가 아니라 해시값에 서명하는 전자 서명도 그렇습니다.
이 쓰임은 「해시값이 같으면 원본도 같다」를 믿고 서 있습니다. 충돌을 사람이 원하는 대로 만들어 낼 수 있다면 그 믿음이 깨집니다. 정상 문서와 해시값이 같은 위조 문서를 지어내면, 정상 문서에 받아 둔 서명이 위조 문서에도 그대로 들어맞습니다.
sequenceDiagram
participant S as 서명자
participant A as 공격자
participant V as 검증하는 쪽
S->>A: 정상 문서 + 그 해시값에 한 서명
A->>A: 해시값이 같은 위조 문서를 지어낸다
A->>V: 위조 문서 + 서명자의 서명
Note over A,V: 서명은 문서가 아니라 해시값에 걸려 있다
V-->>A: 해시값이 같으므로 통과
그래서 이런 쓰임에 쓰는 해시 함수에는 요구가 하나 더 붙습니다. 같은 해시값을 내는 두 입력을 일부러 찾아내는 일이 현실적인 시간 안에 안 되어야 합니다. 이 성질이 충돌 저항성입니다. 충돌이 없어지는 것은 아닙니다. 찾기가 어려워질 뿐입니다.
없앨 수 없고 줄이기만 한다
대응은 두 갈래입니다. 어느 쓰임이냐가 갈래를 정합니다.
| 쓰임 | 충돌이 내는 결과 | 대응 |
|---|---|---|
| 키로 값을 찾는 표 | 한 칸에 여럿이 쌓여 찾는 시간이 늘어난다 | 칸 수를 넉넉히 두고, 같은 칸에 든 것을 뒤처리한다 |
| 값을 대조해 같은지 보는 곳 | 다른 것을 같다고 말한다 | 해시값을 길게 잡고, 충돌 저항성이 살아 있는 함수를 고른다 |
어느 쪽도 충돌을 없애지는 못합니다. 앞쪽은 충돌이 나도 맞는 답이 나오게 만드는 것이고, 뒤쪽은 충돌을 찾는 비용을 감당 못 할 만큼 올리는 것입니다.
해시값을 길게 잡는 쪽은 특히 오해를 삽니다. 값이 길어지면 가짓수가 늘어 우연히 겹칠 확률이 내려갈 뿐, 겹칠 수 있다는 사실은 그대로입니다. 충돌 저항성이 깨진 함수는 길이와 무관하게 물러나야 합니다.
관련 항목
충돌을 만들어 내는 함수와 원리
해시 함수 · 해시 · 비둘기집 원리 · 생일 문제 · 균등 분포
충돌을 안고 도는 자료구조
해시테이블 · 버킷 · 집합 · 블룸 필터 · 적재율 · 일관성 해싱
충돌을 뒤처리하는 방법
충돌 해소 · 분리 연쇄법 · 개방 주소법 · 선형 탐사 · 이중 해싱 · 리해싱
충돌 저항성을 기대고 서는 보안 쓰임
무결성 · 체크섬 · 전자 서명 · 인증서 · 충돌 저항성 · 역상 저항성
충돌 저항성 강도로 갈리는 해시 함수
비밀번호 저장에서 함께 다루는 보안 수단
다른 이름: hash collision · 해시충돌