Static Detection of Post-Quantum Cryptographic Algorithms in Stripped Binaries for Digital Forensic Examination and Migration Assurance

기술 요약: 스트립된 바이너리 내 양자 내성 암호 알고리즘의 정적 탐지

문제 정의
양자 내성 암호(PQC)로의 전환은 중요한 검증 공백에 직면해 있다. 소스 코드나 바이너리에서 양자 취약 알고리즘(RSA, ECC)을 식별하는 도구는 존재하지만, 컴파일되고, 스트립(stripped)되었으며, 정적 링크(statically linked)된 바이너리 내에 표준화된 양자 내성 알고리즘(특히 ML-KEM 및 ML-DSA)의 존재를 확인하는 확립된 방법은 없다. 기존의 암호 발견 도구들은 심볼, 라이브러리 의존성, 런타임 동작 또는 네트워크 트래픽에 의존한다. 이러한 신호들은 심볼 스트립, 정적 링크, 컴파일러 최적화와 같은 표준 빌드 변환 과정에서 파괴된다. 결과적으로, 감사인과 포렌식 조사관은 바이너리가 진정으로 PQC를 구현하고 있는지, 아니면 단지 PQC를 사용한다고 광고만 하는 것인지 확인할 수 없다. 이는 "Kyber" 랜섬웨어 패밀리와 같은 PQC 지원 악성코드의 등장과, 배포된 암호 프리미티브의 검증을 요구하는 규제 명령(예: 행정명령 14412)으로 인해 시급한 문제가 되었다.

방법론: Kestrel 접근 방식
본 논문은 바이너리의 읽기 전용 데이터 섹션에 임베디드된 수론적 변환(Number-Theoretic Transform, NTT) 상수 테이블을 탐지함으로써 ML-KEM 및 ML-DSA를 식별하는 정적 분석 도구인 Kestrel을 소개한다.

1. 신호(The Signal): ML-KEM 및 ML-DSA는 NTT를 통한 다항식 곱셈에 의존하며, 이를 위해 고정된 일차 단위근($\zeta$)의 거듭제곱을 특정 소수($q$)에 대해 미리 계산한 테이블이 필요하다. 코드와 달리, 이러한 상수 테이블은 데이터이며, 알고리즘의 정확성을 깨뜨리지 않고서는 최적화에 의해 제거되거나 변경될 수 없다. 따라서 이들은 스트립과 정적 링크 과정을 거쳐도 유지된다.
2. 지문 유도(Fingerprint Derivation): Kestrel은 수동으로 시그니처 목록을 컴파일하는 대신, 공개된 스킴 파라미터($q$, $\zeta$, 변환 길이, 비트 역전 폭)로부터 결정론적인 절차를 사용하여 완전한 지문 세트를 생성한다. 이 생성기는 순방향 트위들(forward twiddles), 역방향 트위들(inverse twiddles), 그리고 베이스 케이스/모드 루트(base-case/mod-root) 상수의 세 가지 계열을 생성한다. 또한 몽고메리 형태(Montgomery form), 부호 있는/없는 정수, 벡터화된 레이아웃을 포함한 다양한 저장 표현 방식을 고려한다.
3. 탐지 파이프라인:
   • 정규화(Normalization): 탐지기는 읽기 전용 데이터 섹션을 스캔하여 후보 값들을 $q$에 대한 정준 잔여값(canonical residues)으로 정규화한다. 이는 부호 있는/없는 표현을 처리하고, 몽고메리 형태를 다시 평문 잔여값으로 변환한다.
   • 멀티셋 점수 산정(Multiset Scoring): 정확한 바이트 매칭 대신, 탐지기는 기대되는 정준 잔여값을 포함하는 윈도우를 기반으로 점수를 산정하며, 이를 멀티셋(multiset)으로 취급한다. 이러한 순서 독립성은 벡터화된 재배열 및 레이아웃 변형을 수용한다.
   • 상호 확인(Corroboration): 신뢰도를 높이기 위해 하부 SHAKE 함수에 사용되는 Keccak 라운드 상수의 존재 여부를 보조 조건으로 확인한다. 다만, 오탐(false negative)을 방지하기 위해 이를 필수 관문으로 두지는 않는다.
   • 속성 부여(Attribution): 트위들 테이블의 총 바이트 수는 출처를 나타내는 표식 역할을 한다. 서로 다른 구현 계보(예: C 참조 구현, Go 표준 라이브러리, Chrome/BoringSSL)는 서로 다른 수(1, 2, 또는 3개)의 테이블을 저장하며, 이를 통해 도구는 바이너리를 특정 소스 계보로 귀속시킬 수 있다.
