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

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

基本信息

  • 论文ID: 2409.07852
  • 标题: A Toolchain for Assisting Migration of Software Executables Towards Post-Quantum Cryptography
  • 作者: Norrathep Rattanavipanon, Jakapan Suaboot, Warodom Werapun (Prince of Songkla University)
  • 分类: cs.CR (Cryptography and Security)
  • 发表状态: 已提交至IEEE ACCESS期刊
  • 论文链接: https://arxiv.org/abs/2409.07852

摘要

量子计算对当今安全机制构成重大全球威胁。尽管安全专家和公共部门已发布指导方针帮助组织将软件迁移到后量子密码学(PQC)，但缺乏支持这种转换的(半)自动化工具，特别是当软件以二进制可执行文件形式部署时。为解决这一问题，本文首先提出了检测量子脆弱软件可执行文件工具的必要需求。基于这些需求，引入了QED：量子脆弱可执行文件检测工具链。QED采用三阶段方法识别给定可执行文件集合中的量子脆弱依赖关系，从文件级到API级，最终精确识别触发量子脆弱API的静态跟踪。评估结果显示：(1) QED在合成数据集上以100%准确率区分量子脆弱和量子安全可执行文件；(2) QED实用且可扩展，平均在不到4秒内完成对真实世界可执行文件的分析；(3) QED将分析师识别量子脆弱可执行文件所需的手动工作量减少了90%以上。

研究背景与动机

问题定义

随着量子计算技术的快速发展，从1998年的2个量子比特发展到现在超过1000个量子比特，专家预测大规模功能性量子计算机将在未来二十年内商业化。量子计算机能够破解当前广泛使用的公钥密码系统，如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，当且仅当从其入口点（主函数）到实现QV算法（如RSA、Diffie-Hellman、椭圆曲线数字签名）的密码学库API之间存在至少一条可能的执行路径。

工具需求(R1-R5)

  • R1 动态链接：必须能识别通过动态链接使用QV API的可执行文件
  • R2 二进制级分析：不依赖源代码可用性
  • R3 静态特征：仅使用静态特征，不需要运行时执行跟踪
  • R4 可扩展性：支持大量软件可执行文件的分析，在合理时间内完成
  • R5 有效性：不产生假阴性，可容忍少量假阳性

模型架构

QED采用三阶段渐进式分析架构：

第一阶段：文件级依赖分析(P1)

目标：识别对QV密码学库有依赖关系的可执行文件

方法：

  1. 构建软件依赖图G₁ = (V₁, E₁)，其中V₁是文件集合，E₁是直接依赖关系
  2. 通过深度优先搜索发现所有依赖关系
  3. 定位V₁中的QV密码学库
  4. 剪除与密码学库无依赖关系的节点

输出：文件级依赖路径EV₁

第二阶段：API级依赖分析(P2)

目标：减少P1中的假阳性，分析API级依赖关系

方法：

  1. 构建API依赖图G₂ = (V₂, E₂)，E₂包含三元组(n₁, n₂, apis)
  2. 检查前驱节点是否包含对QV API的函数调用
  3. 移除不包含QV API调用的边
  4. 为每条边嵌入API级依赖信息

输出：包含QV API信息的依赖路径EV₂

第三阶段：静态跟踪分析(P3)

目标：精确识别符合QV定义的可执行文件

方法：

  1. 构建静态调用图进行可达性分析
  2. 验证从可执行文件入口点到QV API的执行路径
  3. 支持普通模式和保守模式
    • 普通模式：缺少执行跟踪直接表明非QV
    • 保守模式：将缺失跟踪视为潜在假阴性

输出：静态执行跟踪EV₃

技术创新点

  1. 渐进式分析策略：从粗粒度到细粒度的三阶段分析，平衡速度和准确性
  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. 渐进式分析有效：三阶段设计成功平衡了速度和准确性
  2. 静态分析局限：间接调用仍是静态分析的挑战
  3. 实用性验证：工具在真实环境中表现良好，显著减少手动工作量

相关工作

密码学发现工具

现有工具分为静态和动态两类：

  • 静态方法：基于初始化向量、查找表、汇编指令序列等静态特征
  • 动态方法：基于运行时信息如循环结构、输入输出关系等

PQC迁移研究

  • 迁移流程：诊断→规划→执行→维护四步骤
  • 密码敏捷性：系统适应不同密码算法的能力
  • 应用场景：编译二进制、外部系统资产、网络通信层

本文优势

  • 专门针对量子脆弱性检测
  • 支持动态链接场景
  • 不需要运行时执行或重量级符号分析
  • 提供端到端的实用工具

结论与讨论

主要结论

  1. QED成功满足了所有五个设计需求（R1-R5）
  2. 在合成数据集上实现100%准确率
  3. 在真实世界数据集上显著减少手动工作量
  4. 工具具有良好的可扩展性和实用性

局限性

  1. 间接调用检测：静态分析无法检测通过函数指针的QV API使用
  2. 链接方式限制：假设可执行文件通过动态链接使用密码学库
  3. 死代码问题：可能将永不执行的QV API调用标记为阳性

未来方向

  1. 轻量级动态分析：结合动态分析识别间接调用
  2. 静态链接支持：扩展检测直接实现或静态链接的密码学功能
  3. 自动化修补：从识别扩展到(半)自动修补量子脆弱使用

深度评价

优点

  1. 问题重要性：解决了PQC迁移中的实际痛点
  2. 系统性方法：从需求分析到工具实现的完整流程
  3. 技术创新：三阶段渐进式分析策略设计合理
  4. 实用价值：开源工具对中小企业具有重要价值
  5. 实验充分：合成和真实数据集验证全面

不足

  1. 平台限制：目前仅支持Linux ELF格式，扩展性有限
  2. 语言局限：主要针对C/C++程序
  3. 静态分析局限：对间接调用和死代码分析不足
  4. 评估范围：真实数据集中部分程序缺乏ground truth

影响力

  1. 学术贡献：填补了PQC迁移工具研究的空白
  2. 实用价值：为组织PQC迁移提供了实用工具
  3. 可复现性：开源代码和数据集支持结果复现
  4. 推广潜力：方法可扩展到其他平台和语言

适用场景

  • 企业PQC迁移风险评估
  • 软件供应链安全审计
  • 密码学依赖分析
  • 安全合规性检查

参考文献

论文引用了42篇相关文献，涵盖量子计算发展、PQC迁移指南、密码学检测工具、二进制分析等多个领域的重要工作，为研究提供了坚实的理论基础。

总体评价：本文针对后量子密码学迁移这一重要问题，提出了系统性的解决方案。QED工具链设计合理，实验验证充分，具有重要的学术价值和实用意义。尽管存在一些技术局限性，但为PQC迁移领域做出了重要贡献，特别是为资源有限的中小企业提供了可行的解决方案。