해시
[include(틀:프로젝트 문서, 프로젝트=나무위키 암호화폐 프로젝트)] [include(틀:다른 뜻)]
* # - 넘버 사인 * Hesh - 점착유탄 * 감자 요리 - 해시 브라운 * --해시스완--
[목차]
Hash Function
개요
해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다. 이 값은 또한 해시 코드, 해시섬(sum), 체크섬[* 의미는 살짝 다르지만 해시가 체크섬과 동일한 목적으로 사용되는 경우도 많기는 하다.] 등으로도 불린다.
해시 함수는 보통 그리 복잡하지 않은 알고리즘으로 구현되기 때문에, 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모하는 특성이 있다. 그리고 같은 입력값에 대해서는 같은 출력값이 보장되며, 이 출력값은 가능한 한 고른 범위에 균일하게 분포하는 특성이 있다. 특수 목적용으로 해시값을 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력값을 가지게 하는 해시 함수도 존재한다.
해시 함수는 보통 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에 입력이 다름에도 불구하고 드물게 동일한 값이 출력되는 경우도 존재한다. 자세한 원리는 비둘기 집의 원리와 [문제] 참조. 이러한 경우를 '충돌'한다고 한다. 원칙적으로 해시 함수는 이런 어쩔 수 없는 충돌을 제외하고 의도적으로 충돌을 계산해낼 수 없어야 한다. 간단한 설명은 위키백과의 [저항성] 부분 참조.
이러한 특성에 힘입어 다양한 목적에 맞게 설계된 해시 함수가 존재하며 다음과 같은 다양한 분야에서 매우 유용하게 사용된다.
* 자료구조 * 해시 테이블 (또는 해시 맵) * 해시셋(set) * 블룸 필터(Bloom filter) * 캐시 * 중복 레코드 검색 * 유사 레코드 검색 * 유사 부분 문자열 검색 * 기하학적 해시 * 변조 탐지/에러 검출[* 오픈소스 프로그램을 다운받을 때 md5sum, sha1sum, sha256sum 등으로 bacc82b32fe8b8b45c9225f129196943 과 같은 이상한 문자열을 같이 표기해 놓은 것을 볼 수 있다. 그 문자열이 이 목적으로 사용되는 해시값이다.]
근래에 나오는 언어들은 기본 라이브러리에 해시 함수가 포함되어 있는 경우가 많아서 굳이 구현할 필요 없이 바로바로 해시 값을 추출해서 사용할 수 있다. 다만 좀 오래된 언어들은 확장 라이브러리를 설치하거나 직접 구현하는 식으로 해결해야 한다. 파이썬의 경우에도 사전에 클래스를 넣기 위해서는 해시 함수를 구현해야 하는데, 해시 함수와 함께 비교함수(cmp)도 구현해야 한다. 만약 해시 함수가 구현되어 있지 않다면 그 객체의 주소값을 해시 값으로 대체한다.
유명한 해시 알고리즘으로 Message-Digest Algorithm(MD)과 Secure Hash Algorithm(SHA) 등이 있다. 각 알고리즘은 심각한 해시 충돌 문제 등으로 인해 해시 함수를 개선하며 발표된 순서대로 MDn, SHA-n 식으로 넘버링된다. 다만 SHA-2는 예외로, SHA-256, SHA-512를 함께 SHA-2족(SHA-2 family)이라고 부른다. 2014년 기준으로 최신 버전은 각각 MD6, SHA-3이나 보통은 자신이 사용하는 언어에서 제공하는 라이브러리에 포함된 기본 해시 함수[* MD5나 SHA-1을 기반으로 구현된 사례가 많다.]를 사용하는 편이다.
해시를 사용하는 자료 구조
색인(Index)에 해시값을 사용하는 자료 구조로, 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다.
해시는 리스트를 사용하는 접근법은 동일하지만 여기에 색인 개념이 추가되어 있다. 일단 충분히 큰 공간을 할당받은 다음 해시 함수를 이용하여 고유 색인을 생성한다. 그리고 이 고유 색인과 맞는 위치에 데이터를 저장한다.
예로 설명하면, 0 ~ 10000까지 데이터를 담을 수 있는 리스트를 생성하고, '나무위키'란 단어에 해시 함수를 적용하여 2642란 색인이 생성되면 리스트 2642번 색인에 '나무위키'를 저장하는 방식이다. 해시 함수는 언제나 동일한 해시 값을 반환하기 때문에 '나무위키'를 입력하면 항상 2642란 색인이 나오므로 굳이 정렬하지 않고도 바로 찾을 수 있게 되는 셈. 단, 이러한 목적으로 사용하는 해시 함수는 해시값을 계산하는 비용이 기존 검색 알고리즘에 비해 훨씬 적고 뛰어나야 한다는 전제 조건이 붙는다. 그렇지 않다면 이러한 방법을 사용하는 의미가 없다.
위에서 언급한 것처럼 해시값이 충돌하는 경우가 발생하여 같은 색인이 만들어질 수도 있다. 예를 들어 나중에 입력된 '위키위키' 단어를 해시 함수에 넣었더니 2642란 색인으로 나온다면 '나무위키'와 동일한 색인을 가지게 되는 문제가 발생한다. 이 경우 보통 사용하는 방법은 두 가지 정도인데, 하나는 리스트의 각각의 색인을 연결 리스트[* 트리를 사용하기도 한다. Java8의 해시맵은 Red-Black 트리를 이용하여 체이닝(Chaining) 한다.]로 만들어서 새로 입력이 될 때마다 분리 연결법(Separate Chaining)과 다음에 위치한[* 꼭 +1번째를 말하는 것은 아니다. 현재 색인이 2642일때 다음이 2643이 될 수도 있고 2650이 될 수도 있다. 보통은 규칙적으로 넣는 편으로 1, 2, 3, ... 처럼 +1 하는 방식인 선형 탐색법(Linear Probing), 1, 2(=1+1), 6(=2+4), 15(=6+9), ... 처럼 n의 제곱을 더하는 방식인 2차 탐색법(Quadratic Probing), 추가적인 해시값으로 다음 위치를 결정하는 2중 해싱(Double Hashing) 등이 있다.] 색인들 중 비어있는 곳에 넣는 방식인 개방 주소법(Open Addressing) 등이 있다.
이렇게 충돌 해결을 한다고 해도 결과적으로 충돌로 인한 성능 저하는 막을 수 없다. 그래서 수용률이 일정량을 넘어가게 되는 경우에는 아예 리스트 자체의 크기를 키운 뒤에 재배열을 하는 방법을 사용한다. 다만, 이 과정 자체가 상당히 비용이 많이 드는 과정이라서 실시간으로 빠르게 처리해야되는 환경에서는 무리가 있을 수 있다. 이럴 때는 큰 리스트를 하나 더 만들어서 적당한 타이밍에 몇 개씩 점진적으로 옮기다가 다 옮기면 기존의 테이블을 없애 확장하는 방식도 있기는 하다. 다만 이 경우에는 메모리를 훨씬 더 많이 사용하게 된다.
자료를 기본적으로 정렬하지 않은 상태로 저장하기 때문에 정렬된 순서로 접근하는 것은 비용이 매우 많이 들며 순회를 하는 경우에도 무효한 값들이 많아 실제 데이터의 갯수만 순회하는 것보다 더 많은 비용이 들게 된다. 그리고 부하의 임계점을 적으면 50%, 많아봐야 75% 정도로 잡기 때문에 실제 데이터의 양보다 메모리를 많이 쓰게 된다.
보안과 해시
해시는 보안 분야에서도 널리 사용되는데 이는 해시 함수가 원래의 문장을 복호화할 수 없게 뭉개버린다는 장점, 그리고 원문과 해시값 사이에 선형적 관계가 없다는 특성을 지니고 있기 때문이다. 해시 함수의 결과물은 고정된 길이의 숫자이므로, 원래의 정보는 손실된다.[* 예컨대 1GB짜리 데이터도 SHA-1 해시 함수에 넣으면 고작 40자리의 16진수 해시값으로 변환된다.] 또한 이런 특성 때문에 하나의 원 데이터는 하나의 해시값만 가지지만, 하나의 해시값을 만들어낼 수 있는 원본 데이터는 매우 많다. 그 때문에 해시값만 가지고는 아무리 용을 써도 이미 뭉개진 원문을 복원해내는 것은 불가능하다. 따라서 비밀번호, 전자서명, 전자투표, 전자상거래와 같은 민감한 입력의 무결성을 검증할 때 사용된다. 따라서 어떤 해시 함수에서 해시 충돌이 일어나기 쉽다는 것은 보안 분야에서는 매우 민감한 문제에 해당한다. 데이터의 무결성과 직접적인 연관이 있기 때문이다.
현재까지 개발된 거의 모든 해시 함수는 해시 충돌의 문제가 확인된 상태이다. SHA-1과 SHA-256, SHA-512는 해시 충돌의 가능성이 이론적으로 제시되었다. 2014년 기준으로 문제가 없는 해시 표준으로는 SHA-3가 유일하다. 다만 여기서 이론적으로 제시되었다는 것은 지구 전체의 연산 처리 능력을 기준으로 계산적 가능성을 따지는 것이다. 순수한 무차별 대입(Brute Force)보다 몇 천배 정도 적은 계산 횟수로 복호화할 수 있으면 학계에서는 대체로 '깼다'라고 취급한다. 그런데 예컨대 SHA-1 해시를 무차별 대입으로 깨려면 2^^160^^번의 계산을 해야 하는데, 여기서 1,000배 빨라졌다고 해 봤자 2^^150^^번의 계산이 필요하다. 즉 현실적인 의미로는, SHA-1이나 SHA-2족의 해시가 불안하다고 여기기엔 다소 무리가 있다.
채굴기의 보안 위협
SHA 해독에 그래픽카드보다 96,000배의 연산력을 보이는 ASIC, FPGA 등을 이용한 비트코인 채굴기가 개발되면서 해시 함수의 보안력이 급격히 떨어졌다.
당장 2017년 현재의 상황을 보면, 라데온 R9 290X 8대를 크로스파이어해서 사용한다고 해도 [정도의 해시레이트]가 나오는데, 1,100달러(126만 원) 정도 하는 ASIC 채굴기인 Antminer S9를 사용하면 13,500GH/s가 나온다. 그래픽카드보다 성능이 약 9만 6천 배나 더 낫다는 것이다. [* 그러나 ASIC 채굴기이기 때문에 GPU로만 채굴할 수 있는 이더리움 등은 채굴이 불가능하다.]
- 취소선을 지우기 싫다
~~사실 채굴기는 SHA-256이 아니라 80byte의 문자열을 X라고 두면 이런 연산을 한다. SHA-256(SHA-256(X))~~[* [[1]]]
- 인용표시 이유가?
>이걸로 설명끝. >이런 특별한 경우에만 채굴기를 통한 암호화 해제가 가능하다. >the hashes are generated with SHA-256(SHA-256(X)) >salt + password = 80 bytes >the hash starts with 4 zero-bytes >which will probably make them obsolete it seems like a huge waste of hardware. > >SHA-256을 2번 사용하여 생성된 해쉬이다. >Hash는 비밀번호 부분과 salt 부분의 합이 80바이트여야 한다. >해시는 zero-byte 4바이트로 시작한다. >이것은 큰 하드웨어 낭비처럼 보이기 때문에 아마 쓸모가 없을것이다. > >번역이 정확하지 않은 경우 추가바람
해시 함수의 종류
* MD5 * SHA * SHA-1 * SHA-256, SHA-512 * SHA-3 * CRC * Tiger * Argon2 * Bcrypt * Scrypt * Snefru * Ripemd * Haval * Gost * Joaat * FNV * Whirlpool * PBKDF2
관련 문서
* 암호 알고리듬 * 공개키 암호화 방식 * 대칭 열쇠 암호 * 솔트 (salt) * 비트코인: SHA-256 사용 * 트루크맆트 (TrueCrypt): SHA-512 사용