Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience

1. 문제 정의 (Problem)

기존의 악성 콘텐츠 차단 (Blocklisting) 시스템은 다음과 같은 주요 한계점을 가지고 있습니다.

• 프라이버시 문제: 클라이언트가 서버의 차단 목록 (Blocklist) 을 확인하려면, 클라이언트의 입력 (예: 파일, URL) 이나 서버의 차단 목록 중 적어도 하나가 노출되어야 합니다. 이는 독점적인 차단 목록을 가진 기업이나 민감한 사용자 데이터를 보호해야 하는 상황에서 실용적이지 않습니다.
• TOCTOU (Time-of-Check vs. Time-of-Use) 취약점: 자원을 사용하기 직전에 차단 목록을 확인하는 방식은 확인 (Check) 시점과 사용 (Use) 시점 사이의 시간 차이를 악용한 공격에 취약합니다. 공격자는 확인 후 사용 전까지 해당 자원을 악성 코드로 변경하거나, 새로 발견된 악성 코드가 목록에 추가되기 전까지 공격할 수 있습니다.
• 성능 병목: 프라이버시를 유지하면서 유사성 기반 (Similarity-based) 검색 (예: 퍼지 해시 매칭) 을 수행하는 암호화 프로토콜은 계산 비용이 매우 높아, 실시간 사용 경로 (Critical Path) 에서 수행하기 어렵습니다.

2. 방법론 (Methodology)

저자들은 Half-Moon Cookie (Half Moon) 라는 새로운 프라이버시 보호 차단 프레임워크를 제안합니다. 이 시스템은 명시적 확인 (Explicit Check) 과 암시적 확인 (Implicit Check) 의 두 단계로 구성되어 TOCTOU 공격을 방지하면서도 프라이버시를 유지합니다.

핵심 구성 요소

1. 세 당사자 모델:

   • 송신 클라이언트 ($C_{snd}$): 파일을 서버에 보내기 전 차단 목록 확인을 수행.
   • 수신 클라이언트 ($C_{rcv}$): 파일을 사용하기 직전에 이전 확인 결과를 빠르게 검증.
   • 서버 (S): 독점적인 차단 목록을 보유하며, 확인 결과를 처리.

2. 프로토콜 단계:

   • 1 단계: 명시적 확인 (Explicit Check)
     • $C_{snd}$ 는 서버와 상호작용하여 자신의 입력 $w$ 가 차단 목록과 유사한지 확인합니다.
     • 프라이버시 보호: 입력 $w$ 는 서버에 노출되지 않고, 서버의 차단 목록도 $C_{snd}$ 에게 노출되지 않습니다.
     • 기술적 구현:
       • 임베딩 (Embedding): $w$ 를 해시하여 메트릭 공간 (Hamming distance 기반) 으로 변환합니다. 이때 재사용 가능한 가블드 회로 (Reusable Garbled Circuits, CRGC) 를 사용하여 파일 크기에 비례하는 비용 없이 효율적으로 수행합니다.
       • 테스트 및 커밋 (Test-and-Commit): 변환된 벡터와 서버의 차단 목록 간의 거리를 Fuzzy PSI (Private Set Intersection) 기법을 사용하여 확인합니다.
       • 토큰 생성: 확인이 통과되면, 서버는 해당 항목에 대한 은폐 및 바인딩 토큰 (Hiding and Binding Token) 을 생성하여 허용 목록 (Allowlist) 에 저장합니다. 이 토큰은 입력값을 숨기면서도 나중에 동일한 입력인지 검증할 수 있게 합니다.
   • 2 단계: 암시적 확인 (Implicit Check)
     • $C_{rcv}$ 는 $C_{snd}$ 로부터 파일과 토큰 관련 정보를 받습니다.
     • 서버와 상호작용하여 저장된 허용 목록에 해당 토큰이 있는지 빠르게 확인합니다.
     • 이 과정은 전체 차단 목록을 다시 스캔할 필요가 없으므로 매우 가볍고 빠릅니다.
     • TOCTOU 방어: 서버는 차단 목록이 업데이트되면 허용 목록을 초기화합니다. 따라서 $C_{rcv}$ 는 최신 정책이 적용된 상태에서만 토큰을 검증할 수 있어, 확인과 사용 사이의 시간 차이를 최소화합니다.

