Алгоритмы ГОСТ в стандарте OpenPGP

Если уж смотреть на сам AES-RIJNDAEL с точки зрения сертификационного криптоанализа, он был самым слабым из пяти самых сильных финалистов конкурса AES.

Тогда почему он выиграл конкурс?

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

Роналд Райвест ("R" в аббревиатуре RSA) как-то сказал, что сделать стойкий шифр несложно — введите простую функцию смешивания и рассеивания и обработайте ею текст много-много раз. Что действительно сложно — это сделать шифр, который будет стоек, неприхотлив и быстр.

Роналд Райвест ("R" в аббревиатуре RSA) как-то сказал, что сделать стойкий шифр несложно — введите простую функцию смешивания и рассеивания и обработайте ею текст много-много раз.

... У Шнайера и Райвеста был заочный спор на эту тему. Райвест утверждал, что шифр должен быть максимально простым (RC4, RC5, RC6).
Шнайер утверждал, что простые шифры "ждут меткого удара молотком" – как только появится серьезная атака, она сразу "проломит" много раундов шифра, в то время как умеренно сложные шифры сдаются постепенно, раунд за раундом, давая запас времени на замену стандарта.

Идея простого шифра исследовалась. Почему бы не взять очень простую и быструю функцию шифрования и повторить ее очень много раундов? Так был создан шифр TREYFER. Вот он почти целиком (без описания случайных S-блоков):

!!(blue) for(r=0; r < NumRounds; r++) {
text[0] = text[8];
}
!!

Но оказалось, что такие шифры уязвимы к другим типам атак (кроме традиционных DCA или LCA). В целом, идея доведения простоты до абсурда, провалилась.

Простых и достаточно стойких шифров – единицы. Шифры Райвеста (и кстати ГОСТ) – из их числа.
Но взять простую функцию шифрования и много раз ее повторить (как в ГОСТ) – это не даст гарантии получения стойкого шифра.

Думаю, Райвест сказал эту фразу с долей иронии, намекая на свои непревзойденные способности к созданию простых и одновременно стойких шифров.
В целом он конечно прав (и было бы просто глупо пытаться с ним спорить), но и не следует понимать его слова слишком буквально. По крайней мере среди криптографов есть и те, кто не совсем разделяет его взгляды.

Что действительно сложно — это сделать шифр, который будет стоек, неприхотлив и быстр.

Вот с этой частью высказывания могут согласиться все криптографы.

В целом он конечно прав (и было бы просто глупо пытаться с ним спорить), но и не следует понимать его слова слишком буквально.

Думаю, никто буквально понимать и не станет. Это иносказание, цель которой — дать понять, что по-настоящему хороший алгоритм не может быть написан "на коленке". Простота должна быть оправдана. Простота Rijdael, GOST, Rivest Ciphers — это одно: она облегчает анализ, упрощает поиск скрытых за формальной сложностью дефектов и уязвимостей алгоритма (тот же Twofish Шнайера не прошёл финал AES в том числе и из-за некоторой громоздкости). Но это не простота функции линейного смещения с подстановкой, повторённая сотню раз.

В ГОСТ-Р34.10-94 и ГОСТ-Р34.10-2001 описаны стандарты ЭЦП, в которых применяется хеш ГОСТ-Р34.11-94. Последний достаточно обоснованно раскритикован, но в принципе любой 256-битный хеш может его заменить.
Что известно о стойкости самих алгоритмов преобразования с ассимметричным ключем, кромя уже цитированной статьи (которая не плохо о нем говорит)?
В отличии от DSA и ECDSA, оба алгоритма ГОСТ-34.10 достаточно легко применимы в схемах <<слепой>> подписи, что в будущем может быть немаловажно. Например для анонимного электронного голосования, что несомненно представляет государственный интерес.

Что известно о стойкости самих алгоритмов преобразования с ассимметричным ключем, кромя уже цитированной статьи (которая не плохо о нем говорит)

Были описаны некие схемы "мошенничества" с ГОСТ-2001-подписью. Для этого будто-бы можно сгенерировать "слабую" подпись, а затем в удобный момент отказаться от всех контрактов которые ею подписаны (или показать их недействительность). За рубежом исследований по ГОСТу мало поэтому широкого обсуждения этой темы мне не попадалось.
Аналогичные слабые стороны были обнаружены и в некоторых американских схемах подписей на эллиптических кривых.

Последний достаточно обоснованно раскритикован, но в принципе любой 256-битный хеш может его заменить.

Не может, иначе это уже будет не ГОСТ-Р34.10-2001. По DSS в последние дни много дискуссий, чем заменить в нём SHA-1, так это дискуссии того же рода. Тут выбор такой: или следуем стандартам, или не следуем. Это даже не вопрос выбора параметров алгоритма (понятно, что с DSA может и RIMEMD-160 работать), это именно последовательность в реализации стандарта.

Были описаны некие схемы "мошенничества" с ГОСТ-2001-подписью.

Komlin и некоторые из авторов стандарта занимались этим предметом. Математические выкладки были хороши, но предложенные методы атаки исходили из таких допущений, что вероятность их реального применения очень мала. Работы эти можно найти в библиотеке на bugtraq.ru, а в тамошнем форуме — критику.

