생일 문제

생일 문제는 무작위로 값을 뽑을 때 겹침이 언제 처음 나타나는지를 알려 줍니다. 한 해는 365일이지만 스물세 명만 모여도 생일이 같은 두 사람이 있을 확률이 절반을 넘습니다. 겹침은 값의 가짓수보다 훨씬 이른 지점인 가짓수의 제곱근 근처에서 옵니다. 직관과 어긋나서 생일 역설이라고도 부릅니다.

상세

동창회에 스물세 명이 모였습니다. 사회자가 "제 생일과 같은 분 계세요" 하고 물으면 대개 아무도 손을 안 듭니다. 질문을 "여기 생일이 같은 두 분이 계신가요"로 바꾸면 손이 올라오는 일이 훨씬 잦습니다.

물음의 정의

생일 문제는 가짓수가 N인 값 가운데 하나를 k번 무작위로 뽑을 때, 같은 값이 적어도 두 번 나올 확률을 묻습니다. 뽑은 값은 매번 되돌려 놓습니다. 그래서 같은 값이 다시 뽑힐 수 있습니다. 이런 뽑기를 복원 추출이라고 부릅니다.

생일에 대면 가짓수 N은 365입니다. 뽑는 횟수 k는 방에 모인 사람 수입니다. 사람마다 생일이 365일 가운데 하나로 정해집니다. 두 사람이 같은 날을 가질 수 있습니다.

1부터 365까지 번호가 붙은 공을 넣은 항아리에서 공을 꺼내 번호를 적고 다시 넣는 일과 같습니다.

겹칠 확률을 세는 식

겹칠 확률을 바로 세면 경우가 너무 많이 갈립니다. 대신 반대쪽 사건인 "아무것도 안 겹칠 확률"을 먼저 구합니다. 그 값을 1에서 빼면 겹칠 확률입니다. 이 반대쪽 사건을 여사건이라고 부릅니다.

첫 값은 무엇이 나와도 됩니다. 둘째 값은 첫 값과 달라야 하니 N−1가지 가운데서 나와야 합니다. 셋째 값은 N−2가지 가운데서 나와야 합니다. 이렇게 k번째까지 곱한 것을 전체 경우의 수 N^k 로 나누면 아무것도 안 겹칠 확률입니다.

아무것도 안 겹칠 확률    N × (N−1) × (N−2) × … × (N−k+1)  ÷  N^k
적어도 한 번 겹칠 확률   p(N, k) = 1 − N × (N−1) × … × (N−k+1) ÷ N^k

N에 365를 넣고 사람 수 k를 바꿔 가며 식으로 센 값입니다.

스물두 명까지는 절반에 못 미칩니다. 스물세 명에서 절반을 넘습니다. 서른 명이면 0.706입니다. 사람이 몇 명 늘 때마다 확률이 빠르게 오릅니다.

짝의 수가 늘어나는 속도

겹침은 두 값의 짝에서 납니다. 사람이 k명이면 두 사람씩 고른 짝은 k(k−1)/2개입니다. 한 사람이 들어올 때마다 이미 있던 사람 수만큼 짝이 새로 생깁니다.

아래는 사람이 셋에서 다섯으로 늘 때 짝이 불어나는 모양입니다. 동그라미는 사람입니다. 선은 두 사람의 짝입니다. 점선은 새로 들어온 사람에게서 뻗은 짝입니다.

flowchart TD
    subgraph S3["사람 3명 · 짝 3개"]
        A1(("1")) --- A2(("2"))
        A1 --- A3(("3"))
        A2 --- A3
    end
    subgraph S4["사람 4명 · 짝 6개 · 새 짝 3개"]
        B1(("1")) --- B2(("2"))
        B1 --- B3(("3"))
        B2 --- B3
        B4(("4")) -.- B1
        B4 -.- B2
        B4 -.- B3
    end
    subgraph S5["사람 5명 · 짝 10개 · 새 짝 4개"]
        C1(("1")) --- C2(("2"))
        C1 --- C3(("3"))
        C2 --- C3
        C4(("4")) --- C1
        C4 --- C2
        C4 --- C3
        C5(("5")) -.- C1
        C5 -.- C2
        C5 -.- C3
        C5 -.- C4
    end
    S3 --> S4 --> S5

