Статья: АЛГЕБРАИЧЕСКИЕ АТАКИ НА НЕКОТОРЫЕ НИЗКОРЕСУРСНЫЕ ШИФРЫ НА ОСНОВЕ ФУНКЦИЙ С МАЛЫМ ЧИСЛОМ ВЫХОДНЫХ БИТ (2024)

Kyber представляет собой постквантовый механизм инкапсуляции ключа (Key Encapsulation Mechanism, КЕМ). Более того, на текущий момент Kyber является единственным постквантовым КЕМ, рекомендованным к стандартизации в США по итогам конкурса, проводимого NIST (National Institute of Standards and Technology). Предлагается алгоритмическая оптимизация модульной арифметики, используемой в Kyber, который значительно снижает количество операций приведения по модулю. Предложенная оптимизация позволяет достичь ускорения декапсуляции ключа в 1,83 раз, инкапсуляции ключа - в 1,58 раз и генерации ключевой пары - в 1,41 раз для программной реализации Kyber.

Квантовые вычисления активно развиваются в последние десятилетия: увеличивается количество кубитов, с которыми оперирует квантовый компьютер, и снижается вероятность вычислительных ошибок. Поэтому возникает необходимость в разработке и анализе постквантовых криптосистем - криптосистем, устойчивых к атакам с использованием квантового компьютера. Одним из основных подходов к построению таких криптосистем является теория решёток. В данном подходе стойкость большинства криптосистем сводится к решению задачи нахождения кратчайшего вектора в решётке (SVP). В работе приводятся результаты анализа алгоритма 8-просеивания для решения SVP. Предлагается новый компромисс между временем работы и количеством используемой памяти алгоритма 8-просеивания. Приводится сравнение с известными алгоритмами k-просеивания. На отрезке (20-155n, 20-189n) используемой памяти предложенный алгоритм имеет минимальное время работы среди известных алгоритмов k-просеивания.

Рассмотрена структура некоторых классов турниров, состоящих из одних королей, и их количество. Вершина v турнира называется королём, если длина пути из v до любой другой вершины составляет не более чем 2. Турнир называется простым, если его решётка конгруэнций двухэлементна и содержит только тождественную и универсальную конгруэнции. Основной результат работы состоит в том, что турниры, состоящие из одних королей, не являются простыми.

Сформулированы некоторые необходимые и некоторые достаточные условия максимальности периода конечно-автоматного генератора. Предложен способ построения генератора с максимальным периодом.

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

Работа является продолжением исследований по поиску точных формул для вычисления параметров Бхаттачарьи Z координатных каналов W полярного кода в случае, когда канал передачи является двоичным симметричным и без памяти, требующих полиномиального числа операций. Для этого необходимо уметь строить такие базисы подпространств Zi-1, порожденных первыми i - 1 строками поляризационной матрицы GN полярного кода длины N, и подпространств Ui+1, порожденных последними N - i строками матрицы GN, что вес Хемминга является аддитивной функцией на векторах базиса (или близкой к ней). Эти задачи решаются для двух последовательностей i = 2m + 1 и i = 2m - 1, а также при i≥ N/2. Как следствие, мы находим короткие и полиномиальные формулы для Z W2m+1 и Z W2m-1 а также полиномиально-экспонециальные для Z при i ≥ N/2. В заключении приводится список формул для вычисления всех параметров Бхаттачарьи кода длины 32.

Рассматриваются возможности использования обобщённых (L, G) кодов для решения различных задач защиты информации, в частности использование таких кодов для синдромного встраивания информации, кодового сжатия, взвешенных пороговых схем распределения ключей.

Работа посвящена задаче №7 Олимпиады NSUCRYPTO 2023 г. об описании интересного класса кодов C - с однозначным декодированием к ближайшему кодовому слову в метрике Хэмминга. Доказана возможность представления кода C как матроида и приведено промежуточное решение в случае, когда множество B битов, таких, что существует двухбитовое слово, его содержащее, декодирующееся не в z = позициями битов кода C.

Рассматривается задача описания деревьев, все максимальные поддеревья которых изоморфны. Приводится характеристическая теорема для таких деревьев: все максимальные поддеревья дерева изоморфны тогда и только тогда, когда все его листья подобны. Вводится класс многоуровневых звёзд. Доказывается, что этот класс совпадает с классом деревьев, все максимальные поддеревья которых изоморфны.

