해시 충돌

보안상의 이유로 TU Delft는 많은 방의 문에 숫자 키패드가 달린 자물쇠를 설치하려고 한다. 각 방에는 고유한 비밀번호가 있다. 모든 비밀번호를 저장할 서버를 구축하는 일은 Harry와 Sharon에게 맡겨졌다.

사이버 보안 수업을 들은 두 사람은 비밀번호를 저장하기 전에 해시 함수에 여러 번 통과시키는 것이 좋다는 것을 안다.

Sharon은 방 번호를 비밀번호를 해시 함수에 통과시키는 횟수로 쓰자고 제안했다. 그러면 비밀번호가 같은 두 방이라도 해시 값이 반드시 같지는 않다. 그런데 방 번호와 비밀번호의 조합에 따라 해시 값이 원래 비밀번호와 같아지는 경우가 있어, 보안상 위험하다.

Harry는 역할을 바꾸자고 제안했다. 비밀번호를 방 번호에 해시 함수를 적용하는 횟수로 쓰는 것이다. $c$를 비밀번호, $r$을 방 번호라고 하면 해시 값은 $f^c(r) = \underbrace{f(\cdots f(}_{c \mathrm{times}}r)\cdots)$이다.

Sharon은 함수 $f$가 무엇이든 $f^c(r) = c$를 만족하는 방 번호와 비밀번호가 항상 존재한다고 주장했다. $f$의 세부 사항을 몰라도 그런 쌍을 두 개 찾는 것은 어렵지 않다고 덧붙였다.

Harry는 Sharon이 자기 제안을 질투해서 그런다고 생각했고, 논쟁은 결론 없이 끝났다. 그래서 Harry는 Sharon에게 주장을 증명해 보라고 했다. Harry는 자신이 고른 비밀 해시 함수 $f$를 사용해, 질의로 받은 $c$와 $r$에 대한 해시 값 $f^c(r)$을 돌려주는 프로그램을 작성했다. 이 해시 함수는 $n$이 주어졌을 때 $\{1,\dots,n\}$에 속하는 임의의 $r$을 받고, 같은 범위의 값을 돌려준다. $c$의 값도 같은 범위에 있어야 한다. Sharon의 과제는 제한된 횟수의 질의만으로 $f^c(r) = c$를 만족하는 $c$와 $r$을 찾는 것이다.

당신은 Sharon의 주장이 옳다는 것을 알고 있으며, 그녀를 돕기로 한다.