사람이 하나 늘 때 새로 생기는 짝은 셋, 넷으로 같이 늡니다. 그래서 사람은 하나씩 늘지만 짝은 제곱에 가깝게 늡니다. 스물세 명이면 짝이 253개입니다.

짝 하나가 겹칠 확률은 1/N입니다. 그러면 겹치는 짝 수의 기대값, 곧 평균 몇 쌍이 겹치느냐는 k(k−1)/2N입니다. 스물세 명이면 253/365, 약 0.693입니다.

기대값은 아직 확률이 아닙니다. 짝 하나가 안 겹칠 확률은 1 − 1/N입니다. 짝이 m개면 아무 짝도 안 겹칠 확률은 이 값을 m번 곱한 것에 가깝습니다.

N이 크면 이 곱은 e^(−m/N)에 가까워집니다. e는 자연로그의 밑으로 쓰는 상수입니다. 값은 약 2.718입니다.

짝의 수                    m = k(k−1)/2
겹치는 짝 수의 기대값        m/N = k(k−1)/2N
적어도 한 번 겹칠 확률       p ≈ 1 − e^(−k(k−1)/2N) ≈ 1 − e^(−k²/2N)

이 어림식은 가짓수 N이 크고 뽑는 수 k가 N의 제곱근 정도일 때 맞습니다. 짝끼리 완전히 무관하지는 않아서 오차가 남습니다. 그 오차는 N이 커질수록 줄어듭니다.

스물세 명을 넣으면 1 − e^(−0.693) ≈ 0.500이 나옵니다. 하나씩 곱해 센 0.507과 소수 첫째 자리까지 맞습니다.

제곱근 규칙

어림식의 지수에 든 k²/2N을 보면 위험해지는 지점이 드러납니다. 이 지수는 앞에서 센 겹치는 짝 수의 기대값과 같은 값입니다. k가 N의 제곱근이면 이 지수가 1/2이 됩니다.

flowchart TD
    A["가짓수 N 에서 k 개를 뽑는다"] --> B["짝의 수 = k(k−1)/2"]
    B --> C["짝 하나가 겹칠 확률 = 1/N"]
    C --> D["겹치는 짝 수의 기대값 ≈ k²/2N"]
    D --> E["k 가 √N 이면 기대값 = 1/2"]
    E --> F["겹칠 확률 ≈ 1 − e^(−1/2) ≈ 0.393"]

k가 √N이면 겹칠 확률은 약 0.393입니다. 가짓수의 제곱근만큼만 뽑아도 열에 넷 가까이 겹칩니다. 확률이 절반이 되는 지점은 그보다 조금 뒤인 k ≈ 1.177 × √N입니다.

N에 365를 넣으면 22.5가 나옵니다. 사람은 정수로만 세니 스물세 명이 됩니다.

처음 겹칠 때까지 뽑는 횟수의 평균도 같은 크기입니다. N이 클 때 그 평균은 √(πN/2)에 가까워집니다. π는 원주율입니다. 365를 넣으면 약 24입니다.

결론은 한 줄로 줄어듭니다. 첫 겹침은 가짓수 N이 아니라 √N 근처에서 옵니다.

나를 기준으로 한 물음과의 차이

직관은 대개 이렇게 답합니다. 생일이 놓일 칸(가짓수 N)이 365개니 절반쯤 채우려면 180명은 있어야 한다는 것입니다. 이 어긋남은 계산이 이상해서가 아니라 사람들이 머릿속에서 다른 물음에 답하기 때문에 생깁니다.

먼저 떠오르는 물음은 "나와 생일이 같은 사람이 있나"입니다. 스물세 명 방에서 이 확률은 1 − (364/365)^22, 약 0.059입니다. 이 확률이 절반을 넘으려면 나 말고 253명이 더 있어야 합니다.

