위키원
해시함수
해시함수(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]
충돌 예방법
체이닝
충돌을 허용하지만 이를 최소화 하기 위한 방법 중 하나가 바로 체이닝 방식이다. 체이닝이란 이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, 해시 테이블에선 동일한 해시값이 출력되 충돌이 일어나면, 그 위치에 있던 데이터에 키값을 포인터로 뒤이어 연결한다. 따라서 최초로 저장된 데이터를 시작으로 그 이후의 값이 출력되는 데이터는 모두 연결 리스트의 형태를 취한다. 그렇기 때문에 최초의 위치를 탐색하는 해시과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행된다. 체이닝 방법에서의 수행시간은 삽입 시에는 해시값을 이용해 바로 슬롯에 저장하면 되므로 상수시간에 일어나고, 삭제는 연결리스트의 삭제와 동일하게 상수시간에, 탐색시에는 연결리스트를 따라 가기 때문에 리스트의 길이 만큼 발생하지만, 최악의 경우 즉, 모든 데이터의 해시값이 일치하여 한 인덱스에 저장됬을 경우엔 연결리스트의 탐색시간과 동일한 선형시간을 가지게 된다.
Open Addressing
Open Addressing은 키값을 테이블에 저장하는 Direct Addressing Table과는 다르게, 모든 데이터를 테이블에 저장하는 방식이다. 데이터를 직접 모두 읽어 오기 때문에, 포인터를 쓸 일이 없어 포인터를 사용함으로써 발생할 수 있는 오버헤드를 방지할 수 있고, 포인터가 필요없기 때문에 구현이 훨씬 용이해졌으며, 포인터 접근에 필요한 시간이 없기 때문에 큰 성능 향상이 있다.
- 선형탐사
포인터를 사용하지 않기 때문에, 다른 방법으로 충돌시에 대처해야 하는데 그 중 하나가 선형탐사이다. 선형탐사는 키값으로 인덱스를 계산할 때, 만약 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식이다. 다음으로 이동한 후에도 충돌이 발생했다면 또 다시 바로 다음 인덱스에 저장한다. 즉, 충돌이 일어나지 않을 때 까지 계속해서 다음 인덱스로 이동을 해가며 빈 공간을 찾아 그 위치에 저장하는 방식이다. 이러한 방식은 충돌이 나면 뒤에 있는 슬롯에 데이터를 넣어 하나의 데이터 덩어리를 이루기 때문에, 데이터들의 특정 위치에만 밀집하는 현상인 primary clustering이 일어날 수 있다. 슬롯이 점점 많아지면 많아질수록 탐색 하는데 걸리는 시간이 엄청나게 많이 소요되게 되는 것이다.
- 제곱탐사
제곱탐사는 primary clustering을 방지하기 위해 해시함수를 2차식의 형태로 만드는 것이다. 선형탐사와는 달리 2차식의 형태를 취했기 때문에 한 칸씩 이동하는 것이 아닌 {\displaystyle n^{2}} {\displaystyle n^{2}}칸 만큼 이동하는 방식이다(n은 충돌 횟수). 하지만 처음 시작 해시값이 같을 경우, 그 이후의 해시값들도 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어나는 secondary clustering이라는 단점이 있다.[5]
- 이중해시
제곱탐사의 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 방법이다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다. 이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라고 최초 해시값이 달라져 clustering을 모두 완화할 수 있다.[6]
각주
- ↑ 〈해시 함수〉,《위키백과》
- ↑ 2.0 2.1 그누우우우우,〈해쉬함수의 종류와 특징〉,《솔데스크》, 2009-12-23
- ↑ 김종현, 〈블록체인의 암호기술: 해시함수 활용〉,《브런치》, 2018-08-02
- ↑ 〈해시 충돌〉,《위키백과》
- ↑ 화투, 〈해시 알고리즘 요약정리, 태스트 코드〉, 《티스토리》, 2016-04-12
- ↑ ratsgo, 〈해싱, 해시함수, 해시테이블〉, 《개인 블로그》, 2017-10-25
참고자료
- 〈해시 함수〉,《위키백과》
- code Dragon, 〈해쉬함수, 해쉬함수의 성질, 해쉬함수 특징, 전자서명에 이용되는 해쉬 함수의 특성〉,《티스토리》
- 티핀, 〈해시(Hash)함수란?(이해편)〉,《네이버 블로그》, 2011-10-15
- 〈해시〉,《나무위키》
- 그누우우우우,〈해쉬함수의 종류와 특징〉,《솔데스크》, 2009-12-23
- 김종현, 〈블록체인의 암호기술: 해시함수 활용〉,《브런치》, 2018-08-02
- 〈해시 충돌〉,《위키백과》
- 화투, 〈해시 알고리즘 요약정리, 태스트 코드〉, 《티스토리》, 2016-04-12
- ratsgo, 〈해싱, 해시함수, 해시테이블〉, 《개인 블로그》, 2017-10-25
