Сообщение о взломе блочного шифра ГОСТ 28147-89

Это не баг, а фича - иначе как же СОРМ-2 работать будет?

http://www.cryptopro.ru/forum2/Default.aspx?g=posts&t=3412

ждем когда поломают AES, он тоже не торт

алсо, http://wasm.ru/forum/viewtopic.php?pid=223523#p223523

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

WikiLeaks готовит пополнение.

По ссылке: Можно процитировать Шнайера (правда относительно AES-256, но и в данном случае будет к месту): "...описанный авторами исследования метод представляет интерес для специалистов [в данном случае, возможно представляет] , однако не несет немедленной практической угрозы, поскольку для взлома алгоритма необходимы такие вычислительные мощности, которые появятся еще очень нескоро...".

Переводя с криптографического на математический язык:

Если создать и запомнить 18 квинтиллионов различных незашифрованных текстов, каждый из них зашифровать, запомнить 18 квинтиллионов зашифрованных значений, то это ускорит взлом ГОСТа в 256 раз.

Хороший tradeoff, полезный в хозяйстве.

ЛОР как всегда.

Почитайте второе сообщение в этой теме: http://www.cryptopro.ru/forum2/Default.aspx?g=posts&t=3412

GOST взломан не больше чем AES-256. По предложенной методике требуется 2^216 времени, в то время как для AES-256 есть методики с временем 2^119. В реальности это очень большая разница.

Отличная атака! Есть блок 2^64 бит. Возьмем 2^64 блоков (все возможные) и вычислим для них шифртекст. Ура, теперь мы можем восстановить данные (мы же получили все возможные шифртексты). При чем здесь взлом?

Звучит угрожающе. Типа, наши ученые поменяют константы и все такое.

Продолжаем развлекаться с большими числами.

Представим, что открытый текст и закрытый текст размером ровно в 1 блок, т.е. в 64 бита. Тогда для применения этого взлома нам по сути нужно знать для каждого возможного значения блока результат его шифрования с помощью ГОСТа. Нееет, одно это не позволит нам сразу найти ключи, это всего лишь ускорит его нахождение в 256 раз...

Впрочем, это неважно. Намного интереснее — сколько для этого понадобится памяти.

2^64 раза по 64 бита (8 байт) на открытый текст, и ещё раз столько же на закрытый. Т.е., 2^64 раза по 16 байт. 295 эксабайт.

Кто этот Marcos el Ruptor? И почему http://www.EnRUPT.com не открывается?

Этак, 295 экзальтированных байт. Много это или мало?

По оценкам рынка, в 2010 году продали около 647 (ну, округлим, 650) миллионов жёстких дисков. Всего, в мире, всех видов.

Представим, что все эти диски — трёхтерабайтовые Hitachi Deskstar 7K3000 (а что, хорошая и дешёвая модель; если постараться, можно, допустим, за 150 долларов штука найти). 10^12 байт * 650 миллионов — получаем 650 экcабайт. Ух, здорово! Если бы все производители HDD сложились, то примерно за год, глядишь, и набралось бы места на это хранилище!

Надо не жесткие, а раму мерять. Хотя чего ее мерить, один фиг, в 256 раз быстрее брутфорса - это сильно больше времени существования вселенной.

Решето!

... правда, для этого этих производителей HDD надо мотивировать. Опять же, логистика... 650 миллионов винчестеров ещё доставить-перевезти надо...

Ладно, положим, за каждый из этих винчестеров мы бы и выложили по 150 долларов. Тогда датацентр нам бы обошёлся... как минимум в 97.5 миллиардов долларов. Фигня, на самом деле, копейки. ВВП за 2010-ый год какого-нибудь задрипанного Марокко.

Раму лень, да и дороже она. Да и надо ли много рамы? А вот жёсткие однозначно надо, и они дешёвые.

Рекомендую прочитать статью полностью, т.к. в сабже предоставлен только PoC, а не сама техника.

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

Упс. Мы забыли, что 650 миллионов винчестеров должны быть включены. Будем ориентироваться на 7 ватт в idle и порядка 10 ватт в рабочем состоянии.

6.5 гигаватт, что.

Если запитаемся от самого мощного ядерного реактора в мире (Chooz, France, 1500 MW), то рядом потребуется выстроить ещё пять таких же. Ну, ещё «4.(3) реактора».

