Построение нелинейных биективных преобразований для алгоритмов защиты конфиденциальности данных в недоверенных средах тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Фомин Денис Бониславович

• Фомин Денис Бониславович
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Фомин Денис Бониславович

Введение

Краткое содержание работы. Основные результаты

Заключение

Список литературы

Приложение А. Статья «A timing attack on CUDA implementations of

an AES-type block cipher»

Приложение Б. Статья «New classes of 8-bit permutations based on a

butterfly structure»

Приложение В. Статья «Построение подстановок пространства V2m с

использованием (2m, т)-функций»

Приложение Г. Статья «Об алгебраической степени и

дифференциальной равномерности подстановок пространства V2m, построенных с использованием

(2т,т)-функций»

Приложение Д. Статья «Об инвариантных подпространствах в

XSL-шифрах»

Приложение Е. Статья «Об одном представлении нелинейного

преобразования алгоритма «Кузнечик» с помощью логических функций»

Приложение Ж. Статья «On differential uniformity of permutations

derived using a generalized construction»

Приложение З. Статья «On the impossibility of an invariant attack on

Kuznyechik»

Приложение И. Статья «Об эвристическом алгоритме построения подстановок с заданными криптографическими характеристиками с использованием обобщённой конструкции»

Введение диссертации (часть автореферата) на тему «Построение нелинейных биективных преобразований для алгоритмов защиты конфиденциальности данных в недоверенных средах»

Введение

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

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

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

Для эффективной реализации алгоритмов защиты конфиденциальности данных необходима возможность представления его нелинейных преобразований в виде «небольшого» количества логических операций. В то же время стойкость

алгоритма напрямую зависит от показателей нелинейности подстановок, используемых при его синтезе. В диссертационном исследовании рассматриваются вопросы построения эффективно реализуемых нелинейных биективных преобразований, имеющих «высокие» показатели нелинейности, что позволяет их использовать при синтезе перспективных алгоритмов защиты конфиденциальности данных. Также в диссертации предлагается новый метод анализа алгоритмов защиты конфиденциальности данных, основанный на особенностях используемых нелинейных преобразований. Для гарантирования невозможности применения разработанного метода предложен и обоснован подход, позволяющая оценить стойкость используемого алгоритма защиты конфиденциальности данных.

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

Дополнительной сложностью обеспечения свойств безопасности данных при реализации алгоритмов их защиты является возможность получения нарушителем дополнительной информации из побочных каналов утечки. В 1995 году впервые опубликована статья, в которой была показана принципиальная возможность использования времени выполнения операций для восстановления неизвестной нарушителю информации при реализации различных алгоритмов обеспечения безопасности данных, [67]. В настоящее время, при реализации методов защиты информации необходимо учитывать такие возможности нарушителя, что находит свое отражение в нормативных документах [6; 7].

От правильного выбора модели нарушителя зависит как безопасность информационной системы в целом, так и сложность обеспечения ее корректного функционирования. Недостаточные требования могут привести к нарушению свойств безопасности информационной системы, завышенные же — к невозможности или высокой сложности ее использования.

Возможность реализации методов анализа, использующих информацию о времени выполнения операций на центральном процессоре ЭВМ хорошо известна, [67]. Более того, использование современных стандартизированных алгоритмов защиты конфиденциальности данных оказывается не безопасным

относительно таких методов анализа (см. напр. [13; 19]). Архитектура же графических сопроцессоров сильно отличается от архитектуры центрального процессора современной ЭВМ: они являются массивно-параллельными вычислительными устройствами, одновременно реализующими большое количество простых операций.

Таким образом, задача исследования возможности применения методов анализа с использованием информации из побочных каналов утечки в целом и, в частности, по времени выполнения операций при реализации алгоритмов защиты информации на графических вычислителях является актуальной. Более того, в работе [68] хоть и говорится о потенциальной возможности реализации таких методов анализа, однако предполагается что их применение будет не эффективным или может быть невозможным при минимальном изменении способа реализации алгоритма защиты конфиденциальности данных.

Один из способов защиты от методов анализа, использующих информацию о времени выполнения операций в вычислительном устройстве, является реализация преобразований без хранения специальных таблиц замен, позволяющих эффективно реализовать алгоритмы защиты данных [10; 43; 70; 104]. Для этого необходимо представить все преобразования с использованием логических операций, что без дополнительных оптимизаций приводит к высокому времени работы алгоритмов защиты данных.

В работе [14] был предложен новый подход к таким оптимизациям, заключающийся в том, что вместо выполнения операций над одним аргументом за счёт использования регистров вычислительного устройства возможно параллельное вычисление значений функции защиты конфиденциальности данных. При этом, чем больше длина регистра вычислительного устройства, тем выше производительность такой реализации. В литературе такой способ носит название Ь^Ксе-реализации и в настоящее время активно применяется для вычисления значений алгоритмов защиты конфиденциальности данных, [11; 98], что гарантирует невозможность применения методов анализа по времени выполнения как в случае использования в качестве вычислительного устройства как центрального процессора, так и графического вычислителя, [87].

Эффективность Ь^Ксе-реализации напрямую зависит от количества логических операций, необходимых для вычисления значения нелинейного преобразования. Таким образом, для возможности использования Ь^Ксе-реализаций алгоритмов обеспечения конфиденциальности данных, необходимо, чтобы нели-

нейные преобразования были «легко реализуемыми», что говорит о том, что к ним предъявляются требования аналогичные требованиям к низкоресурсным нелинейным преобразованиям, [78]. При этом, при синтезе подстановок для низкоресурсных устройств используются либо подстановки малой размерности (пространств F4, F2) априори легче реализуемые, чем подстановки больших размерностей, либо нелинейные биективные преобразования которые представляются композицией функций с аргументами меньшей размерности, [21; 26; 88]. В настоящее время существуют три основных универсальных подхода к построению реализаций нелинейных биективных преобразований в виде логических элементов: полный поиск с использованием обхода графа в глубину и использованием метода встречи посередине ([58; 113; 132]), эвристические методы ([55; 58; 100; 137]) и использование алгебраически задаваемых подстановок (в частности, подстановок обращения ненулевых элементов поля), [88].

В то же время при синтезе алгоритмов обеспечения конфиденциальности данных необходимо использовать нелинейные преобразования, позволяющие противостоять известным методам анализа. Эффективность применения линейного [54; 66; 81], разностного [15; 54] и некоторых типов алгебраических методов анализа [30; 57; 97; 109] напрямую зависит от показателей нелинейности используемых в алгоритме подстановок [27] и называемых криптографическими характеристиками подстановок:

- нелинейность;

- показатель дифференциальной 6-равномерности;

- алгебраические степени прямого и обратного преобразований;

- значение графовой алгебраической иммунности.

Значение показателей нелинейности подстановок малой размерности хорошо изучено, однако они далеки от аналогичных значений даже для случайных подстановок больших размерностей. Таким образом, их использование при синтезе перспективных алгоритмов защиты конфиденциальности данных, требует реализации большего количества подстановок при сохранении одинакового уровня безопасности.

Ввиду вышесказанного, имеется большое количество причин построения подстановок большей размерности с использованием функций, определенных над пространствами меньшей размерности:

- имеется возможность программной реализации с таблицами замен,

- возможна программная реализация преобразования с небольшим количеством логических преобразований,

- имеется возможность использования подстановок для реализации низкоресурсных алгоритмов,

- имеется возможность эффективного аппаратного маскирования [21; 71]. Известно большое количество способов построения таких нелинейных преобразований: на основе сети Фейстеля [26; 48; 75], с использованием конструкции типа Misty [26; 49; 80], SPN-сети [74; 99; 108] или других конструкций [107]. В тоже время для нелинейных биективных преобразований перечисленных выше, показатели нелинейности, как правило, не выше аналогичных, полученных случайным поиском.

Таким образом, актуальной задачей является построение нелинейных биективных преобразований, представимых с использованием функций от аргументов меньшей размерности, показатели нелинейности которых будут лучше аналогичных, полученных случайным поиском. Одним из таких способов основан на использовании конструкции типа «бабочка», которая была предложена в [95] в ходе исследования возможности декомпозиции известной 6-ти битовой дифференциально 2-равномерной подстановки [22] и способа построения декомпозиции для нелинейного преобразования Российских криптографических стандартов [17].

