id: Гость   вход   регистрация
текущее время 18:00 05/12/2019
Владелец: unknown (создано 15/09/2008 11:33), редакция от 28/10/2008 10:42 (автор: unknown) Печать
Категории: криптоанализ, атаки, побочные каналы
http://www.pgpru.com/Новости/2008/КубическаяАтакаМожетВскрыватьШифрыБезЗнанияИхВнутреннегоУстройства
создать
просмотр
редакции
ссылки

15.09 // Кубическая атака может вскрывать шифры без знания их внутреннего устройства


Итай Динур и Ади Шамир из департамента компьютерных наук института Вейцмана предложили новый способ атак на алгоритмы шифрования, их работа называется "Cube Attacks on Tweakable Black Box Polynomials".
Выступление Шамира происходило на конференции CRYPTO2008, но сама работа изначально в общем доступе опубликована не была, что породило некоторые преувеличения и неверные толкования после доклада.


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


Ближайшая предыдущая атака такого рода (Fischer, Khazaei, Meier) на потоковый шифр Trivium имела сложность 255 после 672 раундов инициализации. Атака Шамира-Динура снижает этот порог на примере того же шифра до 219 или до 230 после 735 раундов (что было полностью недостижимо ранее). Путём экстраполяции можно определить, что атака всё ещё эффективнее чем простой перебор после 1024 раундов инициализации. Предыдущие атаки такого рода необходимо было адаптировать под каждый алгоритм, они носили эвристический характер, не имели строгой оценки степени сложности и были малоуспешны при применении к полиномам случайного вида.


Кубическая атака, напротив, успешна при применении к полиномам случайного вида степени d относительно n секретных переменных когда число открытых переменных m превышает d + logd n. Сложность атаки составляет 2d-1 n + n2 .
Атака полиномиальна по отношению к n и на удивление мала в случае малых значений d.


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


Решение больших систем полиномиальных уравнений с многими переменными, даже если они являются только квадратическими, является так называемой NP-полной задачей. На этом основана стойкость многих криптографических алгоритмов. Использование алгоритмов на основе базисов Грёбнера по отношению к полиномам с числом неизвестных более 100 требует быстровозрастающих расходов памяти и вероятно не может дать практический результат в криптоанализе.


Попытки линеаризации и построения системы линейных уравнений по методу исключений Гаусса также не дают результата.
Так для системы из 256 уравнений в поле GF(2) на многочленах при d=16 и n=256, количество членов решаемых уравнений возрастает до nd = 2128, что делает данную атаку непрактичной по сравнению с простым перебором. Улучшения данной техники в виде XL и XSL алгоритмов стали весомыми достижениями в алгебраической криптоанализе, но всё ещё оставались непрактичными в большинстве случаев.


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


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


В этой работе авторам удалось показать, что даже если мастер-полином (главный многочлен) достаточно случайный, с высокой вероятностью возможно отделить nd нелинейных членов, получив удивительно малое количество 2dn модифицированных вариантов, затем решить предвычисленную версию n линейных уравнений в n переменных, используя только n2 операций. Например для d=16 и n=10000 можно исключить одновременно все 2200 нелинейных членов, учитывая только 220 производных полиномиальных уравнений, полученных путём шифрования 220 подобранных шифртекстов, меняя в них 20 битов всеми возможными вариантами. После такого "массового уничтожения" нелинейных членов остаётся линейная система уравнений случайного вида со всеми секретными переменными, которую легко решить.


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


Атака называется кубической, потому что она связывает множество всех значений n с d-1-мерными булевыми кубами и суммирует результат по каждому кубу. Данная атака также напоминает атаки интерполяции, квадрата и интегрирования и является их дальнейшим развитием и обобщённым случаем на базе алгебраического криптоанализа.


В полях GF(pk), p>2, атака ближе к атакам дифференциалов высоких порядков, чем к интегральной атаке, но основана больше на алгебраических, чем статистических техниках.


Взлом современных блочных шифров с помощью данной атаки затруднён. Они имеют высокую степень алгебраической сложности, которая растёт экспоненциально с ростом числа раундов (до достижения определённого максимального значения (n + m) ). Однако любой блочный шифр, степень сложности которого меньше чем размер ключа и открытого текста может быть гарантировано атакован.
Впервую очередь это касается облегчённых версий шифров, предназначенных для работы в смарт-картах. В следующей работе авторы обещают представить улучшенную версию атаки против блочных шифров. Её идея известна как "атака встречи посредине", когда биты в середине раундов описываются зависимыми как от открытого текста, так и от шифртекста. Это накладывает на противника ряд дополнительных условий но снижает сложность атаки на корень квадратный от исходного значения степени полиномиальной сложности шифра. Возможно дополнительное применение данной атаки и для случаев двойного шифрования.


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


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


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


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


Источник: Cryptology ePrint Archive


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