Статистический анализ современных блочных шифров
С помощью статистического теста "Стопка книг" исследованы всех блочные шифры, участвовавшие в конкурсе на стандарт шифрования AES (Advanced Encryption Standard), который был организован Национальным институтом стандартов и технологий США. Впервые экспериментально показано, что шифртекст после восьми раундов шифра MARS – финалиста конкурса AES – не подчиняется равномерному распределению. Экспериментально установлено, что шифртекст после половины всех раундов шифров FROG и LOKI97 не подчиняется равномерному распределению. Для этих двух шифров на основании полученных экспериментальных данных построен прогноз, позволяющий сказать, что с помощью 278 и 286 блоков шифртекст после полного числа раундов FROG и LOKI97 соответственно можно отличить от равномерного распределения.
http://www.ict.nsc.ru/jct/annotation/978
В табл. 6 приведены число раундов, после которого шифртекст можно отличить
от случайности ®, полное число раундов ®, размер выборки, на который фиксируются
отклонения (N) и параметры тестирования, введенные в разд. 2. Для шифров RIJNDAEL,
MAGENTA, SAFER+ и DEAL число раундов зависит от длины секретного пользователь-
ского ключа, поэтому в таблице даны все возможные значения. Например, для RIJNDAEL
при 128-битном ключе нужно выполнить 10 раундов,
192-битном 12 и 256-битном 14.
Недавно наткнулся на эту совсем небольшую и достаточно интересную статью,сам не проверял пока, нет времени, но вообще по Rijndael м.б. как нибудь и проверю, бо интересно же :) Вообще статья не очень новая, вдруг кто-либо из уважаемого сообщества уже знаком с подобным материалом и имеет что либо сказать по этому поводу?
Что? Это же основы разработки любой псевдослучайной функции.
Интересные и нужные исследования. Но, они совсем не говорят о слабости шифра.
Так уж и совсем?
Пример:
Берем автомобиль, молотком разбиваем лобовое стекло.
И делаем вывод: двигатель тоже можно разбить молотком.
Или отрываем руль в машине, выходим на дорогу и говорим: если руль сам не едет значит и автомобиль не поедет.
Очевидно, следующим логическим событием в данном контексте должно быть определение характерных признаков алгоритма на шифротексте, как-то так :)
Вот как раз зависимости, при использовании всех раундов, они и не нашли. Поэтому и опубликовали работу о найденных зависимостях только 2-4 раундов, что вполне допустимо.
Классическое определение взлома шифра — это нахождение ключа или чтение открытого текста быстрее, чем полным перебором.
Но в последнее время это определение настолько расширилось, что если кто-то найдёт и опубликует полнораундовый различитель шифра от идеальной псевдослучайной модели, то это тоже будет скорее всего считаться атакой, такой шифр забракуют и посчитают почти взломанным (пример — RC4, хотя он не блочный).
При том, что прицельные виды криптоанализа против малого числа раундов более эффективны. Статистический метод — самый примитивный, годится для выявления грубых изъянов в дизайне и не гарантирует стойкости даже при хороших результатах тестов.
NIST тестировал всех кандидатов статистическими методами во время конкурса (скорее в качестве формальности, чтобы выпустить ещё один отчёт) и даже выпустил свой пакет тестов — "батарея НИСТ".
Скажите, а нахождение полнораундового различителя это и есть возможность отличить шифр от случайной перестановки в моделе случайного оракула?
Да
Берём два автомобиля: у одного стекло разбивается молотком, а у второго – бронированное. Вопрос: у какого автомобиля труднее молотком нарушить работу мотора? :)
Или даже так: известно, что злоумышленник молотком будет пытаться нарушить работу мотора. Какой автомобиль вы выберете?
Чего стебаться то, атомная бомба начиналась с вполне невинных разговоров о чисто теоретических возможностях.
Ответ:по стеклу нельзя судить о моторе, могут сделать бронированное стекло, но это еще не значит что будет хороший мотор...
Так же нельзя судит по 2-м раундам о всем шифре...
Вот ели вы покажете на полнораундной реализации какие-то зависимости, тогда можно будет о чем-то говорить.
Никто не судит по двум раундам о шифре. Такие исследования всегда служат основой для дальнейших изысканий. Взлом хороших криптографических алгоримов редко делается за "один присест".
В том то и дело, что дальнейшие исследования в этом направлении безперспективны, что и показали авторы статьи.
Они смогли вывести зависимости после 2-4-х раундов, и если бы были зависимости для большего числа раундов, думаете они о этом не написали бы? Кричали бы как о мега-научном открытии.
Другое дело если бы они нашли новый вид криптоанализа, хоят бы для начала для такого числа раундов, а потом уже была бы перспектива расширить на больше раундов.
А так .... :)
Москва не сразу строилась. Ктонибудь в будущем распространит зависмости на бОльшее колво раундов.
Скажите, а что за стопка книг?
Я совсем не хочу утверждать о идеальности AES и д.р., но думаю если его и взломают, то последее чем будут ломать, это описанный в статье метод...
"Скажите, а что за стопка книг?" -в статье описан.
Акробат ридера нет, а соединение медленное. Вы не могли бы вкратце описать?
В кратце: для случайных текстов и 100 случайных ключей подсчитывали на каком раунде шифртекст отличен от случайного.
PDF вьювер, всего полтора мегабайта.
http://blog.kowalczyk.info/sof.....trapdf/download.html[link1]
Поправка:текст не случайный.
"Рассмотрим последовательность блоков Xui, u ∈ {0, 1, 2, 3},
у которых подблок с номером u равен i, а остальные – нулевые, i пробегает значения
0, 1, ..., N − 1."
Кстати с таким же успехом могли бы и ключи брать не случайные. По идее больше бы зависимостей нашли. Хотя... с таким же успехом в результате.
Ничего подобного авторы не показали, очевидно же. В статье был продемонстрировен метод, приводящий к интересным резу-
льтатам. Кстати, еще неизвестно, чем бы дело кончилось при наличии доступа к вычислительным мощностям, сравнимым, например, с новым кластером РАН. Опять же, отсутствие материала по теме может означать что угодно, взять хотя-бы узлы замены ГОСТ. Такие дела...©
Вы на вероятности неслучайности шифртекста при большем числе раундов смотрели?)
И кстати если у них будет возможнось работать с величинами 2^86 и более, тогда и их анализ не нужен будет.
НИСТ проводил такое исследование ещё во время конкурса AES. И не одной "стопкой книг", а целой батареей тестов.
И даже получил более "впечатляющие" результаты.
Которые, на самом деле, никого особо не впечатлили.
http://csrc.nist.gov/archive/aes/round1/r1-rand.pdf
В тестах были выявлены и скорректированы ошибки:
http://eprint.iacr.org/2004/018
И "дайхардом" всё проверяли — там и тесты типа "карточные игры" или "сборщик купонов" и т.д.
Эта тема достаточно хорошо исследована и не содержит новизны.
Это предыстоки современного криптоанализа, которыми занимались в семидесятых-восьмидесятых годах.
Единственно, можно заметить, что существует "хи-квадрат криптоанализ", который отличается от простых статистических тестов (учитывает свойства раундовой функции, является расширением линейного криптоанализа) и вот он действительно имеет перспективы для дальнейшего исследования и усовершенствования.
А вот эти авторы ( Anna Rimoldi[link2] + возможно кто-то ещё — работа не опубликована, будет представлена на декабрьской конференции) здесь[link3] утверждают, что взломали полнораундовый AES в модели связанных ключей именно таким методом — с помощью дайхардовских тестов. Правда они использовали комбинированный статистическо-алгебраический (тесты подгонялись под алгебраические особенности шифра — как раз похоже на метод "хи-квадрат") криптоанализ, но зато якобы построили различитель всего за 245 операций.
unknown:"работа не опубликована, будет представлена на декабрьской конференции"
Вот когда будет представлена, увидим.
Кстати идея атаки на AES, испльзуя его алгебраическую структуру, не нова.
Еще одно подтверждение мысли о необходимости осторожного использования математики в криптографии. :)
При том, что она практически вся на ней построена, но слепо верить в неё да, нельзя. Нужно ещё построить модель в рамках которой доказывать ограниченность шифра и как-то аргументированно убедить всех специалистов — что это хорошая модель, покрывающая все мыслимые потребности безопасности.
А потом явится некто вроде Н. Коблица и заявит что-то вроде — "фигня вся эта ваша криптография — никаких доказанных теорем, одни аргументы для убеждения в математической обёртке" ;-)
В неё то как раз можно (почти), а вот в её применимость в конкретных случаях реальной жизни – да, нельзя.
Да, так точнее.
И все атаки не были доведены даже до теоретического завершения.
Зато алгебраическая атака против нескольких раундов DES, который вообще никакой алгебраической структуры не имеет (зато у него S-блоки маленькие), была более успешной. Не всё так просто. Всё ещё сложнее :-)