Кстати, а не хочет кто-нибудь подсчитать, как отвести столько тепла от 650 миллионов винчестеров, и сколько промышленных кондиционеров понадобится?...

http://en.wikipedia.org/wiki/Relative_cost_of_electricity_generated_by_differ... мне подсказывает, что стоимость производства одного мегаватт-часа энергии на ядерном реакторе — около 110 евро. У нас в один час будет потребляться 6500 мегаватт. Т.е., на одну энергию для винчестеров наш Super GOST Cracking Datacenter будет расходовать 715 тысяч евро в час. 17 миллионов евро в день. 6.2 миллиарда евро (почти ровно 9 миллиардов долларов) в год. Годовой ВВП Армении или Мали.

Ладно, мне уже надоело. Если кому охота посчитать, сколько это будет в «типичных гугловых датацентрах», сколько понадобится кондиционеров, с какой частотой будут ломаться винчестеры, сколько понадобится процессоров и процессорного времени на тестовое шифрование 2^64 блоков... это уже вы сами.

Аня Чапмен смотрит на Николя, как на дерьмо.

Если бы все производители HDD сложились, то примерно за год, глядишь, и набралось бы места на это хранилище!

15 лет назад у меня был большой винчестер объёмом 540 Mb - что будет ещё через 15 лет?
пресловутый закон мура говорит, что сокращение времени перебора в 256 раз означает, что компьютер, на котором экономически выгодно будет ломать такие шифры, появится на 16 лет раньше, чем планировалось.

> Кстати, а не хочет кто-нибудь подсчитать, как отвести столько тепла от 650 миллионов

винчестеров, и сколько промышленных кондиционеров понадобится?...

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

> пресловутый закон мура говорит,

Прочитайте закон Мура, что ли.

> А, теперь, вспомним, что каких-то 20 лет назад даже на взлом DES требовалось небозримое время

Таки нет, существовал проект спец-вычислителя для его взлома аж 1977 года. В теории он бы сработал, если бы его построили (а ктро знает чем там NSA занималась...)

Зачем кондиционеры? Построим в Сибири, тайга большая :)

> 15 лет назад у меня был большой винчестер объёмом 540 Mb - что будет ещё через 15 лет?

Да, я знаю, что если по уму, то надо брать интеграл.

Только смысл его брать, если вторая производная уже давно отрицательная?

Время для торжества еще не пришло :)
На всякий эксабайт найдется свой хитрый кубит (tm) компании D-Wave :)

Ну-ну.

Блин, я ТС щас придушу собственными руками! Я чуть не поседел, когда увидел заголовок. Дрожащими руками открыл... а тут... фигня, в общем. Значит так, конкретнее:

Практический результат пока скромен: 2^64 известных открытых текста и 2^64 памяти для хранения пар «открытый текст/шифртекст» позволяют взломать ГОСТ в 2^8 быстрее, чем простой перебор.

Да уж, действительно скромно - предыдущие атаки ускоряли в большее число раз. Для справки: создатели ГОСТ 28147 и не рассчитывали, что вскрытие их детища будет иметь сложность 2^256, Просто такой ключ удобен.

Но в плане криптоанализа это делает полностью справедливым утверждение о том, что «ГОСТ взломан»

4.2. с требованием поправить заголовок. В плане криптоанализа это означает, что это успешная атака на ГОСТ 28147. А «взломан» - это совсем другое, это когда можно сказать что сейчас или в ближайшем будущем успешный влом будет возможен на практике. Для примера: для ГОСТ 28147 была приведена масса различных успешных атак, куда более успешных, чем данная но его «взломаным» не объявляли. На ДЕС не существует ни одной успешной атаки, но он «взломан» и к применению больше не рекомендуется.

очень много работ по атакам на слабые ключи в ГОСТ 28147-89, атакам со связанными ключами, на восстановление секретных S-блоков

Секретные S-блоки? Люди, вы о чем? Их засекречивают только ССЗБ, ибо беспрофитно, в то же время можно нарваться на неудачные блоки. Давно пора в стандарте их зафиксировать, как в ДЕС-е.

Подитожим: Если на основе данной статьи (ничего против нее не имею) утверждать, что ГОСТ28147 взломан, то в таком случае коллизии MD5 на счетах за 5 минут находятся. Короче, развели шум на ровном месте.