생일 문제는 "아무 두 사람의 생일이 같나"를 묻습니다. 기준이 되는 사람이 따로 없습니다. 방 안의 모든 짝을 봅니다. 스물세 명 방에 두 물음을 나란히 두면 이렇습니다.

253명과 253쌍이 같은 수인 것은 우연이 아닙니다. 확률 1/365짜리 맞춰 보기를 몇 번 해야 "한 번은 맞는다"가 절반을 넘는지 세면 253번이 나옵니다.

앞 물음은 그 253번을 사람으로 채웁니다. 뒤 물음은 짝으로 채웁니다. 짝은 사람 수의 제곱으로 늘어나니 스물세 명이면 이미 채워집니다.

비둘기집 원리와의 차이

칸보다 많이 뽑으면 반드시 겹친다는 것은 비둘기집 원리입니다. 그건 N+1번째 값을 뽑을 때의 이야기입니다. 생일 문제는 그보다 훨씬 앞, 칸이 아직 거의 비어 있을 때 이미 겹칠 확률이 커진다는 것을 말합니다.

값을 고르게 흩뿌리는 계산이면 어디에나 같은 셈이 걸립니다. 해시 함수의 출력, 무작위로 뽑는 식별자, 같은 키로 만든 암호문 블록이 그렇습니다. 그 사례는 아래 「예시」와 「사용처」가 다룹니다.

배경

√N에서 오는 겹침이 암호에서 값을 치르게 된 첫 분야 가운데 하나가 전자 서명입니다. 메시지 대신 메시지의 해시값에 서명하는 방식에서는 해시값이 같은 두 메시지가 서명을 나눠 씁니다. 두 입력이 같은 해시값을 내는 것을 해시 충돌이라고 부릅니다.

출력이 n비트인 해시 함수에서 정해 둔 해시값 하나를 맞히려면 2^n번쯤 시도해야 합니다. 메시지를 마음대로 고를 수 있는 공격자라면 해시값이 같은 아무 한 쌍은 2^(n/2)번쯤이면 찾습니다. 2^(n/2)는 가짓수 2^n의 제곱근입니다. 「상세」가 √N이라고 적은 것이 이 수입니다.

그래서 해시를 쓰는 서명 방식은 이 공격에 약할 수 있습니다. 부정직한 서명자는 한 메시지에 서명해 건넨 뒤, 해시값이 같은 다른 메시지에 서명한 것이라고 우길 수 있습니다. 해시의 안전을 출력 길이 n이 아니라 그 절반으로 따져야 하는 까닭이 여기 있습니다.

1979년 Gideon Yuval이 이 계산으로 라빈 전자 서명 방식의 안전을 무너뜨리는 지름길을 보였습니다. 생일 역설을 암호에 쓴 첫 응용 가운데 하나입니다. 그 함의는 Merkle 등 당시 다른 연구자들도 알고 있었습니다.

이렇게 충돌 한 쌍을 찾는 공격이 생일 공격입니다. √N만큼의 일로 끝내는 공격을 제곱근 공격이라 부르기도 합니다. 생일 역설이라는 이름은 스물세 명 방에서 0.507이라는 답이 놀랄 만큼 크다는 데서 왔습니다. 생일 놀라움이라고도 부릅니다.

예시

Sweet32, 64비트 블록 암호의 암호문 겹침

생일 문제는 블록 암호의 암호문 블록끼리 겹치는 일로도 나타납니다. 여기서 보는 것은 웹 보안 연결과 OpenVPN에서 쓰이던 64비트 블록 암호 3DES(Triple DES, Data Encryption Standard 를 세 번 거는 방식)· Blowfish입니다. 재는 것은 겹침이 오기까지 필요한 데이터 양입니다. 결과부터 적으면 64비트 블록은 32 GB(gigabyte, 기가바이트) 근처에서 겹침이 옵니다.

블록 암호는 평문을 정해진 길이의 블록으로 잘라 블록마다 같은 키로 암호화합니다. 블록 길이가 n비트면 암호문 블록이 가질 수 있는 값은 2^n가지입니다. 3DES와 Blowfish는 블록이 64비트입니다.

