id: Гость   вход   регистрация
текущее время 14:51 28/03/2024
Владелец: unknown (создано 14/06/2011 11:21), редакция от 16/06/2011 00:01 (автор: unknown) Печать
Категории: криптография, алгоритмы, симметричное шифрование
http://www.pgpru.com/Новости/2011/ПоказанПервыйКонцептуальныйВзломГОСТ28147-89ПутёмДифференциальногоКриптоанализа
создать
просмотр
редакции
ссылки

14.06 // Показан первый концептуальный взлом ГОСТ 28147-89 путём дифференциального криптоанализа


Исследователи Николя Куртуа (Университетский Колледж Лондона, кафедра компьютерных наук) и Мичал Мижтал (Военный Университет Технологий, Варшава) опубликовали новую атаку на российский стандарт блочного шифрования — ГОСТ 28147-89. Также как и предыдущие работы по взлому полнораундовой версии ГОСТ, атака не имеет практического значения, но показывает некоторые очевидные, по мнению авторов, вещи:


  • ГОСТ не удовлетворяет требованиям стойкого шифра с точки зрения современного сертификационного криптоанализа.
  • Десятилетиями поддерживаемое ведущими криптографами мнение о стойкости ГОСТа к диффереренциальному криптоанализу оказалось ошибочным.

Интересно, что дифференциальный криптоанализ — один из базовых видов криптоанализа, который показывает нестойкость шифра. Если шифр нестоек к такому виду атаки, следует ожидать и наличие атак другого рода. Следует однако отметить, что своё вызывающее на первый взгляд открытие авторы сделали на основе достаточно усложнённой версии дифференциального криптоанализа — с множественными дифференциалами. Это и позволило достичь контраста с принятыми ранее доказательствами стойкости ГОСТа к дифференциальному криптоанализу после всего нескольких раундов.


Лучшая из опубликованных в данной работе атак состоит из одиннадцати пунктов и включает в себя такие абсолютно непрактичные трюки, как угадывание 160 бит ключа из 256 и наличие 264 известных открытых текстов (это все возможные варианты открытых текстов в пределах блока). Стойкость ГОСТа снижается с 2256 до 2228 — именно столько шагов в сумме требует атака для нахождения ключа с вероятностью 50%. В отличие от ранее опубликованных алгебраических атак, которые требуют 2225 шагов, в данной атаке затраты памяти сокращены с 2128 до 264.


Противнику в сценарии таких атак необходимы не только недостижимые вычислительные ресурсы, но и невыполнимые (и в практическом смысле абсурдные) требования, которые он должен получить по доступу к нужным объёмам информации с атакуемой системы. Однако, с теоретической точки зрения, если работа достоверна, можно сказать, что полнораундовый шифр ГОСТ впервые взломан дифференциальным криптоанализом. Чтобы привлечь внимание специалистов на фоне попыток стандартизации ГОСТ в международном стандарте ISO 18033, авторы особо подчёркивают что шифр ГОСТ помимо уже известных рефлективных атак, атак с "двойным отражением" и ряда специфических атак, нестоек даже к ДК.


Данная атака является лишь доказательством концепции, однако может быть интересна теоретикам тем, что в отличие от изучения более сложного класса алгебраических атак, опубликованные константы дифференциалов проверить проще. Авторы обещают опубликовать серию новых атак на шифр ГОСТ в ближайшем будущем, включая и улучшенные версии дифференциальных атак.


Источник: Cryptology ePrint Archive
См. также:
Сообщения о взломе блочного шифра ГОСТ 28147-89 в разгар усилий по его международной стандартизации
Первая атака на функцию хэширования ГOСТ-Р 34.11-94, Рефлективные атаки понижают стойкость шифра ГОСТ


 
На страницу: 1, 2 След.
Комментарии [скрыть комментарии/форму]
— Гость (15/06/2011 16:39)   <#>
угадывание 160 бит ключа из 256