Рассмотрен новый подход к сокрытию кода исполняемых файлов ОС Linux при помощи таблицы перемещений, позволяющий создать криптор без встраивания в исполняемый файл кода расшифрования. Исследованы различные варианты практического применения данного подхода, реализованы соответствующие прототипы крипторов. Оценена опасность подхода для инструментов обратной разработки IDA, Ghidra, angr и антивирусного ПО.

Разработана программная система замера эффективности внутреннего представления схем zk-SNARK. Система предназначена для измерения параметров схем доказательства с нулевым разглашением zk-SNARK - количества ограничений во внутреннем представлении систем ограничений ранга 1 (R1CS), времени работы алгоритмов zk-SNARK и размеров ключей доказательства. Система позволяет разработчикам схем zk-SNARK на этапе написания кода измерять различные параметры производительности и оптимизировать представления системы ограничений. Разработанная программная система может быть использована для замера эффективности произвольных схем zk-SNARK и определения их применимости для различных приложений.

Графовые модели занимают важное место в задачах, связанных с защитой информации и информационной безопасностью. Рассматривается конечная динамическая система, состояниями которой являются все возможные ориентации данного графа, а эволюционная функция задаётся следующим образом: динамическим образом данного орграфа является орграф, полученный из исходного путём переориентации всех дуг, входящих в стоки, других отличий между исходным орграфом и его образом нет. Предлагается, как можно применять данную систему для защиты информации и информационной безопасности, а именно: как модель обеспечения аудита и мониторинга состояния объекта, находящегося под воздействием угроз нарушения его информационной безопасности, и расследования инцидентов информационной безопасности в автоматизированных информационных системах; как модель управления непрерывным функционированием и восстановлением систем, противодействия отказам в обслуживании; как технологию идентификации и аутентификации пользователей и субъектов информационных процессов, систему разграничения доступа.

Исследуются системы некоммутативных символьных линейных однородных уравнений, которые интерпретируются как линейные грамматики формальных языков. Такие системы решаются в виде формальных степенных рядов (ФСР), выражающих нетерминальные символы через терминальные символы алфавита и рассматриваемых как линейные языки. Всякому ФСР поставлен в соответствие его коммутативный образ, который получается в предположении, что все символы обозначают коммутативные переменные, действительные или комплексные. Рассматриваются системы уравнений, которые могут иметь бесконечное множество решений, параметризуемых не произвольными числами, а произвольными ФСР. Оценено количество таких параметров, что даёт некоммутативный аналог известного факта теории линейных уравнений.

С использованием матрично-графового подхода исследуются перемешивающие свойства регистровых преобразований поточных алгоритмов шифрования ТЕА1 и ТЕА2 стандарта цифровой транкинговой радиосвязи ТЕТRА. Получены значения экспонентов перемешивающих матриц, соответствующих регистровым преобразованиям исследуемых алгоритмов. Результаты могут быть использованы для оценки числа тактов работы регистров преобразования ключа в алгоритмах поточного шифрования, необходимых для обеспечения существенной зависимости каждого бита выходной последовательности от всех битов ключа.

Работа посвящена анализу параметров постквантовых схем подписи на основе хешей без сохранения состояния (SPHINCS+, SPHINCS+C и Гиперикум). Предлагаются новые наборы параметров, обеспечивающие 120-битную стойкость к подделке против квантового злоумышленника. Выбор наборов осуществлялся с учётом прикладных характеристик и возможных областей применения рассматриваемых схем.

Работа посвящена истории развития Международной олимпиады по криптографии Non-Stop University CRYPTO, её открытым проблемам и результатам.

Анализируется класс XSL-алгоритмов блочного шифрования с алгоритмом развертывания ключа на основе рекуррентного соотношения второго порядка и матрицей линейного преобразования, у которой существуют хотя бы два равных элемента в некоторой строке обратной матрицы. Предложена атака на 6-раундовый XSL-алгоритм блочного шифрования на основе комбинирования методов встречи посередине, невозможных разностей, а также модификации подхода «уоуо». Сначала на основе обобщения метода встречи посередине формируется множество кандидатов в раундовые ключи первого раунда. Далее для получения множества кандидатов в раундовые ключи шестого раунда строится различитель, основанный на комбинации невозможных разностей и соотношений из модифицированного подхода «уоуо». Вероятность успеха равна 0,7. Полученные результаты подтверждены на модельном XSL-алгоритме блочного шифрования с 16-битным блоком открытого текста.