CBC(Cipher Block Chaining) 모드는 i번째 평문 블록 mi를 바로 앞 암호문 블록 ci−1과 XOR(exclusive OR, 배타적 논리합)한 뒤 암호화해 ci를 만듭니다. XOR는 기호로 ⊕ 라고 적습니다. 같은 키로 2^(n/2) 블록을 암호화하면 암호문 블록 두 개가 겹칠 것으로 기대됩니다. 블록 암호는 입력과 출력이 일대일로 대응하므로 출력이 같으면 입력도 같습니다.

flowchart TD
    A["같은 키로 64비트 블록을 2^32 개쯤 암호화한다"] --> B["암호문 블록 둘이 같아진다 · ci = cj"]
    B --> C["입력도 같았다 · mi ⊕ ci−1 = mj ⊕ cj−1"]
    C --> D["평문 두 블록의 XOR 가 드러난다 · mi ⊕ mj = ci−1 ⊕ cj−1"]

공격자는 이미 본 암호문 블록 ci−1과 cj−1만으로 평문 두 블록의 XOR를 얻습니다. 그중 한 블록의 평문을 알면 다른 블록이 풀립니다. 2^d 블록을 암호화했을 때 겹치는 쌍의 기대 수는 대략 2^(2d−n−1)입니다. 상세의 k²/2N에 k = 2^d, N = 2^n을 넣은 것과 같은 식입니다.

이 경계를 생일 한계라고 부릅니다. 64비트 블록 암호의 이 약점은 오래 알려져 있었습니다. 다만 평문을 어느 정도 미리 알아야 합니다. 그리고 기가바이트당 몇 비트만 새서 실용적이지 않다고 여겨져 왔습니다.

2016년 Karthikeyan Bhargavan과 Gaëtan Leurent은 이 공격을 Sweet32라는 이름으로 시연했습니다. 공격자는 HTTPS(HyperText Transfer Protocol Secure)로 오래 이어지는 3DES 연결을 엿봅니다. 악성 자바스크립트로 트래픽을 만들어 785 GB 안팎을 모으면 보안 HTTP(HyperText Transfer Protocol) 쿠키를 되찾았습니다. 첫 겹침은 32 GB에서 오지만 겹침 한 번이 내주는 것은 평문 두 블록의 XOR 하나뿐이라, 쿠키 한 덩이를 다 되찾으려면 그보다 한참 많은 데이터를 모아야 합니다.

Blowfish를 쓰는 OpenVPN 연결에서는 HTTP 기본 인증 자격 증명을 같은 방식으로 되찾았습니다. 연구진의 시연 환경에서 785 GB를 모으는 데 19~38시간이 걸렸습니다.

Git 의 축약 해시 길이

Git은 해시값을 몇 자로 줄여 보여 줄지를 이 계산으로 정합니다. 그 계산은 Git 소스 odb.c 의 odb_find_abbrev_len() 에 있습니다. 재는 것은 저장소의 객체 수에서 나오는 축약 길이입니다. 객체 수가 늘면 축약 길이도 늘어납니다.

Git은 커밋과 파일 같은 객체를 해시값으로 부릅니다. 화면에는 그 해시값의 앞 몇 자만 16진수로 줄여 보여 줍니다. 줄인 이름끼리 겹치면 그 이름으로 객체 하나를 집을 수 없습니다. 설정 core.abbrev 를 비워 두거나 auto 로 두면 저장소에 든 객체 수를 어림해 이 길이를 정합니다.

len = msb(count) + 1;
/*
 * We now know we have on the order of 2^len objects, which
 * expects a collision at 2^(len/2). But we also care about hex
 * chars, not bits, and there are 4 bits per hex. So all
 * together we need to divide by 2 and round up.
 */
len = DIV_ROUND_UP(len, 2);
/*
 * For very small repos, we stick with our regular fallback.
 */
if (len < FALLBACK_DEFAULT_ABBREV)
        len = FALLBACK_DEFAULT_ABBREV;