3. 보안 모델:

   • T1 (악성 송신자): 악성 $C_{snd}$ 가 차단된 파일을 통과시키거나, 다른 사용자의 토큰을 재사용하는 것을 방지합니다 (토큰의 바인딩 속성).
   • T2 (호기심 많은 서버): 서버는 $C_{snd}$ 의 입력 파일 내용을 알 수 없어야 합니다 (토큰의 은폐 속성).

3. 주요 기여 (Key Contributions)

1. Half-Moon 원리 정의: 프라이버시를 유지하면서 유사성 기반 차단 목록 확인을 수행하고, 이후 빠른 검증을 위한 토큰을 생성하는 3 자 프로토콜을 공식적으로 정의했습니다.
2. 효율적인 구현 프레임워크:
   • 재사용 가능한 가블드 회로 (CRGC): 대용량 파일 (예: 실행 파일) 의 해시 임베딩 비용을 파일 크기와 무관하게 줄였습니다.
   • 거리 인식 PSI: Hamming 거리 기반의 유사성 매칭을 위해 가설 없는 (Assumption-free) Fuzzy PSI 기법을 적용했습니다.
3. 실제 적용 사례 (말웨어 탐지): 이메일 첨부 파일의 말웨어 탐지에 Half-Moon 을 적용하여, 송신자가 무거운 검사를 수행하고 수신자가 가벼운 검사를 수행하는 워크플로우를 제시했습니다.
4. 성능 최적화: 단일 가블드 회로 방식에 비해 네트워크 트래픽과 지연 시간을 획기적으로 줄였습니다.

4. 실험 결과 (Results)

저자들은 C++ 로 프로토타입을 구현하고 Enron 데이터셋 (이메일 첨부 파일) 과 Ember 데이터셋 (말웨어) 을 사용하여 평가했습니다.

• 명시적 확인 성능:
  • 재사용 가능한 가블드 회로 (RGC) 의 효과: RGC 를 사용하지 않은 경우 (기존 방식) 에 비해 통신량과 응답 시간이 1~2 차수 (Orders of Magnitude) 이상 감소했습니다. (예: 5kB 파일 기준, TLSH 해시 사용 시 통신량 68GB $\to$ 60MB, 응답 시간 1000s $\to$ 4.8s).
  • 해시 함수 비교: TLSH, ssdeep, sdhash 중 TLSH가 전체적인 성능 (응답 시간 및 통신량) 에서 가장 우수했습니다. ssdeep 는 편집 거리 (Edit Distance) 를 Hamming 거리로 변환하는 추가 과정으로 인해 오버헤드가 발생했습니다.
  • 동시성 처리: 서버가 250 개 이상의 동시 요청을 처리할 때 성능 저하가 시작되었으나, 단일 가블드 회로 방식에 비해 훨씬 높은 처리량을 보였습니다.
• 암시적 확인 성능:
  • 암시적 확인은 차단 목록 크기와 무관하게 O($\theta$) 의 비용으로 수행됩니다.
  • 기존 Fuzzy PSI 나 Exact PSI 기반 방식에 비해 응답 시간은 100 배 이상, 통신량은 1000 배 이상 개선되었습니다. (예: 100kB 파일 기준, 암시적 확인 응답 시간 0.19s vs Fuzzy PSI 160s).

5. 의의 및 결론 (Significance)

• TOCTOU 취약점 해결: 프라이버시를 유지하면서도, 확인과 사용 사이의 시간 차이를 최소화하여 TOCTOU 공격을 효과적으로 방어하는 첫 번째 실용적인 솔루션 중 하나입니다.
• 프라이버시와 성능의 균형: 기존에는 프라이버시 보호를 위해 고비용의 암호화 연산이 필요해 실시간 적용이 어려웠으나, Half-Moon 은 송신자와 수신자의 역할을 분리하고 효율적인 토큰 검증 기법을 도입하여 실용성을 확보했습니다.
• 확장성: 독점적인 차단 목록을 가진 기업 (예: 안티바이러스 벤더) 이 고객에게 프라이버시를 침해하지 않고 말웨어 검사를 제공할 수 있는 새로운 패러다임을 제시합니다.

이 논문은 프라이버시 보호 기술과 시스템 보안 (TOCTOU 방어) 을 결합하여, 현대적인 사이버 위협 환경에서 효율적이고 안전한 콘텐츠 검증 체계를 구축할 수 있음을 입증했습니다.