생일 공격

2. 이론

암호학적 해시 함수 $H$가지 값을 가지는 $f(x)$에 대해, $f(x\_1)\; =\; f(x\_2)$이고 $x\_1$≠$x\_2$인 두 입력값 $x\_1,\; x\_2$를 찾는 것이 해시 충돌의 목표이다.

$n$가지의 입력값을 임의로 선택한 후 해시 값을 비교한다고 할 때, 해시 충돌을 찾을 확률은 다음과 같이 근사할 수 있다.^[6]

:$p(n;H)\; \backslash approx\; 1\; -\; e^\{-n(n-1)/(2H)\}\; \backslash approx\; 1-e^\{-n^2/(2H)\}$

해시 충돌을 찾을 확률이 $p$ 이상이기 위한 입력값의 가짓수를 $n(p;H)$라고 하면, 위 식에서 다음 근사값을 얻을 수 있다.

:$n(p;H)\backslash approx\; \backslash sqrt\{2H\backslash ln\backslash frac\{1\}\{1-p\}\}$

충돌 확률 $p\; =\; 0.5$로 두면 $n(0.5;H)\; \backslash approx\; 1.1774\; \backslash sqrt\; H$를 얻는다.

해시 충돌을 찾을 때까지 여러 입력값을 대입하여 계산할 경우, 계산 횟수의 기댓값은 다음과 같이 근사할 수 있다.^[13]

:$Q(H)\backslash approx\; \backslash sqrt\{\backslash frac\{\backslash pi\}\{2\}H\}$

따라서, $k$비트 해시 함수의 충돌을 발견하기 위해서는 평균적으로 $\backslash sqrt\{\backslash frac\{\backslash pi\}\{2\}\; 2^\{k\}\}$가지의 입력값만 조사하면 되며, 이것은 모든 가능한 가짓수가 $2^k$인 것에 비교하여 차수를 크게 감소시킨 것이다.

64비트 해시를 예로 들면, 약 1.8 × 10¹⁹개의 서로 다른 출력이 존재한다. 이들이 모두 동일한 확률을 갖는 경우(최상의 경우), 무차별 대입을 통해 충돌을 생성하는 데 '단지' 약 51억 번의 시도가 필요하다.^[7] 이 값은 '''생일 경계'''^[8]라고 불리며, ''l''비트 코드의 경우 2^''l''/2로 근사할 수 있다.^[9]

다음 표는 다양한 비트 수에 대해 특정 충돌 확률을 달성하기 위해 필요한 해시 연산 횟수를 보여준다. (모든 해시가 동일하게 발생한다고 가정)

비교를 위해, 일반적인 하드 디스크의 수정 불가능한 비트 오류율은 10⁻¹⁸에서 10⁻¹⁵ 정도이다.^[10] 이론적으로, MD5 해시 또는 UUID와 같이 약 128비트인 경우, 가능한 출력이 훨씬 많더라도 약 8,200억 개의 문서까지 그 범위 내에 있어야 한다.

2. 1. 용어

• 변수 ''n''은 입력(또는 시도) 횟수를 나타낸다. 공과 상자 문제에서 ''n''은 무작위로 ''H''개의 상자에 던져지는 공의 수를 나타낸다. 각 입력은 상자 중 하나(해시 값)에 공을 던지는 것에 해당한다.
• 변수 ''H''는 해시 함수의 가능한 총 출력 수를 나타낸다. 이는 공이 들어갈 수 있는 고유한 "빈"의 수이다. 총 해시 출력 수는 종종 $H\; =\; 2^l$로 표현되며, 여기서 ''l''은 해시 출력의 비트 길이이다. 공과 상자 문제에서 ''H''는 각 고유한 해시 값에 해당하는 빈의 수를 나타낸다.
• 변수 ''l''은 해시 함수 출력의 비트 길이를 나타낸다. 비트 길이 ''l''의 해시 함수는 $2^l$개의 고유한 출력을 생성할 수 있으므로, 가능한 해시 값(또는 빈)의 수는 $H\; =\; 2^l$이다.
• 변수 ''p''는 충돌이 발생할 확률, 즉 두 개 이상의 입력(공)이 동일한 출력(상자)에 할당될 확률을 나타낸다. 생일 공격에서 ''p''는 충돌할 확률이 50%가 되기 위해 얼마나 많은 입력이 필요한지 추정하기 위해 종종 0.5 (50%)로 설정된다.

