LINUX.ORG.RU
 

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


0

1

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

Алгебраическая атака на полнораундовый ГОСТ более подробно представлена в статье автора

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

Необходимо отметить, что известно очень много работ по атакам на слабые ключи в ГОСТ 28147-89, атакам со связанными ключами, на восстановление секретных S-блоков. В традиционных применениях шифрования с использованием случайно выбираемых ключей до настоящего момента никаких серьёзных криптографических атак на ГОСТ 28147-89 найдено не было.

Новость на pgpru.com

>>> Подробности

ПОСАДИ КОМПЬЮТЕР НА ЦЕПЬ И ЗАСТАВЬ ЛАЯТЬ!

домашняя автоматизация: сделай сам; лучший подарок для техногика

http://www.unicontrollers.com/products/unc01x

 ← 1 2 →
[#]  
Smacker

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

** ()
[#]  
alltiptop
>>-----Цитата---->>

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

<<-----Цитата----<<

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

*** ()
[#]  

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

anonymous ()
[#]  

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

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

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

** ()
[#]  
sig_11

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

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

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

()
[#]  
rymis

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

* ()
[#]  
abraziv_whiskey

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

***** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 16:34:42  

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

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

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

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

** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:01:50  

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

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

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

** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:09:33  
redgremlin

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

***** ()
[#]  

Решето!

()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:09:33  

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

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

** ()
[#] Ответ на: комментарий от redgremlin 20.05.2011 17:12:11  

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

** ()
[#]  
gh0stwizard

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

>>-----Цитата---->>

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

<<-----Цитата----<<
***** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:17:26  

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

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

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

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

** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:29:19  

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

** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:36:52  

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

** ()
[#]  
abumbaher

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

* ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:09:33  

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

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

**** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:29:19  

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

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

***** ()
[#] Ответ на: комментарий от Anonymous 20.05.2011 17:46:15  

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

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

***** ()
[#] Ответ на: комментарий от AS 20.05.2011 18:13:01  

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

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

***** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:38:31  
Fletch

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

* ()
[#] Ответ на: комментарий от Anonymous 20.05.2011 17:46:15  

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

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

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

** ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:09:33  

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

* ()
[#]  
segfault

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

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

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

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

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

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

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

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

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

* ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:29:19  
darkshvein

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

## ()
[#] Ответ на: комментарий от segfault 20.05.2011 22:03:49  
guyvernk

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

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

()
[#] Ответ на: комментарий от segfault 20.05.2011 22:03:49  
Suntechnic

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

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

* ()
[#] Ответ на: комментарий от sig_11 20.05.2011 16:45:41  
Suntechnic

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

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

* ()
[#] Ответ на: комментарий от guyvernk 20.05.2011 23:43:19  
segfault

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

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

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

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

* ()
[#] Ответ на: комментарий от Suntechnic 21.05.2011 0:23:02  
segfault

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

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

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

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

* ()
[#] Ответ на: комментарий от Whoo 20.05.2011 17:36:52  

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

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

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

* ()
[#] Ответ на: комментарий от segfault 21.05.2011 0:31:49  

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

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

* ()
[#]  
RussianNeuroMancer

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

*** ()
[#] Ответ на: комментарий от RussianNeuroMancer 21.05.2011 4:01:19  
GblGbl

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

* ()
[#] Ответ на: комментарий от GblGbl 21.05.2011 7:15:41  
unC0Rr

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

*** ()
[#]  
anonymous_sama

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

* ()
[#] Ответ на: комментарий от anonymous_sama 21.05.2011 9:15:04  

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

anonymous ()
[#] Ответ на: комментарий от gag 21.05.2011 2:46:31  
segfault

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

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

Ваш К.О.

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

* ()
[#] Ответ на: комментарий от anonymous 21.05.2011 9:22:29  
segfault

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

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

* ()
[#] Ответ на: комментарий от anonymous_sama 21.05.2011 9:15:04  
segfault

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

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

* ()
[#] Ответ на: комментарий от segfault 21.05.2011 12:23:36  
anonymous_sama

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

* ()
[#] Ответ на: комментарий от GblGbl 21.05.2011 7:15:41  
RussianNeuroMancer

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

*** ()
[#] Ответ на: комментарий от unC0Rr 21.05.2011 9:01:54  
RussianNeuroMancer

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

*** ()
[#] Ответ на: комментарий от anonymous_sama 21.05.2011 12:34:43  
segfault

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

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

* ()
 ← 1 2 →
Безопасность