충돌 저항성(Collision Resistance)

0 / 4

충돌 저항성이란

충돌 저항성은 해시값이 같은 서로 다른 두 입력, 곧 충돌을 찾아낼 수 없다는 성질입니다. 강한 충돌 저항성이라고도 합니다. 제2 역상과 달리 공격자가 두 입력을 모두 고를 수 있어서, 공격이 더 쉽고 그만큼 지키기 어려운 성질입니다.

주황 줄은 공격자가 고른 입력입니다. 그 아래에 서로 비교한 쌍의 수를 셉니다.

1 / 4

두 입력을 모두 고른다

공격자는 vote yes와 vote no처럼 두 입력을 자유롭게 고를 수 있습니다. 이 둘은 해시값이 다릅니다. 정해진 해시값을 맞힐 필요 없이 아무 두 입력이든 같기만 하면 성공입니다.

2 / 4

입력이 늘면 쌍이 빠르게 는다

입력 4개를 모으면 비교할 쌍이 6개가 됩니다. k개를 모으면 쌍은 약 k²/2개라, 해시값이 2^256가지여도 약 2^128개를 모으면 충돌이 나올 만합니다. 23명만 모여도 생일이 같은 두 사람이 있을 확률이 절반을 넘는 생일 역설과 같습니다.

3 / 4

충돌이 있으면 바꿔치기할 수 있다

해시값이 같은 계약서 두 장을 만들 수 있다면, 무해한 쪽에 서명을 받은 뒤 다른 쪽으로 바꿔도 서명이 그대로 맞습니다. 충돌 저항성을 갖춘 해시 함수는 제2 역상 저항성도 함께 갖춥니다.

4 / 4

MD5와 SHA-1은 깨졌다

MD5는 2004년, SHA-1은 2017년에 실제 충돌이 발견되어 보안 용도로 쓰지 않습니다. 지금은 SHA-256 같은 SHA-2나 SHA-3을 씁니다.