Конструктивные особенности подстановок, задаваемых конструкцией типа «бабочка» могут оказать влияние на безопасность алгоритма обеспечения конфиденциальности данных. Согласно п. 27 Доктрины информационной безопасности Российской Федерации [5] при синтезе алгоритмов защиты информации необходимо на этапе разработки гарантировать невозможность проведения различных методов анализа, что говорит об актуальности исследования влияния свойств предложенных нелинейных биективных преобразований на безопасность алгоритма в целом.

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

Для достижения поставленной цели необходимо было решить следующие задачи:

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

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

3. Разработка новых методов анализа, основанных на свойствах предлагаемых нелинейных биективных преобразований.

Научная новизна:

1. Предложен новый метод анализа алгоритмов обеспечения конфиденциальности данных, реализованных на графических сопроцессорах, с использованием информации о времени выполнения операций.

2. Предложены новые классы нелинейных биективных преобразований, а также разработаны алгоритмы их построения.

3. Предложен новый метод анализа XSL-сетей, основанный на поиске инвариантов их преобразования.

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

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

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

сти. Разработанный математический аппарат позволяет гарантировать свойства для достачтоно широкого семества нелинейных биективных преобразований.

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

Практическая значимость данного диссертационного исследования заключается в следующем:

1. Новый метод анализа показал низкую безопасность алгоритма AES при его реализации в недоверенной среде на графических вычислителях с использованием предвычисленных таблиц, что подтверждается независимыми исследованиями [28; 87]. Показано, что для стандартизированного в РФ алгоритма шифрования Кузнечик [4], применение указанного метода не эффективно.

2. Новые семейства нелинейных биективных преобразований, позволяют их использовать при синтезе перспективных алгоритмов защиты конфиденциальности данных.

3. Уровень безопасности стандартизованного в РФ алгоритма шифрования Кузнечик [4] не снижается относительно разработанного в диссертационном исследовании метода анализа, основанного на поиске инвариантов преобразований.

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

В рамках диссертационного исследования применяются математический аппарат и подходы различных разделов математики, таких как дискретная математика, теория конечных полей, теория графов, теория алгоритмов, а также экспериментальные исследования предлагаемых примитивов и алгоритмов.

Основные результаты, выносимые на защиту:

1. Метод анализа алгоритмов обеспечения конфиденциальности данных специального вида, реализованного на графических вычислителях, по информации о времени выполнения операций.

2. Новые параметрические семейства подстановок и оценка их криптографических характеристик: нелинейность (nonlinearity), алгебраическая степень (algebraic degree), дифференциальная 6-равномерность (differential 6-uniformity).

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

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

- В работах [28; 87] указывается, что предложенный в данном диссертационном исследовании метод анализа алгоритмов обеспечения конфиденциальности данных специального вида, реализованного на графических вычислителях, по информации о времени выполнения операций, применим при практической реализации облачных вычислений.

- Позже в работах зарубежных авторов также исследовался вопрос использования времени выполнения операций при реализации алгоритмов обеспечения конфиденциальности данных, однако с использованием иного подхода (см. напр. [46; 59; 60; 62]).

- Независимо автором [31; 32] были получены нелинейные биективные преобразования, аналогичные одному параметрическому семейству подстановок, представленному в диссертации, и имеющие такие же показатели нелинейности.

- Экспериментальные исследования предложенных автором нелинейных биективных преобразований независимо исследовались в работах [44; 125].

- В работе [122], в частности показано,что раундовые преобразования алгоритма Кузнечик не имеют нелинейных инвариантов специального вида, что не противоречит результатам, полученным автором.

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

- 2023, XII симпозиум «Современные тенденции в криптографии» CTCrypt 2023 (Волгоград), 6-9 июня 2023 г, доклад: «Сложность вычисления некоторых подстановок, имеющих TU-представление».

- 2023, XII симпозиум «Современные тенденции в криптографии» CTCrypt 2023 (Волгоград), 6-9 июня 2023 г, доклад: «О способе построения подстановок, имеющих TU-представление».

- 2021, семинар Научного руководителя Московский институт электроники и математики им. А.М. Тихонова Национального исследовательского университета «Высшая школа экономики» (Москва), 16 декабря 2021 г, доклад: «Построение нелинейных биективных преобразований для построения алгоритмов защиты конфиденциальности данных в недоверенных средах».

- 2021, семинар «Криптография и криптоанализ» Криптографического Центра на базе Института Математики им. С.Л.Соболева, Международного математического Центра в Академгородке, Факультета информационных технологий и Новосибирского государственного университета, 14 сентября 2021 г, доклад: «Использование TU-представления для синтеза нелинейных биективных преобразований».

- 2021, XXIII научно-практическая конференция «РусКрипто'2021» (Солнечногорск), 23-26 марта 2021 г, доклад: «Стойкость алгоритма Кузнечик к обобщенной инвариантной атаке».

- 2021, X симпозиум «Современные тенденции в криптографии» CTCrypt 2021 (Московская область, Руза), 1-4 июня 2021 г, доклад: «On Differential Uniformity of Permutations Derived Using a Generalized Construction».

- 2021, X симпозиум «Современные тенденции в криптографии» CTCrypt 2021 (Московская область, Руза), 1-4 июня 2021 г, доклад: «On the Impossibility of an Invariant Attack on Kuznyechik».

- 2021, 20-я Международная конференция «Сибирская научная школа-семинар "Компьютерная безопасность и криптография"» — SIBECRYPT'21 имени Г.П. Агибалова (Новосибирск), 6-11 сентября 2021 г, доклад: «О способе построения дифференциально 26-равномерных подстановок на F22m».

- 2021, 20-я Международная конференция «Сибирская научная школа-семинар "Компьютерная безопасность и криптография"» —

SIBECRYPT'21 имени Г.П. Агибалова (Новосибирск), 6-11 сентября 2021 г., доклад: «Об эвристическом подходе к построению биективных векторных булевых функций с заданными криптографическими характеристиками».

- 2020, IX симпозиум «Современные тенденции в криптографии» CTCrypt 2020 (Московская область, Руза), 15-17 сентября 2020 г, доклад: «A compact bit-sliced representation of Kuznechik S-box».

- 2019, VIII симпозиум «Современные тенденции в криптографии» CTCrypt 2019 (Светлогорск), 3-7 июня 2019 г, доклад: «On the Way of Constructing 2n-Bit Permutations from n-Bit Ones».

- 2019,18 всероссийская конференция «Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография"» SIBECRYPT'19 (Томск), 9-14 сентября, доклад: «Об аппаратной реализации одного класса байтовых подстановок».

- 2018, VII симпозиум «Современные тенденции в криптографии» CTCrypt 2018 (Суздаль), 28-30 мая 2018 г, доклад: «New classes of 8bit permutations based on a butterfly structure».

- 2018, XIX Всероссийский Симпозиум по прикладной и промышленной математике (осенняя сессия) (Сочи), 22-30 сентября 2018 г, доклад: «О подходах к построению низкоресурсных нелинейных преобразований».

- 2015, IV симпозиум «Современные тенденции в криптографии» CTCrypt 2015 (Казань), 3-5 июня 2015 г, доклад: «A timing attack on CUDA implementations of an AES-type block cipher».

Содержание работы. Результаты диссертационного исследования условно можно разделить на следующие разделы:

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

2. Выбор примитивов для построения нелинейного биективного преобразования, позволяющих гарантировать эффективность программной и аппаратной реализации.

3. Построение параметрических семейств подстановок и оценка их показателей нелинейности.

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

Изложим основные результаты диссертационного исследования. Для начала введем необходимые обозначения.

Полем из двух элементов будем называть множество F2 = {0,1} с заданными естественным образом операциями сложения «+» и умножения «•». Пусть (^П, +) = {(а0,ах,..., ап-х), а е е 0,п — 1} — арифметическое векторное пространство размерности п, 6 = (0,0,..., 0) — ноль векторного пространства. Если рассмотреть аддитивную группу векторного пространства ^П,, 0) и задать специальным образом операцию умножения, то можно построить поле, которое будем обозначать , +, ).

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

