id: Гость   вход   регистрация
текущее время 20:18 04/08/2020
Владелец: 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


 
На страницу: 1, 2, 3 След.
Комментарии [скрыть комментарии/форму]
— Гость (28/10/2012 20:07)   <#>
хотя некоторые S-блоки могут его сделать более слабым против DC, никакие из них не сделают его по настоящему более сильным.
Ключевая фраза, очень точно и ёмко сказано :)

Может ли Куртуа повлиять на принятие ГОСТа в стандарт ISO? Там чисто политическое решение или оно обязано опираться на рекомендации научного комитета, который внимательно следит за работами по криптоанализу ГОСТ?
— Гость (28/10/2012 21:36)   <#>
Он уже повлиял.. На первом голосовании ГОСТ был отклонен из за его работы. В принципе оно то и понятно, ГОСТ разрабатывался в другие времена и для других целей. Тогда еще не существовало случайных оракулов, а безопасность обеспечивалась за счет доказательства через неясность. Если будет принят другой стандарт, то он, конечно же, будет лишен тех недостатков. Однако можно обойтись и костылями – публикацией S-блоков и подправкой ключевого расписания константами.
— unknown (29/10/2012 09:57, исправлен 29/10/2012 09:57)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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



Результаты этой работы были также подтверждены группой Динура-Шамира на FSE-2012.



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



Если как-то пофиксить ключевое расписание, то возможно часть атак на восстановления ключа превратится в более абстрактные различители, но не исчезнет совсем. Сложно оценить, насколько приемлемая картина в итоге получится.

— Гость (30/10/2012 01:21)   <#>

К слову: а когда оно будет окончательно принято? Или уже?
— Гость (30/10/2012 12:24)   <#>
Политика – вещь переменчивая...
— фыва (01/11/2012 06:40)   <#>
и чего только люди не придумают, на что только не наобижаются, только бы не двигаться вперед и не придумывать новых алгоритмов
— Евгений (08/08/2013 14:37)   <#>
Для того, чтобы понять ценность работ этого "ученого" надо просто посмотреть его работы и обратить внимание на одну особенность его статей. Он оперирует не канонической для любого ученого парой "теорема-доказательство", а одним емким словом "факт". Легко видеть, что все такие "факты" приводятся БЕЗ доказательств. Это совершенно новое слово в научной литературе и науке вообще – это, можно сказать, неонаука! Всем, кто уважает такого рода работы, советую не терять время зря, а писать свои неонаучные статьи! Что? Вы не ученый?! НЕ БЕДА! Здесь всем найдется место – используйте слово "факт" и вы в игре! Есть одна тонкость – понижайте оценки – пожалуйста, но не переусердствуйте, не сделайте оценку достижимой для практической проверки! Подскажу начало статьи: "Факт: AES можно взломать за 2^90" – я не жадный, можете брать это и сейчас же отправлять на ePrint. В среде неоученых вы сразу станете героем!
— unknown (08/08/2013 15:34, исправлен 08/08/2013 15:39)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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



Мы живём в эпоху теоретического криптоанализа. Это было сказано (к сожалению, не помню кем), ещё лет 15 назад, если не больше.



Атаку не будут проверять, перебирая 290 вариантов. Также как признанные и давно опубликованные взломы AES и SHA-1, которые недоступны практическому брутфорсу. Достаточно даже не указывать способ взлома, а лишь алгоритм нахождения различителя от идеальной модели, с помощью которого изначально вообще ничего нельзя взломать. Если оформите это так, чтобы теоретические выкладки можно было проверить, то отправляйте на публикацию.


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

— Евгений (08/08/2013 15:59)   <#>


А что утверждения теоретического криптоанализа не нужно теперь доказывать?
— unknown (08/08/2013 16:12, исправлен 08/08/2013 16:15)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Так давно бы уже были бы приведены примеры ошибок в доказательстве или их явная неполнота. Хотя на конференцию CRYPTO его работы таки не приняли, да.


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


В чём отличие работ Куртуа, так это разве что в большой замороченности самих атак: слишком искусственные различители. А так, проверить, совпадают ли заявленные 2148, 2178, 2192, 2216 вполне должно быть возможно и несложно. В отличие от попыток придумать такие работы наугад. Вот коллизию для SHA-1 за 269 шагов тоже никто не видел, а работа китайских авторов всеми признана как доказанная.

— Гость (08/08/2013 16:13)   <#>


Естественно не будут – это пример именно того "факта", который не проверишь. Если бы было не 2^90, а 2^50, то это можно было бы легко проверить. А насчет доказательств – зачем они, вот Куртуа публикует такого рода факты БЕЗ доказательств.


Посмотрите работу Cid. An Analysis of the XSL Algorithm, 2005 года – там хорошо написано, почему предложенные Куртуа алгоритмы работают не лучше полного перебора. Как водится, Куртуа обосновывал все с помощью "фактов" без доказательств, которые оказались не более чем фикцией.

Кстати, разговор не о его работах в области анализа потоковых шифров, а о работах по ГОСТ-у
— Гость (08/08/2013 16:19)   <#>


Так ведь и доказательств Куртуа зачастую не приводит – где искать ошибки-то?
— unknown (08/08/2013 16:19, исправлен 08/08/2013 16:27)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Повторюсь,

коллизию для SHA-1 за 269 шагов тоже никто не видел, а работа китайских авторов всеми признана как доказанная

Первоначальные его наивные оценки XSL-алгоритма почти сразу были признаны неверными, это известный факт, также как и попытки анализа AES/BES совместно с другими авторами. Он указывал на возможность появления алгоритма, но не создал его, а оказалось, что неоптимизированный XSL выжирает много памяти и сам требует много шагов.

— unknown (08/08/2013 16:23, исправлен 08/08/2013 16:24)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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

— unknown (08/08/2013 16:32, исправлен 08/08/2013 16:34)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Естественно не будут – это пример именно того "факта", который не проверишь. Если бы было не 2^90, а 2^50, то это можно было бы легко проверить.

Проверяется легко без проведения самого перебора. Если опубликованы слабые раундовые характеристики, легко пересчитать, сколько шагов потребуется на полнораундовую версию атаки. Доказательства при подробном описании атаки не требуется. Опубликованная характеристика раундовой функции — это факт, который составляет основу проверки.

На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3