생일 공격 (Birthday Attack)

정보보안학

한 줄 정의: 생일 공격은 생일 역설(birthday paradox)의 확률 원리를 이용해, 해시 함수에서 서로 다른 두 입력이 같은 출력값을 갖는 충돌(collision)을 예상보다 훨씬 적은 시도로 찾아내는 공격 기법입니다.

쉽게 풀면

한 방에 사람이 몇 명 있으면 그중 생일이 같은 두 사람이 있을 확률이 50%를 넘을까요? 놀랍게도 23명 정도면 그 확률을 넘는다는 것이 생일 역설입니다. 특정 한 사람과 생일이 같은 사람을 찾으려면 훨씬 많은 사람이 필요하지만, "아무나 두 명이 같으면 된다"는 조건이면 훨씬 적은 인원으로도 가능합니다. 생일 공격은 이 원리를 해시 함수에 적용해, 특정 해시값을 노리는 대신 아무 두 입력이 같은 해시값을 갖기만 하면 되는 충돌을 상대적으로 적은 시도로 찾아내는 방법입니다.

왜 중요한가

해시 함수의 충돌 저항성은 전자서명, 인증서 검증 등 여러 보안 시스템의 기반이 되기 때문에, 정보보안학 분야에서는 생일 공격이 요구하는 계산량을 근거로 해시 함수의 출력 길이가 얼마나 되어야 안전한지 설계 기준을 제시하는 데 이 개념을 사용합니다.

논문에서는 이렇게 쓰입니다

"n비트 해시 함수의 경우 생일 공격에 의해 약 2^(n/2)번의 시도만으로 충돌을 찾을 수 있어, 이는 해시 출력 길이 설계 시 고려해야 할 핵심 기준이다."

생일 공격의 원리가 해시 함수 설계 기준에 직접적으로 반영되는 문맥입니다.

"MD5 해시 함수는 생일 공격 기반의 실용적 충돌 발견이 보고되면서 전자서명 용도로는 더 이상 권장되지 않는다."

실제 취약해진 해시 함수 사례를 다루는 문맥입니다.

조금 더 깊게 보면

n비트 출력을 갖는 이상적인 해시 함수에서 무작위 충돌을 찾는 데 필요한 시도 횟수는 대략 2^(n/2) 수준으로 알려져 있습니다. 이 때문에 SHA-256처럼 256비트 출력을 갖는 해시 함수는 충돌 저항성 관점에서 대략 128비트 수준의 안전성을 갖는다고 평가됩니다. 이러한 이유로 안전한 해시 함수는 특정 목표 안전성 수준의 두 배에 해당하는 출력 길이를 갖도록 설계됩니다.

주의할 점

생일 공격은 원상(preimage) 공격, 즉 주어진 해시값에 대응하는 원본을 찾는 공격과는 다른 개념이므로 혼동하지 않아야 합니다.