해시

해시는 대개 데이터 한 덩이를 대신하는 짧은 값을 부르는 말입니다. 파일이 바뀌었는지 확인하거나 내용에 이름을 붙일 때 이 값을 씁니다. 같은 낱말이 키와 값을 짝지어 담는 그릇의 이름으로도 쓰입니다. 어느 쪽을 가리키는지는 맥락이 정합니다.

상세

「해시」는 짧은 값과 키·값 그릇 둘을 가리킵니다. 둘을 가르는 잣대는 하나입니다. 결과로 손에 쥐는 것이 짧은 값 하나인지, 넣고 꺼내는 그릇인지입니다.

두 뜻이 함께 쓰는 해시 함수

두 뜻은 해시 함수에서 시작합니다. 해시 함수는 아무 길이의 비트열을 받아 길이가 정해진 비트열 하나를 내놓는 함수입니다. 해시 함수에 데이터를 넣어 나온 결과를 해시값이라고 부릅니다. 첫째 뜻의 해시가 이 해시값입니다.

그릇 쪽도 안에서 해시 함수를 씁니다. 그릇마다 자기 해시 함수를 가집니다. 키를 그 함수에 넣어 나온 값으로 키를 둘 칸을 고릅니다. 이 칸을 버킷이라고 부릅니다.

버킷을 늘어놓은 자료구조가 해시테이블입니다. Perl 은 키와 값의 짝을 담는 그릇을 안에서 해시테이블로 구현합니다. 그리고 그 그릇 자체를 해시라고 부릅니다. 둘째 뜻의 해시가 이 그릇입니다.

flowchart TD
    subgraph V1["첫째 뜻 · 값"]
        D["데이터"] --> H1["해시 함수"]
        H1 --> V["해시값 하나"]
    end
    subgraph V2["둘째 뜻 · 그릇"]
        K["키"] --> H2["해시 함수"]
        H2 --> B["키를 둘 버킷"]
        B --> T["해시테이블에 담긴 키와 값의 짝"]
    end

그림에서 첫째 뜻은 해시값 하나를 손에 쥡니다. 둘째 뜻에서 해시값은 안에서 버킷을 고르는 데만 쓰입니다. 쓰는 사람이 다루는 것은 키와 값의 짝을 담은 그릇입니다.

문장으로 가르는 법

그래서 같은 낱말이 문장마다 다른 물건을 가리킵니다. 「파일의 해시를 맞춰 보자」에서 해시는 값입니다. 「이 필드를 해시에 넣어 두자」에서 해시는 그릇입니다.

동사가 단서입니다. 맞춰 보거나 적어 두는 것은 값입니다. 넣거나 꺼내는 것은 그릇입니다.

이 둘 말고도 「해시」는 데이터베이스가 행을 나누는 방식의 이름으로 쓰입니다. 문자 # 를 부르는 이름이기도 합니다. 맥락마다 무엇을 가리키는지는 다음 절에서 봅니다.

맥락별 뜻

맥락 넷에서 「해시」가 무엇을 가리키는지 모읍니다. 첫 줄인 해시값은 쓰임이 많아 소절 다섯으로 나눕니다.

암호와 무결성의 해시값

이 맥락의 해시는 해시 함수에 데이터를 넣어 나온 값입니다. 길이는 해시 함수마다 정해져 있습니다. 보안 문서에서는 같은 값을 메시지 다이제스트, 줄여서 다이제스트라고도 부릅니다. 데이터를 짧게 줄인 표현이라는 뜻입니다.

널리 쓰는 해시 함수는 MD5 와 SHA 계열입니다. MD5 는 Message-Digest algorithm 5 의 줄임말입니다. SHA 는 Secure Hash Algorithm 의 줄임말입니다. 셋의 출력 길이를 나란히 놓으면 이렇습니다.

해시값은 본래 비트열입니다. 사람이 읽고 옮겨 적기 좋게 대개 16진수 문자열로 적습니다. 16진수 한 글자가 4비트를 담으므로 글자 수는 비트 수를 4로 나눈 값입니다. 아래는 test content 라는 내용 한 줄을 Git 에 넣고 돌려받은 SHA-1 해시값입니다.

$ echo 'test content' | git hash-object -w --stdin
d670460b4b4aece5915caf5c68d12f560a9fe3e4

160비트라 16진수 40글자입니다.

