생일 공격 (Birthday Attack)
쉽게 풀면
한 방에 사람이 몇 명 있으면 그중 생일이 같은 두 사람이 있을 확률이 50%를 넘을까요? 놀랍게도 23명 정도면 그 확률을 넘는다는 것이 생일 역설입니다. 특정 한 사람과 생일이 같은 사람을 찾으려면 훨씬 많은 사람이 필요하지만, "아무나 두 명이 같으면 된다"는 조건이면 훨씬 적은 인원으로도 가능합니다. 생일 공격은 이 원리를 해시 함수에 적용해, 특정 해시값을 노리는 대신 아무 두 입력이 같은 해시값을 갖기만 하면 되는 충돌을 상대적으로 적은 시도로 찾아내는 방법입니다.
왜 중요한가
해시 함수의 충돌 저항성은 전자서명, 인증서 검증 등 여러 보안 시스템의 기반이 되기 때문에, 정보보안학 분야에서는 생일 공격이 요구하는 계산량을 근거로 해시 함수의 출력 길이가 얼마나 되어야 안전한지 설계 기준을 제시하는 데 이 개념을 사용합니다.
논문에서는 이렇게 쓰입니다
생일 공격의 원리가 해시 함수 설계 기준에 직접적으로 반영되는 문맥입니다.
실제 취약해진 해시 함수 사례를 다루는 문맥입니다.
조금 더 깊게 보면
n비트 출력을 갖는 이상적인 해시 함수에서 무작위 충돌을 찾는 데 필요한 시도 횟수는 대략 2^(n/2) 수준으로 알려져 있습니다. 이 때문에 SHA-256처럼 256비트 출력을 갖는 해시 함수는 충돌 저항성 관점에서 대략 128비트 수준의 안전성을 갖는다고 평가됩니다. 이러한 이유로 안전한 해시 함수는 특정 목표 안전성 수준의 두 배에 해당하는 출력 길이를 갖도록 설계됩니다. 생일 공격은 해시 함수뿐 아니라 암호학적으로 무작위성을 요구하는 다른 구조, 예를 들어 논스나 세션 식별자의 충돌 가능성을 평가할 때도 동일한 확률 논리로 적용됩니다. 생일 공격에 대한 저항성은 해시 함수의 출력 길이를 늘리는 것으로 비교적 간단히 강화할 수 있어, 신규 해시 표준을 설계할 때 기본 고려 사항으로 반영됩니다.
주의할 점
생일 공격은 원상(preimage) 공격, 즉 주어진 해시값에 대응하는 원본을 찾는 공격과는 다른 개념이므로 혼동하지 않아야 합니다.