id: Гость   вход   регистрация
текущее время 18:01 29/03/2024
Владелец: unknown (создано 25/10/2012 15:46), редакция от 29/10/2012 11:03 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, симметричное шифрование, атаки
http://www.pgpru.com/Новости/2012/НКуртуаПытаетсяДоказатьНевозможностьСозданияСтойкихS-блоковДляГОСТ-28147-89
создать
просмотр
редакции
ссылки

25.10 // Н.Куртуа пытается доказать невозможность создания стойких S-блоков для ГОСТ-28147-89


ГОСТ 28147-89 — широко известный блочный шифр, являющийся стандартом Российской Федерации. Он претендует на альтернативу для AES-256 и 3-DES и с 2010 года его пытаются провести через процедуру прохождения международной стандартизации в комитете международной организации по стандартизации для стандарта ISO 18033.


До 2010 года большинство исследователей считали ГОСТ стойким, а 20-летние попытки криптоанализа — безуспешными. В 2011 было неожиданно открыто множество разных типов атак на ГОСТ: атаки на рефлективных свойствах, атаки с двойным отражением, угадывание с подтверждением без использования рефлективных свойств, улучшенные дифференциальные атаки. Последним шагом большинства атак для восстановления ключа было использование различных классов программно-алгебраических атак, атак встречи посредине и дифференциальных атак угадывания с подтверждением битов ключа.


Если отбросить крайнюю сложность этих атак по количеству требуемых данных и учитывать только время исполнения, то до октября 2011 самой быстрой была атака Куртуа за 2216 шагов. Затем Шамир и др. улучшили эту атаку до значения 2192, что было представлено на конференции FSE 2012. Новая улучшенная дифференциальная атака Куртуа, представленная в его последней работе, многократно снижает стойкость ГОСТ (до уровня 2178) и требует всего одного ключа для полнораундовой версии шифра.


Следует отметить, что на сегодняшний момент для AES в таких условиях известны лишь атаки, снижающие его стойкость по сравнению с полным перебором лишь на несколько битов. Однако, следует отметить и то, что Куртуа снова прибегает к своему излюбленному приёму — исчерпанию полной кодовой книги шифра, исходя из размеров блока. Атака требует 264 известных открытых текстов и 270 затрат памяти. Получение такого объёма открытых текстов при таких размерах блока позволит противнику читать сообщения даже зашифрованные идеальным шифром, хотя и без восстановления ключа. Однако, для доказательства быстрого прогресса в криптоанализе с восстановлением ключа эта атака подходит.


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


Наиболее интересно предположение Н. Куртуа о бесполезности попыток создания стойких S-блоков для ГОСТ:


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

Обычное заблуждение состоит в том, что безопасность такого шифра как GOST против дифференциального криптоанализа (DC) существенно зависит от S-блоков и какие-то "оптимальные" S-блоки могут сделать его более безопасным, см. [18, 20]. Исследователи в научном сообществе изучают S-блоки по отдельности [18] и предлагают новые шифры [18, 20], но когда S-блоки объединяются вместе, всё становится по другому. Мы не уверены, возможно ли вообще сделать такой шифр как ГОСТ устойчивым к дифференциальному криптоанализу за счёт замены только S-блоков [18, 20], идея чего обсуждалась в ходе процесса стандартизации ГОСТа в ISO. Вопрос, как далеко мы можем продвинуться в улучшенных дифференциальных атаках, таких, как изученных в данной работе, остаётся широко открытым.

Мы полагаем, что безопасность ГОСТ против улучшенных форм DC зависит "по существу" от связей в шифре и хотя некоторые S-блоки могут его сделать более слабым против DC, никакие из них не сделают его по настоящему более сильным.

P.S. Данная новость приведена на основе текущих дополнений и уточнений в ревизии работы, ранее рассмотренной в марте 2012.


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


 
Много комментариев (32) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3