КБ-256 - алгоритм блочного шифрования, рекомендованный для защиты больших объёмов данных. Рассматриваются вопросы криптографической стойкости КБ-256 в модели атакующего, имеющего доступ к квантовому компьютеру. Оценивается трудоёмкости применения алгоритма Гровера - сложности квантовой схемы, в которой необходимо реализовать оракул алгоритма КБ-256, а также количество необходимого материала. Помимо этого, рассматривается возможность атаки с помощью алгоритмов поиска скрытого сдвига.

Работа является обзорной, она посвящена алгоритмам аутентифицированного шифрования с присоединёнными данными, а также функционально аналогичным режимам работы алгоритмов блочного симметричного шифрования. Рассмотрены стандартизованные режимы работы Galois/Counter Mode и Multilinear Galois Mode, a также алгоритмы шифрования, изначально разработанные для реализации подобных преобразований, на примере алгоритма Ascon. Показана оптимальность аутентифицированного шифрования с присоединёнными данными для использования в низкоресурсных устройствах на примере радиочастотных меток, взаимодействующих со считывателем по радиоканалу. Обозначены некоторые из возможных критериев выбора конкретного алгоритма и/или режима работы для реализации на целевой низкоресурсной платформе.

В рамках вероятностной модели шифра рассмотрена задача разложения (декомпозиции) в некоторой ортогональной системе координат дискретного пространства Q элементарных событий на пары семейств несовместных событий, независимых с любым событием другого семейства. Показано, что для составного числа N (мощности дискретного пространства элементарных событий) существуют пары независимых подпространств пространства, а для простых чисел N независимых подпространств не существует. Построены примеры, иллюстрирующие полученные теоретические утверждения.

В 2022 г. в Российской Федерации приняты рекомендации по стандартизации, определяющие режим работы блочных шифров DEC, используемый для защиты носителей информации с блочно-ориентированной структурой. Данный режим представляет собой модификацию режима гаммирования со специальным алгоритмом выработки синхропосылки и начальным значением счётчика из номера раздела и номера сектора носителя информации. В работе представлена модель доказуемой (редукционистской) стойкости, формализующая обеспечение конфиденциальности в условиях наличия у нарушителя доступа к квантовому оракулу. В рамках данной модели предложена атака различения на режим DEC, требующая единственный запрос к оракулу. Атака основана на возможности перехода к незапутанному состоянию регистров открытого и шифрованного текстов в случае зашифрования непосредственно открытого текста, переданного нарушителем, и невозможности такого перехода при зашифровании результата применения случайной подстановки к открытому тексту.

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

Основным компонентом криптографической хеш-функции MD4 является 48-шаговая функция сжатия. В 2007 г. прообраз 39-шаговой функции сжатия MD4 был найден с помощью CDCL - основного полного алгоритма решения проблемы булевой выполнимости (SAT). В 2022г. с помощью параллельного SAT-алгоритма Cube-and-Conquer был найден прообраз 43-шаговой функции сжатия MD4. В настоящей работе исследуется 44-шаговая версия функции сжатия MD4, такая, что 44-й шаг ослаблен разными способами. С помощью Cube-and-Conquer найдены прообразы нескольких таких функций. На основе решённых задач предложена оценка времени, необходимого для нахождения прообраза 44-шаговой функции сжатия MD4.

Введён класс разностно-линейных атак различения на блочные шифры. Построена атака (названная разностно-сингулярной), оптимальная в данном классе. Проведены вероятностно-статистические эксперименты с шифрсистемами семейства SmallPresent с длинами блока n ∈ {8,12,16} и R ∈ {3,…, 9} раундами.

Вычисляется восьмая степень матрицы переходных вероятностей схемы Луби - Ракофф, даются оценки объёма материала j-векторных (j = 1, 2) разностно-спектральных атак различения на 8 раундов схемы Луби - Ракофф в модели независимых двублочных текстов.

Изучаются периодические, частотные и автокорреляционные характеристики отрезков промежуточных и выходных последовательностей, вырабатываемых алгоритмом поточного шифрования GEA-1. Результаты получены с использованием известных оценок тригонометрических сумм, зависящих от знаков линейных рекуррентных последовательностей.

