생일 공격

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

생일 공격(birthday attack)은 암호학적 해시 함수해시 충돌을 찾아내는 암호해독 공격으로, 생일 문제의 확률적 결과를 기반으로 한다. 생일 문제에 따르면 해시 함수의 입력값을 다양하게 할수록 해시 값이 같은 두 입력값을 발견할 확률은 빠르게 증가한다. 따라서 모든 값을 대입하지 않고도 해시 충돌을 찾아낼 확률을 충분히 크게 만들 수 있다.

이론[편집]

가지의 값을 가지는 암호학적 해시 함수 에 대해, 이고 인 두 입력값 를 찾는 것이 해시 충돌의 목표이다. 이를 찾기 위해서 가지의 입력값을 임의로 선택한 후 해시 값을 비교한다고 할 때, 해시 충돌을 찾을 확률은 다음과 같다.

를 해시 충돌을 찾을 확률이 이상이기 위한 입력값의 가짓수라고 하면 의 식에서부터 다음의 값이 유도된다.

여기에서 로 두면 를 얻는다.

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

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

외부 링크[편집]