해싱으로 설계하는 빠른 검색과 데이터 무결성

입력을 고정 길이 값으로 다루는 방법

해싱(Hashing)은 길이가 제각각인 데이터를 고정된 길이의 데이터로 매핑하는 과정이다. 데이터 구조, 암호화, 무결성 검증처럼 서로 다른 영역에서 쓰이지만, 입력의 특성을 대표하는 해시값을 만든다는 점은 같다.

해시 함수(Hash Function)는 입력을 해시값으로 변환하는 알고리즘이다. 결과값은 해시 코드(Hash Code) 또는 다이제스트(Digest)라고도 부른다. 해시 테이블(Hash Table)은 이 함수를 이용해 키(Key)와 값(Value)을 연결하는 자료구조다.

해시값은 원본 데이터의 지문처럼 활용된다. 이상적으로는 서로 다른 입력이 서로 다른 결과값으로 이어진다.

⤢✕

해시 함수가 갖춰야 할 성질

해시 함수는 같은 입력에서 늘 같은 결과를 내야 한다. 이 결정성(Deterministic)이 없으면 검색이나 검증에 사용할 수 없다. 계산은 빨라야 하며, 입력이 조금만 달라져도 해시값은 크게 달라지는 눈사태 효과(Avalanche Effect)도 필요하다.

보안에 쓰는 해시 함수라면 일방향성(One-way)도 요구된다. 해시값으로부터 원본 데이터를 계산적으로 복원하기 어려워야 한다.

충돌 저항성(Collision Resistance)은 두 층으로 나뉜다. 약한 충돌 저항성은 주어진 입력의 해시값과 같은 값을 내는 다른 입력을 찾기 어렵다는 뜻이다. 강한 충돌 저항성은 동일한 해시값을 만드는 서로 다른 두 입력 자체를 찾기 어렵다는 뜻이다.

충돌을 피할 수 없을 때의 처리 방식

해시 충돌(Hash Collision)은 서로 다른 입력이 같은 해시값을 만드는 현상이다. 입력 공간과 출력 공간의 크기가 다르므로 충돌은 피할 수 없으며, 해시 테이블은 이를 처리하는 전략을 갖춰야 한다.

체이닝(Chaining)은 같은 해시값을 받은 항목을 연결 리스트로 관리한다. 하나의 버킷에 여러 항목을 넣을 수 있어 유연하지만 메모리 오버헤드가 생길 수 있다.

⤢✕

개방 주소법(Open Addressing)은 충돌한 항목을 테이블 안의 다른 위치에 배치한다. 선형 탐색(Linear Probing)은 다음 인덱스를 차례로 확인하고, 이차 탐색(Quadratic Probing)은 제곱수만큼 건너뛰며 탐색한다. 이중 해싱(Double Hashing)은 두 번째 해시 함수로 오프셋을 정한다.

재해싱(Rehashing)은 해시 테이블 크기를 늘린 뒤 항목을 새 테이블에 다시 배치하는 방식이다. 적재율(load factor)이 임계값을 넘으면 수행한다.

목적에 따라 달라지는 해시 함수 선택

암호화 해시 함수는 보안 속성을 중심으로 선택한다. MD5(Message Digest Algorithm 5)는 128비트 해시값을 만들지만 보안 취약점이 발견되어 보안 용도로는 사용을 지양한다.

SHA(Secure Hash Algorithm) 계열에서 SHA-1은 160비트 해시값을 생성하며 보안 취약점이 발견됐다. SHA-2에는 SHA-256, SHA-384, SHA-512 등이 포함된다. SHA-3는 Keccak 알고리즘 기반의 최신 표준이다. BLAKE2와 BLAKE3는 고성능 암호화 해시 함수로, 병렬 처리를 지원해 높은 효율성을 제공한다.

비암호화 해시 함수는 빠른 처리와 자료구조 활용에 초점을 둔다. MurmurHash는 빠른 연산 속도와 낮은 충돌률을 바탕으로 데이터베이스와 캐싱 시스템에서 활용된다. FNV(Fowler-Noll-Vo)는 구현이 간단하고 빠르며 문자열 해싱에 효과적이다. CRC(Cyclic Redundancy Check)는 오류 감지와 데이터 무결성 검증에 주로 사용한다.

