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. Результаты оценки показывают: (1) QED различает квантово-уязвимые и квантово-безопасные исполняемые файлы с точностью 100% на синтетическом наборе данных; (2) QED практичен и масштабируем, в среднем завершая анализ реальных исполняемых файлов менее чем за 4 секунды; (3) QED снижает объем ручной работы, необходимой аналитикам для выявления квантово-уязвимых исполняемых файлов, более чем на 90%.

Исследовательский контекст и мотивация

Определение проблемы

С быстрым развитием квантовых вычислений, эволюционировавших от 2 кубитов в 1998 году до более чем 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 тогда и только тогда, когда существует по крайней мере один возможный путь выполнения от его точки входа (функция main) до API криптографической библиотеки, реализующей QV-алгоритм (такие как RSA, Diffie-Hellman, подпись ECDSA).

Требования к инструменту (R1-R5)

  • R1 Динамическое связывание: Должен идентифицировать исполняемые файлы, использующие QV API через динамическое связывание
  • R2 Анализ на уровне двоичного кода: Не зависит от доступности исходного кода
  • R3 Статические признаки: Использует только статические признаки, не требует трассировки выполнения во время выполнения
  • R4 Масштабируемость: Поддерживает анализ большого количества программных исполняемых файлов в разумные сроки
  • R5 Действительность: Не производит ложноотрицательные результаты, допускает небольшое количество ложноположительных результатов

Архитектура модели

QED использует трехэтапную архитектуру прогрессивного анализа:

Этап первый: анализ зависимостей на уровне файлов (P1)

Цель: Выявление исполняемых файлов, имеющих зависимости от QV криптографических библиотек

Метод:

  1. Построение графика зависимостей программного обеспечения G₁ = (V₁, E₁), где V₁ — набор файлов, E₁ — отношения прямых зависимостей
  2. Обнаружение всех зависимостей посредством поиска в глубину
  3. Локализация QV криптографических библиотек в V₁
  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 исполняемых файлов, средний размер 248 КБ

Метрики оценки

  • Истинно положительный результат (TPR): Доля правильно выявленных QV исполняемых файлов
  • Истинно отрицательный результат (TNR): Доля правильно выявленных не-QV исполняемых файлов
  • Время выполнения: Время, необходимое для анализа на каждом этапе
  • Использование памяти: Пиковое использование оперативной памяти
  • Снижение ручной работы: Количество файлов, требующих дальнейшего ручного рассмотрения

Детали реализации

  • Язык программирования: 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 секунды на исполняемый файл
  • Общее время обработки: примерно 15 минут для 226 исполняемых файлов
  • Использование памяти: P1 и P2 примерно 180 МБ, P3 примерно 3-5 ГБ
  • Снижение ручной работы: с 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, особенно предоставляя практическое решение для малых и средних предприятий с ограниченными ресурсами.