Автоматизированная модель для дифференциальных атак meet-in-the-middle на шифры AndRX

Почему это исследование важно

Каждый раз, когда мы пользуемся смартфоном, платим в сети или подключаем медицинское устройство, наши данные защищают крошечные цифровые замки — блочные шифры. Эксперты по безопасности постоянно пытаются взломать эти замки, чтобы создавать более надёжные. В этой работе приводится новый способ автоматизации мощного класса атак на популярное семейство легковесных шифров, что помогает исследователям проверить, насколько прочны эти цифровые замки на самом деле.

Как работают современные методы вскрытия кода

Современные блочные шифры перемешивают данные во множестве мелких шагов, или раундов, управляемых секретным ключом. Чтобы оценить безопасность шифра, криптоаналитики ищут закономерности, которые не должны существовать, если система ведёт себя как чистая случайность. Два классических подхода — дифференциальный криптоанализ, отслеживающий, как малые изменения на входе распространяются на выход, и атаки meet-in-the-middle, которые вычисляют состояния одновременно от начала и от конца шифра и ищут совпадения в середине. Каждое из этих средств по отдельности имеет ограничения, но их комбинация даёт более точечный инструмент для изучения структуры шифра.

Слияние двух идей атаки

Исследование сосредоточено на гибридной технике, называемой дифференциальной meet-in-the-middle атакой. Здесь шифр разделяют на три части: входную, среднюю и выходную. В середине атакующий ищет «дифференциальный различитель» — шаблон входных и выходных различий, который встречается чаще, чем случайно, на протяжении нескольких раундов. Вокруг этого ядра атакующий частично шифрует от начала и частично расшифровывает от конца, угадывая только выбранные куски ключа. Когда два направления сходятся в одном и том же внутреннем состоянии, сделанные догадки с большей вероятностью соответствуют реальному ключу, что сокращает пространство поиска.

Преобразование ручного мастерства в автоматический инструмент

Проектирование таких комбинированных атак вручную чрезвычайно трудно, особенно для бит-ориентированных шифров с внутренним состоянием шириной 64, 96 или 128 бит. Авторы создают автоматизированную рамочную систему, использующую программирование с ограничениями — метод описания сложных логических условий, чтобы солвер мог перебрать все допустимые варианты. Сначала они кодируют, как различия проходят через базовые строительные блоки шифра на основе операций AND, сдвига и XOR — семейство, известное как конструкции AndRX. Затем моделируют, какие биты ключа влияют на каждый этап и сколько из этих битов действительно нужно угадывать. Солвер перебирает множество способов разрезать шифр на входную, среднюю и выходную части, выбирая раскладку, минимизирующую общие затраты на атаку.

Дополнительные приёмы для сокращения пространства ключей

Поверх базовой модели фреймворк добавляет две оптимизации, адаптированные к шифрам в стиле Фейстеля на основе AndRX, таким как SIMON и Simeck. Первая, идея эквивалентных субключей, математически сдвигает части раундовых ключей вперёд или назад так, что несколько разных битов ключа ведут себя как один и тот же бит. Это уменьшает число независимых бит, которые нужно учитывать атакующему. Вторая, селективное угадывание ключа, анализирует, как нелинейная операция AND использует свои входы, и показывает, что при определённых условиях один угаданный бит может заменить два. Авторы также описывают, но пока не полностью автоматизируют, ещё два улучшения: параллельное разбиение, которое может добавить дополнительный раунд в атаку без увеличения времени, и приём сокращения объёма данных, уменьшающий число выбранных сообщений, необходимых для атаки.

Что инструмент показывает о реальных шифрах

Чтобы проверить подход, исследователи применили свою автоматизированную модель ко всем стандартным вариантам легковесных шифров SIMON и Simeck, которые рассматриваются для использования в ограниченных устройствах, таких как сенсоры и встроенные контроллеры. Для каждой версии инструмент находит дифференциальную meet-in-the-middle атаку и оценивает её требования по данным, времени и памяти. Во многих случаях эти атаки охватывают больше раундов, чем предыдущие meet-in-the-middle или родственные методы, и часто превосходят ранние impossible differential и zero-correlation атаки по числу покрытых раундов. Например, инструмент даёт атаки на до 51 раунда для 128-битной версии SIMON с 256-битным ключом, расширяя охват ранних методов при сохранении объёма работы ниже, чем полный перебор всех ключей.

Общая картина для будущей криптографии

Для неспециалистов главное сообщение не в том, что SIMON или Simeck «сломаны» в практических условиях, а в том, что автоматизированные инструменты становятся достаточно мощными, чтобы исследовать тонкие слабости, которые было бы очень трудно найти вручную. Представленная здесь рамочная система является универсальной на битовом уровне и в принципе может быть адаптирована к другим семействам шифров. Помогая разработчикам быстро проверять, как новые алгоритмы выдерживают продвинутые комбинированные атаки, такие инструменты поддерживают долгосрочную цель — создание шифрования, остающегося надёжным по мере усложнения аналитических методов.

Цитирование: Chakraborty, D., Sahoo, S., Nguyen, P.H. et al. An automated model for differential meet in the middle attacks on AndRX ciphers. Sci Rep 16, 14773 (2026). https://doi.org/10.1038/s41598-026-41390-w

Ключевые слова: криптоанализ блочных шифров, дифференциальный meet-in-the-middle, шифр SIMON, шифр Simeck, программирование с ограничениями