메시지를 한 비트만 바꿔도 아주 높은 확률로 전혀 다른 다이제스트가 나옵니다. 그래서 해시값 둘만 비교해 보면 데이터가 바뀌었는지 거의 확실히 압니다. 데이터가 바뀌지 않았다는 성질을 무결성이라고 부릅니다.

해시값으로 파일 확인하기

무결성을 확인하는 흔한 방법은 내려받은 파일의 해시값을 두 번 계산해 맞춰 보는 것입니다. 배포하는 쪽이 파일과 함께 그 파일의 해시값을 적어 둡니다. 받은 사람은 자기 손에 들어온 파일로 해시값을 다시 계산해 적힌 값과 맞춰 봅니다.

sequenceDiagram
    participant P as 배포하는 쪽
    participant U as 받은 사람
    P->>P: 파일의 해시값을 계산한다
    P->>U: 파일과 해시값 목록을 내준다
    U->>U: 받은 파일로 해시값을 다시 계산한다
    U->>U: 목록에 적힌 값과 맞춰 본다
    Note over U: 값이 다르면 그 파일은 확인에 실패한다

sha256sum 같은 명령이 이 일을 합니다. 파일마다 해시값을 계산해 출력합니다. --check 를 붙이면 앞서 출력해 둔 목록을 읽습니다. 목록의 파일을 다시 계산해 값이 다르면 그 파일을 실패로 표시합니다.

해시값을 이름으로 쓰는 Git

보통 데이터의 이름은 사람이 붙입니다. 해시값을 쓰면 이름을 내용에서 계산해 낼 수 있습니다. 이렇게 내용으로 주소를 정하는 저장 방식을 내용 주소 지정이라고 부릅니다. Git 이 이 방식으로 저장합니다.

Git 저장소의 바탕은 키와 값을 짝지어 두는 단순한 저장소입니다. 내용을 넣으면 Git 이 키 하나를 돌려줍니다. 그 키가 내용과 헤더를 합쳐 계산한 SHA-1 해시값입니다. 헤더는 Git 이 내용을 저장할 때 함께 붙이는 것입니다. 나중에 이 키로 내용을 다시 꺼냅니다.

Git 에서 맨 낱말 「해시」는 오브젝트 이름과 같은 말입니다. 오브젝트는 Git 이 저장하는 단위입니다. 오브젝트는 내용의 SHA-1 으로 구별됩니다. 그래서 한번 저장한 오브젝트는 바뀔 수 없습니다.

오브젝트는 서로를 해시값으로 가리킵니다. 트리 오브젝트는 블롭이나 하위 트리의 SHA-1 해시값을 파일 이름과 함께 담습니다. 블롭은 내용 한 덩이를 담은 오브젝트입니다. 커밋 오브젝트는 그 시점의 최상위 트리와 부모 커밋을 가리킵니다.

flowchart TD
    C2["커밋 · 이름은 해시값"] -->|부모 커밋의 해시값을 담는다| C1["부모 커밋 · 이름은 해시값"]
    C2 -->|최상위 트리의 해시값을 담는다| T["트리 · 이름은 해시값"]
    T --> F1["블롭 · 이름은 해시값"]
    T --> F2["블롭 · 이름은 해시값"]

그림에서 블롭 하나의 내용이 바뀌면 그 블롭의 해시값이 바뀝니다. 그 값을 담은 트리의 내용이 바뀌니 트리의 해시값도 바뀝니다. 같은 이유로 커밋의 해시값까지 바뀝니다.

해시값에서 원래 데이터로 못 돌아가는 성질

보안용 해시 함수는 정해 둔 해시값을 내는 입력을 찾기가 계산상 불가능하도록 만듭니다. 이 성질을 일방향(one-way)이라고 부릅니다. 역상 저항성이라고도 합니다. 해시값만 가진 쪽은 후보를 하나씩 해시해 같은 값이 나오는지 맞춰 보게 됩니다.

이 성질 덕분에 서버는 비밀번호 대신 비밀번호의 해시를 저장합니다. 솔트는 비밀번호마다 따로 고르는 값입니다. 같은 비밀번호를 쓴 계정 둘이 같은 해시로 저장되는 것을 솔트가 막습니다. 비밀번호는 솔트를 더해 비밀번호 해싱 방식으로 해시해 두어야 합니다.

비밀번호 해싱 방식은 비밀번호와 솔트와 비용 계수 셋을 받아 비밀번호 해시를 냅니다. 비용 계수는 해시 한 번에 들일 비용의 크기를 정하는 값입니다. 짐작 한 번을 비싸게 만드는 것이 이 방식의 목적입니다. 해시된 비밀번호 파일을 손에 넣은 공격자가 후보를 맞춰 볼 때마다 큰 비용을 치르게 합니다.