SATtva:

Последний достаточно обоснованно раскритикован, но в принципе любой 256-битный хеш может его заменить.

Не может, иначе это уже будет не ГОСТ-Р34.10-2001.

У меня задача иная. Мне нужен алгоритм ЭЦП, который с одной стороны достаточно распостронен и изучен (то есть теоретически заслуживает доверие и существуют многократно проверенные реализации), а с другой стороны легко и удобно применим для <<слепых>> подписей.
Соответствие каким-либо стандартам в задачу не входит.
Также, мне кажется, что хеш-функция ГОСТ-Р34.11-94 должна быть рано или поздно заменена на что-то более стойкое (как и SHA1, впрочем), и в этом случае можно будет включить соответствие Российским стандартам в список требований.
Короче, я убежден, что анализ ассимметричных алгоритмов ГОСТ-Р34.10-94 и ГОСТ-Р34.10-2001 отдельно от хеш-функции вполне оправдан и отбрасывать их на основе слабости хеш-функции — недальновидно.
Я бы не удивился, если новая редакция ГОСТ-Р34.10-x оставила бы ассимметричные алгоритмы неизменными при замене хеш-функции. Но еще раз повторяю, что соответствие каким-либо стандартам в мою задачу на данный момент не входит.

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

Стандарты от нас не зависят, нам их как заповеди Господни с небес спускают ответственные органы. А то, что менять будут, так это наверняка (весь вопрос во времени). Тот же NIST, например, давно выпустил рекомендацию по использованию в DSS хэшей SHA-2, которая сводится к использованию в ЭЦП 160 левых битов выхода хэш-алгоритма. Интересно... Знает ли кто-нибудь, как это сказывается на безопасности? Иными словами, как результат лавинного эффекта распределяется по битам хэш-значения? Не будут ли какие-то биты "менее зависимы" от прообраза, чем другие?

Иными словами, как результат лавинного эффекта распределяется по

битам хэш-значения? Не будут ли какие-то биты "менее зависимы" от прообраза, чем
другие?

Да, этот вопрос исследовался и достаточно
давно. Впрочем дискуссия время от времени возникает
и сейчас. Вопрос ставится так – если из длинного
хэш-значения надо получить короткое, то что лучше: простое
отбрасывание или объединение лишних битов
при помощи XOR?

Решили, что простое отбрасывание лучше – если у функции
неравномерные биты, она все равно дефектная.
А при отбрасывании битов у взломщика меньше информации для криптоанализа.

На самом деле это до сих пор предмет тонкого теоретического спора, но большинство вроде за "отбрасывание", а не за "XOR-объединение".
Даже в старых стандартах NIST рекомендуется именно такой способ.

unknown:
В ГОСТЕ очень примитивная функция раунда – в качестве нелинейной операции используется единственный циклический сдвиг. Стопроцентно можно сказать, что это снижает лавинный эффект, по сравнению с расширениями и перестановками DES, потенциально это облегчает различные виды атак.

Размер S-блоков мал, критерии их создания не опубликованы, сами значения S-блоков не определены в стандарте.

У меня очень серьезные основания считать, что это не случайно, и что не по глупости. Я почти уверен, что преобразование ГОСТ 28147-89 не совсем то, чем оно на первый взгляд кажется. Если кого-то интересуют подробности — пожалуйста обращайтесь по адресу 0xA91FAE60D3BE8209.

Я пока не готов к публичным обсуждениям (еще почти ничего не доказано, но знаю где начать), но с удовольствием расскажу о гипотезе в частном порядке. Может быть вместе быстрее докопаемся до истины. :)

По моему разрешен как раз DH, а к RSA не очнь хорошо относятся. По крайней мере в известных мне реализациях Gost TLS, которые прошли сертификацию используется DH.

Добрый день. Хоть тема и поугасла, но все же...
Насчет Sbox-ов: не считаю себя суперкриптоаналитиком, поэтому пользуюсь чужими словами, в работах небезызвестного Schnier'a есть анализ ГОСТ 28147-89 на шифрование, там же как раз и выложен код, который везде ходит как паблик домэйн, так вот он ни словом кажется в Applied cryptography не обмолвился про S боксы, либо я что то не так прочитал 8) тот код что был я прикрутил к проекту www.kame.net (ipv4/ipv6/ipsec) – подсистеме ip для xBSD систем и по тестам в IPSEC (AH, ESP),(хотя и я не особо силен в сишке, так что не проводил никаких оптимизаций, ГОСТ держится на уровне 3DES по скорости, хотя выроботка имитовставки по тому же госту 89-го года в качестве хэша для подписи Auth Header жутко тормозит.

извините, не заметил что тут 3 страницы, читаю и понимаю что я немного не в кассу 8))

llelik:
ГОСТ держится на уровне 3DES по скорости, хотя выроботка имитовставки по тому же госту 89-го года в качестве хэша для подписи Auth Header жутко тормозит.

Вообще-то грамотные реализации ГОСТа в разы быстрее 3DES. Элементарная оптимизация: обьединение пар 4x4 S-блоков в один 8x8. Если памятьи достаточно, то можно и больше.
Правда и так функция медленная, но всетаки значительно быстрее, чем 3DES.