• '''공'''은 해시 함수의 입력을 나타낸다.
• '''상자'''는 해시 함수의 가능한 출력(해시 값)을 나타낸다.
• 두 개 이상의 공이 같은 상자에 떨어질 때 '''충돌'''이 발생한다(즉, 두 개의 입력이 동일한 해시 출력을 생성함).

2. 2. 수학적 분석

참고로, 10⁻¹⁸에서 10⁻¹⁵는 일반적인 하드 디스크에서 수정할 수 없는 비트 오류가 발생하는 확률이다.^[10] 이론적으로, MD5 해시 또는 UUID는 약 128비트이므로, 가능한 출력이 훨씬 많더라도 약 8,200억 개의 문서까지는 하드 디스크에서의 오류 발생 확률 범위 내에 있다고 할 수 있다.

함수의 출력이 고르지 않게 분산되면 충돌을 훨씬 더 빠르게 찾을 수 있다는 것을 쉽게 알 수 있다. 해시 함수의 '균형'이라는 개념은 생일 공격에 대한 함수의 저항력을 정량화한다.^[11]

2. 3. 근사

비교를 위해, 일반적인 하드 디스크의 수정 불가능한 비트 오류율은 10⁻¹⁸에서 10⁻¹⁵ 정도이다.^[10] 이론적으로, MD5 해시 또는 UUID와 같이 약 128비트인 경우, 가능한 출력이 훨씬 많더라도 약 8,200억 개의 문서까지 그 범위 내에 있어야 한다.

좋은 경험 법칙은 암산에 사용할 수 있으며, 다음과 같은 관계를 가진다.

:$p(n)\; \backslash approx\; \{n^2\; \backslash over\; 2H\}$

이는 다음과 같이 쓸 수도 있다.

:$H\; \backslash approx\; \{n^2\; \backslash over\; 2p(n)\}$.

또는

:$n\; \backslash approx\; \backslash sqrt\; \{\; 2H\; \backslash times\; p(n)\}$.

이 근사 방식은 확률이 0.5 이하일 때 잘 작동한다.

2. 4. 증명

3. 응용 및 사례

생일 공격은 여러 분야에서 응용 및 사례를 찾아볼 수 있다.

디지털 서명은 생일 공격에 취약하다. 공격자는 원본 메시지에 다양한 변형을 가해 동일한 해시 값을 갖는 두 개의 다른 메시지를 찾아 서명된 메시지를 위조한다. 이러한 공격을 방지하기 위해, 서명자는 서명 전 문서에 무작위적이고 무해한 변경을 가하고, 서명한 계약서 사본을 보관하여 법정에서 자신의 서명이 사기 계약이 아닌 해당 계약과 일치함을 입증할 수 있다.

폴라드 로 알고리즘은 이산 대수 계산에 생일 공격을 사용하는 알고리즘의 예시다.^[5]

BIND 구현 상의 문제로 인해, 생일 공격을 이용한 DNS의 DNS 캐시 포이즈닝 가능성이 제기되기도 한다.^[16]

3. 1. 디지털 서명 공격

디지털 서명은 생일 공격에 취약할 수 있다. 메시지 $m$은 일반적으로 먼저 $f(m)$을 계산하여 서명되는데, 여기서 $f$는 암호화 해시 함수이고, 그런 다음 일부 비밀 키를 사용하여 $f(m)$에 서명한다. 맬러리가 밥이 사기 계약에 서명하도록 속이려 한다고 가정해 보자. 맬러리는 공정한 계약 $m$과 사기 계약 $m\text{'}$을 준비한다. 그런 다음 맬러리는 쉼표 삽입, 빈 줄, 문장 뒤의 공백 하나 또는 두 개, 동의어 교체 등 의미를 변경하지 않고 $m$을 변경할 수 있는 여러 위치를 찾는다. 이러한 변경 사항을 결합하여 공정한 계약인 $m$의 엄청난 수의 변형을 만들 수 있다.

마찬가지로 맬러리는 사기 계약 $m\text{'}$에 대한 엄청난 수의 변형을 만든다. 그런 다음 공정한 계약과 사기 계약의 버전이 동일한 해시 값 $f(m)\; =\; f(m\text{'})$을 가질 때까지 해시 함수를 이러한 모든 변형에 적용한다. 그녀는 밥에게 서명을 위해 공정한 버전을 제시한다. 밥이 서명한 후 맬러리는 서명을 가져와 사기 계약에 첨부한다. 이 서명은 밥이 사기 계약에 서명했음을 "증명"한다.