почему не все 256?
— unknown (15/06/2011 17:49, исправлен 15/06/2011 17:53)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Ну, такой банальный брутфорс неинтересен, там в работе более тонкие извращения :-) Что там с бедным ГОСТом делают, даже описывать неловко:


  1. Узнают 264 известных открытых текстов (вежливо просят атакуемого проделать значительную часть атаки — зашифровать все возможные тексты в пределах блока и предоставить их противнику).
  2. Угадывают части ключа k0, k1, k2, k3, k4 — те самые 160 бит.
  3. Для каждых угаданных 160 битов k0, k1, k2, k3, k4 и для каждых 264 пар открытый текст/шифртекст (32-раундовых) вычисляют 5 раундов сверху и пять снизу (в обратном направлении). Так получают 264 пар открытый/шифртекст отдельно для внутренних 22 раундов, потратив на это 2160 · 264 · 10/32 ГОСТ-шифрований (т.е. 2223.3 ГОСТ-шифрований и 264 памяти).
  4. Используя знание разниц (дифференциалов) для средних раундов (0x80000000, 0x00000000), оказывается несложно предположить, что раундом раньше разница окажется (0x80000000, 0x00000780) с большой вероятностью.
  5. Теперь разложив ГОСТ в виде 5+1+20+1+5 раундов получаем из разницы (0x80000000, 0x00000780) раундом дальше (0xFFFF8007, 0x00000780)
  6. Теперь можно отфильтровывать хорошие пары для раундов.
  7. ..11

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


Ещё они по предыдущим работам грозят "парадигмой редукции алгебраической сложности" — те атаки, которые ещё пять лет назад считались невозможными, теперь можно проводить, доламывая последние раунды шифра алгебраическими методами криптоанализа.


Практически ГОСТ не взломан, но множественные теоретические взломы показаны, направление для улучшения атак намечено, солидная теоретическая база тоже как бы подведена.


Странно, что для AES, для которого также есть по крайней мере взлом в модели атак со связанными ключами, никому не приходит в голову продлить другие существующие атаки на пару раундов, чтобы доломать его хотя бы в таких особо извращённых формах. Хотя нет, первый взлом AES был круче: "модель открытого ключа" — противнику известны и открытые тексты и шифртексты и ключ, даже не просто известны, а подбирая ключи, доказывалось неслучайное соответствие между открытыми текстами и шифртекстами. Всего лишь различитель — а уже взлом. Который правда удалось улучшить для простых атак со связанными ключами, но почему-то дело дальше не пошло.


Для ГОСТа уровень атак несколько серьёзнее, но пойдёт дело дальше или нет — неясно. Для снятия RIJNDAEL с конкурса в 2000 году атаки со связанными ключами могло бы и хватить: она прямо противоречила критериям стойкости, задекларированным разработчиками ("Rijndael is K-secure"). Но сейчас из-за такой мелочи от AES отказываться никто не будет. А вот от ГОСТа в международном стандарте могут и отказаться, раз атака стала известна до его принятия. Поэтому ГОСТоломы так и спешат и работы у них несколько сумбурные.

— Гость (15/06/2011 20:17)   <#>
Так капец наступит? И если да, то когда?

Какая сравнительная стойкость и ресурсоемкость ГОСТ и AES?
— unknown (15/06/2011 21:37)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Такие сериалы могут годами длиться.
По поводу ресурсоёмкости AES выигрывает почти по всем параметрам, в некоторых случаях значительно (8-битные микроконтроллеры, распараллеливание), в большинстве других случаев преимущество AES незначительно, в некоторых ГОСТ — чемпион (наименьшее число логических элементов при исполнении в специализированном железе).

По поводу сравнительной стойкости.

Что известно сейчас. На AES есть атаки на связанных ключах, на ГОСТ они также были известны и давно. Связанные ключи практически ни в каких протоколах сейчас не используются, но слабость ключевого расписания может облегчать другие атаки. Итак, атаки со связанными ключами ничего не дают в плане практической стойкости. Скрепя зубами ими даже можно пренебречь. Что и пришлось сделать для AES, несмотря на отдельные попытки укрепления его ключевого расписания и робких намёков по исправлению стандарта в этой части.

