해시 함수(Hash Function)

 

해시 함수

• 해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다.^[각주:1]
• 보통 그리 복잡하지 않은 알고리즘으로 구현되기 때문에, 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모하는 특성이 있다.
• 같은 입력값에 대해서는 같은 출력값이 보장되며, 이 출력값은 가능한 한 고른 범위에 균일하게 분포하는 특성가이 있다.
• 위 특성 때문에 다양한 목적에 맞게 설계된 해시 함수가 존재하며, 자료구조, 보안 등 다양한 분야에서 유용히 사용된다.
• 해시 함수의 질은 입력 영역에서의 해시 충돌 확률로 결정되는데, 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 된다.

해시 충돌

해시 함수는 보통 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에 입력이 다름에도 불구하고 드물게 동일한 값이 출력되는 경우도 존재한다.

이러한 경우를 '해시 충돌' 이라 하며 원칙적으로 해시 함수는 이런 어쩔 수 없는 충돌을 제외하고 의도적으로 충돌을 계산해낼 수 없어야 한다.

 

비둘기 집의 원리

$n+1$개의 물건을 $n$개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다.

n개의 비둘기집과 $n+1$마리의 비둘기가 있다고 가정한다.
만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 $n$마리의 비둘기가 존재한다.
그런데 비둘기는 모두 $n+1$마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.

 

생일 문제

사람들이 임의로 모였을 때, 그 중 생일이 같은 두 명이 존재할 확률을 구하는 문제이다.

생일의 가능한 가짓수는 365개 이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.

생일이 같은 두 사람을 찾는 것과 비슷하게, 암호화 해시값이 같은(해시 충돌) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 생일 공격(birthday attack)이라고 부른다.

https://ko.wikipedia.org/wiki/%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C

 

---

암호화 해시 함수

• 암호화 해시 함수는 해시 함수의 일종으로, 해시값으로부터 원래의 입력값과 출력값의 관계를 찾기가 어려운 성질을 가지는 경우를 말한다.
• 해시값을 망가뜨리지 않으면서 입력값을 수정하는 공격에 대해 안전해야 하며 무결성을 증명할 수 있어야 한다.^[각주:2]

암호화 해시 함수의 조건

역상 저항성(preimage reistance)

주어진 해시값에 대한 입력값을 찾는것이 계산상 어려워야 한다.즉, 제 1 역상 공격에 안전해야 한다.
이 성질은 일방향함수와 연관되어 있다.

 

제 2 역상 저항성(second preimage reistance)

메시지를 쉽게 위조할 수 없도록 하는 성질으로, 특정 해시값을 유지하면서 입력값을 변경하는 것이 어려워야 한다.
즉, 제 2 역상 공격에 안전해야 한다.

 

충돌 저항성

해시 충돌에 대해 안전해야한다. (같은 해시값을 출력하는두 개의 입력값을 찾는 것이 계산상 어려워야 한다)
(해시 함수: $H$ / 패스워드: $x, y$)

• 약한 충돌 저항성: 주어진 $x$에 대해, $H(x)=H(y)$인 $y\neq x$를 찾는 것이 어려울 때 해시 함수가 약한 충돌 저항성을 가지고 있다고 한다. 
• 강한 충돌 저항성: {$H(x)=H(y)$와 같이 같은 해시 출력 값을 갖는 $x$와 $y$를 찾는 것이 함수의 출력 값 범위 내에서 무시 가능(negligible)할 때 해시 함수 $H$는 강한 충돌 저항성을 가진다고 한다.

 

암호화 해시 함수의 사용

무결성 검증(Integrity verification)

• 메시지 혹은 문서의 무결성을 확인하기 위해 암호화 해시 함수를 사용해야한다.
  무결성을 증명하고자 하는 입력값에 대한 해시값이 사전에 확인한 해시값과 같아야한다.
• 16년 2월21일 Linux Mint에서 발생한 사건과 같은 문제들을 방지하기 위해서는 자신이 입수한 소프트웨어가 변경되었는지 홈페이지에서 제공하는 해시값과 자신이 받은 소프트웨어의 해시값을 비교해야한다.

메시지 인증코드(MAC, Message Authentication Code)

• 일반적으로, 메시지 인증은 키가 있는 해시 함수(keyed hash function)로 알려진 메시지 인증 코드(MAC, Message Authentication Code)를 사용하여 얻어진다.

전자서명 (Digital signature)

패스워드 보호(Password protection)

키 교환 알고리즘 및 공개 키 암호

1. 해시값은 해시 코드, 해시섬(sum), 체크섬 등으로도 불린다. [본문으로]
2. 암호학적 해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. [본문으로]