id: Гость   вход   регистрация
текущее время 02:55 29/03/2024
Владелец: unknown (создано 23/09/2014 16:22), редакция от 23/09/2014 16:31 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, симметричное шифрование, аутентификация, атаки
https://www.pgpru.com/Новости/2014/НизкаяАлгебраическаяСложностьKeccakKeyakОблегчаетКубическиеАтаки
создать
просмотр
редакции
ссылки

23.09 // Низкая алгебраическая сложность Keccak/Keyak облегчает кубические атаки


Сразу после появления алгоритма Keccak множество исследователей обратило внимание на низкую алгебраическую сложность его раундовой функции.


Keccak Round Function Pseudocode (47 Кб)

Хотя изначально это не казалось большой проблемой, но впоследствии позволило построить достаточное число неполнораундовых различителей и алгебраических атак на их основе, таких как атаки нахождения второго прообраза на обобщённых внутренних дифференциалах и атаки на различителях с нулевой суммой. В ходе конкурса SHA-3 алгоритм Keccak тем не менее был признан финалистом, однако после публикации неожиданных атак исследователям пришлось перестраховаться и до финала увеличить число раундов до 24-ёх.


В ходе конкурса SHA-3 все алгоритмы рассматривались с т.з. хэш-функций, а их дополнительные возможности исследовались криптоаналитиками в меньшей степени. В то время как Keccak может быть использован с секретным ключом в режиме MAC, потокового шифра и аутентифицированного шифрования. Режимов аутентифицированного шифрования на основе губчатых конструкций, используемых в Keccak, было создано несколько, однако на конкурс CAESAR (Competition for Authenticated Encryption: Security, Applicability, and Robustness) авторами был представлен режим аутентифицрованного шифрования (AE) Keyak.


Keccak and Keyak Key Modes (44 Кб)

В атаках на режимы с секретным ключом исследователям Itai Dinur, Pawel Morawiecki, Josef Pieprzyk, Marian Srebrny и Michal Straus (Кафедра компьютерных наук высшей нормальной школы Парижа, Институт компьютерных наук польской академии наук, отделение информатики университета комерции Кельце, Квинслендский университет технологий Брисбена, Австралия) удалось взломать сравнительно большое число раундов Keccak/Keyak, причём эти атаки оказались намного превосходящими атаки полного перебора (грубой силой). Для версий с наименьшим числом раундов удалось проверить работу атак на практике: програмная реализация смогла найти результат за несколько дней работы на обычном компьютере.


Режим использованиеРаундыТип атакиСложность полного перебораСложность
атаки
MAC5Восстановление ключа2128236
MAC6Восстановление ключа2128236
MAC7Восстановление ключа2128297
MAC7Подделка выходного значения2128265
MAC8Подделка выходного значения22562129
Аутентифицированное шифрование (Keyak)6Восстановление ключа2128236
Аутентифицированное шифрование (Keyak)7Восстановление ключа2128276
Аутентифицированное шифрование (Keyak)7Подделка выходного значения2128265
Потоковый шифр6Восстановление ключа2128235
Потоковый шифр8Предсказание гаммы22562128
Потоковый шифр9Предсказание гаммы25122256

Для проведения взлома исследователи использовали модификации кубической атаки на основе подобранных открытых текстов с восстановлением ключа, которая в свою очередь является продолжением атаки дифференциалов высших порядков и атак AIDA (Algebraic IV Differential Attack).


Кубическая атака подразумевает, что бит шифра на выходе задан полиномом чёрного ящика f : Xn → {0,1}, в котором входящие биты являются переменными. В основе атаки лежит наблюдение, что если полином имеет (низкую) алгебраическую сложность d, то суммирование его выходов над 2d-1 входами, в которых подмножество переменных (куб) размерностью d – 1 над всеми возможными значениями, а другие переменные фиксированы как константы, приводит к образованию линейной функции.


Как гласит теорема Динура-Шамира, для заданного полинома f : Xn → {0,1} степени d при предположении, что 0 < k < d существует одночлен t в форме x0 … xk-1. При этом можно записать функцию f(x) = Pt(x) + Qt(x), в которой никакой из членов Qt(x) не делится на t. Следует отметить, что степень Pt≤d-k. Тогда сумма f над всеми значениями куба (определёнными t) будет равна:


 (8 Кб)

степень которого равна самое большее d – k (или 1 если k = d – 1), где куб Ct содержит все двоичные векторы длины k.


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


