생일 공격과 충돌 공격

23명이 모이면 생일이 같은 두 사람이 있을 확률이 50%를 넘습니다. 70명일 때는 99.9%를 넘습니다. 수학적으로 크기가 N인 집합에서는 약 √N개의 표본을 얻으면 충돌 확률이 50%를 넘습니다. 이것이 생일 경계입니다.

n비트 해시 함수에서는 충돌(H(m1) = H(m2), m1 ≠ m2)을 약 2^{n/2}번의 무작위 시도로 찾을 수 있습니다. SHA-256(256비트)의 충돌을 찾으려면 약 2^{128}의 작업이 필요하므로 계산상 불가능합니다. MD5(128비트)는 약 2^{64}의 작업이 필요하여 간신히 가능합니다.

일반적인 충돌 찾기 방법은 2^{n/2}개의 무작위 메시지를 생성하고, 해시를 계산하고, 해시 값으로 정렬한 다음, 중복 값을 찾는 것입니다. 메모리 사용량은 O(2^{n/2})입니다. 로 알고리즘(플로이드의 순환 찾기)은 동일한 시간 비용으로 메모리 사용량을 O(1)로 줄입니다. 반 오르쇼트-위너 병렬 충돌 탐색은 하드웨어를 사용해 시간을 줄입니다.

Wang 연구진 등은 생일 공격이 아니라 차분 암호분석을 사용해 2004년에 MD5의 실용적인 충돌을 발견했습니다. 서로 다른 1024비트 메시지 두 개가 몇 초 만에 동일한 MD5 해시를 갖게 됩니다. Hertzbleed와 선택 접두사 충돌은 인증서 충돌을 가능하게 합니다. 충돌 저항성 측면에서 MD5는 완전히 무력화되었습니다.

더 강력한 방식에서는 임의의 두 접두사 P1, P2가 주어졌을 때 H(P1||S1) = H(P2||S2)가 되도록 접미사 S1, S2를 찾습니다. Stevens 연구진 등은 2017년에 선택 접두사 MD5 충돌을 발견했습니다. 이를 사용해 유효한 MD5 서명이 포함된 악성 CA 인증서를 만들 수 있었습니다. 그 결과 인증서에서 MD5 사용이 중단되었습니다.

Google의 SHAttered(2017)는 최초의 실용적인 SHA-1 충돌입니다. 서로 다른 두 PDF 파일이 동일한 SHA-1 해시를 가졌습니다. SHA-1 압축 2^{63.1}회가 필요했으며, 이는 CPU 6,500년과 GPU 110년에 해당합니다. 비용은 약 $110,000였습니다. 브라우저는 2017년에 SHA-1 인증서의 사용을 중단했습니다.

Merkle-Damgard 해시 함수(MD5, SHA-1, SHA-2)의 경우, H(m)을 알고 있으면 m을 몰라도 H(m||padding||m')을 계산할 수 있습니다. 이로 인해 H(secret||message)와 같은 MAC 구성이 깨집니다. 해결 방법은 HMAC(내부 및 외부 패딩을 사용함) 또는 SHA-3(스펀지 구성, 길이 확장에 면역)을 사용하는 것입니다.

충돌 저항성: 동일한 해시를 갖는 서로 다른 두 메시지를 찾는 것(2^{n/2} 작업량)입니다. 제2 프리이미지 저항성: m이 주어졌을 때 동일한 해시를 갖는 m' ≠ m을 찾는 것(2^n 작업량)입니다. 프리이미지 저항성: 주어진 해시에 해당하는 메시지를 찾는 것(2^n 작업량)입니다. 충돌 저항성이 항상 가장 약합니다.

MAC이 충돌에 취약한 해시를 사용하는 경우, H에서 충돌을 찾을 수 있는 공격자는 MAC을 위조할 수 있습니다. HMAC-MD5는 HMAC 구성에 충돌만이 아니라 프리이미지 공격이 필요하므로 MD5 충돌이 존재하더라도 안전한 것으로 간주됩니다. 그러나 새 시스템에서는 HMAC-MD5에서 다른 방식으로 전환해야 합니다.

Joux(2004): Merkle-Damgard 해시에서 2^k-방향 충돌(동일한 해시를 갖는 2^k개의 메시지)을 찾는 데는 단일 충돌을 찾는 작업량의 k배만 필요하며 2^k배가 필요하지 않습니다. 이는 연결된 해시의 취약점을 더 키웁니다(H1(m)||H2(m)은 생각만큼 강력하지 않습니다).

충돌에 강한 해싱에는 SHA-256 또는 SHA-3을 사용하십시오. 보안 목적으로는 MD5와 SHA-1을 사용하지 마십시오. MAC에는 HMAC-SHA-256 또는 HMAC-SHA-3을 사용하십시오. 비밀번호 해싱에는 Argon2를 사용하십시오(SHA-2를 직접 사용하지 않음). 길이 확장 저항성이 필요하다면 항상 SHA-3을 사용하십시오.

n비트 해시 함수에서 충돌을 찾으려면 해시 평가가 대략 몇 번 필요합니까?

생일 공격은 2^{n/2}의 작업량으로 해시 충돌을 찾습니다. MD5에는 실용적인 선택 접두사 충돌이 있으며, SHA-1은 2017년에 깨졌습니다. 길이 확장 공격은 순진한 H(key||msg) MAC을 무력화합니다. SHA-256 또는 SHA-3을 사용하고, 메시지 인증에는 HMAC을 사용하십시오. 다음 주제: 중간 일치 공격입니다.