퍼지 해시

퍼지 해시(fuzzy hashing, 또는 similarity hashing)는 입력 데이터가 완전히 일치하지 않더라도 유사한 경우를 감지할 수 있도록 설계된 해시 기법이다. 일반 해시 함수(예: SHA-256, MD5)처럼 입력이 조금만 바뀌어도 해시 값 전체가 완전히 달라지는 성질(아발란체 효과)을 지향하지 않고, 유사한 입력에 대해서는 유사한 해시 값을 만드는 특성을 갖는다.

정의 및 배경

퍼지 해시는 ‘비슷하지만 동일하지 않은’ 데이터를 비교하거나 탐지하기 위한 해시 방식이다. 즉, 두 개의 입력이 완전히 동일하지 않아도 어느 정도 유사성이 있다면, 퍼지 해시는 그 유사성을 반영한 해시 결과를 만들어 준다. 반면 암호학적 해시 함수는 아주 작은 변화도 해시 결과 전체를 급격히 변화시키도록 설계되며, 유사성 정보는 보존하지 않는다. 퍼지 해시 기법은 보통 “유사도 비교 → 후보군 좁히기 → 정밀 비교” 흐름으로 사용된다.

주요 기법과 알고리즘

퍼지 해시를 구현하는 대표적인 기법들과 알고리즘은 다음과 같다.

• CTPH (Context-Triggered Piecewise Hashing): 입력을 여러 구간으로 나누고, 각 구간에 대해 전통적 해시를 적용한 뒤 이를 조합하는 방식 (예: ssdeep)
• LSH (Locality-Sensitive Hashing): 유사한 입력이 동일한 해시 버킷으로 매핑될 확률을 높이도록 설계된 해시 함수 군
• SimHash: 벡터 표현에서 코사인 유사도를 근사해 유사 해시를 만드는 기법, 문서 유사도 탐색에 활용
• MinHash: 집합 기반 유사도 (예: Jaccard 유사도)를 추정하기 위해 최소 해시 값을 이용하는 방식
• Nilsimsa Hash: 이메일/스팸 필터링을 위해 고안된 해시 방식으로, 유사 메시지에 대해 유사한 해시를 생성

최근에는 전통적 방식 대신 머신러닝 기반 퍼지 해시도 연구되고 있다. 예를 들어, Perturbation-Consistent Adversarial Kernel Embedding 방식은 데이터 분포에 맞게 해시 함수를 학습하는 접근이다.

장단점

장점

• 입력이 일부 변형되었더라도 유사성을 감지할 수 있다.
• 변형된 파일, 코드, 문서 등 간의 유사 탐지에 유용하다.
• 유사성 기반 검색, 중복 제거, 악성코드 변종 탐지 등에서 효과적이다.

단점 / 한계

• 오탐(false positive)과 누락(false negative)이 발생할 수 있다.
• 유사도 임계값 설정이 중요하다.
• 계산 비용이 전통적 해시보다 높다.
• 퍼지 해시만으로는 완전한 판별이 어려우며 후보군에 대한 정밀 비교가 필요하다.

응용 사례

• 악성코드 탐지 및 변종 분석
• 문서 유사도 검색 및 중복 문서 탐지
• 로그 패턴 유사 탐지
• 파일 버전 관리 및 변형 탐지
• 이메일 스팸 필터링 (예: Nilsimsa)
• 웹 콘텐츠 유사 탐지, 피싱 사이트 탐지

파이썬 예제 코드

다음은 문자열을 대상으로 간단한 퍼지 해시/유사도 비교 예제이다.

import hashlib
from collections import defaultdict

def ngram_hashes(s: str, n: int = 3):
    """문자열 s를 n-그램으로 나눈 후 각 n-그램에 MD5 해시를 취해 Set 반환."""
    hashes = set()
    for i in range(len(s) - n + 1):
        gram = s[i : i + n]
        h = hashlib.md5(gram.encode('utf-8')).hexdigest()
        hashes.add(h)
    return hashes

def jaccard_similarity(set1: set, set2: set) -> float:
    """자카드 유사도 계산."""
    if not set1 or not set2:
        return 0.0
    return len(set1 & set2) / len(set1 | set2)

class FuzzyHashStore:
    def __init__(self):
        self.store = defaultdict(list)

    def insert(self, key: str, value):
        sig = frozenset(ngram_hashes(key))
        self.store[sig].append((key, value))

    def query(self, key: str, threshold: float = 0.5):
        sig = frozenset(ngram_hashes(key))
        results = []
        for sig2, items in self.store.items():
            sim = jaccard_similarity(sig, sig2)
            if sim >= threshold:
                results.extend(items)
        return results

# 사용 예시
if __name__ == "__main__":
    store = FuzzyHashStore()
    store.insert("hello world", "A")
    store.insert("helo world", "B")
    store.insert("goodbye", "C")

    print(store.query("helloo world", threshold=0.4))
    # 출력 예: [('hello world', 'A'), ('helo world', 'B')]

같이 보기

• 해시 함수
• 로컬리티 민감 해싱
• ssdeep
• 유사도 검색
• 악성코드 분석

참고 문헌

• A. Azarafrooz & J. Brock, “Fuzzy Hashing as Perturbation-Consistent Adversarial Kernel Embedding.” arXiv:1812.07071
• Yuping Li, Jiong Jang, Xinming Ou, “Topology-Aware Hashing for Effective Control Flow Graph Similarity Analysis.” arXiv:2004.06563