해시 알고리즘

정의

해시 함수는 임의 길이의 데이터를 고정 길이의 해시값으로 바꾸는 함수다.

같은 데이터는 언제나 같은 해시값을 내고, 데이터가 조금만 바뀌어도 해시값이 크게 달라진다.

해시값만 보고 원래 데이터를 되살릴 수는 없다.

네 가지 성질

해시 함수의 핵심 성질은 네 가지로 정리된다.

단방향성은 해시값에서 원래 입력을 복원하기 어려운 성질이다.

역상 저항성은 주어진 해시값을 내는 입력을 찾기 어려운 성질이다.

제2 역상 저항성은 특정 입력과 같은 해시값을 내는 다른 입력을 찾기 어려운 성질이다.

충돌 저항성은 같은 해시값을 내는 서로 다른 두 입력을 찾기 어려운 성질이다.

충돌은 반드시 존재한다

해시값의 길이는 n비트로 고정되어 있어 가능한 출력은 2의 n제곱 개다.

입력 집합이 출력 집합보다 크면 비둘기집 원리에 따라 충돌은 반드시 존재한다.

그래서 안전성은 충돌이 있느냐가 아니라 찾기가 얼마나 어려우냐로 평가한다.

해시값 생성 절차

앞 문제의 정답은 입력 집합이 출력 집합보다 클 때다.

해시 함수는 메시지를 패딩으로 블록 배수에 맞춘 뒤 블록으로 나눈다.

SHA-2 기준으로 512비트 블록을 압축 함수에 넣어 내부 상태를 갱신한다.

앞 블록의 상태가 다음 블록으로 넘어가는 구조를 머클-담골 구조라 한다.

마지막 상태를 출력하면 고정 길이의 해시값이 된다.

알고리즘 비교

MD5는 128비트 출력이며 보안 용도로는 사용하지 않는 것이 권장된다.

SHA-1은 충돌 공격이 발견되어 신규 사용이 금지된다.

현재 권고는 SHA-2 계열인 SHA-256, SHA-512와 SHA-3 계열이다.

SHA-2가 SHA-1보다 안전한 이유는 출력이 길어 생일 공격 비용이 커지기 때문이다.

정리와 헷갈리는 점

해시 함수와 암호화는 방향이 다르다. 해시 함수는 복호화 자체가 정의되지 않는다.

그래서 해시는 기밀성 목적에는 쓸 수 없고 무결성 목적에만 쓴다.

답안에는 해시 함수는 알고리즘, 해시값은 그 출력이라고 구분해 적는다.

정리하면 해시 함수는 단방향이며 충돌 저항성을 갖추고, 현재는 SHA-256 이상을 권고한다.