확률은 맬러리가 동일한 해시를 가진 두 개의 공정한 계약 또는 두 개의 사기 계약을 찾는 것으로 아무것도 얻지 못하기 때문에 원래 생일 문제와 약간 다릅니다. 맬러리의 전략은 하나의 공정한 계약과 하나의 사기 계약 쌍을 생성하는 것이다. 주어진 해시 함수에 대해 $2^l$은 가능한 해시의 수이며, 여기서 $l$은 해시 출력의 비트 길이이다. 생일 문제 방정식은 여기에 정확히 적용되지 않는다. 충돌 확률이 50%일 경우 맬러리는 약 $2^\{(l/2)\; +\; 1\}$개의 해시를 생성해야 하는데, 이는 고전적인 생일 문제에서 단순한 충돌에 필요한 수의 두 배이다.

이러한 공격을 피하려면 서명 체계에 사용되는 해시 함수의 출력 길이를 생일 공격이 계산상 실행 불가능해질 정도로 충분히 크게 선택할 수 있다. 즉, 일반적인 무차별 대입 공격을 방지하는 데 필요한 비트 수의 약 두 배이다.

폴라드 로 알고리즘은 이산 대수 계산을 위해 생일 공격을 사용하는 알고리즘의 예이다.^[5]

3. 2. 역공격

생일 공격은 암호학에서 해시 함수의 충돌 가능성을 이용하는 공격 방식이다. 이를 이해하기 위해 생일 문제의 예를 들어 설명할 수 있다.

30명의 학생이 있는 반에서, 두 학생의 생일이 같을 확률은 직관적으로 낮아 보이지만, 실제로는 약 70%에 달한다. 이는 $1-\backslash frac\{365!\}\{(365-n)!\backslash cdot\; 365^n\}$ ($n=30$)으로 계산된다.^[5] 반면, 특정 날짜(예: 9월 16일)에 생일인 학생이 있을 확률은 $1\; -\; (364/365)^\{30\}$으로 약 7.9%이다.

생일 공격은 이러한 확률적 특성을 이용한다. 공격자는 무해한 계약과 악성 계약 각각에 대해 다양한 변형을 준비하고, 각 변형에 디지털 서명을 한다. 목표는 동일한 서명을 가진 무해한 계약과 악성 계약 쌍을 찾는 것이다. 예를 들어, 계약의 SHA-256 해시의 첫 번째 바이트를 디지털 서명으로 사용한다고 가정하면, 공격자는 무해한 계약과 악성 계약 각각의 변형들을 생성하여 동일한 서명을 갖는 쌍을 찾는다.

공격자는 피해자가 무해한 계약에 서명하도록 유도한 후, 동일한 서명을 가진 악성 계약으로 바꿔치기한다. 피해자는 자신이 무해한 계약에 서명했다고 생각하지만, 실제로는 악성 계약에 서명한 셈이 된다.

이러한 공격은 서명자가 맬러리(공격자)인 경우에도 가능하다. 맬러리는 밥에게 공정한 계약을 제안하고, 밥의 계약을 약간 수정한 무해한 버전과 악성 계약을 만든다. 두 계약은 동일한 디지털 서명을 갖도록 조작된다. 맬러리는 수정된 무해한 계약에 서명하여 밥에게 주고, 나중에 동일한 서명을 가진 악성 계약을 제시하며 그것이 진짜 계약이라고 주장한다.

이 공격의 진행 과정은 다음과 같다.

1. 계약 제안: 밥은 맬러리에게 공정한 계약을 제안한다.

2. 계약 위조: 맬러리는 밥의 계약을 약간 수정한 무해한 버전과 악성 계약, 두 가지 버전을 만든다. 두 버전은 동일한 디지털 서명을 갖는다.

3. 서명 전달: 맬러리는 수정된 무해한 계약에 서명하여 밥에게 전달한다.

4. 위험 발생: 밥이 수정된 계약 사본을 보관하지 않으면, 맬러리는 나중에 악성 계약을 제시하며 서명된 계약이라고 주장할 수 있다.

5. 결과:

• 밥이 수정된 계약 사본을 보관하지 않으면 맬러리의 사기는 완벽하게 성공한다.
• 밥이 수정된 계약 사본을 보관하더라도, 맬러리는 밥이 계약을 변경했다고 주장하며 책임을 회피할 수 있다.

3. 3. DNS 캐시 포이즈닝

BIND 구현 상의 문제 등으로 인해, 생일 공격을 이용한 DNS의 DNS 캐시 포이즈닝 가능성이 논의되고 있다.^[16]