해쉬 함수

해쉬 함수(Hash function)

해쉬 함수는 임의의 길이를 갖는 메시지를 입력 받아 고정된 길이의 해쉬값을 출력하는 함수이다. 암호 알고리즘에는 키가 사용되지만, 해쉬 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 된다. 이러한 함수를 사용하는 목적은 입력 메시지에 대한 변경할 수 없는 증거값을 뽑아냄으로서 메시지의 오류나 변조를 탐지할 수 있는 무결성을 제공하는 목적으로 주로 사용된다.

해쉬 함수는 전자 서명과 함께 사용되어 효율적인 서명 생성을 가능하게 한다. 긴 메시지에 대해 서명을 하는 경우, 전체 메시지에 대해 직접 서명을 하는 것이 아니고 짧은 해쉬값을 계산해 이것에 대해 서명을 하게 된다. 공개키 연산은 많은 계산량을 필요로 하기 때문에 전체 메시지를 공개키 길이의 블록 단위로 나누어 모든 블록에 대해 서명을 하는 것은 매우 비효율적이다. 그러므로 먼저 메시지를 입력 받아 짧은 해쉬값을 계산하고, 이것에 대해 한 번의 서명 연산을 하는 것이다. 이 계산값은 원래의 메시지에 대한 서명으로 인정된다.

해쉬값에 대한 서명이 원 메시지에 대한 서명으로 인정되기 위해서는 같은 해쉬값을 갖는 또 다른 메시지를 찾아내기가 계산적으로 어려워야 한다. 해쉬 함수는 임의의 길이의 입력으로부터 짧은 길이의 해쉬값을 출력하므로 입력은 서로 다르지만 같은 출력을 내는 충돌이 반드시 존재한다. 만일 같은 해쉬값을 갖는 다른 메시지를 찾아내기가 쉽다면, 서명자는 자신의 서명에 대해 다른 메시지에 대한 서명이라고 우길 수 있을 것이다. 이것이 가능하다면, 전자 서명에 대한 신뢰가 불가능하고 전자 거래에 사용할 수 없게 될 것이다. 그러므로 안전한 해쉬 함수로 사용될 수 있기 위해서는 충돌을 찾아내기 어렵다는 특성을 가져야 한다.

한편, 해쉬 함수는 전자 서명에 사용된다고 했는데, 이것은 서명자가 특정 문서에 자신의 개인키를 이용하여 연산함으로서 데이터의 무결성과 서명자의 인증성을 함께 제공하는 방식이다. 메시지 전체에 대해 직접 서명하는 것은 공개키 연산을 모든 메시지 블록마다 반복해야 하기 때문에 매우 비효율적이다. 따라서 메시지에 대한 해쉬값을 계산한 후, 이것에 대해 서명함으로서 매우 효율적으로 전자 서명을 생성할 수 있다. 서명자는 메시지 자체가 아니라 해쉬값에 대해 서명을 하였지만 같은 해쉬값을 갖는 다른 메시지를 찾아내는 것이 어렵기 때문에, 이 서명은 메시지에 대한 서명이라고 인정된다.

송신자의 신분에 대한 인증이 필요 없고, 데이터가 통신 중 변조되지 않았다는 무결성만이 필요한 경우에는 해쉬 함수를 메시지인증코드(MAC, Message Authentication Code)라는 형태로 사용할 수 있다. 송신자와 수신자가 비밀키를 공유하고 있는 경우, 송신자는 메시지와 공유된 비밀키를 입력으로 하여 해쉬값을 계산하면 메시지인증코드가 된다. 메시지와 함께 메시지인증코드를 함께 보내면 수신자는 메시지가 통신 도중 변조되지 않았다는 확신을 가질 수 있다.

대표적인 해쉬 함수는 다음과 같다.

 

SHA(Secure Hash Algorithm)

최조의 알고리즘은 1993년 미국 국가 안전 보장국(NSA)이 설계하였으며, 미국 표준 기술 연구소(NIST)에 의해 SHS(Secure Hash Standard, FIPS PUB 180)으로 출판되었으며, 다른 함수들과 구별하기 위해 보통 SHA-0으로 불린다. 2년 후 SHA-0의 압축 함수에 비트 회전 연산을 하나 추가한 SHA-1(FIPS PUB 180-1)이 발표되었으며, 그 후에 4종류의 변형, 즉 SHA-224, SHA-256, SHA-384, SHA-512(FIPS PUB 180-2)가 추가로 발표되었다. 이들을 통칭해서 SHA-2라고 하기도 한다. SHA-1은 SHA 함수들 중 가장 많이 쓰이며, TLS, SSL, PGP, SSH, IPSec 등 많은 보안 프로토콜과 프로그램에서 사용되고 있다. 하지만 최근 SHA-0과 SHA-1에 대한 분석 결과가 발표됨에 따라 SHA-2를 사용할 것이 권장되고 있다.

 

HAS-160

국내에서 개발된 대표적인 해쉬 함수인 HAS-160[28]은 2000년 12월 국내 해쉬 함수 표준(TTAS.KO-12.0011/R1)으로 채택되었다. HAS-160의 설계 원리는 SHA-1의 설계 사상이 유사하지만, 메시지 확장 과정이 기존의 MD계열 해쉬 함수와는 차이가 있어, 최근 제안된 다양한 해쉬 함수 분석 기법에 대하여 아직까지는 안전성을 갖고 있다.