네트워크 보안에서 생일 공격(Birthday Attack)이란? 원리와 취약점 총정리

생일 공격(Birthday Attack)이란 무엇인가?

생일 공격은 확률론의 유명한 '생일 역설(birthday paradox)'을 암호 해독에 응용한 공격 기법입니다. 이름에서 연상되는 것과 달리 실제 생일과는 무관하며, 해시 함수의 충돌(collision)을 찾아내는 데 활용됩니다. 주로 두 명 이상의 당사자가 통신하는 상황에서 악용될 수 있습니다.

생일 역설의 원리와 예시

생일 역설이란, 무작위로 모인 사람들 중 두 사람이 같은 생일일 확률이 우리의 직관보다 훨씬 높다는 현상을 말합니다. 놀랍게도 단 23명만 모여도 두 사람이 같은 생일일 확률이 약 50%를 넘어섭니다.

예를 들어 방에 사람들이 한 명씩 들어오는 상황을 가정해 보겠습니다. 방 안에 이미 k명이 있을 때, 새로 들어온 사람이 기존 인원 중 누군가와 생일이 같을 확률은 k/365입니다. 첫 번째 사람은 1/365, 다음 사람은 2/365처럼 각 입장자의 일치 확률을 순서대로 더해 나가면, 인원수가 늘어날수록 생일이 겹칠 확률이 급격히 상승한다는 사실을 확인할 수 있습니다.

무차별 대입 공격의 변형인 이유

생일 공격은 무차별 대입(brute force) 공격의 한 종류로 분류됩니다. 일반적인 무차별 대입 공격이 가능한 모든 경우의 수를 하나씩 시도하는 반면, 생일 공격은 생일 역설이 보여주듯 무작위 시도를 일정 횟수만 반복해도 충돌이 발생할 확률이 크게 높아진다는 점을 이용합니다. 즉, 무작위 공격 시도와 고정된 순열(permutation)을 결합하여 전체 탐색 공간보다 훨씬 적은 시도 횟수로 목표를 달성할 수 있습니다.

생일 공격의 확률 계산

모집단의 크기(n)에 따라 같은 생일을 가진 사람이 존재할 확률(p(n))은 다음과 같이 빠르게 증가합니다.

해시 함수에 대한 생일 공격의 작동 방식

출력 범위가 r인 해시 함수 h에 대한 생일 공격의 목표는 약 r^1/2(루트 r)번의 시도, 즉 해시 연산 내에서 충돌을 찾아내는 것입니다. 여기서 충돌이란 서로 다른 입력 x_i ≠ x_j에 대해 동일한 출력 y_i = y_j가 나오는 경우를 의미하며, q는 시도 횟수를 뜻합니다. 요컨대 n비트 출력을 가지는 해시 함수라면 약 2^n/2번의 시도만으로 충돌을 발견할 수 있어, 전체 탐색 공간을 모두 시도하는 것보다 압도적으로 효율적입니다.

디지털 서명이 취약한 이유

디지털 서명은 생일 공격에 노출되기 쉬운 대표적인 영역입니다. 일반적으로 디지털 서명은 메시지 m에 대해 먼저 암호학적 해시 함수 H(m)를 계산한 뒤, 개인 키(비밀 키)로 그 해시값에 서명하는 방식으로 이루어집니다.

예를 들어 앨리스(Alice)가 밥(Bob)을 속여 가짜 계약서에 서명하게 만들려 한다면, 내용은 전혀 다르지만 해시값이 동일한 두 개의 문서, 즉 정상 문서와 악의적 문서를 미리 준비합니다. 그런 다음 밥에게 정상 문서에 서명하게 하면, 그 서명은 해시값이 같은 악의적 문서에도 유효하게 적용되어 버립니다.

생일 공격에 취약한 알고리즘: MD5

MD5는 생일 공격에 취약한 대표적인 해시 알고리즘입니다. 128비트로 짧은 다이제스트 길이 때문에 실제 환경에서도 충돌 쌍이 발견된 바 있으며, 현재는 보안이 중요한 용도로 사용이 권장되지 않습니다. 따라서 SHA-256처럼 해시 길이가 긴 최신 알고리즘으로의 전환이 필요합니다.

생일 공격의 정의 요약

정리하면, 생일 공격이란 확률론의 생일 문제를 이용해 암호 시스템에서 충돌을 찾아내는 공격 기법입니다. 공격자는 생일 역설이 보여주는 비정상적으로 높은 충돌 확률을 활용하여, 예상보다 훨씬 적은 시도로 동일한 해시값을 가지는 서로 다른 메시지를 만들어냄으로써 통신 당사자들을 기만할 수 있습니다.

생일이 같을 확률은 얼마나 될까?

특정한 한 사람과 생일이 정확히 같을 확률은 1/365로 매우 낮습니다. 하지만 '두 사람이 우연히 같은 생일일 가능성' 자체는 생각보다 흔합니다. 어떤 특정인과 생일이 같을 확률이 50%를 넘으려면 약 253명이 필요한 반면, '누구든' 같은 생일인 사람이 존재할 확률은 단 23명만 모여도 절반을 넘깁니다. 바로 이러한 확률의 비대칭성이 생일 공격의 핵심 원리입니다.