Исторически первым опубликованным методом анализа, использующим информацию из побочных каналов утечки является восстановление ключевой информации алгоритмов защиты данных с открытым ключом [67] по времени их работы на центральном процессоре. С развитием науки появились новые методы анализа с использованием информации из разнообразных источников утечки информации: сигналы в канале питания, сигналы от электромагнитного излучения, информация о температуре или звуках, издаваемых устройством [69; 116].

До 2015 года не было известно методов анализа алгоритмов защиты информации, реализованных на графических вычислителях, по информации из побочных каналов утечки. На конференции СТСгур^15 впервые был представлен такой метод анализа, где в качестве побочного канала утечки информации использовалась информация о времени выполнения алгоритма защиты конфиденциальности данных. Позже, в октябре 2015 года, на конференции ICCD'15, зарубежными авторами была представлена работа, [105], где предлагался метод анализа с использованием информации, получаемой из цепи питания графического вычислителя.

Первый раздел посвящен описанию представленного на СТСгур^5 и позже опубликованного в [133] метода анализа. В качестве предмета исследования в пер-

вом разделе была выбрана реализация алгоритма защиты конфиденциальности данных, реализованного на графическом вычислителе с использованием наиболее эффективного подхода, основанного на использовании предвычисленных таблиц, [43; 56; 65]. В качестве объекта исследования — алгоритм обеспечения конфиденциальности данных, построенный на основе XSL-сети. В рамках данного раздела будем считать, что п — размер блока в битах, т — число нелинейных биективных преобразований (подстановок) на подвекторах длины п', п = П • т.

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

- Наложение неизвестного нарушителю параметра, называемого раундо-вым ключом: Х[К]: ^ где Х[К](а) = К 0 а; а,К е ¥%.

- Нелинейное преобразование, представляющее собой параллельное применение подстановок пространства ЩП': 8: ЩП ^ 8(а) = 8(аь ... ,а8) = (п(а1),..., п(ат)), аг е ЩП, п е S (ЕП^ ,г = 1,... ,т.

- Линейное преобразование: Ь: ЕП ^ Ца) = а • V, где V е СЬП. При реализации алгоритма обеспечения конфиденциальности данных происходит итеративное применение описанных выше операций, при этом каждая итерация называется раундом.

В случае, когда т является квадратом некоторого натурального числа т = к2, можно считать, что преобразования алгоритмов из предлагаемого семейства выполняются над элементами к х к матрицы:

Список литературы диссертационного исследования кандидат наук Фомин Денис Бониславович, 2023 год

ЛИТЕРАТУРА

1. Малышев Ф. М. Двойственность разностного и линейного методов в криптографии // Матем. вопр. криптогр. 2014. Т. 5. Вып. 3. С. 35-48.

2. Matsui M. Linear cryptanalysis method for DES Cipher // LNCS. 1994. V. 765. P. 386-397.

3. Малышев Ф. М., Трифонов Д. И. Рассеивающие свойства XSLP-шифров // Матем. вопр. криптогр. 2016. Т. 7. Вып. 3. С. 47-60.

4. Daemon J. and Rijmen V. The Design of Rijndael: AES — The Advanced Encryption Standard. Berlin; Heidelberg: Springer, 2002. 238 p.

5. Сидельников В. М. О взаимной корреляции последовательностей // Проблемы кибернетики. 1971. Вып. 24. С. 15-42.

6. Nyberg K. Differentially uniform mappings for cryptography // LNCS. 1994. V. 765. P. 55-64.

7. Bilgin B., Nikova S., Nikov V., et al. Threshold Implementations of all 3 х 3 and 4 х 4 S-boxes. IACR Cryptology ePrint Archive. 2012. http://eprint.iacr.org/2012/300.

8. Bora A., Tolga M. S., and Ercan B. Classifying 8-bit to 8-bit S-boxes based on power mappings from the point of DDT and LAT distributions // LNCS. 2008. V. 5130. P. 123-133.

9. Biryukov A., De Canniere C., Braeken A., and Preneel B. A toolbox for cryptanalysis: Linear and affine equivalence algorithms // LNCS. 2003. V. 2656. P. 33-50.

10. Leander G. and Poschmann A. On the classification of 4 bit S-boxes // LNCS. 2007. V. 4547. P. 159-176.

11. Saarinen M.J. О. Cryptographic analysis of all 4 х 4-bit S-boxes // LNCS. 2012. V. 7118. P. 118-133.

12. Menyachikhin A. V. Spectral-linear and spectral-differential methods for generating S-boxes having almost optimal cryptographic parameters // Матем. вопр. криптогр. 2017. Т. 8. Вып. 2. С. 97-116.

13. Fomin D. B. New classes of 8-bit permutations based on a butterfly structure // Матем. вопр. криптогр. 2019. Т. 10. Вып. 2. С. 169-180.

14. Фомин Д. Б. Построение подстановок пространства V2m с использованием (2m, m)-функций // Матем. вопр. криптогр. 2020. Т. 11. Вып. 3. С. 121-138.

15. Фомин Д. Б. Об алгебраической степени и дифференциальной равномерности подстановок пространства V2m, построенных с использованием (2m, т)-функций // Матем. вопр. криптогр. 2020. Т. 11. Вып. 4. С. 133-149.

16. Feistel H. Cryptography and computer privacy // Scientific American. 1973. V. 225(5). P. 15-23.

17. Feistel Н., Notz W. А., and Smith J. L. Some cryptographic techniques for machine to machine data communications // Proc. IEEE. 1975. V. 63(11). P. 1545-1554.

18. Webster A. F. and Tavares S. E. On the design of S-boxes // LNCS. 1986. V. 218. P. 523-534.

19. Augot D. and Finiasz M. Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes. IACR Cryptology ePrint Archive. 2014. http://eprint.iacr.org/ 2014/566.

20. Augot D. and Finiasz M. Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions // IEEE Intern. Symp. Inform. Theory. 2013. P. 1551-1555.

21. Barreto P. and Rijmen V. The KHAZAD Legacy-Level Block Cipher. Submission to NESSIE. 2000. https://www.researchgate.net/publication/228924670_The_Khazad_ legacy-level_block_cipher.

22. Gupta K. C. and Rayl.G. On constructions of involutory MDS matrices // LNCS. 2013. V.7918. P. 43-60.

23. Junod P. and Vaudenay S. Perfect diffusion primitives for block ciphers building efficient MDS matrices // LNCS. 2004. V. 3357. P. 84-99.

24. Nakahara J. Jr. and Abrahao E. A new involutory MDS matrix for the AES // Intern. J. Network Security. 2009. V.9(2). P. 109-116.

25. Poschmann A. Lightweight Cryptography — Cryptographic Engineering for a Pervasive World. IACR Cryptology ePrint Archive. 2009. http://eprint.iacr.org/2009/516.

26. Анашкин А. В. Полное описание одного класса MDS-матриц над конечным полем характеристики 2 // Матем. вопр. криптогр. 2017. Т. 8. Вып. 4. С. 5-28.

27. ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры. М.: Стандартинформ, 2015.

28. D.STVL.9 — Ongoing Research Areas in Symmetric Cryptography. ECRYPT, 2008. 108 p.

29. Погорелое Б. А., Пудовкина М. А. Комбинаторная характеризация XL-слоёв // Матем. вопр. криптогр. 2013. Т. 4. Вып. 3. С. 99-129.

30. Погорелое Б. А., Пудовкина М. А. О расстояниях от подстановок до импримитивных групп при фиксированной системе импримитивности // Дискретная математика. 2013. Т. 25. № 3. С. 78-95.

31. Погорелое Б. А., Пудовкина М. А. О расстоянии от подстановок до объединения всех им-примитивных групп с равными параметрами систем импримитивности // Дискретная математика. 2014. Т. 26. № 1. С. 103-117.

32. Пудовкина М. А. О вероятностях r-раундовых пар разностей XSL-алгоритма блочного шифрования Маркова с приводимым линейным преобразованием // Прикладная дискретная математика. Приложение. 2014. № 7. С. 52-54.

33. Standaert F. X., Piret G., Rouvroy G., et al. ICEBERG : An involutional cipher efficient for block encryption in reconfigurable hardware // LNCS. 2004. V.3017. С. 279-299.

