위키원
해시함수
해시함수(hash function)는 해시(hash)를 이용한 함수(function)이다.
개요
해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 출력하는 함수이다. 해시함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다. 해시함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다. 예를 들어서, DNA sequence에서 유사한 패턴을 찾는데 사용될 수도 있다. 또한 암호학에서도 사용될 수 있다. 암호용 해시 함수는 매핑된 해싱 값만을 알아가지고는 원래 입력 값을 알아내기 힘들다는 사실에 의해 사용될 수 있다. 또한 전송된 데이터의 무결성을 확인해주는 데 사용되기도 하는데, 메시지가 누구에게서 온 것인지 입증해주는 HMAC를 구성하는 블록으로 사용된다. 해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다) 해시 함수의 질은 입력 영역에서의 해시 충돌 확률로 결정되는데, 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 된다. 해시함수중에는 암호학적 해시함수(Cryptographic Hash Function)와 비암호학적 해시함수로 구분되곤 한다. 암호학적 해시함수의 종류로는 MD5, SHA계열 해시함수가 있으며 비암호학적 해시함수로는 CRC32등이 있다. 암호학적 해시함수는 역상, 제2역상, 충돌쌍에 대하여 안전성을 가져야 하며 인증에 이용된다 . 암호학적 해시함수는 임의의 길이를 입력 받기는 하지만 MD Strength Padding할 때 길이정보가 입력되므로 최대 길이에 대한 제한이 있다. 예를 들어 패딩시 하위 8비트에 길이정보가 입력 되는 경우에는 해시가능한 최대 길이는 0xFF가 되어 255바이트가 된다.(실제 길이정보는 패딩방식에 따라 다를 수 있다)[1]
특징
- 일방향 함수(one-way function)으로 다양한 길이의 입력을 고정된 짧은 길이의 출력으로 변환하는 함 수로 데이타의 무결성 검증, 메세지 인증에 사용한다
- 다양한 가변 길이의 입력에 적용될 수 있어야 한다.
- 고정된 길이의 출력을 만든다.
- 주어진 입력값을 해시하는 것은 쉽다.
- 해시 결과값으로 입력값을 계산하는 것은 불가능 하다.
- 동일한 해시값을 가지는 서로 다른 메시지 쌍이 없다.[2]
종류
- SNEFRU : 1990년 R.C.Merkle에 의해 제안됬다. 128/254 bit 암호화 알고리즘이다.
- N-HASH : 1989년 일본 NTT의 미야구치 등이 발표했다.
- MD4 : 1990년 Ron Rivest에 의해 개발된 MD5의 초기 버전으로서, 입력 데이터(길이에 상관없는 하나의 메시지)로부터 128비트 메시지 축약을 만듦으로써 데이터 무결성을 검증하는데 사용되는 알고리즘이다.
- MD5 : 1992년 Ron Rivest에 의해 개발. MD5는 널리 사용된 해시 알고리즘이지만, 충돌 회피성에서 문제점 이 있다는 분석이 있으므로 기존의 응용과의 호환으로만 사용하고 더 이상 사용하지 않도록 하고 있다.
- SHA : 1993년에 미국 NIST에 의해 개발되었고 가장 많이 사용되고 있는 방식이다.
SHA1은 DSA에서 사용하도록 되어 있으며 많은 인터넷 응용에서 default 해시 알고리즘으로 사용된다. SHA256, SHA384, SHA512 는 AES의 키 길이인 128, 192, 256 비트에 대응하도록 출력 길이를 늘인 해시알고리즘이다.
- RMD : RMD128, RMD160는 RIPE 프로젝트의 RIPEMD나 MD4, MD5를 대신하기 위하여 디자인된 해시 알 고리즘이다. 128 비트의 출력을 내는 RMD128은 역시 충돌 회피성에서 문제점이 있다. RMD160은 효 율성은 떨어지지만 안전성을 높인 것으로 많은 인터넷 표준들에서 널리 채택되고 있다. RMD256과 RMD320은 각각 RMD128과 RMD160을 확장한 것이다.
- TIGER : TIGER는 64 비트 프로세서에 최적화되어서 64 비트 프로세서에서는 매우 빠르다.[2]
활용
블록체인에서는 해시함수를 3가지 목적으로 활용한다. 첫째, 공개키의 해시값을 지갑 주소로 활용하여 익명화된 거래를 수행하고, 가상화폐의 전자지갑 주소는 공개키 기반 암호화 알고리즘에서 생성된 공개키의 해시값을 사용한다. 개인정보(송신자의 계좌정보) 없이 익명화된 거래를 통해 송금자의 신원을 감추고, 송금할 수 있다. 둘째, 해시함수를 사용하여 2가지의 무결성 검증에 사용된다. 하나는 체인으로 연결된 블록 헤더의 해시값을 활용하여, 해시값 체인으로 연결된 블록의 무결성 검증에 사용된다. 또 다른 무결성 검증은 각 블록의 전체 거래를 하나의 해시값(머클루트)으로 저장하고, 필요할 경우에는 언제든, 해당 블록의 머클루트 값으로, 블록 내에 포함된 개별 거래의 위변조 여부를 검증할 수 있다. 모든 거래 데이터의 해시값을 머클트리(Merkle Tree)를 이용하여 만들어지는 머클루트에 저장하고, 향후 거래 내역의 위변조 여부를 검증할 때, 원본 해시값과 비교를 통하여, 각 거래의 무결성을 검증할 수 있다. 또한 머클루트는 1MB로 크기가 제한된 비트코인의 각 블록의 크기를 효율적으로 사용할 수 있게 해준다. 전체 거래내역을 다 저장할 필요 없이, 머클루트라는 한 개의 해시값만 저장하면, 해당 블록 내의 모든 거래내역의 진위를 필요할 때, 비교할 수 있기 때문이다. 셋째, 합의 알고리즘에서 PoW(Proof of Work) 방식을 사용할 경우, 해시값을 활용한 채굴 문제에 활용한다. 해시값을 활용한 채굴 문제를 먼저 맞히는 채굴자에게 채굴 권한과 보상을 제공한다. 해시캐시(Hashcash) 문제 풀이를 통한 작업증명(PoW)은 채굴(Mining)이라고도 하는데, 채굴자에 대한 보상을 통해, 채굴을 경쟁하고, 채굴자가 자율적으로 새로운 블록을 생성하도록 유도한다.[3]
해시충돌
해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시충돌은 항상 존재한다. 해시충돌은 해시함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시충돌이 자주 발생하지 않도록 구성되어야 한다. 암호학적 해시함수의 경우 해시 함수의 안전성을 깨뜨리는 충돌 공격이 가능할 수 있기 때문에 의도적인 해시 충돌을 만드는 것이 어려워지도록 만들어야 한다.[4]
각주
- ↑ 〈해시 함수〉,《위키백과》
- ↑ 2.0 2.1 그누우우우우,〈해쉬함수의 종류와 특징〉,《솔데스크》, 2009-12-23
- ↑ 김종현, 〈블록체인의 암호기술: 해시함수 활용〉,《브런치》, 2018-08-02
- ↑ 〈해시 충돌〉,《위키백과》
참고자료
- 〈해시 함수〉,《위키백과》
- code Dragon, 〈해쉬함수, 해쉬함수의 성질, 해쉬함수 특징, 전자서명에 이용되는 해쉬 함수의 특성〉,《티스토리》
- 티핀, 〈해시(Hash)함수란?(이해편)〉,《네이버 블로그》, 2011-10-15
- 〈해시〉,《나무위키》
- 그누우우우우,〈해쉬함수의 종류와 특징〉,《솔데스크》, 2009-12-23
- 김종현, 〈블록체인의 암호기술: 해시함수 활용〉,《브런치》, 2018-08-02
- 〈해시 충돌〉,《위키백과》