Исследуются схемы для обработки сигнала, получаемого с кольцевых осцилляторов; преобразованные последовательности тестируются на свойства случайности. Предложено пять вариантов преобразования выходного сигнала. В качестве инструментов преобразования использованы комбинации метода фон Неймана и Математические методы криптографии 71 операции XOR. Тестирование полученных последовательностей выполнено с помощью пакета тестов NIST STS. Последовательность, полученная после преобразования №5, показала наилучший результат по итогам тестирования и была сравнена с последовательностью, зашифрованной алгоритмом AES в режиме счётчика. Сравнение показало, что количество успешно пройденных тестов преобразованной последовательности выше, чем у последовательности, зашифрованной алгоритмом AES.

Приводятся результаты анализа схемы VKO и комбинированной схемы VKO+подпись в моделях обобщённой группы и биективного случайного оракула. Получена верхняя оценка сложности задачи различения выхода схемы VKO от случайной равновероятной строки (в эвристике обобщенной группы), а также показано, что возможности получения подписи сообщений по алгоритму genGOST не даёт никакой дополнительной информации противнику в этой задаче (в эвристике биективного случайного оракула).

Описываются атаки на протоколы аутентифицированной выработки общего ключа SIGMA, SIG-DH и TS3-1 при наличии у нарушителя возможности навязывания связанных долговременных ключей честным участникам при их регистрации в сети. Важным условием реализуемости описываемых атак является наличие у схем подписи, используемых в указанных протоколах, уязвимости к атаке со связанными ключами (примером уязвимой схемы подписи является схема EGDSA). В результате каждой из трёх описываемых атак реализуется угроза ложной аутентификации. Атаки отличаются используемым набором возможностей нарушителя, необходимости которых вызвана особенностями конструкции протоколов в части подписываемых сообщений. Если подписывается идентификатор инициатора, передаваемый в первом сообщении, то дополнительно требуется возможности навязывания честному участнику его идентификатора при регистрации в сети. Если подписывается эфемерный ключ ответчика, то требуется возможности компрометации будущих открытых эфемерных ключей.

Изучается множество булевых функций от малого числа переменных с оптимальными показателями алгебраической и корреляционной иммунности. Исследуется возможность использования данных функций в качестве координатных функций S-блока.

Предложены тесты криптоаналитической обратимости для функций от трёх аргументов. Сформулированы алгоритмы построения функции восстановления и генерации обратимых функций.

Рассматривается конструкция векторной булевой функции, координаты которой получаются из одной булевой функции с помощью циклического сдвига вектора переменных. Предложен алгоритм построения такой функции, обладающей свойством обратимости; доказаны его полнота и корректности; посчитано количество доставляемых им функций, а также количество обратимых функций в обобщённой конструкции - когда к вектору переменных применяется произвольная полноцикловая перестановка.

Бент-функции вида F2 → Zq, где q ≥ 2- натуральное число, называются обобщёнными бент-функциями. Обобщённые бент-функции, для которых можно определить дуальную бент-функцию, называются регулярными. Исследуются обобщённые бент-функции, алгебраическая степень которых равна 1. Получены необходимые и достаточные условия того, что обобщённая булева функция алгебраической степени 1 является бент-функцией. Исследованы условия, при которых функция будет регулярной, а также слабо регулярной. Для случая q = 2k получено описание компонентных булевых функций обобщённой бент-функции алгебраической степени 1, из которого следует, что две из них, имеющие наибольший индекс, являются квадратичными, а остальные - постоянными.

Рассматриваются оценки мощности множеств Pn обратимых функций F : F2→F2, для которых любое U ⊆ F2 и его образ F(U) не могут одновременно являться аффинными подпространствами F2 размерности k, где 3 ≤ k ≤ n - 1. Приведены нижние оценки мощности Pn и Pn … ∩ Pn-1, усиливающие результаты 2007 г. (W. Е. Clark и др.)о непустоте данных множеств. Доказано, что почти все подстановки на F2 принадлежат Pn ∩ … ∩ Pn-1. Для мощностей множеств Pn и Pn∩ … ∩ Pn-1 получены асимптотические оценки сверху и снизу с точностью до 0(2n!). Оценено снизу число функций из Pn∩ …∩ Pn-1, которые отображают ровно одно аффинное подпространство F размерности 3 в аффинное подпространство.