34. Burov D. A. and Pogorelov B. A. An attack on 6 rounds of KHAZAD // Матем. вопр. криптогр. 2016. Т. 7. Вып. 2. С. 35-46.

35. Burov D. A. and Pogorelov B. A. The permutation group insight on the diffusion property of linear mappings // Матем. вопр. криптогр. 2018. Т. 9. Вып. 2. С. 47-58.

36. Буров Д. А. Подгруппы прямого произведения групп, инвариантные относительно действия подстановок на сомножителях // Дискретная математика. 2019. Т. 31. № 4. C. 3-19.

37. Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х т. Пер. с англ. М.: Мир, 1988.

38. Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра: учебник. В 2-х т. Т. 2. М.: Гелиос АРВ, 2003.

39. SimS.M., KhooK., Oggier F.E., and Peyrin T. Lightweight MDS involution matrices // FSE. 2015. P. 471-493.

40. Coy Puente O. and de la Cruz Jiménez R. A. Construction of orthomorphic MDS matrices with primitive characteristic polynomial // CTCrypt'20. 2020. https://ctcrypt.ru/files/ files/Oliver\CTCrypt2020.pdf.

41. Khan A. A. and Murtaza G. Efficient Implementation of Grand Cru with TI C6x+ Processor. IACR Cryptology ePrint Archive. 2011. http://eprint.iacr.org/2011/385.

42. Watanabe D., Furuya S., Yoshida H., et al. A new keystream generator MUGI // LNCS. 2002. V. 2365. P. 179-194.

43. Halevi S., Coppersmith D., and Jutla C. S. Scream: A Software-Efficient Stream Cipher. IACR Cryptology ePrint Archive. 2002. http://eprint.iacr.org/2002/019.

44. http://www.cryptonessie.org — The New European Schemes for Signatures, Integrity and Encryption (NESSIE). 2003.

45. DaemanJ., KnudsenL.R., and Rijmen V. The block cipher SQUARE // FSE'97. 1997. V.1267. P. 149-156.

46. Агиевич С. В., Галинский В. А., Микулич Н. Д., Харин Ю. С. Алгоритм блочного шифрования BelT. elib.bsu.by.

47. ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хэширования. М.: Стандартинформ, 2012.

48. BiryukovA., Perrin L., and Udovenko A. Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1 // LNCS. 2016. V.9665. P. 372-402.

49. Perrin L. Partitions in the S-Box of Streebog and Kuznyechik. Cryptology ePrint Archive. 2019. https://eprint.iacr.org/2019/092.

50. Горчинский Ю. Н. О гомоморфизмах многоосновных универсальных алгебр в связи с криптографическими применениями // Труды по дискретной математике. 1997. Т. 1. С.67-84.

51. Todo Y., Leander G., and Sasaki Y. Nonlinear Invariant Attack — Practical Attack on Full SCREAM, iSCREAM, and Midori64. Cryptology ePrint Archive. 2016. https://eprint. iacr.org/2016/732.

52. Буров Д. А. О существовании нелинейных инвариантов специального вида для раун-довых преобразований XSL-алгоритмов // Дискретная математика. 2021. Т. 33. № 2. С.31-45.

REFERENCES

1. Malyshev F. M. Dvoystvennost' raznostnogo i lineynogo metodov v kriptografii [The duality of differential and linear methods in cryptography]. Matem. Vopr. Kriptogr., 2014, vol.5, no.3, pp. 35-48. (in Russian)

2. Matsui M. Linear cryptanalysis method for DES cipher. LNCS, 1994, vol. 765, pp. 386-397.

3. Malyshev F. M. Trifonov D. I. Rasseivayushchiye svoystva XSLP-shifrov [Diffusion properties of XSLP-ciphers]. Matem. Vopr. Kriptogr., 2016, vol.7, no.3, pp. 47-60. (in Russian)

4. Daemon J. and Rijmen V. The Design of Rijndael: AES — The Advanced Encryption Standard. Berlin; Heidelberg, Springer, 2002. 238 p.

5. Sidel'nikov V. M. O vzaimnoy korrelyatsii posledovatel'nostey [Cross-correlation of sequences]. Problemy Kibernetiki, 1971, no. 24, pp. 15-42. (in Russian)

6. Nyberg K. Differentially uniform mappings for cryptography. LNCS, 1994, vol. 765, pp. 55-64.

7. Bilgin B., Nikova S., Nikov V., et al. Threshold Implementations of all 3 х 3 and 4 х 4 S-boxes. IACR Cryptology ePrint Archive. 2012. http://eprint.iacr.org/2012/300.

8. Bora A., Tolga M. S., and Ercan B. Classifying 8-bit to 8-bit S-boxes based on power mappings from the point of DDT and LAT distributions. LNCS, 2008, vol. 5130, pp. 123-133.

9. Biryukov A., De Canniere C., Braeken A., and Preneel B. A toolbox for cryptanalysis: Linear and affine equivalence algorithms. LNCS, 2003, vol.2656, pp. 33-50.

10. Leander G. and Poschmann A. On the classification of 4 bit S-boxes. LNCS, 2007, vol.4547, pp.159-176.

11. Saarinen M.J. О. Cryptographic analysis of all 4 х 4-bit S-boxes. LNCS, 2012, vol.7118, pp.118-133.

12. Menyachikhin A. V. Spectral-linear and spectral-differential methods for generating S-boxes having almost optimal cryptographic parameters. Matem. Vopr. Kriptogr., 2017, vol. 8, no. 2, pp. 97-116.

13. Fomin D. B. New classes of 8-bit permutations based on a butterfly structure. Matem. Vopr. Kriptogr., 2019, vol. 10, no. 2, pp. 169-180.

14. Fomin D.B. Postroenie podstanovok prostranstva V2m s ispol'zovaniem (2m, m)-funktsiy [Construction of permutations on the space V2m by means of (2m, m)-functions]. Matem. Vopr. Kriptogr., 2020, vol. 11, no.3, pp. 121-138. (in Russian)

15. Fomin D. B. Ob algebraicheskoy stepeni i differentsial'noy ravnomernosti podstanovok prostranstva V2m, postroennykh s ispol'zovaniem (2m, m)-funktsiy [On the algebraic degree and differential uniformity of permutations on the space V2m constructed via (2m, m)-functions]. Matem. Vopr. Kriptogr., 2020, vol. 11, no. 4, pp. 133-149. (in Russian)

16. Feistel H. Cryptography and computer privacy. Scientific American, 1973, vol. 225(5), pp. 15-23.

17. Feistel Н., Notz W. А., and Smith J. L. Some cryptographic techniques for machine to machine data communications. Proc. IEEE, 1975, vol. 63(11), pp. 1545-1554.

18. Webster A. F. and Tavares S. E. On the design of S-boxes. LNCS, 1986, vol. 218, pp. 523-534.

19. Augot D. and Finiasz M. Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes. IACR Cryptology ePrint Archive. 2014. http://eprint.iacr.org/ 2014/566.

20. Augot D. and Finiasz M. Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions. IEEE Intern. Symp. Inform. Theory, 2013, pp.1551-1555.

21. Barreto P. and Rijmen V. The KHAZAD Legacy-Level Block Cipher. Submission to NESSIE. 2000. https://www.researchgate.net/publication/228924670_The_Khazad_ legacy-level_block_cipher.

22. Gupta K. C. and Ray I. G. On constructions of involutory MDS matrices. LNCS, 2013, vol. 7918, pp. 43-60.

23. Junod P. and Vaudenay S. Perfect diffusion primitives for block ciphers building efficient MDS matrices. LNCS, 2004, vol.3357, pp. 84-99.

24. Nakahara J. Jr. and Abrahao E. A new involutory MDS matrix for the AES. Intern. J. Network Security, 2009, vol. 9(2), pp. 109-116.

25. Poschmann A. Lightweight Cryptography — Cryptographic Engineering for a Pervasive World. IACR Cryptology ePrint Archive, 2009. http://eprint.iacr.org/2009/516.

26. Anashkin A. V. Polnoe opisanie odnogo klassa MDS-matrits nad konechnym polem kharakteristiki 2 [Complete description of a class of MDS-matrices over finite field of characteristic 2]. Matem. Vopr. Kriptogr., 2017, vol.8, no. 4, pp. 5-28. (in Russian)

