2025-11-15T18:46:12.059559

A Toolchain for Assisting Migration of Software Executables Towards Post-Quantum Cryptography

Rattanavipanon, Suaboot, Werapun
Quantum computing poses a significant global threat to today's security mechanisms. As a result, security experts and public sectors have issued guidelines to help organizations migrate their software to post-quantum cryptography (PQC). Despite these efforts, there is a lack of (semi-)automatic tools to support this transition especially when software is used and deployed as binary executables. To address this gap, in this work, we first propose a set of requirements necessary for a tool to detect quantum-vulnerable software executables. Following these requirements, we introduce QED: a toolchain for Quantum-vulnerable Executable Detection. QED uses a three-phase approach to identify quantum-vulnerable dependencies in a given set of executables, from file-level to API-level, and finally, precise identification of a static trace that triggers a quantum-vulnerable API. We evaluate QED on both a synthetic dataset with four cryptography libraries and a real-world dataset with over 200 software executables. The results demonstrate that: (1) QED discerns quantum-vulnerable from quantum-safe executables with 100% accuracy in the synthetic dataset; (2) QED is practical and scalable, completing analyses on average in less than 4 seconds per real-world executable; and (3) QED reduces the manual workload required by analysts to identify quantum-vulnerable executables in the real-world dataset by more than 90%. We hope that QED can become a crucial tool to facilitate the transition to PQC, particularly for small and medium-sized businesses with limited resources.
academic

소프트웨어 실행 파일의 양자 후 암호화로의 마이그레이션을 지원하는 도구 체인

기본 정보

  • 논문 ID: 2409.07852
  • 제목: A Toolchain for Assisting Migration of Software Executables Towards Post-Quantum Cryptography
  • 저자: Norrathep Rattanavipanon, Jakapan Suaboot, Warodom Werapun (송클라 왕자 대학교)
  • 분류: cs.CR (암호화 및 보안)
  • 발표 상태: IEEE ACCESS 저널에 제출됨
  • 논문 링크: https://arxiv.org/abs/2409.07852

초록

양자 컴퓨팅은 현재의 보안 메커니즘에 중대한 글로벌 위협을 야기한다. 보안 전문가와 공공 부문이 조직의 소프트웨어를 양자 후 암호화(PQC)로 마이그레이션하도록 지원하는 지침을 발표했음에도 불구하고, 특히 소프트웨어가 바이너리 실행 파일 형태로 배포될 때 이러한 전환을 지원하는 (반)자동화 도구가 부족하다. 이 문제를 해결하기 위해, 본 논문은 먼저 양자 취약 소프트웨어 실행 파일 검출 도구의 필수 요구사항을 제시한다. 이러한 요구사항을 바탕으로 QED(양자 취약 실행 파일 검출 도구 체인)를 소개한다. QED는 주어진 실행 파일 집합에서 양자 취약 종속성을 파일 수준에서 API 수준까지, 최종적으로 양자 취약 API를 트리거하는 정적 추적을 정확히 식별하는 3단계 접근 방식을 채택한다. 평가 결과는 다음을 보여준다: (1) QED는 합성 데이터셋에서 100% 정확도로 양자 취약 및 양자 안전 실행 파일을 구분한다; (2) QED는 실용적이고 확장 가능하며, 평균 4초 미만으로 실제 실행 파일 분석을 완료한다; (3) QED는 분석가가 양자 취약 실행 파일을 식별하는 데 필요한 수동 작업량을 90% 이상 감소시킨다.

연구 배경 및 동기

문제 정의

양자 컴퓨팅 기술의 빠른 발전으로 1998년의 2개 큐비트에서 현재 1000개 이상의 큐비트로 발전했으며, 전문가들은 대규모 기능성 양자 컴퓨터가 향후 20년 내에 상용화될 것으로 예측한다. 양자 컴퓨터는 RSA(4098개의 논리 큐비트 필요)와 타원곡선 암호(2330개의 논리 큐비트 필요)와 같이 현재 광범위하게 사용되는 공개키 암호 시스템을 깨뜨릴 수 있다.

중요성

양자 공격 위협에 대한 전 지구적 인식이 증가하고 있으며, NIST 등 기관은 조직이 양자 준비 팀을 구성하여 소프트웨어 시스템을 양자 후 암호화로 마이그레이션할 준비를 할 것을 권장한다. 여기에는 다음이 포함된다:

  1. 조직 내 암호화 사용을 평가하기 위한 암호화 인벤토리 작성
  2. 이러한 인벤토리를 기반으로 한 위험 평가

