[oss-gost-crypto] "Про ГОСТовский шифр Кузнечик, его SBox и потерянные сиды"

Thu Jun 27 11:29:27 MSK 2019

Игорь, ну это же не совсем так.
Я конечно не настоящий сварщик, но для шифров показывают и семантическую
стойкость при заданных ограничениях, и сведение к NP-полным задачам.
Если бы все шифры принимались только на веру, у нас была бы куча проблем :)
В случае Кузнечика авторы много раз говорили в кулуарах, что поиск был
действительно случайным перебором с проверкой алгебраических параметров
получаемых перестановок: понятно, что в таком случае шансы наткнуться на
эту перестановку так же велики, как и на любую другую. Просто этот процесс
был выполнен один раз, довольно давно, и даже код, при помощи которого
искалось, давно утрачен. Я предлагал собственно взять какой-то из
суперкомпьютеров и запустить на нем такой же поиск еще раз чтобы показать,
что она найдется. Но это может занять много времени :))
Я согласен, что наследие "закрытой криптографии" нам мешает, но в данном
конкретном случае это уж слишком возмутительный наезд, потому что по сути
совершенно необоснованный.

On Wed, Jun 26, 2019 at 11:58 AM Igor Ustinov <igus at cryptocom.ru> wrote:

> Вартан, вот не соглашусь. Криптография - наука "гуманитарная" от начала и
> до конца, не существует ни одного научного обоснования стойкости ни одного
> шифра (ну кроме абсолютно стойкого шифра Шеннона), стойкий шифр - этот тот,
> в стойкость которого мы *верим*, и не более того, так что никаких
> аргументов, кроме "гуманитарных", в криптографии нет и быть не может. И
> поскольку стойкость - это вопрос веры, то дело не в том, закладывалась
> структура сознательно или "сама выросла", а в том, можно ли доверять "этим
> русским".
> NIST вот накушался заявлений, что наверное NSA знает что-то такое про
> структуру S-блоков DESа, и для AESа пошёл по пути полной прозрачности. И
> если вдруг сейчас в AESе нароют что-то этакое странное, они спокойно
> ответят, что бог его знает, как так вышло, но вы же все в этом участвовали,
> и крыть будет нечем. Что мешало 8 Центру пойти по этому же пути, а не
> наступать на давно известные грабли? Да ничего не мешало! Но нет, мы же
> сами с усами, нам мировые тенденции не указ, мы такие крутые, великая
> криптографическая держава, мы по старинке разработаем алгоритм силами кучки
> никому не известных (потому что жутко засекреченных) криптографов и никому
> не покажем вплоть до момента принятия в качестве государственного
> стандарта. Так что в дерьмо мы вляпались вполне закономерно, и никто, кроме
> нас самих, в этом дерьме не виноват.
> В общем, если мы хотим, чтобы наши стандарты нормально принимались
> международным сообществом, надо разрабатывать их так, как это нынче принято
> в международном сообществе. А пока мы демонстрируем, что международное
> сообщество нам не указ, мы и получаем в ответ вполне логичную реакцию.
>
> С уважением,
> Игорь Устинов
> зам.ген.директора
> ООО "Криптоком"
>
> On 26.06.2019 0:30, Wartan Hachaturow wrote:
>
> Коллегия математиков забывает тебе сказать, что все то, что
> "проделывалось" с перестановками -- было выявлено путем предъявления атаки.
> Слабых групп ключей, trapdoor'ов, черта в ступе. В данном случае нет даже
> на намека на то, что структура понижает сложность атаки, не то что не
> выявлена закладка.
> Говорю же -- гуманитарщина, никакого научного обоснования вывода "уберите
> стандарт" нет.
>
> Аргументы Перрина -- это его оценка степени простоты найденной им
> структуры.
> Даже если бы среди всех матриц перестановок была всего одна с простой
> структурой, то при абсолютно случайном поиске ты бы наткнулся на нее с той
> же вероятностью, что и на все остальные (если поиск действительно
> случайный, как говорят авторы). И требование "обосновать" появилось уже
> *после того*, как появился Кузнечик.
>
> Реально, гадать на кофейной гуще с "а вдруг эти русские что-то задумали"
> -- это "хайли-лайкли" рассуждения, подходит для хабра, но не подходит для
> серьезной дискуссии.
>
> On Tue, Jun 25, 2019 at 10:17 PM Paul Wolneykien <manowar at altlinux.org>
> wrote:
>
>> 25.06.2019 22:09, Wartan Hachaturow пишет:
>> >
>> > И да -- нет атаки, нет повода для наброса.
>>
>>   А вот знаешь, мне тут коллегия математиков подсказывает, что это
>> неправда. Что, мол, на протяжении истории шифров с s-box'ами чего только
>> не вытворяли, и чего в них только не встраивали — как бэкдоры, так и
>> защиты от атак — и что поэтому и существует в новое время требование
>> обосновать S-box.
>>
>>
>> > On Tue, Jun 25, 2019, 21:57 Paul Wolneykien <manowar at altlinux.org
>> > <mailto:manowar at altlinux.org>> wrote:
>> >
>> >     25.06.2019 20:17, Wartan Hachaturow пишет:
>> >     > Паш, вопрос того, есть там такая структура или нет -- безусловно
>> можно
>> >     > обсуждать, и он даже важен с точки зрения создания эффективных
>> >     > железных реализаций (потому что как вот это место традиционно
>> самое
>> >     > сложное для реализации примитивами). Более того, наличие таких
>> >     > структур показано для перестановок кучи шифров, и для них это
>> >     считается
>> >     > даже достоинством.
>> >     >
>> >     > Просто его не надо связывать с вопросом наличия атаки.
>> >
>> >       А я пока и не связываю. Но мне категорически не нравится, что
>> авторы
>> >     шифра заявляют "No secret structure was enforced during
>> construction of
>> >     the S-box", а потом некую структуру находят. Точнее даже не так:
>> >     заявление о структуре было сделано в 2015 году, а цитата из
>> документа,
>> >     датированного 2018 годом. Что это означает? Что найденная структура
>> не
>> >     "секретная" (было очевидно из описания, да вы не заметили) или что
>> она
>> >     не была "enforced" (само выросло)? Или же то, что это заявление было
>> >     сделано по политическим соображениям? Но тогда это заведомая
>> глупость,
>> >     раз её так быстро обнаружили.
>> >       Просто мы тут пытаемся продвигать патчи в свободные проекты, для
>> чего
>> >     волей-неволей приходится защищать позицию надёжности ГОСТов.
>> Возникает
>> >     вопрос: если известной атаки действительно нет, то для чего было
>> >     защищать позицию "нет структуры"? Может быть авторы Кузнечика хотели
>> >     скрыть не атаку, а что-то другое. Но что именно и почему?
>> >       То, что ты написал выше вполне согласуется с ответом из документа:
>> >     "Results of [1] (Biryukov, Perrin, Udovenko 2015) solved a great
>> >     optimization problem". Очень иронично, но и очень похоже на полный
>> >     игнор: мол, пока скрытой атаки не найдёте, мы все остальные
>> обвинения
>> >     будем пропускать мимо ушей. Они, конечно, могут пропускать сколько
>> >     угодно, но совершенно непонятно, почему на эти обвинения за них
>> должен
>> >     отвечать кто-то другой.
>> >
>> >
>> >     > Они не связаны ни прямо (атаки Перрин не показал), ни
>> теоретически (из
>> >     > наличия структуры не следует наличие атаки).
>> >     > Вот эта связка им проводится исключительно гуманитарными
>> аргументами
>> >     > ("nothing up my sleeve" и вот это всё), и делается она явно ради
>> >     > вывода "а давайте уберем из стандартов".
>> >     >
>> >     >
>> >     > On Tue, Jun 25, 2019 at 2:12 PM Paul Wolneykien
>> >     <manowar at altlinux.org <mailto:manowar at altlinux.org>
>> >     > <mailto:manowar at altlinux.org <mailto:manowar at altlinux.org>>>
>> wrote:
>> >     >
>> >     >     14.06.2019 08:14, Vitaly Chikunov пишет:
>> >     >     > JFYI
>> >     >     >
>> >     >     > Очередные news про sbox Кузнечика.
>> >     >     >
>> >     >     >   https://habr.com/ru/company/virgilsecurity/blog/453254/
>> >     >     >   Про ГОСТовский шифр Кузнечик, его SBox и потерянные сиды
>> >     >     >
>> >     >     >   Scratch вчера в 09:01
>> >     >     >   Блог компании Virgil Security, Inc., Информационная
>> >     >     безопасность, Криптография
>> >     >
>> >     >       Всем привет. А насколько, всё-таки, правомерен данный
>> аргумент?
>> >     >
>> >     >     "Но и структура, в 4 раза меньшая чем Sbox, не может попасть в
>> >     SBox
>> >     >     случайно, что бы там ни говорили авторы и защитники
>> Кузнечика."
>> >     >
>> >     >       Лично мне он кажется правомерным, но может быть я что-то
>> >     упускаю из
>> >     >     виду? Аналогично вот с этим:
>> >     >
>> >     >     "Основная проблема в том, что структура есть, а авторы
>> >     Стрибог/Кузнечник
>> >     >     утверждали обратное."
>> >     >
>> >     >       Из цитат, которые приводятся в статье, следует, что есть
>> некое
>> >     >     начальное "пи", которое обязано быть (псевдо)случайным, но,
>> >     кажется, не
>> >     >     следует, что весь S-Box целиком обязан быть таким же
>> >     (псевдо)случайным
>> >     >     как "пи". (Иначе к чему вообще разделение на "пи" и S-Box?)
>> Или я
>> >     >     неправ?
>> >     >       Далее, в исошном документе
>> >     >
>> >      (
>> https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf)
>> >     >     авторы шифра описывают набор условий, которым должен
>> удовлетворять
>> >     >     S-Box, полученный на основе определённого "пи" (но конкретные
>> >     >     преобразования из "пи" в S-Box, там, насколько я понял, не
>> >     указываются).
>> >     >     Не следует ли, однако, из данного набора условий (набора
>> >     отношений между
>> >     >     "пи" и  S-Box) как раз то, что может (должна?) существовать
>> >     "структура,
>> >     >     в 4 раза меньшая, чем S-Box", которая полностью его описывает?
>> >     >     _______________________________________________
>> >     >     oss-gost-crypto mailing list
>> >     >     oss-gost-crypto at lists.altlinux.org
>> >     <mailto:oss-gost-crypto at lists.altlinux.org>
>> >     >     <mailto:oss-gost-crypto at lists.altlinux.org
>> >     <mailto:oss-gost-crypto at lists.altlinux.org>>
>> >     >     https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> >     >
>> >     >
>> >     >
>> >     > --
>> >     > Regards, Wartan.
>> >     >
>> >     >
>> >     > _______________________________________________
>> >     > oss-gost-crypto mailing list
>> >     > oss-gost-crypto at lists.altlinux.org
>> >     <mailto:oss-gost-crypto at lists.altlinux.org>
>> >     > https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> >     >
>> >
>> >     _______________________________________________
>> >     oss-gost-crypto mailing list
>> >     oss-gost-crypto at lists.altlinux.org
>> >     <mailto:oss-gost-crypto at lists.altlinux.org>
>> >     https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> >
>> >
>> >
>> > _______________________________________________
>> > oss-gost-crypto mailing list
>> > oss-gost-crypto at lists.altlinux.org
>> > https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> >
>>
>> _______________________________________________
>> oss-gost-crypto mailing list
>> oss-gost-crypto at lists.altlinux.org
>> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>>
>
>
> --
> Regards, Wartan.
>
> _______________________________________________
> oss-gost-crypto mailing listoss-gost-crypto at lists.altlinux.orghttps://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>
>
> _______________________________________________
> oss-gost-crypto mailing list
> oss-gost-crypto at lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>

-- 
Regards, Wartan.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.altlinux.org/pipermail/oss-gost-crypto/attachments/20190627/c605b3de/attachment-0001.html>