27. GOST R 34.12-2015. Informatsionnaya tekhnologiya. Kriptograficheskaya zashchita informatsii. Blochnye shifry. [GOST P 34.12-2015. Information Technology. Cryptographic Data Security. Block Ciphers]. Moscow, Standartinform, 2015. (in Russian)

28. D.STVL.9 — Ongoing Research Areas in Symmetric Cryptography. ECRYPT, 2008. 108 p.

29. Pogorelov B. A. and Pudovkina M. A. Kombinatornaya kharakterizatsiya XL-sloyov [Combinatorial characterization of XL-layers]. Matem. Vopr. Kriptogr., 2013, vol.4, no. 3, pp. 99-129. (in Russian)

30. Pogorelov B. A. and Pudovkina M. A. On the distance from permutations to imprimitive groups for a fixed system of imprimitivity. Discr. Math. Appl., 2013, vol. 24(2), pp. 95-108.

31. Pogorelov B. A. and Pudovkina M. A. On the distance from permutations to the union of all imprimitive groups with identical parameters of imprimitivity systems. Discr. Math. Appl., 2014, vol. 24(3), pp. 163-173.

32. Pudovkina M. A. O veroyatnostyakh r-raundovykh par raznostey XSL-algoritma blochnogo shifrovaniya Markova s privodimym lineynym preobrazovaniyem [On probabilities of r-round differences of a Markov XSL block cipher with a reducible linear transformation]. Prikladnaya Diskretnaya Matematika. Prilozheniye, 2014, no. 7, pp. 52-54. (in Russian)

33. Standaert F. X., Piret G, Rouvroy G, et al. ICEBERG : An involutional cipher efficient for block encryption in reconfigurable hardware. LNCS, 2004, vol. 3017, pp. 279-299.

34. Burov D. A. and Pogorelov B. A. An attack on 6 rounds of KHAZAD. Matem. Vopr. Kriptogr., 2016, vol. 7, no. 2, pp. 35-46.

35. Burov D. A. and Pogorelov B. A. The permutation group insight on the diffusion property of linear mappings. Matem. Vopr. Kriptogr., 2018, vol.9, no. 2, pp.47-58.

36. Burov D. A. Podgruppy pryamogo proizvedeniya grupp, invariantnyye otnositel'no deystviya podstanovok na somnozhitelyakh [Subgroups of Cartesian Product of Groups that are Invariant on Nonlinear Layer]. Diskretnaya Matematika, 2019, vol.31, no. 4, pp. 3-19. (in Russian)

37. Lidl R. and Niederreiter H. Finite Fields. Cambridge, Cambridge University Press, 1984.

38. Gluhov M. M., Elizarov V. P., and Nechaev A. A. Algebra: Study Book. Moscow, Gelous ARV, 2003. (in Russian)

39. Sim S. M., Khoo K., Oggier F. E., and Peyrin T. Lightweight MDS involution matrices. FSE, 2015, pp.471-493.

40. Coy Puente O. and de la Cruz Jiménez R. A. Construction of orthomorphic MDS matrices with primitive characteristic polynomial. CTCrypt'20, 2020. https://ctcrypt.ru/files/ files/Oliver\CTCrypt2020.pdf.

41. Khan A. A. and Murtaza G. Efficient Implementation of Grand Cru with TI C6x+ Processor. IACR Cryptology ePrint Archive. 2011. http://eprint.iacr.org/2011/385.

42. Watanabe D., Furuya S., Yoshida H., et al. A new keystream generator MUGI. LNCS, 2002, vol. 2365, pp. 179-194.

43. Halevi S., Coppersmith D., and Jutla C. S. Scream: A Software-Efficient Stream Cipher. IACR Cryptology ePrint Archive. 2002. http://eprint.iacr.org/2002/019.

44. http://www.cryptonessie.org — The New European Schemes for Signatures, Integrity and Encryption (NESSIE), 2003.

45. DaemanJ., Knudsen L. R., and Rjmen V. The block cipher SQUARE. FSE'97, 1997, vol. 1267, pp. 149-156.

46. Agievich S. V., Galinskiy V. A., Mikulich N. D., and Kharin Yu. S. Algoritm blochnogo shifrovaniya BelT. [BelT Block Cipher]. elib.bsu.by. (in Russian)

47. GOST R 34.11-2012. Informatsionnaya tekhnologiya. Kriptograficheskaya zashchita informatsii. Funktsiya kheshirovaniya. [GOST P 34.11-2012. Information Technology. Cryptographic Data Security. Hash Function]. Moscow, Standartinform, 2012. (in Russian)

48. BiryukovA., Perrin L., and Udovenko A. Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. LNCS, 2016, vol.9665, pp. 372-402.

49. Perrin L. Partitions in the S-box of Streebog and Kuznyechik. Cryptology ePrint Archive, 2019. https://eprint.iacr.org/2019/092.

50. Gorchinskiy Yu. N. O gomomorfizmakh mnogoosnovnykh universal'nykh algebr v svyazi s kriptograficheskimi primeneniyami [On homomorphisms of multibase universal algebras in connection with cryptographic applications]. Trudy po Diskretnoy Matematike, 1997, vol. 1, pp. 67-84. (in Russian)

51. Todo Y., Leander G, and Sasaki Y. Nonlinear Invariant Attack — Practical Attack on Full SCREAM, iSCREAM, and Midori64. Cryptology ePrint Archive. 2016. https://eprint. iacr.org/2016/732.

52. Burov D. A. O sushchestvovanii nelineynykh invariantov spetsial'nogo vida dlya raundovykh preobrazovaniy XSL-algoritmov [About existence of the special nonlinear invariants for round functions of XSL-ciphers]. Diskretnaya Matematika, 2021, vol.33, no. 2, pp. 31-45. (in Russian)

Приложение Е

Статья «Об одном представлении нелинейного преобразования алгоритма «Кузнечик» с помощью логических функций»

Об одном представлении нелинейного преобразования алгоритма «Кузнечик» с помощью логических функций / О. Д. Авраамова, Д. Б. Фомин, В. А. Серов [и др.] // Математические вопросы криптографии. 2021. Т. 12, № 2. С. 21—38 DOI

https://doi.org/10.4213/mvk354

Разрешение на копирование: статья доступна в открытом доступе на сайте журнала по ссылке http://mi.mathnet.ru/mvk3 64

МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КРИПТОГРАФИИ 2021 Т. 12 № 2 С. 21-38

УДК 519.719.2 DOI https://doi.org/10.4213/mvk354

A compact bit-sliced representation of Kuznyechik S-box

О. D. Avraamova1, D. B. Fomin2, V. A. Serov1, A. V. Smirnov1,

V. N. Shokov1

1 Lomonosov Moscow State University, Russia

2 Higher School of Economics, Moscow, Russia

Получено 25.XI.2020

Abstract. In this paper we consider a bit-sliced implementation of the non-linear transformation shared by GOST R 34.12-2015 "Kuznyechik" block cipher and GOST R 34.11-2012 "Streebog" hash function. We combine analytical and computer methods to get a 226 Boolean operations representation.

Keywords: block cipher, hash function, S-box, Kuznyechik, Streebog, bit-slice, Boolean functions minimization

Об одном представлении нелинейного преобразования алгоритма «Кузнечик» с помощью логических функций

О. Д. Авраамова1, Д. Б. Фомин2, В. А. Серов1, А. В. Смирнов1, В. Н. Шоков1

1 Московский государственный университет имени В. А. Ломоносова, Москва

2 НИУ Высшая школа экономики, Москва

Аннотация. Рассматриваются способы реализации нелинейного преобразования блочного алгоритма шифрования с длиной блока 128 бит «Кузнечик» (ГОСТ Р 34.12-2015) и хеш-функции «Стрибог» (ГОСТ Р 34.11-2012). Показана возможность реализации подстановки за 226 логических операций.

Ключевые слова: блочный шифр, хеш-функция, подстановка, Кузнечик, Стрибог, битовая реализация, минимизация представления булевой функции

Citation: Matematicheskie Voprosy Kriptografii, 2021, v. 12, № 2, pp. 21-38 (Russian) © Академия криптографии Российской Федерации, 2021 г.

1. Introduction