В фазе предварительной подготовки (оффлайн-фазе) противник подготавливает данные для криптосистемы независимо от значения секретного ключа. Если определить открытые переменные (которые контролирует атакующий, такие как текст сообщения или в некоторых случаях вектора инициализации) как v = (v1 , … vd-1), а секретные переменные ключа через x = (x1 , … xn), то выход (бит шифртекста, гаммы или хэша) будет определяться полиномом f(v,x). После чего вводится обозначение:

 (4 Кб)

для некоего куба Ct, где L(x) называется superpoly от Ct. Подразумевая, что степень f(v,x) равна d можно записать L(x) = a1 x1 + … + a1 x1 + c. В подготовительной фазе находятся линейные superpoly для L(x), которые в конечном итоге позволяют построить набор линейных уравнений в секретных переменных. Линейные коэффициенты L(x) интерполируются для нахождения:


 (11 Кб)

В самом общем случае полное символьное описание f(v,x) неизвестно и требуется оценка степени d с использованием дополнительного сложного подготовительного шага. Этот шаг заключается в переборе кубов разных размерностей и проверке их superpoly L(x) на свойство линейности. Но в специализированных атаках на Keccak степень f(v,x) легко определяется и без такого дополнительного шага.


Онлайн-фаза проводится после задания секретного ключа в криптосистеме. В ней используется возможность задания атакующим открытых переменных v. Для каждого куба Ct атакующий вычисляет двоичное значение bt путём суммирования над кубом Ct или говоря иначе:

 (4 Кб)

Для заданного куба Ct его bt будет эквивалентно линейному выражению L(x), определённому на подготовительной фазе, следовательно получается единичное линейное уравнение вида a1 x1 + … + a1 x1 + c = bt.
Рассматривая множество различных кубов Ct, атакующий стремится сконструировать достаточное число линейных уравнений. Если количество (линейно независимых) линейных уравнений равно числу секретных переменных, то такая система решается методом Гауссова сокращения.


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


Исследователи сделали множество наблюдений, относящихся к применению алгебраических атак в отношении режимов использования Keccak с секретным ключом. С учётом того, что алгебраическая степень раундовой функции равна 2, то после 5 раундов степень алгебраической сложности Keccak будет не выше 25 = 32 и для любого куба с 32 переменными его superpoly будет содержать только линейные члены, что и помогает избежать тестирования superpoly на линейность. Однако, некоторые superpoly могут быть константами, т.е. не содержат никакой информации о ключе. Это происходит из-за слабой диффузии переменных в начальных раундах, что приводит к уменьшению алгебраической сложности битов на выходе по сравнению с максимально возможным 32-битным значением степени. Исследователи смогли выбрать 117 линейно независимых выражений superpoly путём поиска в течении нескольких дней на обычном компьютере. Лишь 20-25% superpoly оказались подходящими (не константами). С другой стороны, рассмотрение других наборов битов на выходе, позволяло сократить поиск и найти подходящие superpoly быстрее.


В онлайн-фазе 5-раундового Keccak атакующий использует 19 кубов с 31 переменной, получая 19·231 ≈ 235 вызовов Keccak. Имея вычисленные значения superpoly, атакующий конструирует набор из 117 линейно независимых уравнений и вычисляет полный 128-битный ключ, угадывая значения 11 дополнительных линейно независимых уравнений. Для 5-раундового Keccak сложность онлайн-фазы состоит из 235 вызовов функции Keccak, т.к. затратами на операции линейной алгебры можно пренебречь.


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


Подробности разных вариантов алгебраических атак на основе специфических свойств Keccak и Keyak приведены в работе. Авторы отмечают, что если взлом в режиме хэш-функции по предыдущим исследованиям пока составляет 5 раундов, то в ключевых режимах Keccak им удалось взломать до 9 раундов, что снижает оценки запаса прочности Keccak, особенно с возможностями дальнейшего улучшения атак. При этом для полных 24 раундов они пока оценивают стойкость ключевых режимов Keccak как всё ещё высокую. В то же время в Keyak используется сокращённая внутренняя функция перестановки с полным количеством раундов, равным 12. Для Keyak авторы отмечают, что запас прочности для него меньше, хотя всё ещё достаточен.


Источник: Cryptology ePrint Archive
См. также: Перспективные режимы Sponge-шифрования, Хэш-функция Keccak и конструкция Sponge как универсальный криптопримитив, Прогресс в криптоанализе Keccak/SHA-3, Кубическая атака может вскрывать шифры без знания их внутреннего устройства.


 
Комментариев нет [показать комментарии/форму]
Общая оценка документа [показать форму]
средний балл: +2респондентов: 9