첫 줄은 객체 수 count 의 최상위 비트 위치에 1을 더해 len 을 잡습니다. 객체가 2의 len 제곱 개쯤 있다는 뜻입니다.

주석은 이 수에서 겹침이 2^(len/2) 근처에 온다고 봅니다. 16진수 한 자가 4비트라는 점까지 합쳐 len 을 2로 나누고 올린 값을 축약 길이로 씁니다. 그 값이 FALLBACK_DEFAULT_ABBREV, 곧 7보다 작은 저장소는 7자를 씁니다.

auto 로 정한 길이는 축약 이름이 한동안 겹치지 않기를 바라고 잡은 값입니다. 손으로 정할 때 가장 짧은 길이는 4자입니다.

사용처

제곱근 규칙은 길이와 상한을 정하는 근거로 쓰입니다. 다루는 것은 해시 함수의 출력 길이 권고, 64비트 블록 암호의 데이터 상한, Git 의 축약 해시 셋입니다. 재는 것은 그 셋이 정한 숫자입니다. 셋 모두 절반·제곱근 선을 받아 그 숫자를 잡았습니다.

NIST 의 해시 함수 권고

미국 국립표준기술연구소 NIST(National Institute of Standards and Technology)는 권고 SP 800-107(Special Publication 800-107)을 냈습니다. 이 권고는 해시 함수의 충돌 저항 강도를 출력 길이의 절반으로 잡습니다. 충돌 저항이 b비트라는 말은 충돌 한 쌍을 높은 확률로 찾는 데 2^b번쯤의 일이 든다는 뜻입니다.

해시값을 잘라 쓸 때 충돌 저항이 s비트 필요하면 자른 길이를 2s비트 이상으로 둬야 한다고 적습니다 (shall, 규범적 요구). 절반이라는 값은 가짓수 2^L의 제곱근 2^(L/2)와 같습니다.

64비트 블록 암호의 키당 데이터 상한

64비트 블록 암호인 3DES는 한 키 묶음으로 2^32 블록쯤 암호화하면 암호문 충돌이 일어날 가능성이 큽니다. 충돌 확률을 아주 작게 두려면 데이터 양이 2^32 블록보다 한참 적어야 합니다. 이 약점이 AES를 만들 때 128비트 블록을 요구한 동기가 됐습니다. Sweet32 시연 뒤 세 곳이 한 키로 처리하는 양을 줄이거나 3DES를 뒤로 물렸습니다.

OpenVPN의 64 MB 기본값은 Sweet32 공격을 막는 데 얼마간 보탬이 되도록 넣은 값입니다. 0으로 꺼 둘 수는 있지만 매우 권하지 않습니다. 키를 자주 바꾸면 한 키로 암호화하는 양이 생일 한계보다 훨씬 작게 묶입니다. 위 표의 3DES 는 표준 이름이 TDEA(Triple Data Encryption Algorithm)입니다.

Git 의 축약 해시

Git은 축약 해시 길이를 저장소의 객체 수로 정합니다. 객체가 2^len개쯤이면 겹침이 2^(len/2)에서 온다는 계산이 근거입니다. 그래서 저장소가 커질수록 축약 이름이 길어집니다. 계산 자체는 「예시」에 있습니다.

보장과 가정

「상세」의 식이 약속하는 것과 그 약속이 선 전제를 정리합니다. 살피는 것은 전제가 깨진 생일 분포와 난수 발생기 사례입니다. 재는 것은 겹침이 얼마나 앞당겨졌나입니다.

요약하면 가짓수가 좁아지면 겹침도 그 좁아진 가짓수의 제곱근에서 옵니다. 균등이 깨져도 결론이 버티는 경우가 하나 있습니다. 가짓수가 좁아져 결론이 무너지는 경우는 둘입니다.

해시 함수에 이 계산을 얹을 때는 해시 출력이 고른 무작위 값에 가깝다고 가정하는 것이 보통입니다. 생일 공격은 해시 함수의 내부를 보지 않습니다. 출력 길이와 한 번 계산하는 데 드는 시간만 봅니다.

생일이 고르게 흩어지지 않을 때

