Регистрация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, Рефлективные атаки понижают стойкость шифра ГОСТ
почему не все 256?
комментариев: 9796 документов: 488 редакций: 5664
Ну, такой банальный брутфорс неинтересен, там в работе более тонкие извращения :-) Что там с бедным ГОСТом делают, даже описывать неловко:
Ну и т.д., можно не пересказывать этот занятный криптоанализ, с практической точки зрения напоминающий конечно упражнения из Камасутры, стоя в гамаке. Но с теоретической точки зрения формально — быстрее чем брутфорс и с любого серьёзного конкурса такими изысканиями сшибать кандидатов можно. Авторы ещё намекают, что это лишь концепт и всего лишь черновик. Ну, посмотрим.
Ещё они по предыдущим работам грозят "парадигмой редукции алгебраической сложности" — те атаки, которые ещё пять лет назад считались невозможными, теперь можно проводить, доламывая последние раунды шифра алгебраическими методами криптоанализа.
Практически ГОСТ не взломан, но множественные теоретические взломы показаны, направление для улучшения атак намечено, солидная теоретическая база тоже как бы подведена.
Странно, что для AES, для которого также есть по крайней мере взлом в модели атак со связанными ключами, никому не приходит в голову продлить другие существующие атаки на пару раундов, чтобы доломать его хотя бы в таких особо извращённых формах. Хотя нет, первый взлом AES был круче: "модель открытого ключа" — противнику известны и открытые тексты и шифртексты и ключ, даже не просто известны, а подбирая ключи, доказывалось неслучайное соответствие между открытыми текстами и шифртекстами. Всего лишь различитель — а уже взлом. Который правда удалось улучшить для простых атак со связанными ключами, но почему-то дело дальше не пошло.
Для ГОСТа уровень атак несколько серьёзнее, но пойдёт дело дальше или нет — неясно. Для снятия RIJNDAEL с конкурса в 2000 году атаки со связанными ключами могло бы и хватить: она прямо противоречила критериям стойкости, задекларированным разработчиками ("Rijndael is K-secure"). Но сейчас из-за такой мелочи от AES отказываться никто не будет. А вот от ГОСТа в международном стандарте могут и отказаться, раз атака стала известна до его принятия. Поэтому ГОСТоломы так и спешат и работы у них несколько сумбурные.
Какая сравнительная стойкость и ресурсоемкость ГОСТ и AES?
комментариев: 9796 документов: 488 редакций: 5664
Такие сериалы могут годами длиться.
По поводу ресурсоёмкости AES выигрывает почти по всем параметрам, в некоторых случаях значительно (8-битные микроконтроллеры, распараллеливание), в большинстве других случаев преимущество AES незначительно, в некоторых ГОСТ — чемпион (наименьшее число логических элементов при исполнении в специализированном железе).
По поводу сравнительной стойкости.
Что известно сейчас. На AES есть атаки на связанных ключах, на ГОСТ они также были известны и давно. Связанные ключи практически ни в каких протоколах сейчас не используются, но слабость ключевого расписания может облегчать другие атаки. Итак, атаки со связанными ключами ничего не дают в плане практической стойкости. Скрепя зубами ими даже можно пренебречь. Что и пришлось сделать для AES, несмотря на отдельные попытки укрепления его ключевого расписания и робких намёков по исправлению стандарта в этой части.
Атаки на ГОСТ, требующие знания всей кодовой таблицы не просто недостижимы по гигантским вычислительным ресурсам, но и требуют фактически того, чтобы атакуемый сам сознательно предоставил атакующему огромную часть этих ресурсов (сгенерировал и как-то передал 264 пар открытых/шифртекстов), т.е. действительно специально помогал ломать свой ключ, потратив на это огромные вычислительные ресурсы. Это всё возможно только в мысленном эксперименте.
Так что и AES и ГОСТ — пока оба стойкие в практическом плане шифры.
Но с точки зрения сертификационного криптоанализа уязвимы оба. И теоретикам есть над чем подумать. Причём можно только прогнозировать, что часть (большинство ?) скорее всего не примет атаки на ГОСТ или AES как серьёзные аргументы для сравнения, но часть посчитает аргументы против ГОСТ более весомыми. Николя Куртуа (давний скептик по поводу AES) считает, что ГОСТ уже сейчас и в перспективе слабее по запасу прочности, чем AES и 3DES (в пересчёте на размер ключа/блока). О подтверждении работ Н. Куртуа другими независимыми исследователями известно мало, но те же рефлективные атаки турецкого исследователя в 2007 году также как-то прошли незамеченными, а фактически они предвосхищают события 2011 года и показывают схожие результаты. Вот только тогда ГОСТ вероятно ещё не был кандидатом на международную сертификацию (не особо кстати и важную, но тем не менее) и был мало кому интересен.
Тема ГОСТа всплывала у нас в обсуждениях ещё в 2005 году с весьма похожими прогнозами на то, что мы имеем сейчас по данным Куртуа. Вот ещё "о зловещей роли" КГБ/ФСБ.
В общем, гадать о будущем неблагодарно, но ГОСТ простой, понятный (кроме S-блоков), достаточно хорошо спроектированный шифр и если "капец" и будет, то долгий и мучительный. Но интересный. Причём, наиболее вероятно отсутствие практических взломов и принятие нового стандарта.
комментариев: 9796 документов: 488 редакций: 5664
Кстати, "парадигма редукции алгебраической сложности" по смыслу больше походит на "парадигма алгебраической редукции сложности" — "Algebraic Complexity Reduction", следует этот термин понимать скорее так. Поправил даже предыдущую новость. Интересное направление в применении алгебраического криптоанализа.
P.S. Это просто праздник какой-то (с точки зрения такого всплеска внимания к ГОСТу):
Допустим, в руках противника оказался двухтерабайтный диск, зашифрованный ГОСТом, и точно такой же незашифрованный — ситуация, которая вполне может случиться на практике. Сколько там пар открытых/шифрованных текстов?
Кстати, наверняка вся советская криптография сколько-то лет назад была закрытой. Как давно её открыли и даже выпустили публично известный стандарт под именем "ГОСТ"?
комментариев: 9796 документов: 488 редакций: 5664
2 TB = 2 · 8 · 240 = 244 бит. Маловато. Надо минимум 1048576 пар таких винчестеров, чтобы просто дотянуть до 264 бит. Или всего ( 2 · 26 · 264) / 244 = 134217728 винчестеров для размещения всех пар открытый/шифртекст. При этом все блоки открытого текста должны быть на них специально сгенерированы неповторяющимися от {00...0} до {11...1} и было естественно ясно, где какой блок лежит, что при использовавнии обычных режимов шифрования (с рэндомизацией и сцеплением) нереалистично.
Опять же, гипотетическая передача противнику всех возможных вариантов пар "открытый/шифртекст", специально сгенерированных для него на одном ключе, позволит ему читать любой шифртекст, зашифрованный на этом ключе, даже не восстанавливая сам этот ключ. Весь практический выигрыш был бы только в том, что ключ можно было бы вычислить один раз и больше не возиться с массивом-датацентром из винчестеров.
В предыдущей новости подробнее указано. С 1989 он ДСП, с 1994 полностью рассекречен и опубликован.
комментариев: 9796 документов: 488 редакций: 5664
Отправляя каждый раз мегабайт неповторяющихся открытых текстов в секунду на одном ключе, без смены векторов инициализации (а это не ключ — это случайное число в начале сообщения, которое не нужно согласовывать, поэтому его использование не стоит в большинстве случаев никаких ресурсов и обязательно применяется) на такую "переписку" уйдёт (( 27 ) · ( 264 )/(2 20 ))/ (3600 · 24 · 365) = 71404103 лет. При этом нужно ни разу не повторить ни одного блока.
Не забудьте ещё сохранить свою переписку для противника, а то как он получит эти открытые тексты?
Это нормальное исследование только с точки зрения теории, где в самом надуманном и неправдоподобном сценарии достаточно доказать, что число шагов взлома быстрее, чем простой перебор — значит шифр неидеален.
Надеюсь, что да, но для этого шифрование должно постоянно есть энтропию, и насколько тут всё корректно и хорошо в протоколах реализовано — без понятия. Вот как часто новые ключи загоняются в SSL-сессию?
комментариев: 9796 документов: 488 редакций: 5664
Атаки становятся только сильнее © Шнайер :)
В пределах одной сессии рекеинг обычно не производится, если приложение не закрывает сеанс. В конфигах SSL-VPN его можно выставлять вручную — чаще всего каждый час.
man сертификационный криптоанализ, и, о ужас, аналогично оцениваются и американские шифры.