Новость предлагаю удалить. Хоть сам я и криптолог, но ЛОР - не криптофак.

Если вместо памяти взять HDD, то оно будет высчитываться до пришествия следующего поколения динозавров, мягко говоря.

То есть на AES никто переходить не будет?

А вообще попахивает грязным пиаром чтобы ISO не стандартизировало рюске

Секретные S-блоки? Люди, вы о чем? Их засекречивают только ССЗБ, ибо беспрофитно, в то же время можно нарваться на неудачные блоки. Давно пора в стандарте их зафиксировать, как в ДЕС-е.

А разве требования к блокам S и алгоритм их выбора известен? Я не криптолог, но помню что было только известно о том какие таблицы откровенно плохи. О том какие именно таблицы хороши вроде как никто не знает (ну из смертных я имею ввиду). Не?

По предложенной методике требуется 2^216 времени, в то время как для AES-256 есть методики с временем 2^119. В реальности это очень большая разница.

В реальности разница может и большая, а на практике никакой.

> То есть на AES никто переходить не будет?

Зачем? ГОСТ выигрывает в быстродействии при соответствующей стойкости.

А вообще попахивает грязным пиаром чтобы ISO не стандартизировало рюске

ISO и без этого не собиралось его стандартизировать. У нас в СНГ этот стандарт только приводят в нормальный вид. А если и собиралась, то никакий пиар их не остановит - там сидят ученые, а не быдло. То, что время от времени выдодят такие публикации - это совсем не черный пиар. Наоборот, это означает, что шифром занимаются аналитики, не только местные. И за 20 лет такого анализа он еще не дискредитирован. А вот AES еще зеленый (малоизученый), следовательно, внушает поменьше доверия.

> А разве требования к блокам S и алгоритм их выбора известен?

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

О том какие именно таблицы хороши вроде как никто не знает (ну из смертных я имею ввиду). Не?

Во-первых, никто не запрещает использовать блоки, указанные в ГОСТ Р 34.11-94 (там используется преобрахование по ГОСТ 28147). Во-вторых, сейчас эти блоки собираются стандартизировать. В третьих, я на днях видел 6 наборов s-блоков (пришли в Украину из России как предложение ввести их в международный стандарт СНГ), и, кажется, они даже не секретны.

> 715 тысяч евро в час

А где это в Европе ток такой дешевый (0.11 Евро)?

Для справки: в Германии уже вырос до 0.22 ... 0.25

> Зачем? ГОСТ выигрывает в быстродействии при соответствующей стойкости.

Так вот почему в процы стало модно включать команды для AES.

Возьмём человека, зашифровавшего сообщение с помощью 4048-битного RSA, и скальпель. С помощью скальпеля получаем ключ. Ура! RSA с 4048-битным ключом взломан! Статью писать?

Конечно! Про секреты памяти. Заставить запомнить 4096-битный ключ это нефигово так

Зачем 4096-битный... всего лишь 4048-битный!

Только Blowfish остальное от диавола

только серпент кошерен однако!

> Так вот почему в процы стало модно включать команды для AES.

В процы включают команды для AES для оптимизации исполнения популярного сегодня шифра. Точно так же, как в свое время в проц запихивали линейный рекуррентный сдвиговый регистр.

Ваш К.О.

Кстати, команды, специализированные под ГОСТ 28147 в проц включать не нужно - они уже давным-давно включены.

> только серпент кошерен однако!

Чем он лучше AES? Конструктивный ответ можете дать?

> Только Blowfish остальное от диавола

Да ну... а ничего, что половина идей Blowfish была почерпана как раз из ГОСТ 28147. Причем, Авторы ставили себе как цель быстродействие алгоритма. Как следствие, мы получаем, что лавинные эффекты у Blowfish хуже.

И теперь покажи мне нормальную консольную утилиту как bcrypt для его использования.

Заставить запомнить
Ну я же не писал, что из памяти узнаём.

4096-битный... всего лишь 4048-битный
Тьфу, точно, 4096.

Легко! Берешь исходники bcrypt, заменяешь blowfish на ГОСТ 28147, profit!!! Если надо, могу отсыпать исходников самого шифра, я его раз десять писал для разных нужд.

Нашел проблему... решаемую за 5-10 минут на ноуте на коленках. И уж тем более, это не аргумент в пользу какого-либо шифра.