생일이 365일에 고르게 흩어지지 않아도 결론은 무너지지 않습니다. 큰 집단에서 무작위로 뽑은 스물세 명이면 생일이 같은 두 사람이 있을 확률이 절반을 넘습니다. 생일이 어떤 분포를 따르든 그렇다는 것이 1977년에 증명됐습니다. 균등 가정이 깨져도 스물세 명이라는 경계가 뒤로 밀리지 않는다는 뜻입니다.

난수 발생기가 고를 수 있는 값이 좁을 때

명목상 가짓수가 커도 나올 수 있는 값이 좁으면 생일 문제의 N은 그 좁은 수입니다. Debian의 openssl 패키지는 Debian만의 잘못된 변경 탓에 난수 발생기를 예측할 수 있게 됐습니다. 취약한 첫 판은 2006년 9월에 올라갔습니다. 공지는 2008년 5월에 나왔습니다.

이 판은 씨앗을 프로세스 ID로만 넣었습니다. 프로세스 ID 가운데 0번은 커널 몫입니다. 상한인 32768에도 닿지 않습니다. 쓸 수 있는 값은 32,767개입니다.

나올 수 있는 난수 흐름은 그래서 아키텍처마다 32,767가지뿐이었습니다. N에 32,767을 넣으면 그 제곱근은 약 181입니다. 같은 난수 흐름에서는 같은 키가 만들어집니다. 식으로 세면 키를 이백 개 남짓만 만들어도 겹칠 확률이 절반에 이릅니다.

인터넷 전체를 조사한 2012년 연구는 겹침을 직접 셌습니다. 키를 만들 때 쓸 수 있는 예측 불가능성의 양을 엔트로피라고 부릅니다. TLS(Transport Layer Security) 인증서의 0.75%가 키 생성 때 엔트로피가 모자라 키를 나눠 쓰고 있었습니다. 다른 1.70%도 같은 결함 있는 구현에서 나와 깨질 수 있다고 의심됐습니다.

키가 충분한 엔트로피로 만들어졌다면 조사한 규모에서 중복 키가 하나도 안 나와야 합니다. 중복 키는 그래서 그 장치의 키 생성 과정을 의심하라는 신호로 읽힙니다.

난수 발생기 두 사례 모두 가정 1이 깨졌습니다. 가정이 깨지면 「√N에서 첫 겹침」이라는 보장도 같이 깨집니다. 겹침은 명목상 가짓수로 어림한 때보다 훨씬 일찍 옵니다.

관련 항목

생일 문제가 자릿수 근거가 되는 설계 요소

솔트 · UUID · 세션 식별자 · 액세스 토큰 · 기본 키 · 캐시 키 · URL 단축기 · 축약 해시

겹침이 실제로 터졌을 때 나는 오류

해시 충돌 · 충돌 해소 · 유일 제약 · 중복 키 · 데이터 유실

제곱근 규칙을 파고드는 공격과 그 대상

생일 공격 · 생일 한계 · 제곱근 공격 · 해시 함수 · 충돌 저항성 · 전자 서명 · 메시지 인증 코드 · 무차별 대입 공격 · 레인보우 테이블 · Sweet32

생일 한계에 걸리는 블록 암호와 운용 모드

블록 암호 · CBC · 3DES · Blowfish · AES · 운용 모드

제곱근 규칙으로 길이와 상한을 정한 표준과 도구

SHA-256 · NIST · OpenVPN · OpenSSL · Git

이 확률을 세울 때 쓰는 수학 도구

비둘기집 원리 · 기대값 · 여사건 · 조합 · 균등 분포 · 독립 시행 · 복원 추출

겹칠 값을 뽑아 주는 무작위 장치

난수 발생기 · 유사난수 함수 · 엔트로피 · 암호학적 난수 발생기

겹침을 피하려고 무작위 대신 쓰는 발급 방식

자동 증가 · 일련번호 · 스노우플레이크 · 중앙 발급기

겹침 확률이 성능으로 드러나는 저장 구조

해시테이블 · 블룸 필터 · 인덱스 · 샤딩 · 일관성 해싱