Атаки на ГОСТ, требующие знания всей кодовой таблицы не просто недостижимы по гигантским вычислительным ресурсам, но и требуют фактически того, чтобы атакуемый сам сознательно предоставил атакующему огромную часть этих ресурсов (сгенерировал и как-то передал 264 пар открытых/шифртекстов), т.е. действительно специально помогал ломать свой ключ, потратив на это огромные вычислительные ресурсы. Это всё возможно только в мысленном эксперименте.

Так что и AES и ГОСТ — пока оба стойкие в практическом плане шифры.

Но с точки зрения сертификационного криптоанализа уязвимы оба. И теоретикам есть над чем подумать. Причём можно только прогнозировать, что часть (большинство ?) скорее всего не примет атаки на ГОСТ или AES как серьёзные аргументы для сравнения, но часть посчитает аргументы против ГОСТ более весомыми. Николя Куртуа (давний скептик по поводу AES) считает, что ГОСТ уже сейчас и в перспективе слабее по запасу прочности, чем AES и 3DES (в пересчёте на размер ключа/блока). О подтверждении работ Н. Куртуа другими независимыми исследователями известно мало, но те же рефлективные атаки турецкого исследователя в 2007 году также как-то прошли незамеченными, а фактически они предвосхищают события 2011 года и показывают схожие результаты. Вот только тогда ГОСТ вероятно ещё не был кандидатом на международную сертификацию (не особо кстати и важную, но тем не менее) и был мало кому интересен.

Тема ГОСТа всплывала у нас в обсуждениях ещё в 2005 году с весьма похожими прогнозами на то, что мы имеем сейчас по данным Куртуа. Вот ещё "о зловещей роли" КГБ/ФСБ.

В общем, гадать о будущем неблагодарно, но ГОСТ простой, понятный (кроме S-блоков), достаточно хорошо спроектированный шифр и если "капец" и будет, то долгий и мучительный. Но интересный. Причём, наиболее вероятно отсутствие практических взломов и принятие нового стандарта.
— unknown (15/06/2011 22:50, исправлен 16/06/2011 00:00)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Кстати, "парадигма редукции алгебраической сложности" по смыслу больше походит на "парадигма алгебраической редукции сложности" — "Algebraic Complexity Reduction", следует этот термин понимать скорее так. Поправил даже предыдущую новость. Интересное направление в применении алгебраического криптоанализа.
P.S. Это просто праздник какой-то (с точки зрения такого всплеска внимания к ГОСТу):

# Nicolas Courtois: Security Evaluation of GOST 28147-89 In View Of International Standardisation. Report officially submitted to the International Standards Organisation (ISO). Also available at eprint.iacr.org/2011/211/.
# Nicolas Courtois: Algebraic Complexity Reduction and Cryptanalysis of GOST. Preprint.
# Nicolas Courtois, Michal Misztal: Differential Cryptanalysis of GOST. At eprint.iacr.org/2011/312/.
# Nicolas Courtois, Michal Misztal: Aggregated Differentials and Cryptanalysis of PP-1 and GOST. in 11th Central European Conference on Cryptology, will be held in Debrecen, Hungary, on June 30 – July 2, 2011.
# Nicolas Courtois, Theodosis Mourouzis: Black-Box Collision Attacks on the Compression Function of the GOST Hash Function Accepted as SHORT paper at the 6th International Conference on Security and Cryptography SECRYPT 2011, 18-21 July, Seville, Spain.

— Гость (16/06/2011 04:53)   <#>
требуют фактически того, чтобы атакуемый сам сознательно предоставил атакующему огромную часть этих ресурсов (сгенерировал и как-то передал 264 пар открытых/шифртекстов), т.е. действительно специально помогал ломать свой ключ

Допустим, в руках противника оказался двухтерабайтный диск, зашифрованный ГОСТом, и точно такой же незашифрованный — ситуация, которая вполне может случиться на практике. Сколько там пар открытых/шифрованных текстов?

