Аннотация результатов, полученных в 2018 году
В современной информационной безопасности криптографические методы играют одну из центральных ролей. Расширение сферы применения методов защиты информации и появление новых угроз приводит к росту множества криптографических конструкций. Зачастую это делает нетривиальной проблему выбора того или иного шифра для решения конкретной задачи на конкретном типе устройств и платформ. В силу сказанного актуальной является проблема использования интеллектуальных методов, позволяющих оценивать стойкость потоковых шифров к тем или иным видам криптографических атак, сравнивать стойкость различных шифров и в итоге выбирать наилучший шифр в применении к конкретной ситуации. Настоящий проект направлен на разработку нового подхода к оценке стойкости заданного алгоритма потокового шифрования. Проект развивает (при активной совместной коллаборации) результаты исследований научной группы, возглавляемой Семеновым А.А. в ИДСТУ СО РАН. В последних работах указанного коллектива задачи построения одного класса атак были сведены к проблеме минимизации специальных оценочных функций Black-Box типа. Более точно, функции, введенные в [Semenov et al. 2016, 2018], позволяют осуществлять сравнительный анализ стойкости различных шифров к алгебраическим атакам, относящимся к классу guess-and-determine и использующим представление задачи в виде булевой формулы SAT. В большинстве случаев, поиск декомпозиционного множества (guessed bits set) осуществляется вручную посредством анализа особенностей рассматриваемого шифра и соответствующей шифру SAT-формулы. Ранее в упомянутых работах был предложен подход, в рамках которого задача поиска декомпозиции ставится как задача оптимизации специальной псевдобулевой функции Black-Box типа, значения которой стохастически оценивают трудоемкость соответствующей guess-and-determine attack. Для оптимизации авторы использовали алгоритмы поиска с запретами (Tabu Search) и имитации отжига (Simulated Annealing). В настоящем проекте впервые для поиска декомпозиционного множества разрабатываются и применяются эволюционные алгоритмы. В рамках первого этапа выполнения проекта были получены следующие результаты: 1. Разработаны новые эволюционные алгоритмы (ЭА) оптимизации оценочных функций black-box типа, оценивающих эффективность SAT-декомпозиций в задачах SAT-based криптоанализа. В качестве стратегий направленного поиска после ряда предварительных исследований выбраны (1+1)-ЭА и генетический алгоритм (ГА) с размером популяции 10. Отдельного внимания заслуживает предложенная модификация функции приспособленности (ФП), так называемая адаптивная стратегия. При начальных этапах запуска алгоритма используется меньший размер выборки Монте-Карло (например, M=10), используемый для вычисления ФП. Это ведет к потере точности функции, но при этом существенно ускоряется работа алгоритма на начальных этапах. При приближении к локальному оптимуму для повышения точности вычисления ФП используется стандартный для задачи размер выборки (например, M=1000). 2. Разработанные алгоритмы реализованы в виде программных приложений, эффективно работающих в параллельных и распределенных вычислительных средах. Исходные коды и средства запуска расположены в открытом репозитории (https://github.com/lytr777/CryptoEv). Любой желающий имеет возможность ознакомиться с деталями реализации и инструкциями запусков. Вычисления в распределенных системах реализованы с использованием программного интерфейса MPI. Реализация была успешно апробирована на вычислительных кластерах Университета ИТМО и Иркутском вычислительном кластере «Академик В.М. Матросов». 3. Был проведен ряд экспериментальных исследований по использованию разработанных и реализованных алгоритмов для построения guess-and-determine атак на ряд поточных шифров. С детальными результатами экспериментальных исследований можно ознакомиться в опубликованной работе “Evolutionary Computation Techniques for Constructing SAT-Based Attacks in Algebraic Cryptanalysis”. Для экспериментов было выбрано шесть алгоритмов потокового шифрования. Для четырех из них были построены новые декомпозиционные множества с лучшими оценками времени SAT-атаки, чем у построенных предложенными ранее алгоритмами. Таким образом, была показана применимость на практике разработанных и реализованных алгоритмов. По результатам работ была опубликована статья (https://link.springer.com/chapter/10.1007/978-3-030-16692-2_16) в трудах конференции EvoStar 2019, являющейся одной из самых признанных в области эволюционных вычислений. Были сделаны устный и постерные доклады в Лейпциге, Германия (постер и презентацию можно найти на личной странице руководителя проекта http://rain.ifmo.ru/~ulyantsev/papers.html).

Аннотация результатов, полученных в 2019 году
Второй и заключительный этап проекта продолжает исследования, направленные на разработку новых методов для анализа устойчивости алгоритмов потокового шифрования, основанных на применении эволюционных алгоритмов и SAT-решателей. 1. Были разработаны усовершенствования предложенных в первом этапе эволюционных алгоритмов оптимизации оценочных Монте-Карловских функций black-box типа, оценивающих эффективность SAT-декомпозиций в задачах SAT-based криптоанализа. Основное усовершенствование заключается в модернизации функции приспособленности (ФП) за счет использования статистических тестов. Во время работы алгоритма оптимизации проверяется множество SAT-декомпозиций, эффективность которых хуже текущего решения. Для таких декомпозиций можно прервать вычисления на более ранних стадиях вычисления ФП, которая в настоящем проекте вычисляется итеративно и требует большого числа вычислительных ресурсов. Для решения о прерывании текущая выборка результатов запусков SAT-решателей оценивается на каждой итерации при помощи критерия Уилкоксона. 2. Был реализован программный фреймворк EvoGuess (https://github.com/ctlab/EvoGuess) для оценки стойкости алгоритмов потокового шифрования к SAT-based атакам. Данный фреймворк состоит из четырех модулей и включает в себя разработанные ранее методы и их улучшения. Включена возможность использования как параметризуемых, так и непараметризуемых SAT-решателей ROKK, Lingeling, Treengeling, MiniSat, CryptoMiniSAT, PaInleSS, Glucose, Maple, Minicard. Реализованный фреймворк находится в открытом доступе, его можно использовать как для криптоанализа алгоритмов шифрования, так и для реализации аналогичных исследовательских проектов, подразумевающих параллельное решение множества SAT-формул в процессе работы алгоритма оптимизации. 3. С реализованным фреймворком EvoGuess были проведены экспериментальные исследования. Подтверждена целесообразность использования статистических тестов и параметризованных SAT-решателей в задачах SAT-based криптоанализа. В данной серии экспериментов исследовались алгоритмы потокового шифрования A5/1, Bivium, Trivium-64, Trivium-96 на пяти идентичных узлах Иркутского вычислительного кластера «Академик В.М. Матросов». Полученные результаты показали, что разработанные улучшения позволили с использованием тех же ресурсов рассмотреть в разы большее число потенциальных декомпозиционных множеств: в 4.31 раза для A5/1; в 1.48 раза для Bivium; в 2.56 раза для Trivium-64 и в 1.92 раза для Trivium-96. Были построены новые декомпозиционные множества с улучшенными оценками. По результатам второго этапа работ была опубликована статья (doi.org/10.1145/3321707.3321847) в трудах конференции GECCO 2019 (ранг A), являющейся самой известной в области эволюционных вычислений. Статья с описанием фреймворка (doi.org/10.23919/MIPRO.2019.8757214) была опубликована в трудах конференции MIPRO. Были сделаны устные доклады в Праге, Чехия; Опатии, Хорватия; а также на Конгрессе Молодых Ученых в Санкт-Петербурге (презентации доступны на личной странице руководителя проекта http://rain.ifmo.ru/~ulyantsev/papers.html).