해시 충돌 탐지 - Birthday attack

이전에 해시함수에 대해선 한번 설명을 했다. 그럼 이번에는

이 해시함수의 해시값 충돌을 탐지하는 birthday attack 을 한번 알아보자.

 

이름이 생일? 공격인데, 왜그런가.. birthday attack 이란 이름은

birthday paradox 에서 시작한다. 

 

birthday paradox 란,

한 집단에 23명 이상의 사람이 모이면 그 중 생일이 같은 사람이 적어도 한쌍 이상 있을 확률이 1/2을 넘어간다.

라는 것을 birthday paradox라고 한다. 근데 이게 왜 paradox인데? 파라독스는 역설이란 말인데..

 

일단 가정해보자. 내가 지금 속해 있는 집단에 k명이라는 인간들이 들앉아있다.

"생일이 같은 사람이 있을 확률이 얼마나 될것 같니?" 라고 물어보면

대부분 생각이 "거의 없지 않나?" 가 나올 것이다.

하지만 이게 실제로 계산해보면 생각보다 확률이 굉장히 높다.

그래서 birthday paradox 라는 말이 나왔다.

 

이런 결과가 왜나오냐면, 항상 지 생일만 생각해서 그렇다 (이기적인 놈들)

내 관점에서 내 생일과 같을 확률만 계산하기 때문에 낮게 나오는 것이다.

내가 빠진 다른 사람들과의 관계도 고려를 해야 한다.

 

첫 번째는 365일 중 어떤 날을 선택할 수 있다. 확률은 1/365

두 번째는 첫 번째 사람과 다른 날을 선택해야 하며, 이 확률은 1 - 1 / 365

세 번째는 365일에서 선택할 수 있는 날이 2개 줄었으니 1 - 2 / 365  

 

 

이와 같이 23명까지 전개해보면,

1 * (1 - 1 / 365) * (1 - 2 / 365) * (1 - 3 / 365) * ... (1 - 22 /365) = 0.493

 

서로 생일이 다를 확률이 0.493 이니까

생일이 같은 사람이 있을 확률은 1 - 0.493 = 0.507 로 50%가 넘음을 알 수 있다.

 

 

이것을 일반화 해서 Birthday attack 에 적용을 시켜보자.

 

충분히 큰 숫자 M 과 (Mi, Mj) 의 쌍이 해시값이 충돌할 확률을 가지고 

 

해시 충돌을 일으키는 것이 생일공격이다.

 

N의 가능성이 있을때, 최소한 

길이의 리스트를 조사하면 중복을 발견할 확률이 50% 이상이다.

 

e.g. 64비트 해시값이 있을 때, 2^32 번 계산을 하면 중복되는 해시값이 50%가 넘는다.

중복되는 해시값을 찾았다면 다음과 같은 방법으로 birthday attack을 활용할 수 있다.

 

A가 B에게 사기를 칠라칸다. 해시값이 같은 문서를 여러가지 방법으로 조작을 하는 것이다.

이렇게 변조를 해도 birthday attack을 이용해 충돌하는 해시를 찾을 수만 있다면 사기를 칠 수 있을 것임.

 

참고 url: http://celdee.tistory.com/226