기존 방법의 한계

  1. 전문 도구 부족: 현재 PQC 마이그레이션 작업을 지원하도록 특별히 설계된 (반)자동화 도구가 없다
  2. 수동 분석 부담: 분석가는 산재된 다양한 도구와 수동 분석에 의존하여 양자 취약 소프트웨어 시스템을 식별해야 한다
  3. 바이너리 분석 과제: 분석가는 일반적으로 소스 코드에 접근할 수 없으며 프로그램 바이너리를 기반으로 PQC 마이그레이션을 수행해야 한다
  4. 비용 문제: 고급 바이너리 분석 지식이 필요하여 예산, 시간 및 인력 비용이 증가한다

연구 동기

이러한 과제, 특히 중소기업이 PQC 마이그레이션을 수행할 자원이 부족한 문제를 해결하기 위해, 본 논문은 분석가의 작업 부담을 경감하기 위한 자동화 도구 개발을 목표로 한다.

핵심 기여

  1. 요구사항 수립: 소프트웨어 실행 파일의 PQC 마이그레이션을 지원하는 도구의 요구사항 사양을 처음으로 체계적으로 수립했다
  2. QED 도구 체인: 제시된 요구사항을 충족하는 QED 도구 체인을 설계 및 구현했으며, 오픈소스 코드를 공개했다
  3. 실증 검증: 합성 및 실제 데이터셋에서 QED의 정확성과 효율성을 검증하여 100% 참양성률을 달성하고 90% 이상의 수동 작업량을 감소시켰다
  4. 실용적 가치: 자원이 제한된 중소기업을 위한 중요한 PQC 마이그레이션 지원 도구를 제공했다

방법론 상세 설명

작업 정의

주어진 소프트웨어 실행 파일 집합에 대해, QED의 목표는 양자 취약(QV) 실행 파일을 식별하는 것이다. 소프트웨어 실행 파일은 진입점(메인 함수)에서 QV 알고리즘(RSA, Diffie-Hellman, 타원곡선 디지털 서명 등)을 구현하는 암호화 라이브러리 API까지 적어도 하나의 가능한 실행 경로가 존재할 때 QV로 정의된다.

도구 요구사항(R1-R5)

  • R1 동적 링킹: 동적 링킹을 통해 QV API를 사용하는 실행 파일을 식별할 수 있어야 한다
  • R2 바이너리 수준 분석: 소스 코드 가용성에 의존하지 않는다
  • R3 정적 특성: 정적 특성만 사용하며, 런타임 실행 추적이 필요하지 않다
  • R4 확장성: 많은 수의 소프트웨어 실행 파일 분석을 지원하며, 합리적인 시간 내에 완료한다
  • R5 유효성: 거짓 음성을 생성하지 않으며, 소수의 거짓 양성을 허용한다

모델 아키텍처

QED는 3단계 점진적 분석 아키텍처를 채택한다:

1단계: 파일 수준 종속성 분석(P1)

목표: QV 암호화 라이브러리에 대한 종속성이 있는 실행 파일을 식별한다

방법:

  1. 소프트웨어 종속성 그래프 G₁ = (V₁, E₁)을 구성한다. 여기서 V₁은 파일 집합이고 E₁은 직접 종속성이다
  2. 깊이 우선 탐색을 통해 모든 종속성을 발견한다
  3. V₁에서 QV 암호화 라이브러리를 찾는다
  4. 암호화 라이브러리와 종속성이 없는 노드를 제거한다

출력: 파일 수준 종속성 경로 EV₁

2단계: API 수준 종속성 분석(P2)

목표: P1의 거짓 양성을 감소시키고 API 수준 종속성을 분석한다

방법:

  1. API 종속성 그래프 G₂ = (V₂, E₂)를 구성한다. E₂는 3중항(n₁, n₂, apis)을 포함한다
  2. 선행 노드가 QV API에 대한 함수 호출을 포함하는지 확인한다
  3. QV API 호출을 포함하지 않는 간선을 제거한다
  4. 각 간선에 API 수준 종속성 정보를 포함시킨다

출력: QV API 정보를 포함하는 종속성 경로 EV₂

3단계: 정적 추적 분석(P3)

목표: QV 정의를 충족하는 실행 파일을 정확히 식별한다

