26 · 블라인드 인덱스: 평문 없이 검색

암호화된 SSN을 저장했는데, 나중에 특정 SSN을 가진 환자의 기록을 찾아야 합니다. 평문이 디스크에 없으니 일반적인 검색은 불가능합니다. 그렇다고 전체 기록을 복호화해서 비교하는 건 느리고 — 그 순간 평문이 서버 메모리에 올라오니 비밀이 새어나갑니다. 이 딜레마를 푸는 것이 블라인드 인덱스(blind index)입니다. 평문을 디스크에 남기지 않으면서도 검색이 가능한 비법을 살펴봅시다.

DB에서는 어떻게 했나 — 암호화와 검색의 딜레마

관계형 DB에서 컬럼을 암호화하면 WHERE ssn = '123-45-6789' 쿼리가 동작하지 않습니다. DB는 저장된 값이 같은지 비교해야 하는데, 암호화된 칼럼의 값이 매번 다르거나(비결정론적 암호화), 복호화해야만 비교할 수 있기 때문입니다. 복호화하면 DB 서버가 평문을 봐야 하니 내부 위협에 무력해집니다.

일부 DB 확장(예: pgcrypto, Always Encrypted)은 결정론적 암호화를 써서 같은 입력 → 같은 암호문을 만들어 인덱스를 허용합니다. 하지만 결정론적이면 동일 값이 같은 암호문을 가지므로 공격자가 빈도 분석을 할 수 있습니다. Quipu-Log의 블라인드 인덱스는 이 문제도 고려한 설계입니다.

블라인드 인덱스의 발상

핵심 아이디어는 단순합니다. 검색 비교는 원본 평문이 아니라 토큰의 다이제스트끼리 합니다. 쓸 때와 검색할 때 같은 변환을 적용하면, 평문 없이도 일치 여부를 확인할 수 있습니다.

토큰화 3가지 — Exact / Prefix(n) / Ngram(n)

어떤 토큰을 만드느냐에 따라 지원하는 검색 방식이 달라집니다. Quipu-Log의 FieldIndex는 세 가지를 제공합니다.

crates/quipu-core/src/schema.rs — FieldIndexpub enum FieldIndex {
    None,
    Exact,       // 소문자화한 전체 값 하나 → 대소문자 무시 일치 검색
    Prefix(usize), // 길이 1..=n 접두사 전부 → n자까지 접두사 검색
    Ngram(usize),  // n자 슬라이딩 윈도 → 부분 문자열 검색(n = 3이 일반적)
}

실제 토큰화 로직을 보면 char 단위로 동작하므로 한글, 일본어 등 멀티바이트 문자도 올바르게 처리됩니다.

crates/quipu-core/src/tokens.rs — value_tokenspub(crate) fn value_tokens(text: &str, idx: FieldIndex) -> Vec<String> {
    let norm = normalize(text); // to_lowercase()
    let chars: Vec<char> = norm.chars().collect(); // char 단위 — 멀티바이트 안전
    match idx {
        FieldIndex::Exact => { out.insert(norm); }
        FieldIndex::Prefix(n) => {
            for len in 1..=n.min(chars.len()) { out.insert(chars[..len].iter().collect()); }
        }
        FieldIndex::Ngram(n) => {
            for w in chars.windows(n) { out.insert(w.iter().collect()); }
        }
        _ => {}
    }
}

예를 들어 "Alice Kim"을 Prefix(3)으로 처리하면 ["a", "al", "ali"] 세 토큰이 생성됩니다. "김철수"를 Ngram(2)로 처리하면 ["김철", "철수"] 두 토큰이 만들어집니다.

도메인 분리 — 인덱스 토큰이 본문 다이제스트와 섞이지 않게

인덱스 토큰을 HMAC으로 처리할 때 입력 앞에 "idx:" + 필드명 + NUL을 붙입니다. 이것이 도메인 분리(domain separation)입니다.

crates/quipu-core/src/crypto.rs — index_token_digest_withlet mut data = Vec::with_capacity(4 + field.len() + 1 + token.len());
data.extend_from_slice(b"idx:");           // 도메인 분리
data.extend_from_slice(field.as_bytes());   // 필드명
data.push(0);                               // NUL 구분자
data.extend_from_slice(token.as_bytes());   // 실제 토큰

세 가지 인덱스 모드의 특성 비교

블라인드 인덱스는 어디에 저장되나

토큰 다이제스트는 RegistryRecord.tokens에 영속화됩니다. 서버 재시작 후에도 검색이 가능한 이유입니다 — 평문이 없어서 재시작 후 토큰을 다시 만들 수 없기 때문에, 쓰기 시점에 저장해두는 것이 필수입니다.

crates/quipu-core/src/registry.rs — RegistryRecordpub struct RegistryRecord {
    // ...기타 필드...
    pub tokens: BTreeMap<String, FieldTokens>,  // 필드명 → 토큰 다이제스트 목록
}

pub struct FieldTokens {
    pub key_version: u32,    // 어떤 HMAC 키 버전으로 만들었나
    pub digests: Vec<String>, // 토큰별 HMAC 다이제스트
}

검색 시에는 인메모리 포스팅 리스트(token_index)를 이용해 후보를 빠르게 좁힙니다. Ngram 검색에서는 질의어의 모든 n-gram 다이제스트가 포스팅 리스트의 교집합에 있는 entity_id가 후보입니다. 포스팅 리스트는 서버 시작 시 레지스트리 레코드를 스캔해서 재구축됩니다.

키 없이는 오프라인 공격이 불가능하다

필드 보호가 Hmac이나 Rsa인 경우, 인덱스 토큰도 HMAC 키로 다이제스트를 만듭니다. 즉 공격자가 디스크에 저장된 토큰 다이제스트를 가져가도, HMAC 키 없이는 어떤 토큰이 이 다이제스트를 만들었는지 역산할 수 없습니다.

정리

• 블라인드 인덱스는 쓰기 시점에 평문 → 토큰 → 다이제스트를 만들어 저장. 평문이 디스크에 남지 않음.
• 검색 시 질의어에도 같은 변환을 적용해 다이제스트 비교 → 평문 없이 일치 확인 가능.
• Exact는 대소문자 무시 일치, Prefix(n)는 접두사 검색, Ngram(n)는 부분 문자열 검색.
• Hmac/Sha256 + Ngram은 위양성 가능 — Rsa + Ngram이면 복호화로 확정 가능.
• 인덱스 토큰도 도메인 분리 HMAC으로 보호 — 키 없이 오프라인 공격 불가.