A permutation is a bijective mapping of a non-empty finite set onto itself. In applications, permutations of Vn, where Vn is an n-dimensional vector space over Galois field GF(2), are often used. Usually the dimension of the vector space is not large, most popular versions being n = 4 or n = 8. Permutation may be implemented as a lookup table and this representation is often called an S-box.

S-boxes are widely used in the synthesis of block ciphers and hash-functions. They allow one to combine necessary non-linearity with reasonable implementation complexity of the overall scheme. At the same time, cipher strength against known methods of cryptanalysis depends strongly on certain properties of S-boxes used, and its potential speed and lower resource-consumption — on the effectiveness of software and hardware implementation of these elements.

We use the number of Boolean operations as the measure of complexity of an S-box implementation. In this paper we consider implementations of the non-linear transformation of «Kuznyechik» GOST R 34-12.2015 [1] in the basis of AND, OR, NOT and XOR Boolean functions and try to get a way to make it as compact as possible. The choice of these four functions as the basis is justified by the existence of its effective hardware and software implementation on different platforms. Inside formulas, we'll use short notation: • for AND, + for OR, - for NOT and 0 for XOR.

In the classical problem of Boolean functions minimization the basis is formed by conjunction (AND), disjunction (OR) and negation (NOT). In this form the problem is intimately connected with the simplification of electrical schemas. Karnaugh charts used to complete the problem for electrical schemas are quite usable for manual optimization of Boolean functions with small number of variables. Computer analog of this method was developed by W. Quine and extended by E. McCluskey and is known as Quine-McCluskey algorithm. The distinctive feature of our situation is the existence of additional XOR operation, so finding transformation rules for formulae minimization for the new set of operations is a reasonable problem.

Composition of the paper is the following. In section 1 we consider the decomposition of «Kuznyechik» permutation found by A. Biryukov, L. Perrin, and A. Udovenko in [2], which we call the BPU-decomposition. In section 2 we implement linear and bilinear elements of BPU-decomposition and eliminate branching. In section 3 we consider ways of computer optimization of non-linear elements of the decomposition. In concluding section we compare the overall complexity of our method with other existing solutions.

2. BPU-decomposition

In «Kuznyechik» algorithm, by GOST R 34-12.2015, a non-linear transformation n of vector space V8 is used. If we try to minimize it directly, using, for example, Espresso algorithm (in Logic Friday [3] realization), we get 3492 Boolean operations — quite a lot. So some other approach is needed.

Fig. 1: The structure of BPU-decomposition taken from [2]

The authors of [2] suggested to represent n as a composition of nonlinear transformations , u1, I, a, ' of V4, linear transformations a and ! of Vg and multiplication © in Galois field GF(24, ©, ©) = GF(2)[x]/(f (x)) with irreducible polynomial f (x) — x4 © x3 © 1, where © is the addition and © is the multiplication in the finite field.

Consider the action of n on the set of pairs (l,r),l,r 2 GF(24). In [2] the following algorithm to compute n(l || r) was used (see fig. 1):

1) (l || r) :— a(l || r),

2) if r — 0, then l :— u0(l), else l :— v1(l © I(r)),

3) r :— a(r © '(l)),

4) (l || r) :— !(l || r).

The value of (l || r) after step 4 equals to n(l || r). The non-linear transformations (not all of them are bijective) ^i, I, a, ' are given in

the following table (in hexadecimal representation):

I 0,1, c, 8, 6, f, 4, e, 3, d, b, a, 2, 9, 7, 5

Уо 2, 5, 3, b, 6, 9, e, a, 0,4, f, l, 8, d, c, 7

Vi 7, 6, c, 9, 0, f, 8,1,4, 5, b, e, d, 2, 3, a

b, 2, b, 8, c, 4,1, c, 6, 3, 5, 8, e, 3, 6, b

о c, d, 0,4, 8, b, a, e, 3, 9, 5, 2, f, 1, 6, 7

3. Implementation of linear and bilinear elements of decomposition and branching elimination

3.1. Bit-sliced implementation of multiplication in the finite field

One of important elements of the decomposition is the multiplication in the finite field GF(24). It is used twice during the algorithm. Let's find the representation of this operation by Boolean functions. To do it, we consider GF(24) as a four-dimensional algebra over GF(2). In this case the components of binary representation of elements of GF(24) will be simply the coordinates of these vectors in the standard basis (ei = (1000) = 8, e2 = (0100) = 4, ea = (0010) = 2, e4 = (0001) = 1}. (In this section elements of GF(24) will be typesetted in bold and coordinate indexes will be written above).

By the associative, commutative and distributive laws of GF(24), operations } and 0 are commuting, and the distributive law holds. So it is sufficient to know pair-wise products of basic vectors, and the product of any two arbitrary vectors may be computed by linearity:

z = (x © y) = f X xO © f XX yj j = X

4=1 / Vj=1 ' i,j

= V x • yj (ег © e,)

in vector form and

zk = (x © y)k =

x^ © Qx yj e^j = x* yj (ег © е,- ^

= X xX • yj (e* © e, )k, к = 1,...,4,

i,3

in coordinate form.

Let's make a table of pair-wise products of basic vectors:

1000 0100 0010 0001

1000 1111 1011 1001 1000

0100 1011 1001 1000 0100

0010 1001 1000 0100 0010

0001 1000 0100 0010 0001

Separating coordinates, we have

C1 C2 C3 C 4

1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0

1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0

1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0

1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

and for every coordinate zk (k = 1,..., 4) we have

'C

11

yk - ( rp 1 Df*2 rp3 ^y»4)

/C/ - I tXj ^ tXj ^ tXj ^ tXj I

41

-14

-44/

y2

3

y3

4 y4

k

k

Now (returning to lower coordinate indexes) we are able to write down formulae for every coordinate:

Z1 — (X1 © £2 © £3 © £4) • y1 © (X1 © £2 © £3) • y2 © (£ © £2) • y3 © £ • y4,

Z2 — £1 • y1 © £4 • y2 © £3 • y3 © £2 • y4,

Z3 — (£1 © £2) • y1 © £1 • y2 © £4 • y3 © £3 • y4,

Z4 — (£1 © £2 © £3) • y1 © (£1 © £2) • y2 © £1 • y3 © £4 • y4.

So we need 13 operations to compute z1, 7 for z2, 8 for z3, and 10 for z4. Multiplication in our realization of GF(24) requires 38 Boolean operations if we do not use auxiliary variables to store intermediate results. If we use intermediate variables (denote them by P with indices), the number of operations may be reduced further. For example, the expression (£1 © £2)

appears more than once:

zi = (P2 0 £4) • yi 0 P2 • y2 0 Pi • ya 0 xi • y4, z2 = xi • yi 0 £4 • y2 0 £3 • y3 0 £2 • y4, Z3 = Pi • yi 0 Xi • y2 0 £4 • y3 0 £3 • y4, Z4 = P2 • yi 0 Pi • y2 0 £i • y3 0 £4 • y4,

Pi = £i 0 £2,

P2 = £i 0 £2 0 £3 = Pi 0 £3. The latter realization has complexity 31.

3.2. Implementation of linear mappings

Let's estimate the complexity of linear transformations a and ! in terms of Boolean functions. Matrix representations of a and ! are the following:

a =

0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0

0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0

0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0

1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0

1 0 0 0 1 0 1 0 , ! = 0 0 0 0 1 0 0 0

0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0

0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1

Let l = (li, l2, l3,l4), r = (ri,r2, r3,r4) be representations of field elements as vectors. Using an intermediate variable pi we can represent a by the following equations:

а1(1Ъ ^ ¿3, ¿4 a2 (11, ^ ¿3, ¿4 a3(^b ^ ¿3, ¿4 a4(l1, ¿2, ¿3, ¿4 = a2(^1, ¿2, ¿3 a5 ( ¿1, ^ ¿3, ¿4 a6(^b ^ ¿3, ¿4 a7 ( ¿1, ^ ¿3, ¿4 a8 ( ¿1, ^ ¿3, ¿4 P1 = Г1 0 Г3.

Г1 ,Г2,Г3, Г4) = Г1, Г1 ,Г2,Г3, Г4) = /2 0 Г1 ,Г2,Г3, Г4) = ¿2 0 Г1 ,Г2,Г3, Г4) = ¿1 0

Г4, Г3 ( ¿2 0

Г4 = a2(¿1 ,¿2, ¿3, ¿4,Г1,Г2,Г3,Г) 0 Г3,

¿3 0 Г1 0 Г2 0 Г3 0 Г4 , ¿4, Г1 ,Г2,Г3, Г4) 0 a5(¿1, ¿2, ¿3, ¿4,ГЬГ2,Г3,^4) 0 ¿3 0 Г2,

Г1 ,Г2,Г3,Г4) = ¿1 0 Г1 0 Г3 = ¿1 0 Р1, Г1 ,Г2,Г3, Г4) = ¿2 0 Г2, Г1 ,Г2,Г3, Г4) = ¿4 0 Г1 0 Г3 = ¿4 0 Р1, Г1 ,Г2,Г3, Г4) = ¿3,

Overall complexity of a is 9 XOR operations. In the same way, the complexity of ! is 5 XOR operations. So we get 14 Boolean operations to represent two linear mappings.

3.3. Elimination of branching

Let's return to item 2 of BPU algorithm: «2. If r — 0 then l :— (l) else l :— v1 (l } I(r))». Write down a Boolean function which takes the value 1 at a single point r — (0, 0, 0, 0) and has zero value at all other points [4, p. 25-30]:

Io,0,0,0(r) — n • -T2 • f3 • r4 — rT+r2Tr3Tr4.

The complexity of this function is 4 Boolean operations, the complexity of its negation — 3 operations. Now we can express l by a non-branching formula:

r — Io,o,o,o(r) • ^0(l) + Io,o,o,o(r) • (l @ I(r)), i — 1,..., 4. (1)

It should be stressed that we compute I0,0,0,0(r) only once. To be more precise, we first calculate its negation (3 operations) and then, by doublenegation law, compute I0,0,0,0(r) itself, which gives one additional operation. One needs 16 Boolean operations to represent four equations above. Using the fact that 0 is a fixed point for the permutation I we can reduce the amount of Boolean operations to 13. Let's consider the following equations:

l1 — Io,o,o,o(r) • (^0(l) © (0)) © (l @ I(r)), i — 1,..., 4. (2) If r — (0, 0, 0, 0), then

Io,o,o,o(r) • K(l @ I(r)) — (l } I(r)), i — 1,..., 4,

and equations (1) and (2) are equivalent.

Otherwise, let r be equal to 0. The equation (1) is equivalent to

Io,o,o,o(r) • ^0 (l) — ^0(l).

Using the fact that I(0) — 0 and £ 0 0 — 0 for all £ 2 GF (24) it's rather easy to show that (2) is also equivalent to ^0(l) for any i — 1,..., 4:

Io,o,o,o(r) • (^0(l) © K (0)) © (l } I(r))|)=o

