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
Может ли Куртуа повлиять на принятие ГОСТа в стандарт ISO? Там чисто политическое решение или оно обязано опираться на рекомендации научного комитета, который внимательно следит за работами по криптоанализу ГОСТ?
комментариев: 9796 документов: 488 редакций: 5664
Там, где голосование происходит по странам, политики не избежать. Да и стандарты в данном случае там не разрабатываются с нуля, а проталкиваются больше готовые, в чём уже есть экономический интерес. Мнение экспертов конечно учитывается, но это скорее не такое мероприятие, где созданы идеальные условия для решения проблем научным сообществом.
Результаты этой работы были также подтверждены группой Динура-Шамира на FSE-2012.
Теперь Н.Куртуа считает и пытается обосновать, что для S-блоков такого размера, с такой раундовой функцией, это мало что даст.
Если как-то пофиксить ключевое расписание, то возможно часть атак на восстановления ключа превратится в более абстрактные различители, но не исчезнет совсем. Сложно оценить, насколько приемлемая картина в итоге получится.
К слову: а когда оно будет окончательно принято? Или уже?
комментариев: 9796 документов: 488 редакций: 5664
Хитрость не в этом: сейчас часто показывают результат, который можно проверить теоретически, не прибегая к практическим вычислениям по полному взлому и не показывают методику как он получен. Атаку проверяют на теоретических выкладках: на примере таких-то дифференциалов, которых не должно быть в идеальной модели и пр.
Мы живём в эпоху теоретического криптоанализа. Это было сказано (к сожалению, не помню кем), ещё лет 15 назад, если не больше.
Атаку не будут проверять, перебирая 290 вариантов. Также как признанные и давно опубликованные взломы AES и SHA-1, которые недоступны практическому брутфорсу. Достаточно даже не указывать способ взлома, а лишь алгоритм нахождения различителя от идеальной модели, с помощью которого изначально вообще ничего нельзя взломать. Если оформите это так, чтобы теоретические выкладки можно было проверить, то отправляйте на публикацию.
Куртуа часто заносит на шумном самопиаре, но его исследования подтверждены независимо, в т.ч. группой Шамира. Он первооткрыватель многих направлений в алгебраическом криптоанализе и его методы неоднократно подтвердили свою работоспособность, вплоть до практических атак на слабые шифры. На основе работ Куртуа группа Динура-Шамира создала кубический криптоанализ, который теперь стандартно используется при оценке стойкости потоковых шифров.
А что утверждения теоретического криптоанализа не нужно теперь доказывать?
комментариев: 9796 документов: 488 редакций: 5664
Так давно бы уже были бы приведены примеры ошибок в доказательстве или их явная неполнота. Хотя на конференцию CRYPTO его работы таки не приняли, да.
Я вот не вижу, чем его работа отличается от аналогичных работ в этой же области. Во вполне уважаемых работах с доказательствами может быть ещё хуже: просто табличка с дифференциалами, по которой можно посчитать, что при такой-то атаке будет прохождение через столько-то раундов быстрее, чем брутфорс или чем должно быть по теории.
В чём отличие работ Куртуа, так это разве что в большой замороченности самих атак: слишком искусственные различители. А так, проверить, совпадают ли заявленные 2148, 2178, 2192, 2216 вполне должно быть возможно и несложно. В отличие от попыток придумать такие работы наугад. Вот коллизию для SHA-1 за 269 шагов тоже никто не видел, а работа китайских авторов всеми признана как доказанная.
Естественно не будут – это пример именно того "факта", который не проверишь. Если бы было не 2^90, а 2^50, то это можно было бы легко проверить. А насчет доказательств – зачем они, вот Куртуа публикует такого рода факты БЕЗ доказательств.
Посмотрите работу Cid. An Analysis of the XSL Algorithm, 2005 года – там хорошо написано, почему предложенные Куртуа алгоритмы работают не лучше полного перебора. Как водится, Куртуа обосновывал все с помощью "фактов" без доказательств, которые оказались не более чем фикцией.
Кстати, разговор не о его работах в области анализа потоковых шифров, а о работах по ГОСТ-у
Так ведь и доказательств Куртуа зачастую не приводит – где искать ошибки-то?
комментариев: 9796 документов: 488 редакций: 5664
Повторюсь,
Первоначальные его наивные оценки XSL-алгоритма почти сразу были признаны неверными, это известный факт, также как и попытки анализа AES/BES совместно с другими авторами. Он указывал на возможность появления алгоритма, но не создал его, а оказалось, что неоптимизированный XSL выжирает много памяти и сам требует много шагов.
комментариев: 9796 документов: 488 редакций: 5664
Так всё правильно, сам анализ скрыт. Выданы готовые для проверки результаты. Правильно всё названо: Fact. Такой-то конкретный из его работы дифференциал подставляете и видите, что он проходит через раунды так, как заявляет автор и по его работе делаете пересчёт на число шагов. То, что он нашёл этот дифференциал и есть доказательство, но уже в виде факта. Но он скрывает методику, как к сожалению часто делают многие криптографы.
комментариев: 9796 документов: 488 редакций: 5664
Проверяется легко без проведения самого перебора. Если опубликованы слабые раундовые характеристики, легко пересчитать, сколько шагов потребуется на полнораундовую версию атаки. Доказательства при подробном описании атаки не требуется. Опубликованная характеристика раундовой функции — это факт, который составляет основу проверки.