[oss-gost-crypto] "Про ГОСТовский шифр Кузнечик, его SBox и потерянные сиды"
Igor Ustinov
igus at cryptocom.ru
Thu Jun 27 13:55:35 MSK 2019
А вот я как раз сварщик, и реальную цену всем этим сведениям к NP-полным
задачам, нулевому разглашению и прочим красивым словам очень хорошо себе
представляю. Все существующие доказательства стойкости всех шифров (ну
кроме абсолютно стойкого шифра Шеннона) сводятся к "мы вот тут
попробовали, ничего у нас не вышло, наверное, стойкий". Как следствие,
чем больше людей пробовало, тем сильнее наша вера, что наверное таки да,
стойкий. AES перед принятием 2 года терзал весь мир, и после этого уже
19 лет в покое не оставляют, и ничего выдающегося не нашли, а на
Кузнечик смотрят всего 4 года (а до принятия его в качестве
государственного стандарта его анализом занимались вообще полтора
землекопа исключительно в недрах Конторы), и вот уже нарыли что-то
странное и непонятное, а разработчики в ответ невнятно бормочут про
случайное попадание. Памятуя, что разработчики служат в организации,
гордо провозглашающей себя наследницей КГБ, а у этой организации
репутация в мире вполне определенная, нужно быть ну очень благодушным,
чтобы не начать сомневаться в их искренности. А в криптографии и вообще
в информационной безопасности благодушие - не самая распространенная
черта характера.
В общем, если к вы подошли к человеку в тёмной подворотне с ножом в руке
и вежливо попросили закурить, не стоит удивляться и оскорбляться, что он
испугался.
On 27.06.2019 11:29, Wartan Hachaturow wrote:
> Игорь, ну это же не совсем так.
> Я конечно не настоящий сварщик, но для шифров показывают и
> семантическую стойкость при заданных ограничениях, и сведение к
> NP-полным задачам.
> Если бы все шифры принимались только на веру, у нас была бы куча
> проблем :)
> В случае Кузнечика авторы много раз говорили в кулуарах, что поиск был
> действительно случайным перебором с проверкой алгебраических
> параметров получаемых перестановок: понятно, что в таком случае шансы
> наткнуться на эту перестановку так же велики, как и на любую другую.
> Просто этот процесс был выполнен один раз, довольно давно, и даже код,
> при помощи которого искалось, давно утрачен. Я предлагал собственно
> взять какой-то из суперкомпьютеров и запустить на нем такой же поиск
> еще раз чтобы показать, что она найдется. Но это может занять много
> времени :))
> Я согласен, что наследие "закрытой криптографии" нам мешает, но в
> данном конкретном случае это уж слишком возмутительный наезд, потому
> что по сути совершенно необоснованный.
>
> On Wed, Jun 26, 2019 at 11:58 AM Igor Ustinov <igus �� cryptocom.ru
> <mailto:igus �� 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 �� altlinux.org <mailto:manowar �� altlinux.org>> wrote:
>>
>> 25.06.2019 22:09, Wartan Hachaturow пишет:
>> >
>> > И да -- нет атаки, нет повода для наброса.
>>
>> А вот знаешь, мне тут коллегия математиков подсказывает,
>> что это
>> неправда. Что, мол, на протяжении истории шифров с s-box'ами
>> чего только
>> не вытворяли, и чего в них только не встраивали — как
>> бэкдоры, так и
>> защиты от атак — и что поэтому и существует в новое время
>> требование
>> обосновать S-box.
>>
>>
>> > On Tue, Jun 25, 2019, 21:57 Paul Wolneykien
>> <manowar �� altlinux.org <mailto:manowar �� altlinux.org>
>> > <mailto:manowar �� altlinux.org
>> <mailto:manowar �� 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 �� altlinux.org <mailto:manowar �� altlinux.org>
>> <mailto:manowar �� altlinux.org <mailto:manowar �� altlinux.org>>
>> > > <mailto:manowar �� altlinux.org
>> <mailto:manowar �� altlinux.org> <mailto:manowar �� altlinux.org
>> <mailto:manowar �� 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 �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>
>> > <mailto:oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>>
>> > > <mailto:oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>
>> > <mailto:oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>>>
>> > >
>> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> > >
>> > >
>> > >
>> > > --
>> > > Regards, Wartan.
>> > >
>> > >
>> > > _______________________________________________
>> > > oss-gost-crypto mailing list
>> > > oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>
>> > <mailto:oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>>
>> > >
>> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> > >
>> >
>> > _______________________________________________
>> > oss-gost-crypto mailing list
>> > oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>
>> > <mailto:oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>>
>> > https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> >
>> >
>> >
>> > _______________________________________________
>> > oss-gost-crypto mailing list
>> > oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>
>> > https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>> >
>>
>> _______________________________________________
>> oss-gost-crypto mailing list
>> oss-gost-crypto �� lists.altlinux.org
>> <mailto:oss-gost-crypto �� lists.altlinux.org>
>> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>>
>>
>>
>> --
>> Regards, Wartan.
>>
>> _______________________________________________
>> oss-gost-crypto mailing list
>> oss-gost-crypto �� lists.altlinux.org <mailto:oss-gost-crypto �� lists.altlinux.org>
>> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>
> _______________________________________________
> oss-gost-crypto mailing list
> oss-gost-crypto �� lists.altlinux.org
> <mailto:oss-gost-crypto �� lists.altlinux.org>
> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
>
>
>
> --
> Regards, Wartan.
>
> _______________________________________________
> oss-gost-crypto mailing list
> oss-gost-crypto �� lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/oss-gost-crypto
----------- ��������� ����� -----------
�������� � ������� HTML ���� �������...
URL: <http://lists.altlinux.org/pipermail/oss-gost-crypto/attachments/20190627/6f58d31c/attachment-0001.html>
More information about the oss-gost-crypto
mailing list