솔트 값은 32비트 이상이어야 합니다. 저장된 해시들 사이에서 솔트 값이 되도록 겹치지 않게 고릅니다. 솔트와 해시는 비밀번호마다 둘 다 저장해야 합니다.

해시값이 같을 때

해시값이 다르면 입력이 다른 것은 확실합니다. 같은 해시 함수에 같은 입력을 넣으면 언제나 같은 값이 나오기 때문입니다.

해시값이 같을 때는 사정이 다릅니다. 해시 함수는 아무 길이의 입력을 정해진 길이로 줄입니다. 입력은 끝없이 많습니다. 출력의 가짓수는 정해져 있습니다.

그래서 같은 값을 내는 서로 다른 입력은 반드시 있습니다. 이 일을 해시 충돌이라고 부릅니다. 값이 같다고 해서 입력이 같다고는 못 합니다.

flowchart TD
    C["해시값 둘을 맞춰 본다"]
    C -->|다르다| A["입력이 다른 것이 확실하다"]
    C -->|같다| B["같은 입력이거나 해시 충돌이다"]
    B --> W["입력은 끝없이 많다 · 출력의 가짓수는 정해져 있다"]
    W --> X["그래서 같은 값을 내는 다른 입력은 반드시 있다"]

보안용 해시 함수는 그런 두 입력을 찾기가 계산상 불가능하도록 만듭니다. 이 성질을 충돌 저항성이라고 부릅니다. MD5 는 이 성질을 증명이 아니라 추측으로 내세웠습니다.

지금 MD5 는 일부러 한 변조에 안전하다고 보지 않습니다. 디지털 인증서 같은 파일을 고치면서도 MD5 다이제스트로 한 서명이 유효해 보이게 만드는 방법이 알려져 있습니다. 주어진 MD5 값을 내는 파일을 새로 찾는 일은 지금으로서는 불가능하다고 여겨집니다. 더 안전한 해시가 필요하면 SHA-2 · SHA-3 · BLAKE2b 를 고려합니다.

키와 값을 담는 그릇

이 맥락의 해시는 값이 아닙니다. 키와 값의 짝을 담아 두는 그릇입니다. 키를 주면 거기 짝지은 값을 꺼내 줍니다. 프로그래밍 언어와 저장소가 이 그릇을 맨 낱말 「해시」로 부릅니다.

Redis 에서는 키를 필드라고 부릅니다. Redis 의 해시는 그 필드와 값의 짝을 모은 레코드 타입입니다. 간단한 객체를 나타내거나 카운터 여러 개를 묶어 둘 때 씁니다. 아래는 자전거 한 대의 정보를 해시 하나에 넣고 필드 하나를 꺼내는 예입니다.

> HSET bike:1 model Deimos brand Ergonom type 'Enduro bikes' price 4972
(integer) 4
> HGET bike:1 model
"Deimos"

HSET 으로 필드 넷을 한 번에 넣습니다. 이미 있는 필드에 넣으면 값을 덮어씁니다. HGET 은 필드 이름으로 값 하나를 꺼냅니다. 해시 하나에는 필드와 값의 짝을 4,294,967,295 개까지 넣을 수 있습니다.

Ruby 의 Hash 는 겹치지 않는 키 하나하나를 값 하나에 짝짓는 객체입니다. 배열과 갈리는 것은 키입니다. 배열의 인덱스는 언제나 정수입니다. 해시의 키는 거의 어떤 객체든 될 수 있습니다.

h = {:foo => 0, :bar => 1, :baz => 2}

키와 값 사이의 => 를 Ruby 에서는 해시 로켓이라고 부릅니다.

Perl 의 내장 데이터 타입은 셋입니다. 스칼라, 스칼라의 배열, 그리고 「해시」라고 부르는 스칼라의 연관 배열(associative array)입니다. 해시는 문자열 키로 값을 찾는 순서 없는 모음입니다. 해시 전체를 가리킬 때는 변수 이름 앞에 % 를 붙입니다.

$days{'Feb'}   # 해시 %days 에서 'Feb' 에 짝지은 값

Redis·Ruby·Perl 셋 모두에서 「해시」는 「해시테이블」을 줄여 부른 말이 아닙니다. 맨 낱말 「해시」가 그 자료형의 정식 이름입니다. 그래서 「Redis 해시」는 해시값이 아니라 필드를 넣고 빼는 저장 구조를 가리킵니다.

