О вероятностях разностных траекторий sponge-функции Bash-f | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/27

О вероятностях разностных траекторий sponge-функции Bash-f

Предлагаются два метода оценки снизу весов разностных траекторий sponge-функции Bash-f. Оценки ограничивают сверху вероятности траекторий и могут использоваться при обосновании стойкости основанных на Bash-f криптографических алгоритмов к разностным атакам. Для полных 24-тактовых траекторий лучшая из оценок ограничивает вероятности величиной 2-386.

On probabilities of differential trails in the bash-f sponge function.pdf 1. Sponge-функции и разностные траектории Sponge-функция - это бесключевая подстановка, действующая на двоичные слова достаточно большой (по криптографическим меркам) размерности. Располагая sponge-функцией, можно построить целую линейку симметричных криптографических алгоритмов разнообразного назначения - от древовидного хэширования до аутен-тифицированного шифрования. Эти алгоритмы достаточно просты и имеют высокий потенциал быстродействия на распространённых аппаратных платформах. Обычная sponge-функция F преобразует слово X G {0,1}n в слово Y G {0,1}n, выполняя d тактов (итераций) X - F^X,-!), i - 1, 2,...,d, с Xo - X и Y - Xd. Здесь F, - тактовые подстановки. Слова X, интерпретируются как векторы над двоичным полем F2. Преобразования F, представляют собой композиции линейных и нелинейных преобразований этих векторов. Нелинейные преобразования, как правило, действуют локально на подвек-торы x G Fm, где m невелико. Действие задаётся подстановками S: Fm ^ Fm, которые в криптографии принято называть S-блоками. В разностном криптоанализе рассматривается обработка не одного, а сразу двух слов: X и X'. Пусть AX - X ф X' - их сумма, AX, - сумма слов, полученных в результате применения i тактов к X и X', i - 1, 2,... , d. Поскольку сложение по модулю два равносильно вычитанию, суммы AX, являются также разностями (отсюда и название - «разностный криптоанализ»). Ненулевые биты разностей будем называть активными. Последовательность разностей AX, AX1, AX2, ..., AXr называется (r-тактовой разностной) траекторией. Траектории с нулевой входной разностью AX тривиальны (состоят из нулей), мы их далее не рассматриваем. Пусть траектория порождается случайными X и X' с фиксированной разностью AX. Возможность достаточно точного прогнозирования AXr при r, близких к d, является предпосылкой для разностных атак. При обосновании стойкости F требуется оценить точность прогнозов и, в частности, получить оценки сверху для вероятностей траекторий. Мы строили разностную траекторию, суммируя промежуточные результаты обработки входных слов. Можно поступить по-другому. Представим себе вероятностную машину M, которая работает исключительно с разностями, последовательно применяя к ним преобразования F1,..., Fr, точнее, их композиционные элементы. Линейные преобразования применяются к разностям (или их фрагментам) так же, как если бы речь шла о первоначальных словах. Остаётся рассмотреть действие S-блока S на фрагмент разности Ax. Если Ax - 0, то разность Ay на выходе S также нулевая. Если же Ax - a - 0, то M выбирает Ay случайным образом в соответствии с вероятностным распределением P{Ay - в | Ax - a} - ^ £ I{S(u ф a) ф S(u) - в}, индуцируемым S (здесь I{E} -индикатор наступления события E). Случайный выбор Ay мотивируется случайным выбором входов F, которые порождают разностную траекторию. Следует понимать, что M только моделирует разностные траектории. Но это моделирование достаточно точно, точность считается удовлетворительной в практических случаях. Подача на вход S ненулевой разности Ax называется активацией S-блока. Активация является точкой ветвления - после неё выходная разность Ay определяется неоднозначно. Если активация произошла во время обработки разности AXi-1, то речь идёт о нескольких вариантах следующей разности AXj. Во время обработки AXj могут происходить новые активации, которые приводят к новым ветвлениям, и так далее. Другими словами, M на фиксированном входе AX порождает несколько вариантов траекторий. Число вариантов, как правило, экспоненциально быстро растёт с увеличением длины траектории r. Пусть во время генерации траектории AX, AX1,... , AXr произошло sa активаций S-блоков и p - произведение соответствующих вероятностей P{Ay = в | Ax = a}. Величина p и есть интересующая нас вероятность траектории. Далее вместо p будет удобнее использовать характеристику wa = - log2 p, которую называют весом траектории [1, 2]. Мы получим оценки снизу для веса траекторий sponge-функции Bash-f. 2. Sponge-функция Bash-f Sponge-функция Bash-f введена в работе [3]. Функция преобразует двоичные слова длины n = 1536, называемые состояниями. Состояние разбивается на 24 подслова длины 64. Слова записываются в матрицу размера 3 х 8. Строки и столбцы матрицы называются плоскостями: горизонтальными и вертикальными. Функция Bash-f построена как многократная композиция преобразований усложнения и перемешивания. За усложнение отвечает преобразование S3, которое применяется к тройке 64-разрядных слов. Тройки соответствующих друг другу битов этих слов (вертикальные линии) одновременно подвергаются действию фиксированного трёхби-тового S-блока. Одновременность достигается формульным заданием S3 с помощью логических операций AND, OR, NOT и сложения XOR. За перемешивание в Bash-f отвечают преобразования L3 и P. Первое преобразование также применяется к тройке 64-разрядных слов. Слова суммируются по правилу XOR, циклически сдвигаются, снова суммируются и т. д. Всего выполняется шесть сложений и четыре сдвига. Преобразование P переставляет местами 24 обрабатываемых слова. Выполняется d =24 такта. На каждом такте сначала к вертикальным плоскостям применяется L3, затем S3, затем плоскости перемешиваются с помощью P. Дополнительно, для разрушения однородностей, к 24-му слову добавляется тактовая константа. S-блок S: F3 ^ F2 выбран так, что для любого ненулевого a G F3 существует в точности четыре ненулевых в G F2, для которых P{Ay = в | Ax = a} = 4. Таким образом, вес Wa и число активных S-блоков sa связаны соотношением wa = 2sa. Пусть sa (r) -минимальное число активных S-блоков на нетривиальных траекториях Bash-f длины r и WA(r) = 2sA(r) -минимальный вес траекторий. 3. Результаты Мы получили оценки снизу для величины wa(24) двумя различными методами. Первый метод почти полностью автоматизирован, он реализуется компьютерной программой и, как всякий автоматизированный метод, имеет перспективы быстрого улучшения и точной верификации результатов. Второй метод почти полностью ручной, он реализуется прямыми расчётами на основе известных свойств L3 и P и, как всякий ручной метод, опережает автоматизированный, если не требует вычислений большого объема. Методы появились в ходе разработки Bash-f, в настоящей работе они усиливаются. В [1, 2] получены аналогичные оценки для величины wa(24), только применительно к sponge-функции Keccak-f (точнее, Keccak-f[1600]). Эта функция является ядром известного семейства алгоритмов хэширования SHA-3. В Keccak-f также выполняется d - 24 такта, длина состояния несколько больше: n - 1600. Оценки представлены в таблице. Как видим, на сегодняшний день оценки для Bash-f лучше оценок для Keccak-f. Оценки снизу для wa(24) Год, источник Bash-f Keccak-f метод 1 метод 2 2012 [1] 296 2015 (разработка Bash-f) 300 324 2017 [2] 368 2019 (настоящая работа) 386 372 Опишем суть наших методов. Будем работать с характеристиками s^(r). Метод 1. Оценивание sa (r) предполагает перебор разностных траекторий длины r. Прямой перебор затруднён уже при r - 3. Для сокращения перебора использовано сжатое описание траектории, фиксирующее только частичную информацию об их разностях. Такую частичную информацию мы назвали проекцией. Использовались следующие проекции: 1) avl -число активных S-блоков (вертикальных линий); 2) avp - число активных (т.е. хотя бы с одним активным битом) вертикальных плоскостей; 3) avls - число активных S-блоков для каждой из вертикальных плоскостей (упорядоченный набор из восьми чисел). Пусть [p](i) -проекция p разности i-го такта; [p1,...,pk](i,...,j) -набор проекций ([pu](v)), 1 ^ u ^ k, i ^ v ^ j. Некоторые проекции однозначно определяют другие. Например, сумма чисел в [avls](i) совпадает с [avl](i), количество ненулевых чисел в [avls](i) -с [avp](i). В этом смысле avls можно считать расширением проекций avl и avp. Очевидно, что сумма [avl](1) + ... + [avl](r) (*) представляет собой число активных S-блоков подразумеваемой r-траектории, а минимум суммы (*) по всем допустимым наборам проекций и есть искомое значение s^(r). Оценивание s^(r) выполняется в три этапа по схеме метода ветвей и границ. На первом (подготовительном) этапе рассчитываются характеристики линейного преобразования L3, которые позволяют отсеивать недопустимые наборы проекций на третьем этапе. На втором этапе перебираются проекции [avl, avp](1,... , r) и вычисляется минимум суммы (*). При этом наборы проекций, на которых он достигается, сохраняются. На третьем этапе перебираются расширенные проекции [avls](1,... , r), соответствующие проекциям, сохранённым на втором этапе. Если для некоторых i и j не существует допустимого набора [avls](i,... , j), соответствующего [avl, avp](i,... , j) из сохранённого набора, то набор [avl, avp](i,... , j) помечается как недопустимый и вычисления возвращаются ко второму этапу для уточнения минимума. Метод 2. Во втором методе оценивается снизу число активных S-блоков на четырёх тактах. Использованы свойства преобразований L3, S3, P, заложенные при проектировании Bash-f [3]. Особую важность имеет следующий факт: если на выходе L3 получена вертикальная плоскость с малым числом активных линий, то на вход была подана плоскость с большим числом активных линий. Базовые свойства преобразований выступают в роли аксиом, из которых аналитически выводятся теоремы - новые свойства, имеющие отношение к оцениванию. Затем просматриваются допустимые конфигурации, представляющие собой пары «число активных вертикальных линий на входах L3 на втором такте, проекция [avp](2)». Для каждой конфигурации оценивается снизу проекция [avl](1) (как будто бы от второго такта мы возвращаемся к первому) и проекции [avl](3, 4). В итоге получена оценка sa(4) = min([avl](1) + [avl](2) + [avl](3) + [avl](4)) ^ 31, откуда sa(24) ^ 6sa(4) ^ 186.

