출력이 256비트인 이상적인 해시 함수에 대해 무차별 대입로 공격할 때 필요한 계산 횟수의 기준으로, '주어진 해시값이 되는 입력을 찾는(역상 공격)' 경우와 '같은 해시값이 되는 서로 다른 두 입력을 아무것이나 찾는(충돌 공격)' 경우의 조합으로 올바른 것은?

정답: A. 역상 공격은 약 2^256회, 충돌 공격은 약 2^128회

출력이 n비트인 이상적인 해시 함수에서는 해시값이 2^n가지 있으며, 입력을 하나 시도할 때마다 정해진 해시값과 일치할 확률은 1/2^n입니다. 그래서 역상 공격에는 대략 2^n회, n = 256이라면 약 2^256회의 계산이 필요합니다. 한편 충돌 공격에서는 어느 두 개가 일치해도 되므로, k개의 입력을 시도하면 비교할 수 있는 쌍이 약 k^2/2가지로 늘어납니다. k^2/2가 2^n에 가까워지는, k가 2^(n/2) 정도에서 충돌을 찾을 가능성이 높아지며, n = 256이라면 약 2^128회입니다. 이것은 '23명이 있으면 생일이 같은 두 사람이 있을 확률이 50%를 넘는다'는 생일 역설과 같은 생각으로, 생일 공격이라고 합니다. 이 때문에 해시 함수의 충돌에 대한 강도는 출력 비트 수의 절반으로 추정되며, 128비트 상당의 강도를 원한다면 256비트 출력이 필요합니다.