'23명이 있으면 생일이 같은 두 사람이 있을 확률이 50%를 넘는다'는 생일 역설을 이용하여 충돌을 찾는 공격. 출력이 n비트인 값을 무작위로 만들어 가면 약 2^(n/2)개에서 같은 값의 쌍이 나타날 확률을 무시할 수 없게 된다. 이 때문에 n비트 해시 함수의 충돌에 대한 강도는 약 n/2비트로 여겨진다. 블록 길이 64비트의 블록 암호에서는 하나의 키로 약 2^32블록(32 GiB)을 암호화하면 암호문 블록의 일치가 일어나기 시작하므로, 블록 길이 128비트인 AES가 사용된다. 무작위 논스를 사용할 때의 사용 횟수 상한에도 같은 사고방식이 사용된다.
일본어 명칭: 誕生日攻撃
생일 공격(Birthday Attack)은(는) 암호 기술의 기초와 응용, 정보 보안 기초 등 2개 분야의 연습 문제 2개에 나와요.
분야: 암호 기술의 기초와 응용
정답: B. 약 32 GiB
64비트 블록의 값은 2⁶⁴가지이므로, 생일 역설에 의해 약 2^(64/2) = 2³²개의 블록을 암호화하면 같은 값의 쌍이 나타날 확률을 무시할 수 없게 됩니다(2³²개에서 약 39%). 1블록은 8바이트이므로 데이터양은 2³² × 8 = 2³⁵바이트 = 32 GiB입니다. CBC 모드에서 암호문 블록이 일치하면 대응하는 두 평문 블록의 XOR을 알게 되며, 2016년에 공표된 Sweet32 공격에서는 3DES로 보호된 장시간의 HTTPS 통신에서 Cookie를 꺼낼 수 있음이 밝혀졌습니다. 블록 길이가 128비트인 AES에서는 기준이 2⁶⁴블록까지 넓어집니다.
64비트 블록의 값은 2⁶⁴가지이므로, 생일 역설에 의해 약 2^(64/2) = 2³²개의 블록을 암호화하면 같은 값의 쌍이 나타날 확률을 무시할 수 없게 됩니다(2³²개에서 약 39%).
1 GiB = 2³⁰바이트, 1 EiB = 2⁶⁰바이트로 한다. 블록 길이가 64비트인 블록 암호(3DES…이것은 '23명이 있으면 생일이 같은 두 사람이 있을 확률이 50%를 넘는다'는 생일 역설과 같은 생각으로, 생일 공격이라고 합니다.
출력이 256비트인 이상적인 해시 함수에 대해 무차별 대입로 공격할 때 필요한 계산 횟수의 기준으로, '주…블록 암호 운용 모드(Block Cipher Mode of Operation) 쿠키(Cookie) AES 해시 함수(Hash Function) 논스(Nonce) 디피-헬먼 키 교환(Diffie-Hellman Key Exchange) 봉투 암호화(Envelope Encryption) 암호 민첩성(Crypto Agility) 인증 기관(Certificate Authority) 인증 암호화(AEAD)