Ключевые слова

sponge-функция, S-блок, разностный криптоанализ, разностная траектория, sponge function, S-box, differential cryptanalysis, differential trail

Авторы

ФИООрганизацияДополнительноE-mail
Агиевич Сергей ВалерьевичБелорусский государственный университеткандидат физико-математических наук, заведующий НИЛ проблем безопасности информационных технологий НИИ прикладных проблем математики и информатикиagievich@bsu.by
Маслов Александр СергеевичБелорусский государственный университеткандидат физико-математических наук, старший научный сотрудник НИЛ проблем безопасности информационных технологий, НИИ прикладных проблем математики и информатикиmaslov@bsu.by
Ярошеня Юлия СергеевнаБелорусский государственный университетмладший научный сотрудник НИЛ проблем безопасности информационных технологий НИИ прикладных проблем математики и информатикиyuliya_10.06@mail.ru
Всего: 3

Ссылки

Daemen J. and Van Assche G. Differential propagation analysis of Keccak // FSE'2012. LNCS. 2012. V. 7549. P. 422-441.
Mella S., Daemen J., and Van Assche G. New techniques for trail bounds and application to differential trails in Keccak // IACR Trans. Symmetric Cryptology. 2017. No. 1. P. 329-357.
Agievich S., Marchuk V., Maslau A., and Semenov V. Bash-f: another LRX sponge function // Математические вопросы криптографии. 2017. Т. 8. №2. С. 7-28.
 О вероятностях разностных траекторий sponge-функции Bash-f | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/27

О вероятностях разностных траекторий sponge-функции Bash-f | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/27