방법:

  1. 도달 가능성 분석을 위한 정적 호출 그래프를 구성한다
  2. 실행 파일 진입점에서 QV API까지의 실행 경로를 검증한다
  3. 일반 모드와 보수 모드를 지원한다
    • 일반 모드: 실행 추적 부재는 비-QV를 직접 나타낸다
    • 보수 모드: 누락된 추적을 잠재적 거짓 음성으로 간주한다

출력: 정적 실행 추적 EV₃

기술적 혁신 포인트

  1. 점진적 분석 전략: 거친 입도에서 세밀한 입도로의 3단계 분석으로 속도와 정확성의 균형을 맞춘다
  2. API 이름 정보 활용: API 이름 정보를 기반으로 암호화 사용을 검출하여 컴파일러 최적화로 인한 거짓 음성을 회피한다
  3. 동적 링킹 지원: 동적 링킹을 통해 암호화 라이브러리를 사용하는 시나리오를 특별히 처리한다
  4. 유연한 분석 모드: 일반 및 보수 두 가지 모드를 제공하여 분석가가 필요에 따라 선택할 수 있도록 한다

실험 설정

데이터셋

합성 데이터셋

  • 암호화 라이브러리: OpenSSL v1.1.1, OpenSSL v3.3.1, MbedTLS v2.28.8, wolfSSL v5.7.2
  • 암호화 원시: SHA-512, AES-256, Diffie-Hellman, RSA, ECDSA(마지막 세 개는 QV)
  • 직접 종속성 집합: 20개 실행 파일(12개 QV, 8개 비-QV)
  • 간접 종속성 집합: 20개 실행 파일(12개 QV, 8개 비-QV)
  • 총계: 40개 실행 파일(24개 QV, 16개 비-QV)

실제 데이터셋

  • Coreutils: 109개 비-암호화 소프트웨어(비-QV)
  • UnixBench: 18개 성능 벤치마크 도구(비-QV)
  • Network: 13개 네트워크 도구 프로그램(7개 QV, 6개 비-QV)
  • tpm2-tools: 86개 TPM 기능 구현 도구
  • 총계: 226개 실행 파일, 평균 크기 248KB

평가 지표

  • 참양성률(TPR): QV 실행 파일을 올바르게 식별하는 비율
  • 참음성률(TNR): 비-QV 실행 파일을 올바르게 식별하는 비율
  • 실행 시간: 각 단계의 분석에 필요한 시간
  • 메모리 사용: 피크 RAM 사용량
  • 수동 작업량 감소: 추가 수동 검토가 필요한 파일 수

구현 세부사항

  • 프로그래밍 언어: Python3(약 800줄 코드)
  • 종속성 라이브러리: pyelftools(ELF 파일 처리), NetworkX(그래프 연산), angr(정적 호출 그래프 구성)
  • 실험 환경: Ubuntu 20.04, Intel i5-8520U @ 1.6GHz, 24GB RAM

실험 결과

주요 결과

합성 데이터셋 정확성

단계직접 종속성간접 종속성전체
P1TPR: 100%, TNR: 0%TPR: 100%, TNR: 0%TPR: 100%, TNR: 0%
P1+P2TPR: 100%, TNR: 100%TPR: 100%, TNR: 0%TPR: 100%, TNR: 50%
P1+P2+P3TPR: 100%, TNR: 100%TPR: 100%, TNR: 100%TPR: 100%, TNR: 100%

실제 데이터셋 성능

  • 평균 처리 시간: 실행 파일당 약 4초
  • 총 처리 시간: 226개 실행 파일 약 15분
  • 메모리 사용: P1과 P2는 약 180MB, P3는 약 3-5GB
  • 수동 작업량 감소: 226개에서 20개로 감소(91.15% 감소)

절제 실험

  • P1 단계: 빠른 초기 필터링이지만 거짓 양성률이 높다
  • P2 단계: 거짓 양성을 크게 감소시키며, 특히 직접 종속성 시나리오에서 효과적이다
  • P3 단계: 정확도를 더욱 향상시키지만 계산 오버헤드가 더 크다

사례 분석

  • 거짓 음성 사례: curl 프로그램은 간접 호출(함수 포인터) 사용으로 인해 정적 호출 그래프 분석이 실패한다
  • 거짓 양성 제거: sftp와 scp 프로그램은 OpenSSL에 링크되어 있지만 비-QV API만 사용한다

실험 발견

  1. 점진적 분석의 효과: 3단계 설계가 속도와 정확성을 성공적으로 균형 맞춘다
  2. 정적 분석의 한계: 간접 호출은 여전히 정적 분석의 과제이다
  3. 실용성 검증: 도구는 실제 환경에서 잘 작동하며 수동 작업량을 크게 감소시킨다