데이터베이스가 행을 나누고 찾는 방식

PostgreSQL 에서 해시는 방식의 이름으로도 쓰입니다. 테이블을 나누는 방식 가운데 하나가 해시 분할입니다. 인덱스 종류 가운데 하나도 해시입니다. 두 방식 모두 안에서 해시값을 씁니다.

해시 분할은 테이블을 파티션 여럿으로 나눕니다. 파티션마다 나눌 수(modulus)와 나머지(remainder)를 정해 둡니다. 행의 파티션 키를 해시한 값을 나눌 수로 나눕니다. 그 나머지가 어느 파티션의 나머지와 같으면 행은 그 파티션에 들어갑니다.

해시 인덱스는 인덱스한 열의 값에서 뽑은 32비트 해시 코드를 저장합니다. 그래서 같은지 비교하는 조건만 처리합니다. 인덱스한 열이 = 비교에 쓰이면 쿼리 플래너가 해시 인덱스를 쓸지 따져 봅니다.

기호 이름

문자 # 의 유니코드 정식 이름은 NUMBER SIGN 입니다. 이 문자의 별칭에 hashtag 와 hash 가 있습니다. pound sign · crosshatch · octothorpe 도 같은 문자의 별칭입니다. 「해시 기호」라고 할 때의 해시가 이 뜻입니다.

배경

키·값 그릇을 맨 낱말 「해시」로 부르는 것은 Perl 입니다. 옛 이름이 무엇이었고 왜 짧은 이름으로 부르게 됐는지를 봅니다.

Perl 은 4판에서 이 그릇을 연관 배열이라고 불렀습니다. 연관 배열은 영어로 일곱 음절이나 되는 긴 이름입니다. Perl 은 그 대신 짧게 「해시」라고 부릅니다. 같은 그릇을 딕셔너리라고 부르는 언어도 있습니다. Python 의 dict 가 그렇습니다.

Perl 은 이 그릇을 효율적으로 구현하려고 안에서 해시테이블을 씁니다. 그릇의 이름은 해시입니다. 그 안의 자료구조 이름은 해시테이블입니다. 바깥의 그릇과 안의 자료구조가 「해시」라는 낱말을 나눠 갖습니다. 「해시」라는 낱말 자체의 어원은 확인하지 못했습니다(미확인).

경계

해시와 헷갈리는 이웃 말 넷을 가릅니다. 그다음 애매한 케이스 하나를 판정합니다.

해시 함수와 해시

해시 함수는 비트열을 받아 길이가 정해진 비트열을 내는 함수입니다. 해시는 그 함수가 낸 결과입니다. 함수와 결과는 다른 것입니다.

다만 함수 이름과 값 이름은 서로 건너갑니다. 「SHA-256 해시」는 SHA-256 함수를 가리킬 때가 있습니다. 그 함수가 낸 값을 가리킬 때도 있습니다. Git 에서는 함수 이름인 SHA-1 이 거꾸로 오브젝트 이름, 곧 오브젝트를 구별하는 값을 가리키는 말로 쓰입니다.

다이제스트와 지문

다이제스트는 해시값의 다른 이름입니다. 보안 쪽에서는 해시값과 메시지 다이제스트를 같은 말로 씁니다. 지문(fingerprint)도 같은 값을 부르는 이름입니다. MD5 는 입력의 128비트 「지문」, 곧 메시지 다이제스트를 내는 알고리즘입니다.

체크섬

체크섬은 전송 중에 생긴 오류를 잡으려고 데이터에 붙이는 짧은 값입니다. 순환 중복 검사(CRC, Cyclic Redundancy Check)가 대표입니다. 체크섬이 맞아도 오류가 숨어 있을 수 있습니다. 그 확률은 체크섬 비트 수를 C 라 할 때 2의 -C 제곱을 넘지 않습니다.

해시값과 체크섬은 낱말이 섞여 쓰입니다. sha256sum 은 자기가 내는 SHA-2 해시값을 체크섬이라고 부릅니다. Git 도 SHA-1 해시값을 체크섬이라고 부릅니다.

가르는 선은 무엇을 막느냐입니다. CRC 같은 체크섬은 우연한 손상을 잡습니다. MD5 다이제스트는 우연한 손상을 잡는 데는 단순한 CRC 보다 믿을 만합니다. 그러나 일부러 한 변조에는 안전하다고 보지 않습니다. 변조까지 걱정해야 하면 SHA-2 같은 더 안전한 해시를 고려합니다.

