해시함수

해시함수(hash function)란 임의의 길이를 가진 입력 데이타를 고정된 길이를 갖는 값으로 매핑하는 함수를 일컫는다. 해시함수는 크게 암호학적 해시함수와 비암호학적 해시함수로 나눌 수 있다. 암호학에서 사용하는 해시함수는 특별히 암호학적 해시함수(Cryptographic Hash Function) 라고 불리우는데, 이는 임의의 데이타를 고정된 길이의 비트 배열로 변환하는 기능을 가진다.

암호학적 해시함수는 특히 2개의 서로 다른 입력이 동일한 해시값을 생산하는 것이 계산적으로 불가능해야 하는데, 이를 충돌 저항성(Collision resistance)이라 한다. 또한, 암호학적 해시함수는 입력값이 아주 조금 변경되더라도 전혀 다른 해시값을 생성해야 하는데, 이를 눈사태 효과(Avalanche effect)라고 부른다. 예를 들어, 백만비트를 입력받아 해싱을 할 때, 동일한 입력 중 한 비트만 변경해도 해시 결과가 전혀 다른 값으로 출력되는 것을 눈사태 효과라 한다.

암호학에서의 해시함수는 일방향 함수(One-way function)로서 해시값을 보고 원래의 데이타를 찾는 것이 실용적으로 불가능한 함수이다. 즉, 암호화 알고리즘과 달리 해시는 일방향으로 변형되기 때문에, 해시값으로부터 원래의 값을 찾는 것이 실용적으로 불가능하다. 여기서 실용적으로 불가능하다는 것은 이론적으로 불가능하다는 의미가 아니라 아주 오랜 시간 동안^{(예를 들어, 수백년)} 실행해야 결과를 얻을 수 있다는 것을 의미한다. 암호학에서 해시함수는 디지탈 서명, 메시지 다이제스트, 메시지 인증 코드, 파일 체크섬 검증, 블럭체인 등 매우 다양한 분야에서 사용되는데, 특히 데이타의 내용이 변조 되었는지를 확인하기 위해^{(데이타 무결성)} 많이 사용된다.

해시함수는 기본적으로 긴 데이타(L)를 압축하여 작은 데이타(S)로 만드는 기능을 갖는다. 긴 데이타 L을 작은 데이타의 공간 S에 넣는 방법은 여러 가지가 있을 수 있는데, 예를 들어 아주 단순하게는 L의 일부 비트들을 발췌하여 S에 넣을 수 있다. 이 경우 만약 L이 100 비트이고 S가 10 비트이면, L의 10번째 마다 비트들을 골라 S에 넣을 수 있을 것이다. 그러나, 이러한 단순한 방식은 해커에 의해 쉽게 이용될 수 있다. 즉, 해커는 다른 비트들은 바꾸면서 10번째 비트들을 건들지 않으면 다른 입력 데이타로 동일한 해시값을 생성할 수 있을 것이다. 해시함수는 이렇게 해커가 쉽게 다른 입력 데이타로 동일한 해시값을 도출하지 못하도록 하는 변환 과정을 수행해야 하며, 이를 위해 통상 여러 라운드의 치환과 전치를 수행하게 된다.

해싱은 일반적으로 긴 데이타 L을 일정한 블럭 크기로 잘라 이로부터 압축된 작은 데이타 S를 생성하고, 다음 블럭과 이전의 S를 혼합하여 다시 새로운 압축 해시 S를 생성하는 식의 블럭암호 운용 방식을 사용한다. 이러한 방식의 해싱은 Merkle–Damgård 해시함수로 불리우는데, 일반적으로 많이 사용되는 MD5, SHA1, SHA2 등이 이러한 방식을 사용하고 있다.

해시함수의 종류

암호학적 해시함수는 여러 가지 종류들이 있는데, 그 중 많이 사용되는 해시함수는 다음과 같다.

• MD5 : MD5는 (RSA를 개발했던) Ronald Rivest에 의해 1991년 개발된 해시함수이다. MD5는 128bit (16 바이트) 해시값을 생성하는데, 현재는 보안상 안전하지 않아 잘 사용되지 않고 있다.
• SHA-1 : SHA-1 (Secure Hash Standard 1)은 1995년 미국 NSA에서 발표한 해시함수로서 160bit (20 바이트)의 해시값을 생성한다. SHA-1은 SSL/TLS, SSH, IPSec 등을 비롯하여 기존의 많은 프로그램들에서 사용되고 있다. SHA-1은 이론적으로 보안상의 문제가 생길 수 있다고 여겨지고 있고, 따라서 현재는 SHA-256 이상을 사용할 것을 권장하고 있다.
• SHA-2 : SHA-2 (Secure Hash Standard 2)는 2001년 미국 NSA에서 발표한 해시함수로서 SHA-224, SHA-256, SHA-384, SHA-512 등의 4가지 변형이 있는데, 이 중 SHA-256와 SHA-512가 주로 사용된다. 해시값의 크기는 SHA-* 뒤에 명시되어 있는데, 예를 들어 SHA-256 는 256bit (32 바이트), SHA-512는 512bit (64 바이트)의 해시값을 생성한다. SHA-256은 현재 가장 널리 사용되는 해시함수 중의 하나이다. 비트코인은 Merkle Tree를 빌드하거나 블럭체인을 구성하기 위한 Mining 해시함수로 SHA-256을 사용하고 있으며, 기타 암호화폐의 여러 부분에서도 SHA-256을 많이 사용하고 있다.
• SHA-3 : SHA-3 (Secure Hash Standard 3)는 2015년 미국 NIST에서 발표한 해시함수로서 SHA-2와 동일하게 4개의 224, 256, 384, 512 비트의 해시값을 생성하는데, SHA-3는 SHA-2와 다른 해시 알고리즘(Keccak)을 사용한다.
• RIPEMD : RIPEMD (RACE Integrity Primitives Evaluation Message Digest)는 1992년 유럽의 RIPE 프로젝트에 의해 처음 개발되었는데, 초기의 RIPEMD는 보안상의 문제점을 가지고 있었다. 이후 1996년 벨기에의 Hans Dobbertin를 비롯한 연구진이 보안상의 문제를 보완하여 RIPEMD-128, RIPEMD-160, RIPEMD-256, RIPEMD-320 등 4가지 변형을 발표하였으며, 이 중 RIPEMD-160이 가장 많이 사용되고 있다. RIPEMD-160은 160bit (20 바이트)의 해시값을 생성하는데, 한 예로 비트코인에서 주소를 생성할 때 SHA-256과 함께 RIPEMD-160 해시함수를 사용하고 있다.

참고로, C# / .NET Framework에서의 해시함수들은 아래와 같은 계층 구조를 가지고 있다.

아래 예제는 SHA256 해시값을 생성하여 이를 16진수 문자열로 출력하는 예이다. SHA256은 출력으로 32 바이트 해시값을 생성한다.

public static void SHA256Hash()
{
    string s = "Hello World";
    byte[] bytes = Encoding.UTF8.GetBytes(s);
    byte[] hash;
    using (var sha2 = SHA256.Create())
    {
        hash = sha2.ComputeHash(bytes);
    }

    string hex = BitConverter.ToString(hash)
                    .Replace("-", "");
    Console.WriteLine(hex);

    var exp = "A591A6D40BF420404A011733CFB7B190D62C65BF0BCDA32B57B277D9AD9F146E";
    Console.WriteLine(hex.SequenceEqual(exp));
}