해시 함수의 특성(충돌 저항성 등)

핵심 정리

해시 함수는 임의 길이의 입력 데이터를 받아 고정 길이의 해시값을 만드는 함수다. 해시는 메시지의 무결성을 확인하는 데 사용한다. 원문 전체 대신 짧은 해시값을 보관하면, 나중에 원문에서 다시 계산한 해시값과 비교해 원문이 바뀌었는지 가려낼 수 있다.

암호학적 해시 함수가 갖추어야 할 성질은 일방향성과 충돌 저항성, 그리고 계산 효율성이다. 일방향성은 해시값으로부터 입력을 되돌리기 어려운 성질이다. 이 성질은 해시값으로부터 원래 입력을 계산적으로 찾기 어려워야 한다는 역상 저항성과 같은 방향의 요구다. 해시 함수는 출력으로부터 입력을 복원하기 어려운 일방향 함수이므로 데이터 암복호화에는 적합하지 않다.

충돌 저항성은 같은 해시 값을 내는 서로 다른 두 입력을 찾기 어려운 성질이다.충돌 저항성은 같은 해시 값을 내는 서로 다른 두 입력을 찾기 어려운 성질이다. 충돌 저항성이 무너지면 같은 해시값을 가진 다른 데이터로 원본을 바꿔 치는 공격이 가능해진다. 해시 함수가 이 성질들을 갖추지 못하면 공격자가 해시값만으로 원본을 위조하거나 바꿔치기할 수 있으므로, 해시를 전자서명이나 무결성 검사에 쓸 수 없게 된다.

해시 함수는 임의 크기 데이터의 해시값을 효율적으로 계산할 수 있어야 한다. 계산이 지나치게 무거우면 대량의 데이터를 처리하거나 무결성 검사를 자주 수행하기 어려워진다.

자세히

역상 저항성과 제2 역상 저항성

역상 저항성은 해시값만 주어졌을 때 그 값을 만드는 입력을 찾기 어려운 성질이다. 제2 역상 저항성은 입력 하나와 그 해시값이 주어졌을 때 같은 해시값을 내는 다른 입력을 찾기 어려운 성질이다. 두 성질은 입력을 찾는 방향이 다르다. 역상 저항성은 해시값만 알고 있을 때의 공격에 대응하고, 제2 역상 저항성은 이미 알려진 입력을 바꾸면서 해시값을 유지하려는 공격에 대응한다. 두 성질을 한눈에 비교하면 다음과 같다.

표의 세 성질 가운데 충돌 저항성이 가장 강한 요구에 해당한다. 해시 함수가 충돌 저항성을 만족하면 제2 프리이미지 저항성도 만족한다. 따라서 충돌 저항성을 확보하면 제2 역상 저항성도 자동으로 만족한다. 반대 방향은 성립하지 않으므로, 제2 역상 저항성만 있다고 해서 충돌 저항성도 있다고 보면 안 된다.

충돌 저항성의 두 가지 기준

충돌 저항성은 두 가지 기준으로 나누어 볼 수 있다. 특정한 입력 하나를 정해 두고 그와 같은 해시값을 내는 다른 입력을 찾기 어려운 성질은 약한 충돌 저항성이다. 약한 충돌 저항성은 주어진 패스워드를 기준점으로 삼아 같은 해시값을 내는 다른 패스워드를 찾는 상황과 연결된다. 반면 상대를 정하지 않고 같은 해시값을 내는 임의의 두 입력을 찾기 어려운 성질은 강한 충돌 저항성이다. 약한 충돌 저항성은 입력 하나가 기준점이 되므로 요구 범위가 좁고, 강한 충돌 저항성은 입력 쌍 전체를 대상으로 하므로 요구 범위가 넓다. 시험에서는 이 둘을 구별해야 한다.

고정 길이 출력

입력이 짧든 길든 해시값의 길이는 같아야 한다. 입력이 한 바이트든 대용량 파일이든 출력의 길이는 같으므로, 해시값을 보관하는 저장소의 크기를 미리 정해 둘 수 있다. 해시 함수는 입력 데이터의 길이와 관계없이 고정 길이의 해시값을 생성한다. 긴 파일도 짧은 해시값으로 바꾸어 비교할 수 있다는 점이 이 성질의 실용적 가치다. 고정 길이 출력은 해시 함수가 입력을 요약하는 방식을 결정하는 조건이다.

효율성과 구현

해시 함수는 하드웨어와 소프트웨어 모두에서 실용적으로 구현될 수 있어야 한다. 효율성은 안전성과 별개의 요건이다. 안전성이 아무리 높아도 계산이 느리면 실제 시스템에서 쓸 수 없다. 계산 과정이 비교적 쉬워야 한다는 요구도 같은 이유에서 나온다.