암호화

암호화는 키가 있으면 원래 데이터로 되돌릴 수 있게 바꾸는 일입니다. 해시는 원래 데이터를 찾아내기가 계산상 불가능하도록 만든 값입니다. 원문을 나중에 다시 꺼내야 하면 해시가 아니라 암호화를 씁니다.

두 일은 함께 쓰이기도 합니다. MD5 는 전자 서명용으로 만들었습니다. 큰 파일을 먼저 다이제스트로 줄입니다. 그다음 그 다이제스트를 공개 키 암호 방식의 비밀 키로 암호화합니다. 이때도 해시와 암호화는 따로 도는 두 단계입니다.

언어 내장 hash() 가 돌려주는 정수

Python 의 hash() 나 Java 의 hashCode() 가 돌려주는 정수도 앞에서 말한 해시값인가. 맞습니다. 객체를 해시 함수에 넣어 나온 값입니다. 다만 보장이 다릅니다.

이 정수는 해시테이블을 위해 있습니다. Python 은 딕셔너리를 조회할 때 키를 빨리 비교하는 데 이 값을 씁니다. Java 의 hashCode() 도 HashMap 같은 해시테이블을 위해 정수를 돌려줍니다. 같다고 비교되는 두 객체는 같은 값을 내야 합니다. 다른 두 객체가 꼭 다른 값을 낼 필요는 없습니다.

갈리는 것은 실행 사이의 보장입니다. Python 의 str·bytes 해시값은 기본으로 예측할 수 없는 무작위 값과 섞입니다. 이 값은 한 프로세스 안에서는 변하지 않습니다. Python 을 다시 실행하면 달라질 수 있습니다. Java 의 hashCode() 도 같은 실행 안에서만 같으면 됩니다.

Python 이 무작위 값을 섞는 것은 서비스 거부 공격을 막으려는 것입니다. 공격자가 골라 넣은 입력은 딕셔너리 삽입 비용을 입력 수의 제곱으로 불릴 수 있습니다. 이 무작위화는 Python 3.3 부터 기본으로 켜져 있습니다. 관련 설정은 환경 변수 PYTHONHASHSEED 입니다.

그래서 이 정수는 적어 두었다가 나중에 다시 계산해 맞춰 보는 쓰임에 못 씁니다. 파일 무결성 확인이나 Git 처럼 내용에 이름을 붙이는 일이 그런 쓰임입니다. 뜻은 해시값과 같습니다. 다른 것은 보장입니다.

관련 항목

해시값을 만들어 내는 함수와 알고리즘

해시 함수 · 암호학적 해시 함수 · MD5 · SHA-1 · SHA-256 · SHA-2 · SHA-3 · BLAKE2 · CRC

해시값을 적는 단위와 표기

16진수 · 비트 · 바이트 · 비트열

해시값으로 지키는 성질과 장치

무결성 · 체크섬 · 결정성 · 전자 서명 · 디지털 인증서 · 메시지 인증 코드 · HMAC

해시값을 이름으로 쓰는 저장 구조

내용 주소 지정 · Git · 커밋 · 트리 · 오브젝트 · 머클 트리 · 중복 제거 · 블록체인

해시값이 겹치거나 뚫리는 방식

해시 충돌 · 비둘기집 원리 · 생일 문제 · 충돌 저항성 · 역상 저항성 · 레인보우 테이블

해시로 비밀번호를 저장하는 기법

비밀번호 해싱 · 솔트 · 비용 계수 · bcrypt · Argon2

해시와 달리 되돌릴 수 있는 변환

암호화 · 복호화 · 공개 키 암호 · RSA

해시라는 이름으로 부르는 키·값 그릇

해시테이블 · 연관 배열 · 딕셔너리 · 버킷 · Redis · HSET · HashMap

언어가 객체에서 해시값을 뽑는 장치

hashCode · equals · 해시 무작위화 · 서비스 거부 공격

해시값으로 행이나 서버를 고르는 기법

해시 인덱스 · 해시 분할 · 파티셔닝 · 인덱스 · 일관성 해싱 · 로드 밸런서 · PostgreSQL

해시를 별칭으로 갖는 기호와 그 쓰임

해시태그 · 유니코드 · URL 프래그먼트 · 주석

해시를 기록해 쓰는 분야

메타데이터 · 버전관리 · 암호학 · 자료구조 · 데이터베이스