Кстати, наверняка вся советская криптография сколько-то лет назад была закрытой. Как давно её открыли и даже выпустили публично известный стандарт под именем "ГОСТ"?
— unknown (16/06/2011 09:38, исправлен 16/06/2011 10:03)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

2 TB = 2 · 8 · 240 = 244 бит. Маловато. Надо минимум 1048576 пар таких винчестеров, чтобы просто дотянуть до 264 бит. Или всего ( 2 · 26 · 264) / 244 = 134217728 винчестеров для размещения всех пар открытый/шифртекст. При этом все блоки открытого текста должны быть на них специально сгенерированы неповторяющимися от {00...0} до {11...1} и было естественно ясно, где какой блок лежит, что при использовавнии обычных режимов шифрования (с рэндомизацией и сцеплением) нереалистично.


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


В предыдущей новости подробнее указано. С 1989 он ДСП, с 1994 полностью рассекречен и опубликован.

— Гость (16/06/2011 10:19)   <#>
гипотетическая передача противнику всех возможных вариантов пар "открытый/шифртекст", специально сгенерированных для него на одном ключе
Допустим, с кем-то ведётся переписка и все сообщения шифруют одним ключом. Конечно, для современных IM и прочих систем это малореалистично, хотя в OTR до конца не уверен.
— unknown (16/06/2011 10:52, исправлен 16/06/2011 10:58)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Отправляя каждый раз мегабайт неповторяющихся открытых текстов в секунду на одном ключе, без смены векторов инициализации (а это не ключ — это случайное число в начале сообщения, которое не нужно согласовывать, поэтому его использование не стоит в большинстве случаев никаких ресурсов и обязательно применяется) на такую "переписку" уйдёт (( 27 ) · ( 264 )/(2 20 ))/ (3600 · 24 · 365) = 71404103 лет. При этом нужно ни разу не повторить ни одного блока.


Не забудьте ещё сохранить свою переписку для противника, а то как он получит эти открытые тексты?


Это нормальное исследование только с точки зрения теории, где в самом надуманном и неправдоподобном сценарии достаточно доказать, что число шагов взлома быстрее, чем простой перебор — значит шифр неидеален.

— Гость (16/06/2011 11:11)   <#>
в самом надуманном и неправдоподобном сценарии достаточно доказать, что число шагов взлома быстрее, чем простой перебор
Ага, проходили, знаем. Потом ещё одна такая новость — и бац, уже 100 лет, а не 100 миллионов лет :)

поэтому его использование не стоит в большинстве случаев никаких ресурсов и обязательно применяется
Надеюсь, что да, но для этого шифрование должно постоянно есть энтропию, и насколько тут всё корректно и хорошо в протоколах реализовано — без понятия. Вот как часто новые ключи загоняются в SSL-сессию?
— unknown (16/06/2011 12:14)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Потом ещё одна такая новость — и бац, уже 100 лет, а не 100 миллионов лет :)

Атаки становятся только сильнее © Шнайер :)
Вот как часто новые ключи загоняются в SSL-сессию?

В пределах одной сессии рекеинг обычно не производится, если приложение не закрывает сеанс. В конфигах SSL-VPN его можно выставлять вручную — чаще всего каждый час.
— Гость (16/06/2011 14:27)   <#>
Атаки становятся только сильнее © Шнайер :)
Шифры — тоже :)
— Doker (16/06/2011 17:52)   <#>
Это просто PR с целью давления на комитет по стандартизации.
— Гость (19/06/2011 14:48)   <#>
И еще добавьте то, что ГОСТ – Советский криптоалгоритм. Поэтому он будет подвергаться гораздо более сильным нападкам. То, что я вижу сейчас, а именно, абсолютно неприменимые на практике атаки, это подтверждает. Когда и они закончатся, начнется "политика", софистика и брызганье слюнями.
— Гость (19/06/2011 16:16)   <#>
а именно, абсолютно неприменимые на практике атаки

man сертификационный криптоанализ, и, о ужас, аналогично оцениваются и американские шифры.
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3