검색·검증·인증에서의 해싱

해시 테이블은 O(1) 시간 복잡도로 데이터를 검색할 수 있다. 데이터베이스는 빠른 레코드 검색을 위해 해시 인덱스를 구현하고, 메모리 캐시는 해싱으로 데이터 검색을 최적화한다.

무결성 검증에서는 디지털 서명으로 메시지의 무결성과 출처를 인증하고, 파일 체크섬으로 다운로드 파일을 확인한다. 블록체인도 트랜잭션 무결성을 보장하고 블록을 연결하는 데 해싱을 사용한다.

패스워드 저장에서는 비밀번호를 해시값으로 저장해 원본 노출을 막는다. 해시 기반 메시지 인증 코드(HMAC) 같은 인증 메커니즘과 디지털 포렌식의 파일 식별·증거 무결성 검증에도 적용된다. 이 밖에 중복 콘텐츠 식별을 통한 저장 공간 최적화, 서버 클러스터의 일관된 요청 분배, 집합 멤버십 테스트를 위한 블룸 필터(Bloom Filter)에도 쓰인다.

패스워드와 해시 테이블 구현

패스워드 해싱은 솔트와 패스워드를 결합해 해시한 뒤, 솔트와 해시를 함께 보관하는 형태로 구현할 수 있다.

import hashlib
import os

def hash_password(password):
    # 솔트 생성 (무작위 바이트)
    salt = os.urandom(32)

    # 패스워드와 솔트를 결합하여 해싱
    hash_obj = hashlib.pbkdf2_hmac(
        'sha256',
        password.encode('utf-8'),
        salt,
        100000  # 반복 횟수
    )

    # 솔트와 해시를 함께 저장
    return salt + hash_obj

def verify_password(stored_password, provided_password):
    # 저장된 패스워드에서 솔트 추출
    salt = stored_password[:32]
    stored_hash = stored_password[32:]

    # 제공된 패스워드 해싱
    hash_obj = hashlib.pbkdf2_hmac(
        'sha256',
        provided_password.encode('utf-8'),
        salt,
        100000  # 저장 시 사용한 것과 동일한 반복 횟수
    )

    # 해시값 비교
    return hash_obj == stored_hash

아래 구현은 버킷마다 연결 리스트를 두는 체이닝 방식의 간단한 해시 테이블이다.

public class SimpleHashTable<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private LinkedList<Entry<K, V>>[] buckets;
    private int size;

    @SuppressWarnings("unchecked")
    public SimpleHashTable() {
        buckets = new LinkedList[DEFAULT_CAPACITY];
        for (int i = 0; i < DEFAULT_CAPACITY; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    public void put(K key, V value) {
        int index = getIndex(key);
        LinkedList<Entry<K, V>> bucket = buckets[index];

        // 키가 이미 존재하는지 확인
        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }

        // 새 엔트리 추가
        bucket.add(new Entry<>(key, value));
        size++;
    }

    public V get(K key) {
        int index = getIndex(key);
        LinkedList<Entry<K, V>> bucket = buckets[index];

        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }

        return null;
    }

    private int getIndex(K key) {
        // 해시 코드를 버킷 인덱스로 변환
        return Math.abs(key.hashCode()) % buckets.length;
    }

    private static class Entry<K, V> {
        K key;
        V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

설계에서 확인할 제약

입력 공간이 출력 공간보다 크면 비둘기집 원리(Pigeonhole Principle)에 따라 충돌은 불가피하다. 따라서 적절한 충돌 해결 전략과 적재율 관리가 필요하다.

레인보우 테이블 공격은 미리 계산된 해시값 테이블을 이용해 원본 복구를 시도한다. 솔트(Salt)와 키 스트레칭(Key Stretching) 기법은 이에 대한 대응책이다.

해시 테이블 크기와 충돌 가능성 사이에는 성능과 공간의 트레이드오프가 있다. 보안이 중요한 경우에는 검증된 암호화 해시 함수를 선택해야 한다. 양자 컴퓨팅의 발전에 따라 현재의 암호화 해시 함수들이 도전받을 수 있으나, 데이터 구조와 무결성 검증에서 해싱의 기본 원리와 중요성은 계속 유지될 전망이다.