— Io,o,o,o(0) • (^0(l) © (0)) © (l } I(0)),

— 1 • (^0 (l) © (0)) © (0) — ^0 (l), i — 1,...,4. (3)

At the same time (0) = (0,0,1, 0). That means that we only have to add one additional XOR operator to represent the equation (2).

After branching elimination the complexity of our representation has increased by 13 operations. The number of operations of each kind is given in a table below:

AND OR NOT XOR Total

10,0,0,0 (r) 3 3

Io,o,o,o(r) 1 1

Final glue

by every coordinate 1 1(2)

Final glue

for all coordinaetes 4 5 9

Total 13

4. Computer implementation of non-linear elements 4.1. Formulation of the problem

Consider a transformation table 24 ! 24 or 28 ! 28. The goal is to represent it as a set of Boolean functions in the basis of logical functions AND, OR, NOT, XOR with the minimal number of operations. The number of 1- and 2-input operations (AND, OR, NOT, XOR) required to implement a function will be used as the evaluation criteria.

This estimate coincides with the actual complexity of the circuit when it is implemented by integrated circuits containing corresponding logic elements. It also coincides if the FPGA function is used to implement it, since logical operations in this situation are formed using a matrix of macrocells, and the operation does not depend on the FPGA choice.

The algorithm is constructed as follows: at the first optimization step, the Quine-McCluskey algorithm is used, then the steps described below in sections 4.3.1-4.3.6 are iteratively repeated. After that, rules 4.4-4.7 are applied, with repetitive calls to procedures 4.3.1-4.3.6 if necessary.

For an example illustrating the steps of the algorithm we use the table of values of the v\ function from BPU-decomposition:

Table 1

X 0 1 2 3 4 5 6 7 8 9 a b c d e f

Y 7 6 c 9 0 f 8 1 4 5 b e d 2 3 a

Each of the Y bits may be represented in the form of PDNF, consisting of precisely 8 members since it is a coordinate function of a permutation. For example, for Yo in this example, this function will have the following form:

Y0 — (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3)

+ (Xo • X1 • X2 • X3) + (Xo • X1 • X2 • X3) + (X0 • X1 • X2 • X3)

+ (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3).

The complexity of this representation is 47 operations.

Using the optimization techniques shown below, this function may be simplified to the following form:

Yo — (X1 + X2) © Xo © X3.

The complexity of this representation is 4. Thus, for this particular example, the complexity decreases by more than 11 times as a result of our optimization.

As a second example, consider Y3:

Y3 — (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3)

+ (X0 • X1 • X2 • X3) + (Xo • X1 • X2 • X3).

This function representation requires 45 operations.

By means of optimization this function may be simplified to the following form:

Y3 — ((Xo © X3) • X2) © X1.

The complexity of this representation of the function is 3, which is 15 times better than the original one.

4.2. Quine—McCluskey algorithm

One of the algorithms for minimizing Boolean functions was proposed by Willard Quine and improved by Edward McCluskey. Since the algorithm is described in sufficient detail in many sources (see, for example, [5, p. 232-239]), its implementation will not be described in this paper.

Consider the simplification of the above examples of functions with this algorithm. For a formula representing the function Yo (with initial com-

plexity of 47 operations)

Y0 = (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3)

+ (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3)

after optimization we get a formula with complexity 29 (1.5 times less complexity for this example):

Y0 = (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3)

+ (X0 • X1 • X3)

+ (X0 • X2 • X3) + (X0 • X1 • X3) + (X0 • X2 • X3).

For the Y3 function (the initial complexity of the representation is 45 operations), the Quine-McClusky method gives the result of 22 operations (optimization by 2 times):

Y0 = (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X3)

+ (X0 • X2 • X3) + (X1 • X2).

4.3. Further optimization of the Quine—McClaskey algorithm

As further steps for optimizing Boolean functions, an algorithm consisting of several steps is proposed. Moreover, each step is performed for all members of the polynomial inside the brackets. If optimization has been performed at any of the steps of the algorithm, then the algorithm starts again from the first step.

4.3.1. Duplicate Elimination

This step removes duplicates that may have appeared in previous iterations:

X1 • X1 • X2 = X1 • X2, X1 + X1 + X2 = X1 + X2, X1 e X1 e X2 = X2.

4.3.2. Removing the common factor under the logical OR performed on logical AND

(X1 • X2) + (X1 • X3) = X1 • (X2 + X3). _МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КРИПТОГРАФИИ_

For the above example (Yo function with complexity 47), the representation after this transformation takes the form

Yo — (Xo • ((X • X • X3) + (X3 • (X1 + X2))))

