# 생일 공격 (Birthday Attack)

생일 공격(Birthday Attack)은 확률 이론의 생일 문제 뒤에 있는 수학을 이용해, 해시 함수에서 같은 출력을 내는 서로 다른 두 입력(충돌)을 찾는 암호 공격의 한 유형입니다. 출력 길이가 n비트인 해시라면 특정 출력을 맞히는 데는 약 2^n번의 시도가 필요하지만, 아무 충돌이나 찾는 데는 약 2^n/2번이면 충분합니다. 이 공격은 디지털 서명처럼 해시에 의존하는 통신을 악용하는 데 사용될 수 있습니다.

## 생일 문제

23명이 있는 방에서 두 사람이 같은 생일을 공유할 확률은 50%를 조금 넘습니다. 특정한 한 사람과 생일이 같은 사람을 찾는 것이 아니라 어느 두 사람이든 겹치면 되기 때문에, 비교할 수 있는 쌍의 수가 사람 수의 제곱에 비례해 빠르게 늘어납니다. 이 직관에 어긋나는 현상을 “생일 역설”이라고도 합니다.

## 암호화에 적용되는 방법

암호화의 생일 공격은 이 확률 원리를 이용합니다. 생일 대신 해시 함수의 충돌을 찾습니다. **해시 함수**는 데이터의 디지털 지문과 같습니다. 모든 입력을 받아 고정된 길이의 출력을 생성합니다. 입력의 경우의 수가 출력보다 많으므로 충돌은 반드시 존재하며, 좋은 해시 함수는 그것을 찾기 어렵게 만들 뿐입니다.

공격자는 특정 해시 출력을 찾을 필요가 없습니다. 대신, 동일한 해시 출력을 생성하는 *두 개의 서로 다른 입력*을 찾으려고 합니다. 이것을 **충돌**이라고 합니다.

## 예시

안전한 메시징 앱이 있다고 가정해 보겠습니다. 메시지가 변조되지 않았는지 확인하기 위해 해시 함수를 사용하여 디지털 서명이 생성됩니다.

- 공격자는 정상 메시지와 악성 메시지를 각각 조금씩 바꾼 버전을 대량으로 생성합니다. 생일 역설로 인해 출력 길이가 n비트인 해시에서는 각각 약 2^n/2개의 변형만 만들어도 해시가 같은 쌍을 찾을 가능성이 높아집니다.
- 그런 다음 각 버전의 해시를 계산하여 충돌을 찾습니다.
- 정상 메시지 변형과 악성 메시지 변형 사이에서 해시가 같은 쌍이 발견되면, 상대방에게 정상 메시지에 서명하게 한 뒤 그 서명을 악성 메시지에 붙여 바꿔치기할 수 있습니다.

수신자는 디지털 서명(해시에 기반)이 유효해 보이기 때문에 악성 메시지가 합법적이라고 생각하도록 속게 됩니다.

## 생일 공격이 관련된 영역

1. **디지털 서명:** 해시 충돌을 이용해 서명을 위조하고 데이터 무결성을 손상시킵니다.
2. **해시 충돌:** 보안 조치를 우회하기 위해 서로 다른 입력에 대해 동일한 해시 값을 찾습니다. MD5와 SHA-1은 실제로 충돌이 만들어져 서명 용도로는 더 이상 안전하지 않은 것으로 평가됩니다.

## 대응과 핵심 내용

생일 공격은 충돌 확률을 최소화하기 위해 강력한 해시 함수와 큰 해시 크기의 중요성을 강조합니다. 충돌 저항성으로 128비트 보안을 원하면 출력이 256비트인 해시(예: SHA-256)가 필요한 이유가 여기에 있습니다. 보안 연구원은 이 원리로 암호 시스템의 약점을 평가하고, 개발자는 더 긴 해시 출력을 선택해 공격에 대비합니다.

---
출처: https://achivx.kr/glossary/birthday-attack-%EC%83%9D%EC%9D%BC-%EA%B3%B5%EA%B2%A9/ · ACHIVX 용어 사전 · 수정일 2026-10-20