관련 연구

암호화 발견 도구

기존 도구는 정적 및 동적 두 가지 범주로 나뉜다:

  • 정적 방법: 초기화 벡터, 조회 테이블, 어셈블리 명령어 시퀀스 등 정적 특성을 기반으로 한다
  • 동적 방법: 루프 구조, 입출력 관계 등 런타임 정보를 기반으로 한다

PQC 마이그레이션 연구

  • 마이그레이션 프로세스: 진단→계획→실행→유지보수 4단계
  • 암호화 민첩성: 다양한 암호화 알고리즘에 적응하는 시스템의 능력
  • 응용 시나리오: 컴파일된 바이너리, 외부 시스템 자산, 네트워크 통신 계층

본 논문의 장점

  • 양자 취약성 검출에 특화되어 있다
  • 동적 링킹 시나리오를 지원한다
  • 런타임 실행이나 무거운 기호 분석이 필요하지 않다
  • 엔드-투-엔드 실용 도구를 제공한다

결론 및 토론

주요 결론

  1. QED는 모든 5개의 설계 요구사항(R1-R5)을 성공적으로 충족한다
  2. 합성 데이터셋에서 100% 정확도를 달성한다
  3. 실제 데이터셋에서 수동 작업량을 크게 감소시킨다
  4. 도구는 우수한 확장성과 실용성을 갖는다

한계

  1. 간접 호출 검출: 정적 분석은 함수 포인터를 통한 QV API 사용을 검출할 수 없다
  2. 링킹 방식 제한: 실행 파일이 동적 링킹을 통해 암호화 라이브러리를 사용한다고 가정한다
  3. 죽은 코드 문제: 절대 실행되지 않는 QV API 호출을 양성으로 표시할 수 있다

향후 방향

  1. 경량 동적 분석: 동적 분석을 결합하여 간접 호출을 식별한다
  2. 정적 링킹 지원: 직접 구현되거나 정적으로 링크된 암호화 기능 검출을 확장한다
  3. 자동화된 패칭: 식별에서 (반)자동 양자 취약 사용 패칭으로 확장한다

심층 평가

장점

  1. 문제의 중요성: PQC 마이그레이션의 실제 문제점을 해결한다
  2. 체계적 접근: 요구사항 분석에서 도구 구현까지의 완전한 프로세스
  3. 기술적 혁신: 3단계 점진적 분석 전략 설계가 합리적이다
  4. 실용적 가치: 오픈소스 도구는 중소기업에 중요한 가치를 제공한다
  5. 충분한 실험: 합성 및 실제 데이터셋 검증이 포괄적이다

부족한 점

  1. 플랫폼 제한: 현재 Linux ELF 형식만 지원하며 확장성이 제한적이다
  2. 언어 제한: 주로 C/C++ 프로그램을 대상으로 한다
  3. 정적 분석 한계: 간접 호출 및 죽은 코드 분석이 불충분하다
  4. 평가 범위: 실제 데이터셋의 일부 프로그램이 기준 진실(ground truth)이 부족하다

영향력

  1. 학술 기여: PQC 마이그레이션 도구 연구의 공백을 채운다
  2. 실용적 가치: 조직의 PQC 마이그레이션을 위한 실용 도구를 제공한다
  3. 재현성: 오픈소스 코드와 데이터셋이 결과 재현을 지원한다
  4. 확산 가능성: 방법론을 다른 플랫폼과 언어로 확장할 수 있다

적용 시나리오

  • 기업 PQC 마이그레이션 위험 평가
  • 소프트웨어 공급망 보안 감사
  • 암호화 종속성 분석
  • 보안 규정 준수 검사

참고문헌

논문은 양자 컴퓨팅 발전, PQC 마이그레이션 지침, 암호화 검출 도구, 바이너리 분석 등 여러 분야의 중요한 작업을 포함하는 42개의 관련 문헌을 인용하여 연구에 견고한 이론적 기초를 제공한다.

종합 평가: 본 논문은 양자 후 암호화 마이그레이션이라는 중요한 문제에 대해 체계적인 해결책을 제시한다. QED 도구 체인은 설계가 합리적이고 실험 검증이 충분하며, 중요한 학술적 가치와 실용적 의의를 갖는다. 일부 기술적 한계가 있지만, PQC 마이그레이션 분야에 중요한 기여를 하였으며, 특히 자원이 제한된 중소기업을 위한 실행 가능한 솔루션을 제공한다.