+ (Xo • ((X • X2 • X3) + ((X1 + X2) • X3))

with the complexity value of 20.

4.3.3. Optimization of occurrences of the same term with and without negation for logical AND and OR, as well as optimization of constant members

We use formulas X1 • X — 0,X1 + X — 1,X1 • 0 — 0,X1 + 1 — 1.

4.3.4. Optimization of «NOT»

At this step, an attempt is made to reduce the number of NOT operations, using a single formula

X1 + X 2 — X1 • X2.

For the above example (formula with complexity 47), the representation of the function after this operation will take the following form:

Yo — ((X1 + X2 + X3 + (X1 + X2) • X3) • Xo)

+ (((X1 • X2 • X3) + ((X1 + X2) • X3)) • Xo)

with complexity 18.

4.3.5. Search on the table of pattern optimal functions

At this step, a table of optimal functions is used. The construction of the table is described below. A table of values of the function being optimized (or its parts) is generated. After that the values from this table are compared with the reference ones from the table of optimal functions. If they coincide, the pattern optimal function is used instead of the original one. At the moment, the table of optimal functions is constructed for functions of up to 4 variables.

To construct the table of optimal functions, the following approach was used (let us consider the case of compiling a table for three variables). First, functions are created within one operation (for each of the AND,

OR, XOR operations) by sequentially arranging the brackets and NOT operations, for example:

F — Xo + X1 + X2, F — Xo + X1 + X2, F — X 0 + X1 + X2,

F — X 0 + X1 + X2, F — X 0 + X1 + X2, F — X 0 + X1 + X2, F — Xo + X1 + X2, F — Xo + X1 + X2,

and so on.

After that, formulas using combinations of binary operations are added (OR and XOR, for example), for which all combinations of parentheses

and negation are also sorted out, for example: _

F — (Xo + X1) ©X2, F — Xo + (X1 ©X2),F — (Xo + X1) ©X2, and so on.

At the next step, functions with tables of the same complexity are removed from the list of functions, while leaving the function with the minimum number of operations. The final list of pattern optimal functions is entered into the program in symbolic form from a file, which allows, on one hand, not to spend time on calculating the table each time the algorithm is run, and, on the other hand, it allows to supply the table with functions obtained by other algorithms or empirically.

We consider two examples of optimization of the components of the function Yo

F — (X1 • X2 • X3) + ((X1 + X2) • X3).

The table of values for this function (the number of operations is 8) is the following:

Xi 0 1 0 1 0 1 0 1

X2 0 0 1 1 0 0 1 1

X3 0 0 0 0 1 1 1 1

F 0 1 1 1 1 0 0 0

In the table of optimal functions there is a function with complexity 2, the truth table of which is similar to the above:

f = X3 e (Xi + X2).

Accordingly, part of the polynomial may be replaced with this function. Consider another example (the initial complexity of the representation

is 8): ___

F = (Xi + X2 + X3 + ((Xi + X2) • X3)) • X0.

Note that in this polynomial there is a common part X1 + X2. Let us denote it by Pi. The function will take the form

F = (Pi + X3 + (Pi • X3)) • X0.

According to the truth table, the algorithm finds the following optimal function:

F = X0 + (X3 © Pi). Let us return from P back to X1 + X2

F = Xo + (X3 © (Xi + X2)).

The complexity of the resulting function is 4. As a result of this optimization step, the initial function will take the following form (complexity of 8 operations):

Y0 = (((Xi + X2) © X3) + X0) + (((Xi + X2) © X3) • X0).

4.3.6. Search for XOR possible usage

This step analyzes the possibility to use XOR, in accordance with the formulas

X0 • X1 + X0 • Xi = X0 © Xi,

(X0 + Xi ) + (X0 • Xi ) = X0 © Xi. For the above example, the formula for the function Y0 will take the form

Y0 = X0 © (Xi + X2) © X3.

As a result, the complexity of the formula has become 4, which is about 10 times less than the original.

4.4. Additional optimization by combining brackets

In some cases, the above optimizations do not provide the minimal representation of the function. Consider an example. After a number of optimizations Y2 function has become like that:

Y2 = (Xi • X2 • X3) + ((Xi + X2) • X3).

An additional step is provided for handling such cases. If there are more than two terms under the brackets, then several functions are formed with different placement of brackets:

Y2 = (Xi •(X-X3)) + ((Xi+X2)^X 3 ),Y2 = (X • (Xi ^3 )) + ((Xi +X2) • X3),

Y> — (X3 • (X1 • X2)) + ((X1 + X2) • X3).

After that every formula from the set is optimized by the algorithm described above, and the formula with smallest resulting complexity is chosen. In our case it is the third function. It is transformed like this:

Y2 — (X3 • (X1 • X2)) + ((X1 + X2) • X3) — (X3 • (X1 + X2 )) + ((X1 + X2) • X3

— (X1 + X2) © X3.

4.5. Primary XOR-optimization

In some cases, the optimization techniques discussed above do not lead to the best representation. Consider bit Y3 of table 2:

Y3 — (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3)

+ (X0 • X1 • X2 • X3) + (X0 • X1 • X2 • X3).

The initial number of operations in the representation of this function is 45.

As a result of the above optimizations, one can get a function of the following form:

Y3 — ((Xo © X3) • X2 • X1) + ((Xo © X3) • X1 • X2).

The number of operations in this representation is 9, which is 5 times less than the original.

Nevertheless, for representations of the function with the number of operations greater than 2, the algorithm makes an additional optimization attempt.

4.6. Using the Algebraic Normal Form (ANF)

Further, the program uses the representation of the function in the form of Zhegalkin polynomial (ANF). First, if one or more variables are found in the Zhegalkin polynomial in the form of terms of the first degree and are not found in any monomial anymore, they may be separated as terms modulo two, immediately reducing the dimension of the problem. If there are no such variables, in some cases it is still possible to reduce the complexity of the representation by separating certain variables as modulo two sum-mands. Let us return to our example from section 3.1 (Table 1). Since the XOR function takes the value 1 when arguments are different and 0 when

their values are the same, we can represent the value Y in the following form:

Y = Xj © F(X),

where Xj is one of X bits, and F(X) is equal to 0 for all cases where

Y = Xj and is equal to 1 if Y = Xj.

Obviously, one has to choose the bit X such that as many as possible

Y = Xj, because in this case F(X) will have less terms. Consider the values of Y3 in the following table:

3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

X to 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

Xi 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Xo 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

3 0 0 1 1 0 1 1 0 0 0 1 1 1 0 0 1

For each of Xi,i = 0,..., 3, the number of positions in which the value of Xi coincides with the value of Y, is calculated. For this example, we get the following result

X0 Xi X2 X3

8 12 8 8

Accordingly, the function will have the form

Y3 = Xi © F(X).

We represent F(X) in the form of PDNF with a value of 1 for cases of mismatch between X and Y (mismatching values are indicated by squares around them). So we get the function

Y3 = Xo © ((Xo • Xi • X2 • X3) + (Xo • Xi • X2 • X3)

+ (Xo • Xi • X2 • X3) + (Xo • Xi • X2 • X3)).

The complexity of this representation of the function is 21. However, F(X) may be optimized by the methods indicated above. After the specified processing, the function takes the form

Y3 = Xo © ((Xo © X3) • X2).

The complexity of this representation is 3.

4.7. Merging common parts

As the final step, the algorithm attempts to find common parts both within one function and among all functions of the set, in order to optimize their calculation.

For example, for the above table, the algorithm worked out the following set of functions:

Yo — Xo © (X1 + X2) © X3, Y1 — ((X2 + X3) © (Xo • X2))+ X1 © (X1 • X3), Y2 — ((X1 © X2) • (Xo © X3)) © X2, Y3 — Xo © ((Xo © X3) • X2).

Total complexity is 19 operations. At the last step, the algorithm explores what is included in Yo, Y2, and Y3. The algorithm denotes such common parts by the symbol P. For the given example, the following formulas are obtained:

Yo — Po © (X1 + X2),

Y1 — ((X2 + X3) © (Xo • X2))+ X1 © (X1 • X3), Y2 — ((X1 © X2) • Po) © X2,

Y3 — Xo © ((Po • X2)), Po — (Xo © X3).

After merging the common parts into separate functions, the complexity of our example is reduced from 19 to 17.

4.8. Optimization results

As a result of the above algorithm, the following set of Y functions was produced for the test data table:

Yo — Po © (X1 + X2),

Y1 — ((X2 + X3) © (Xo • X2))+ X1 © (X1 • X3), Y2 — ((X1 © X2) • Po) © X2, Y3 — Xo © ((Po • X2)), Po — (Xo © X3).

The total complexity of this set of functions is 17, which is approximately 10 times less than the complexity of the set of non-optimized functions,

equal to 188. The following are explicit formulas for all nonlinear functions involved in BPU-decomposition:

Number

F Presentation of opera-

tions

I Yo = (Xo ■ Xi) + (((Xo © Xi) + Pi) ■ X3)

Yi = (Xo ■ X2) © (Xi ■ Pi ■ P2) © X3

Y> = ((Xi © X3) ■ ((Xo + X2) © Xi)) © X2 26

Y3 = (Xi ■ X2) + (((Xi © X2) + P2) ■ Xo)