Атака методом бумеранга, предложенная в 1999 г., является разновидностью разностной атаки. Её преимущество заключается в том, что даже при невысоком показателе дифференциальной равномерности шифр всё равно может быть уязвим. Данная работа посвящена такому параметру векторной булевой функции, как бумеранговая равномерности, который характеризует стойкости функции к атаке методом бумеранга. В качестве исследуемого класса функций рассматриваются квадратичные подстановки. Изучена зависимости бумеранговой характеристики от дифференциальной для этого класса, основным результатом является выражение, связывающее бумеранговую равномерности функции со значениями её DDT-таблицы и полученное благодаря использованию матричного подхода к работе с квадратичными функциями, а также известных свойств дифференциальной и бумеранговой характеристик. Исследованы некоторые конструкции квадратичных подстановок для малого числа переменных на предмет бумеранговой характеристики и установлены другие их свойства.

Рассматривается количество ближайших бент-функций к некоторым бент-функциям из класса Мэйорана - МакФарланда М2n, близкое к оценкам для него: нижней l2n = 22n+1- 2n и точной верхней £2n. Для бент-функций вида f(х,у) = ⟨х,σ(у)⟩ ⊕ φ(у) ∈ М2n где σ построена с помощью функции инверсии элементов конечного поля, подсчитано число ближайших бент-функций при тождественно нулевой φ, а также показано, что для некоторой подходящей φ количество ближайших к f меньше чем l2n + 82(2n - 1), т. е. равно l2n + о(l2n) при n → ∞. Получена формула числа бент-функций, ближайших к f(x, у) = ⟨x, у⟩ ⊕ y1y2.. .ym ∈ M2n,где 3 ≤ m ≤ n. Для m = 3 и m = n это число равно о(L2n) и 1/3L2n + о(L2n соответственно при n → ∞. Приведена полная классификация M6 по числу ближайших бент-функций.

Приводятся аналоги теорем о строении медиальных и парамедиальных квазигрупповых алгебр и некоторых их обобщений применительно к случаю сильно зависимых бинарных операций.

Рассматриваются разбиения Wn,l подмножества Vn(2m) декартова произведения V1 (2m) векторного пространства Vn(2m) полем F2m, состоящего из всех l-грамм с попарно различными координатами, l,n,m ∈ N,l,n ≥2. Такие разбиения обобщают «классические» разностные разбиения при l = 2 и встречаются в методах криптоанализа, использующих линейности, высшие, усечённые, невозможные и кратные разности. На Vn(2m) задано покоординатное действие группы S(Vn(2m)) на l-граммах. Описываются свойства подстановок, максимально удалённых относительно метрики Хемминга от группы, сохраняющей разбиения W декартово произведения Vn(2m). Данные подстановки названы совершенно рассеивающими разбиение W. Указана связь между подстановками, совершенно рассеивающими разбиения Wn,l, APN-подстановками, АВ-подстановками и 2r- разностно-равномерными подстановками, r ≥ 1. Сравниваются свойства рассеивания разбиений W(n,3) известными классами подстановок S-боксов.

Приводятся все возможные характеристические многочлены эндоморфизма Фробениуса геометрически разложимых обычных абелевых многообразий размерности 3 над конечным полем.

Рассматриваются все возможные двоичные последовательности, имеющие длину a + b и состоящие из a единиц и b нулей. Для такой последовательности исследуется число пар содержащихся в ней подпоследовательностей заданной длины s (так называемых s-цепочек) с совпадающими значениями элементов этих подпоследовательностей. В предположении, что все исходные последовательности равновероятны, предлагается точная формула для числа пар s-цепочек с совпадающими значениями.

Рассматриваются 5-конфигурации, определяемые их матрицами инциденций над полем GF(2), которые должны быть невырожденными и содержать в каждой строке и каждом столбце ровно 5 единиц, причём обратная матрица также должна обладать этим свойством. Изучаются автоморфизмы 5-конфигураций. Указывается связь между группой автоморфизмов ориентированного графа без петель и параллельных дуг с двумя входными и двумя выходными дугами при каждой вершине и группой автоморфизмов 5-конфигурации, получаемой по этому орграфу.