4. 주요 기여
   1. 유도 절차: 공개 파라미터만으로 임의의 변환 기반 격자 스킴에 대한 지문 세트를 생성하는 일반적인 방법을 제공하여, 향로 또는 미검증 구현에 대한 커버리지를 보장한다.
   2. 강력한 탐지기: 데이터를 정규화하고 멀티셋 매칭을 사용하는 점수 산정 메커니즘을 통해, 다양한 컴파일러, 최적화 수준 및 난독화 기술 전반에 걸쳐 높은 재현율(recall)을 달로 달성하며, 분석적으로 도출된 오탐 경계치를 가진다.
   3. 계보 귀속: 소스 코드에 대한 접근 없이 오직 상수 테이블의 구성과 개수만을 바탕으로 주요 구현 계보(C-참조 vs. 명세 기반 구현)를 구별할 수 있는 능력을 입증하였다.
   4. 운영 검증: 본 방법은 두 가지 특정 맥락에서 검증되었다: 포렌식 조사(실행이 불가능한 압수된 디스크 이미지 분석) 및 이전 보증(출시된 바이너리에 대한 벤더의 주장을 검증).

실험 결과

• 재현율 및 정밀도: 네 개의 독립적인 구현 계보(C, Go, Rust, BoringSSL)와 모든 빌드 변환(스트립, 정적 링크, LLVM 명령어 치환 포함)에 걸친 실험에서, Kestrel은 ML-KEM에 대해 128/128의 재현율을, ML-DSA에 대해 255/256의 재현율(단 하나의 누락은 탐지 실패가 아닌 알려진 참조 구현의 특이 사항임)을 달성했다. 정밀도는 **100%**였으며 **오탐은 제로(0)**였다.
• 시스템 스윕(System Sweep): 실제 운영 중인 리눅스 시스템의 바이너리 6,224개를 스캔한 결과 오탐이 전혀 발견되지 않았다. 이 도구는 OpenSSH 키 교환 바이너리와 컨테이너 관리 스택(containerd, docker, runc)을 포함하여 ML-KEM을 포함하고 있는 12개의 미분류 프로그램을 식별해 냈다. 특히, 컨테이너 도구들은 프로젝트 유지 관리자의 명시적인 인지 없이 Go 언어 런타임으로부터 상속된 PQC 코드를 포함하고 있었다.
• 포렌식 복구: 삭제된 바이너리가 포함된 디스크 이미지를 대상으로 한 시험에서, 전통적인 파일 카빙(file carving)은 파일 복구에 실패했다. 그러나 Kestrel은 로우(raw) 미할당 공간을 스캔하여 ML-KEM 테이블을 성공적으로 탐지함으로써, 해당 신호가 파일 수준의 파괴에도 생존함을 입증했다.
• 적대적 회피: 도구는 사소한 회피 기법(재배열, 패딩, 분할)에 저항력을 가졌다. 오직 "바이트 재작성(byte-rewrite)" 회피(테이블을 런타임 키로 XOR 연산)만이 탐지를 무력화할 수 있었는데, 이는 암호 코드의 실질적인 수정을 요구한다.

의의 및 주장
본 논문은 Kestrel이 스트립된 바이너리 내의 양자 내성 격자 스킴 존재를 검증하는 최초의 실용적인 방법을 제공하며, 현재의 마이그레이션 및 포렌식 툴링의 사각지대를 해결한다고 주장한다.

• 컴플라이언스(Compliance): 바이너리가 실제로 주장된 PQC 프리미티브를 포함하고 있는지 확인함으로써 법적 마이그레이션 기한의 준수 여부를 검증할 수 있게 한다. 이는 벤더의 선언이나 소스 레벨 스캔에 의존하는 것과 차별화된다.
• 포렌식(Forensics): 조사관이 실제 PQC 구현과 허위 주장(예: PQC를 사용한다고 주장하지만 RSA를 사용하는 악성코드)을 구분할 수 있게 하며, 삭제되거나 손상된 파일에서 PQC를 탐지할 수 있게 한다.
• 범위 제한: 저자는 본 방법의 경계를 명시한다: 본 방법은 저장된 변환 테이블을 가진 격자 스킴(ML-KEM, ML-DSA)에만 적용되며, 일반적인 빌드 관행을 가정한다. 이는 해시 기반 스킴(SLH-DSA), 상수를 런타임에 계산하는 스킴, 또는 상수가 데이터 테이블이 아닌 명령어로 방출되는 매니지드 런타임(managed runtimes)은 다루지 않는다.

결론적으로, 본 논문은 상수 매칭 기법 자체는 확립된 것이나, 이를 스트립된 바이너리 내의 양자 내성 프리미티브에 적용하는 것은 새롭고 필수적인 작업임을 강조한다. 이는 해당 프리미티브가 일반적인 컴파일 과정에서도 제거할 수 없는 지문을 남기기 때문이다.