Comments 142
Я же верно понимаю, что это таблица подстановок генерируется каждый раз снова при установке защищённого канала? (По типу приватных ключей) или же она единая на всю систему/страну? И при определении (подборе) данной таблицы можно говорить о компрометации вообще любой криптографии основанной на кузнечике?
Понятно, т.е она константа вычисляемая кодом
на основе алгоритма, который (предположительно) выдаёт прогнозируемый результат?
А, понятно, т.е там даже не кодом вшита а прямо массивом чисел, это удивительно.
А каким образом если будет установлено, что sbox не случайный — это поможет взлому или докажет Бэкдор? Мне кажется этого не хватает в посте.
Собственно уже установлено что sbox не случайный, ибо вероятность подобных совпадений — примерно как выиграть во все лотереи по одному билету (набору цифр).
Говорить о бекдоре и "поможет взлому" — нельзя без доказательств, т.е. будет крайней желтизной. Надо отдать должное Scratch за то что не перешел эту грань (хотя рядом) и в статье всё есть, включая основной вопрос — Зачем отрицалось наличие структуры.
Тем не менее, всё таки стоит явно отметить, что наличие структуры в sbox — это не плохо и не хорошо само по себе, а не-идеальные mix/max нелинейности не облегчают атаки.
Для задачи дешифрования/поиска ключа эта часть уже известна. Только экономия кода для программы.
Осмелюсь повторить, что умеренное ослабление — крайне маловероятно, мягко говоря, ибо 275 УК как "Деятельность, направленной против безопасности Российской Федерации").
Т.е. вижу примерно один сценарий (авторы Стриборг/Кузненик получили готовый или исправленный SBOX и были не в курсе его структуры). Как вариант, возможно повторение истории.
Проблема в том, что специально подобранный SBox превращается в маленький "асимметричный" шифр. Который снижает стойкость всего алгоритма шифрования.
Если это так, то тот, у кого находится "закрытый" ключ от SBox, может проводить эффективную атаку на криптоалгоритм.
Если SBox можно сгенерировать с помощью 58 байт, то, возможно, придется перебирать только 2^58 вариантов для поиска ключа вместо 2^256 вариантов.
В принципе, что из себя представляет «Колмогоровская сложность»? Например, есть функция Акермана. У неё очень короткий код. Однако:
Эта функция растёт очень быстро, например, число A(4,4) настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.
Так какова сложность функции Акермана?
Ещё пример: сейчас многие спорят, можно ли использовать ARX конструкции для криптографии, и насколько они хуже, чем SBox. Однако есть доказанная теорема (простите, не сохранил ссылку), что любой SBox на двоичными числами можно реализовать через ARX операции. Так что, не удивительно, что для SBOX находят алгоритмические описания.
Однако есть доказанная теорема (простите, не сохранил ссылку), что любой SBox на двоичными числами можно реализовать через ARX операции.
Это скорее всего есть в пятой главе о функциональной полноте в Rotational Cryptanalysis of ARX.
«Миром правит не тайная ложа, а явная лажа» (с).
Что касается дальнейшей судьбы алгоритма, вероятность принять его как международный стандарт довольно низкая. Это признают как члены ISO, так и сотрудники российских компаний
Похоже так и не дождаться шифрсьютов для TCL/HTTPS с российскими криптоалгоритмами, и не увидим мы этой поддержки в браузерах от Google, Mozilla и других.
Это будет означать наличие двойных стандартов и дискриминации.
Это будет означать, что он им не нужен — не более.
Не согласен с формулировкой.
Подобное противопоставление (они — мы) просто еще один шаг к "чебурнету".
В итоге просто будут функциональные форки/клоны OpenSSL (и других библиотек), отдельные версии браузеров и т.д.
Хотя такой сценарий нельзя назвать совсем плохим — будет создан спрос на соответствующие компетенции и их локальную наработку.
Жалко то как!
(На самом деле — нет)
На зло маме отморозить уши? Ну и что в этом плохого? В чем проблема использовать не зарубежного УЦ а местного, но сертификаты с нормальным шифрованием?
Все еще хуже.
с обычными сертификатами я иду либо в LE и получаю сертификат DV-сертификат. Либо к любому продавцу, с карточкой и получаю DV (если показать документы — то OV). Цены объявлены известны, процедура автоматизированная (кроме проверки документов).
С ГОСТ — проблема даже просто узнать где это сертификат тебе продадут и почем. Ну то есть места то есть но там мягко говоря надо разбираться что конкретно надо и как и какие дополнительные требования.
Scratch, мне кажется стоит аккуратно обозначить в статье возможные причины "мухлежа со структурой".
Уместно вспомнить об истории с таблицей замен в Магме, где таблица замен была загружаемым параметром.
IMHO для Стрибог авторы взяли уже готовый S-BOX, либо он был им предоставлен в какой-то момент. Соответственно, я допускаю, что авторы не знали об алгоритме генерации, т.е. не являются авторами S-BOX. Поэтому и решились давать объяснения в виде "поиска от случайного" и затем "потеряли сиды".
В принципе это соответствует практическим традициям применения крипто-схем с таблицами замен. Причем как с отечественными традициями (явная выдача разных таблиц), так и с зарубежными (тоже самое, только "не столь публично" как у нас).
То что алгоритм генерации решили не раскрывать (или не решились раскрывать) — точно не является плюсом для публичного национального стандарта.
Думаю, стало неожиданным, что алгоритм генерации был восстановлен так быстро. Предполагаю был с умом запущен подбор набора уравнений в GPU-кластере и т.п., но и утечки нельзя исключать. Ну а для авторов Стриборга и Кузненича это стало facepalm-ом.
Крики "бэкдор" и "мы все умрем" IMHO только от "около диванных" аналитиков. Тут у меня несколько тезисов:
- Наличие структуры не говорит о бэкдоре или слабости. В массе S-BOX-ов есть структура. Нужен глубокий анализ с выводами/доказательствами и никак иначе. Мягко говоря, крайне маловероятно, что в S-BOX умышленно внесли слабость (ибо 275 УК). IMHO структура как-раз от обратного, т.е. для стойкости (но безусловно хотелось-бы увидеть доказательства).
- Факт замалчивания структуры неприятен и по-хорошему заставляет ждать публичных результатов криптоанализа "еще три года" после раскрытия алгоритма генерации S-BOX. Т.е. если вы НЕ попадаете под требования регулятора и вольны не использовать Стрибог/Кузненик, то еще года три (видимо) будете относится к ним как к молодым (не проверенными временем) крипто-схемам.
- К заявлениям "в наших SBOX не структуры" стоит относится очень осторожно. Это примерно невозможно доказать. Соответственно, утверждение "в SBOX не структуры" никогда не означает что структуры действительно нет, и нас ждет еще несколько каминг-аутов.
Гипотетическая смена таблицы замен не должна стать проблемой, поскольку AFAIK чуть менее чем во всех отечественных "железных" реализациях предусматривается такая возможность (закладывается в требования).
Это повышает вероятность того, что существует достаточно простое алгебраическое описание работы шифра.
Тот, кому известно просто алгебраическое описание, может взламывать шифр.
Направление мысли понятно?
Не-не, там ещё хуже — только два возможных значения у каждого бита и только две базовые операции с ними (причем одна вообще унарная!).
;)
Начнем с простых примеров.
Какая система уравнений проще, на ваш взгляд?
Вот эта: S = A+B mod 16
Или вот эта:
S0 = (A0 XOR B0)
S1 = (A1 XOR B1) XOR ((A0 AND B0) OR (A0 XOR B0))
S2 = (A2 XOR B2) XOR (((A1 XOR B1) AND ((A0 AND B0) OR (A0 XOR B0))) OR (A1 AND B1))
S3 = (A3 XOR B3) XOR ((((A2 XOR B2) AND (A1 XOR B1)) AND ((A0 AND B0) OR (A0 XOR B0))) OR (((A2 XOR B2) AND (A1 AND B1)) OR (A2 AND B2)))
Тут вы немного путаете "божий дар с яичницей".
Очевидно, что для анализа удобнее иметь "алгебраическое описание" компактно отражающее ход мыслей авторов (т.е. дизайн), а не реверсить его из таблицы чисел.
И как уже писал, сокрытие факта наличия структуры (это в первую очередь) и самой структуры (это во вторую очередь) не является плюсом для публичного стандарта.
Однако, мыслимое вами "алгебраическое описание" не будет доказательством наличия/отсутствия тех или иных свойств, хотя (возможно!) позволит легче выполнить такое доказательство (публичный аудит).
Алгебраическое описание — это также инструмент оптимизации системы уравнений в целях взлома.
Вам накидать статей, как шифры семейства ARX пытаются ломать через алгебраические атаки?
Там как раз основная проблема, что после некоторого числа итераций алгебраическое описание плохо работает, поэтому ломают алгоритмы с урезанным числом итераций.
Наличие простого (и согласованного!) алгебраического описания для двух последовательных шагов алгоритма (к тому же, скрытого авторами) — это очень подозрительно, я бы сказал.
В случае Стрибог так и есть. Читаем Leo Perrin.
Два последовательных шага алгоритма описываются операциями по модулю одного и того же полинома, представляете?
Просто нет слов.
Наверняка, кто-то в недрах секретных НИИ получил медаль за это… ну или пулю в затылок.
Я ничего не путаю.
Алгебраическое описание — это также инструмент оптимизации системы уравнений в целях взлома.
Нет, вы всё-таки путаете "описание алгебраической структуры" с чем-то из списка: "описание алгебраической атаки", "доказательство стойкости против таких-то видов атак", "системой уравнений или её выводом".
Вам накидать статей, как шифры семейства ARX пытаются ломать через алгебраические атаки?
Не надо, у меня своё есть )
Там как раз основная проблема, что после некоторого числа итераций алгебраическое описание плохо работает, поэтому ломают алгоритмы с урезанным числом итераций.
При меньшем числе итераций более простая система уравнений. Соответственно её можно немножко по-SAT-ить, по-коррелировать, по-rainbow-ить и т.п.
… Читаем Leo Perrin ...
Вот цитата из его текста:
First of all, I would like to emphasize that I have not found an attack leveraging these properties. Still, I don't know the answer to the question above...
Perrin нашел структуру.
Но из наличия структуры не следует, что какая-то атака становится проще.
Термин "подозрительно" тут не совсем уместен, это FUD.
Утверждение что "атака возможна" — это "не понял / не понял, но осуждаю", тоже FUD.
Тем не менее, изначально FUD конечно пошел от авторов Стрибог/Кузнечик.
И теперь, после работы Perrin, стало очень интересно.
Ведь кроме упомянутой ранее 275 УК могут быть еще два варианта: продвинутые авторы S-box и/или продвинутая контрразведка.
Разбираетесь в дифференциальном криптоанализе — тогда welcome.
Но из наличия структуры не следует, что какая-то атака становится проще.
В ваших постах очень много фраз «не доказано/не следует».
А давайте тогда просто считать надежными все шифры, которые еще не взломаны.
Вы же любите бинарную логику? Шифр либо уже взломан, либо надежен. Классно, да?
Только вот криптоанализ — дело длинное и дорогое.
От первого подозрения до полноценного взлома иной раз проходят десятки лет.
Криптоанализировать все шифры нет возможности, не хватит спецов.
Поэтому подход «не доказано/не следует» не прокатывает.
Прокатывает отбрасывать шифры при первых подозрениях.
Шифров не жалко, новых нарожают.
В первую очередь стоит отбрасывать шифры, разработчики которых лгут.
Термин «подозрительно» тут не совсем уместен, это FUD.
Предлагаете вообще убрать FUD из криптографии?
И сразу заживем?
В ваших постах очень много фраз «не доказано/не следует».
А давайте тогда просто считать надежными все шифры, которые еще не взломаны.
Вы же любите бинарную логику? Шифр либо уже взломан, либо надежен. Классно, да?
Давайте еще раз переформулирую.
Наличие структуры в s-box может равновероятно говорить как о стойкости к каким-то атакам, так и о бекдоре.
Поэтому без аналитических доказательств говорить что наличие структуры "подозрительно" или "плохо" — это либо FUD и манипуляция, либо недопонимание.
В массе других случаев это может быть "подозрительным", но не здесь.
Другое дело — сам факт "отрицания" наличия структуры при заходе в международный комитет. Но свои варианты причин уже озвучивал.
Только вот криптоанализ — дело длинное и дорогое.
От первого подозрения до полноценного взлома иной раз проходят десятки лет.
Криптоанализировать все шифры нет возможности, не хватит спецов.
Поэтому подход «не доказано/не следует» не прокатывает.
Тут явная манипуляция — попытка навязать неверные выводы озвучив пару верных утверждений.
Прокатывает отбрасывать шифры при первых подозрениях.
Шифров не жалко, новых нарожают.
«А сегодня криптоанализом не все могут заниматься. Вернее заниматься могут не только лишь все, мало кто может это делать» — вот буквально это и наблюдаем ;)
Хотя никто не запрещает заниматься анализом (каких угодно шифров) и публиковать результаты, что и сделал Leo Perrin. Кто угодно может оценивать эти результаты, делать выводы и т.д.
Однако, часть работы регулятора связанных с ним структур в том, чтобы обеспечить выполнение соответствующих протоколов, в том числе обеспечить криптоанализ и доказательство стойкости для национальных крипто-стандартов со стороны "специально обученных людей". При этом соответствующие обсуждения и доказательства не обязаны быть публичными.
В первую очередь стоит отбрасывать шифры, разработчики которых лгут.
Ложь — это преднамеренное искажение информации.
Как уже писал, я не склонен считать что "официальные" разработчики Стрибог/Кузненик знали о структуре s-box. Проще говоря, думаю, они не являются авторами s-box.
А вот вопрос "как так получилось" — как раз становится более интересным.
Если без шуток, то ваше "направлением мысли" НЕ в сторону логики, алгебры и метематики.
А то я теряюсь в догадках.
Основная проблема в том, что «структура» S-box Кузнечика коррелирует со «структурами» других шагов алгоритма.
Для точности: Этот многострадальный S-box был сделан для Стрибога, а потом использован в Кузнечике.
Не могли бы мы чуть более подробнее пояснить, какие именно, на ваш взгляд, преобразования, структуры или шаги в Стрибог или Кузнечике "коррелируют" с процедурой генерации S-Box?
Это повышает вероятность того, что существует достаточно простое алгебраическое описание работы шифра.
Как уже писал "про лотерею" — наличие структуры можно считать доказанным фактом. Поэтому "достаточно простое алгебраическое описание" существует с такой достоверностью, что её вероятность крайне сложно повысить.
Тот, кому известно просто алгебраическое описание, может взламывать шифр.
Нет, это неверный вывод. Пока нет доказательств (наличия/отсутствия тех или иных свойств), никакое знание "просто формулы" не позволяет сделать подобных выводов (как и обратных).
Т.е. видя формулу модульной экспоненты, но не зная всего что "стоит за" RSA и самой проблемы факторизации (и её отсутствия в некоторых случаях), вы не сможете ничего сказать о стойкости.
Направление мысли понятно?
Нет (
Нет, это неверный вывод. Пока нет доказательств (наличия/отсутствия тех или иных свойств), никакое знание «просто формулы» не позволяет сделать подобных выводов (как и обратных).
Т.е. видя формулу модульной экспоненты, но не зная всего что «стоит за» RSA и самой проблемы факторизации (и её отсутствия в некоторых случаях), вы не сможете ничего сказать о стойкости.
Вам не кажется, что требования к асимметричным шифрам сильно отличаются от требований к симметричным шифрам и хеш-функциям?
А у хеш функций вообще не должно быть простого описания.
И вроде как это всем понятно, даже самим авторам Streebog.
Кроме того, авторы Streebog в неформальных дискуссиях утверждали (см. Резюме в [ 9 ]), что они хотели избежать слишком сильной алгебраической структуры, чтобы предотвратить некоторые атаки. Хотя в этом подходе априори нет ничего плохого, он полностью расходится с их конечным результатом: как показано в следующем разделе, их S-блок имеет чрезвычайно сильную алгебраическую структуру.
translate.google.com/translate?hl=&sl=en&tl=ru&u=https%3A%2F%2Fwho.paris.inria.fr%2FLeo.Perrin%2Fpi.html%23sec-2-4
Не могли бы мы чуть более подробнее пояснить, какие именно, на ваш взгляд, преобразования, структуры или шаги в Стрибог или Кузнечике «коррелируют» с процедурой генерации S-Box?
Читаем tosc.iacr.org/index.php/ToSC/article/view/7405/6577
To this end, we provide a newsimpler representation of the linear layer of Streebog as a matrix multiplication in the exact same field as the one used to define pi. We deduce that this matrix interacts in a non-trivial way with the partitions preserved by pi
Вам не кажется, что требования к асимметричным шифрам сильно отличаются от требований к симметричным шифрам и хеш-функциям?
А у хеш функций вообще не должно быть простого описания.
И вроде как это всем понятно, даже самим авторам Streebog.
Давайте переформулирую:
Простота/сложность внешнего вида уравнения, системы уравнений или крипто-формулы примерно не коррелирует со сложностью решения или проведения атаки.
the linear layer of Streebog as a matrix multiplication in the exact same field as the one used to define pi
Тут я должен признать свой ляп из-за невнимательности, т.е. читая работу Perrin-а я смотрел на инфу о кузнечике, а когда писал вам "какие преобразования, структуры или шаги в Стрибог или Кузнечике коррелируют" не исключил Стрибог.
На всякий, еще раз повторю, во всей истории меня напрягает не простота каких-то формул, а факт того что (вероятно) разработчики НЕ являются авторами s-box и (пока) НЕ объяснили его происхождение после раскрытия структуры.
По сути, если раньше просто не было оснований верить в отсутствие закладок в этом s-box, то сейчас появились серьёзные основания считать, что закладки таки есть.
У суда нет оснований не доверять сотруднику полиции…
Технически подкованные граждане — государству:
У нас нет оснований доверять любым «алгоритмам» от государственных структур, не прошедшим независимый аудит.
Шумящий диод такого не генерирует
случайность на то и случайность, что там может быть вообще что угодно, а человек очень силён в поисках структур, последовательностей и алгоритмов
Этот аргумент разбирается в разделе «Колмогоровская сложность».
Не то, чтобы я придираюсь и занудствую. Но, эти два массива вынуты вами непонятно откуда, в оригинальной статье я таких последовательностей не нашел. Возможно, там был простенький их рассчет, но тогда не понятно, почему бы именно такой расчет не включить в программу?
Рискну пока идут тесты ;)
Leo Perrin нашел "структуру", из чего следует что у Стрибог/Кузнечик есть определенные "свойства".
Эти свойства изложены в разделе 2.2 его статьи.
Что в этом "плохого" описано в разделе 2.3.
Если из предыдущего раздела и заключительного 2.4 попытаться сделать выводы, то:
- Основная проблема в том, что "структура есть", а авторы Стрибог/Кузнечник утверждали обратное.
- Условия для бэкдора (по методу из диссертации Арно Банье) в Кузненике не найдены.
- Взаимодействия s-box c линейныйм слоем (всем остальным) в Стрибог не понято.
- Векторы атак не найдены, но "подозрительно, ибо не понятно".
- Ай-я-яй, так нельзя...
Основная проблема в том, что «структура есть», а авторы Стрибог/Кузнечник утверждали обратное.
Авторы шифра/хеша всего лишь соврали о его дизайне.
Подумаешь, проблема, правда? Это все культурные традиции.
И вообще, хватит распространять FUD.
Давайте поскорее стандартизируем его и включим во все реализации SSL.
Ведь чем больше разных шифров поддерживается в стандарте SSL, тем секьюрнее.
Авторы шифра/хеша всего лишь соврали о его дизайне.
Подумаешь, проблема, правда?
IMHO вы пытаетесь "громче хайпануть", а НЕ разобраться в ситуации,
Свое отношение к этой ситуации и возможные причины уже излагал.
Это все культурные традиции.
Теперь точно один минус от меня.
Давайте поскорее стандартизируем его и включим во все реализации SSL.
Ведь чем больше разных шифров поддерживается в стандарте SSL, тем секьюрнее.
Стрибог/Кузнечик уже "стандартизированы" в документах российского регулятора и RFC.
Этого уже IMHO достаточно как для включения реализации в существующие открытые реализации SSL/TLS, так и для разработки отечественных.
При этом Стрибог/Кузнечик вовсе не обязаны быть международным стандартом, быть одобренными или всем нравиться.
Тем не менее, попытка "зайти в ISO/IEC" со скрытой алгебраической структурой, дискуссии об отсутствии такой структуры и попытка объяснить её обнаружение "просто совпадением" — для меня выглядят (мягко говоря) странными и нерациональными. Поэтому я склонен предполагать наличие каких-то (пока) скрытых причин или обстоятельств, начиная от банального незнания авторами факта наличия структуры (получили готовый s-box), до 275 УК и даже игр разведок.
Но всё это, до аналитических доказательств, не говорит о наличии бэкдора или, наоборот, о какой-то стойкости к (пока) нераскрытым атакам.
Теперь точно один минус от меня.
Да пожалуйста.
Затыкать рот неугодным — это тоже ваши культурные традиции.
Я минусы не ставлю принципиально, это мои традиции.
IMHO вы пытаетесь «громче хайпануть», а НЕ разобраться в ситуации,
Свое отношение к этой ситуации и возможные причины уже излагал.
Хайпанул Leo Perrin. Чувака ждет прекрасная карьера. Мне-то чего хайповать?
Меня поражают ваши упорные попытки оправдать Стрибог/Кузнечик, все эти «не следует», «не доказано», рассуждения про алгебру уровня форумного тролля, поэтому я и высказался.
Ведь авторы реально соврали, осознанно или нет.
Мне интересно, что бы вы сказали, если бы в шифре разработки US такое нашли.
Орали бы на весь хабр.
Стрибог/Кузнечик уже «стандартизированы» в документах российского регулятора и RFC.
Этого уже IMHO достаточно как для включения реализации в существующие открытые реализации SSL/TLS, так и для разработки отечественных.
Серьезно?
Будем включать всякие туземные шифры в продукты, которыми пользуется весь
мир?
Что дальше? Индийские шифры, пакистанские шифры?
Это очень стремно, с учетом возможности downgrade attack.
Или может добавим лишние ключи для сборки, типа CONFIG_RU_CRYPTO?
Тем самым усложняя и так непростой продукт и жертвуя безопасностью?
Может, вообще сделаем локализованные сборки OpenSSL, для каждой страны своя?
Я лишь имел ввиду, что минусы в карму ограничивают мою возможность писать комменты.
Меня поражают ваши упорные попытки оправдать Стрибог/Кузнечик, все эти «не следует», «не доказано».
Оправдывать нет необходимости, ибо (еще раз) показанные структуры могут примерно равновероятно говорить как о стойкости к каким-то атакам, так и о наличии бэкдора.
рассуждения про алгебру уровня форумного тролля, поэтому я и высказался.
Вам достаточно корректно были даны простые пояснения (aka vulgarized explanation) о том, что по критерию насколько "много букв" или "мало букв" в "описании" (системе уравнений) нельзя судить о трудоемкости решения и стойкости крипто-схемы.
Ведь авторы реально соврали, осознанно или нет.
Опять манипуляция, нельзя "соврать несознательно".
Свое мнение относительно авторов и происхождения s-box уже многократно озвучивал.
Мне интересно, что бы вы сказали, если бы в шифре разработки US такое нашли.
Ни разу не было и вот опять.
Т.е. "если бы" — не то склонение.
Орали бы на весь хабр.
Обычно я просто спокойно доношу свое мнение — в критических местах не должно быть недоверенных алгоритмов, софта и железа. А к RC6 у меня доверия гораздо больше чем к Rijndael.
Будем включать всякие туземные шифры в продукты, которыми пользуется весь
мир?
Это что, крипто-шовинизм?
Что дальше? Индийские шифры, пакистанские шифры?
Да, если они соответствующим образом сформируют/оформят свои национальные стандарты и RFC.
Иначе говоря и в том числе, если регуляторы в этих странах перестанут доверять AES и т.д.
Это очень стремно, с учетом возможности downgrade attack.
Стремно — это когда вы не можете выбрать набор шифров и приоритет их использования из-за ограничений инфраструктуры.
"downgrade attack" — здесь это манипуляция, FUD или недопонимание.
Или может добавим лишние ключи для сборки, типа CONFIG_RU_CRYPTO?
Тем самым усложняя и так непростой продукт и жертвуя безопасностью?
Продукт усложнили до нас, мягко говоря — это отдельная боль и история.
"Жертвовать безопасностью" — здесь это манипуляция, FUD или недопонимание.
Может, вообще сделаем локализованные сборки OpenSSL, для каждой страны своя?
Если координаторы "сообщества разработчиков" OpenSSL (и других проектов) будут против подключения национальных крипто-схем (не важно по каким причинам), то это неизбежно.
к RC6 у меня доверия гораздо больше чем к Rijndael
Если не секрет, почему?
Циклически сдвиги зависящие от данных.
Мне кажется если есть часть дифузии данных внутри блока зависит от входных данных это значит что сложнее заниматься криптанализом шифра, это не значит что там с меньшей вероятностью будут пробелмы.
Всё верно.
Говоря о "зависящих от данных циклических сдвигах" именно это я и имел в виду.
Умножение тоже хорошо добавляет диффузии, из расчета "попугаев на операцию".
Тем не менее, условно "при прочих равных", сдвиги и умножения дают более "широкие S-блоки", т.е. больше диффузии.
Соответственно, условно "при прочих равных", достаточно меньшего количества раундов.
Немного не так.
Сдвиги и умножения дают больше конфузии (по Шеннону), т.е. сильно усложняют алгебраическую зависимость выхода от входа.
А так как операции за раунд не вносят (не должны) статистических сдвигов, то на следующем раунде диффузия как-бы "домножается" на конфузию. Проще говоря, диффузия во втором раунде также зависит от данных, то теперь эти данные перемешаны сами с собой.
Проще говоря, имеется мощнейший лавинный эффект, который обеспечивает взаимное "домножение" диффузии и конфузии на каждом следующем раунде.
Если посмотреть на это "со стороны данных", то можно подать на вход нечто, что отравит сдвиги или умножение в первом раунде. Но уже на следующем раунде это будет не возможно (не должно быть) при правильной процедуре разворота ключа. Таким образом, слабым ключом и подобранным текстом, можно отравить только первых два раунда, но дальше диффузия и конфузия будут примерно стабильны.
+++
При этом зависимость от данных существенно расширяет систему уравнений описывающих состояние и создает инварианты, и все это растет экспоненциально с количеством раундов. Поэтому самой простой атакой достаточно быстро становится подбор ключа.
Стремно — это когда вы не можете выбрать набор шифров и приоритет их использования из-за ограничений инфраструктуры.
«downgrade attack» — здесь это манипуляция, FUD или недопонимание.
Набор шифров выбирают клиент и сервер на основе того, что в них реализовано.
Коммуникации на этом этапе еще не защищены шифрованием.
Итак, допустим, сервер говорит вам, что поддерживает только один шифр.
Вы тоже его поддерживаете. Вы начинаете использовать этот шифр, предложенный сервером.
Только это был не сервер, а MITM прокси.
Шифр был слабым. В результате, вас поимели.
Я, думаю, я верно понимаю суть downgrade attack.
Если нет — исправляйте.
Это что, крипто-шовинизм?
Крипто-шовинизм или нет, но рассмотрим гипотетическую ситуацию.
1) Некое государство N стандартизирует у себя некий блочный
шифр K.
N переводит все национальные SSL сервера на шифр K.
2) N добивается включения шифра K в OpenSSL.
Шифр K становится доступен в браузерах при установке SSL соединения.
3) Теперь при подключении любого человека на Земле можно провести MITM атаку, downgrade атаку, и заставить его браузер использовать шифр K при установке SSL соединения.
4) Шифр K содержал закладку, которую никто не заметил.
Туземцы из N тихонько имеют весь мир.
Ситуацию можно ухудшить.
Пусть у нас несколько государств Ni и у каждого свой шифр Ki, на котором работают национальные сервера.
Что теперь делать?
Так что я думаю, никто не будет включать национальные шифры в OpenSSL.
Ох, этак мы скоро смысл жизни будем обсуждать.
Давайте обозначим как Т1 мой тезис "Стремно — это когда вы не можете выбрать набор шифров и приоритет их использования из-за ограничений инфраструктуры".
Набор шифров выбирают клиент и сервер на основе того, что в них реализовано.
Вот смотрите, ваше описание одной из раздновидностей "Downgrade attack" начинается с условия, которое попадает под Т1.
Коммуникации на этом этапе еще не защищены шифрованием.
Итак, допустим, сервер говорит вам, что поддерживает только один шифр.
Вы тоже его поддерживаете. Вы начинаете использовать этот шифр, предложенный сервером.
Ага, еще одно условие попадающее под Т1.
Только это был не сервер, а MITM прокси.
Шифр был слабым. В результате, вас поимели.
Теперь предположим, что согласно Т1 я имею возможность не использовать те шифры (их версии/подверсии и все прочие потроха), к которым не имею доверия — всё, атаки не получится.
Если я не слишком умный/продвинутый, то список "правильных" шифров мне сообщит/порекомендует регулятор.
Я, думаю, я верно понимаю суть downgrade attack.
Если нет — исправляйте.
Ну можно придраться, что вы описываете один из подвидов downgrade attack, который является одним из сценариев MITM. С другой стороны, это пересекающиеся множества, соответственно вопрос сугубо из области таксономии.
Так-что "суть" downgrade attack вы понимаете, но вот корень проблемы и рецепт лечения видите совершенное неверно.
1) Некое государство N стандартизирует у себя некий блочный
шифр K.
N переводит все национальные SSL сервера на шифр K.
2) N добивается включения шифра K в OpenSSL.
Шифр K становится доступен в браузерах при установке SSL соединения.
3) Теперь при подключении любого человека на Земле можно провести MITM атаку, downgrade атаку, и заставить его браузер использовать шифр K при установке SSL соединения.
4) Шифр K содержал закладку, которую никто не заметил.
Туземцы из N тихонько имеют весь мир.
Еще раз.
При выполнении обозначенного Т1 у меня будет возможность использовать только те шифры, которым я доверяю своим умом или с помощью регулятора.
Если сервер не поддерживает нужные мне шифры, то в моих глазах он просто не хочет чтобы я его использовал.
Если будет MITM без поддержки "правильных для меня" шифров или без умения их вскрывать, то либо я не смогу пользоваться скомпрометированной сетью, либо наличие MITM ничего не изменит.
Если же MITM сумеет вскрывать "мои правильные шифры", то проблема у моего регулятора и/или у меня (от "большого" ума).
Ситуацию можно ухудшить.
Пусть у нас несколько государств Ni и у каждого свой шифр Ki, на котором работают национальные сервера.
Что теперь делать?
Лечить инфраструктуру, включая OpenSSL и прочие аналогичные проекты, не допуская какое-либо навязывание или дискриминацию национальных стандартов.
Так что я думаю, никто не будет включать национальные шифры в OpenSSL.
Тогда OpenSSL умрет как международный проект. Т.е. будет форкнут или станет внутренним проектом страны "с самыми правильными шифрами".
По части остального откомменчусь.
Еще раз.
При выполнении обозначенного Т1 у меня будет возможность использовать только те шифры, которым я доверяю своим умом или с помощью регулятора.
Будет дерьмовая ситуация, когда вам надо коннектиться к национальным сайтам стран N1 и N2 с шифрами K1 и K2, при этом вы не хотите использовать K1 и K2 на других сайтах.
То есть, надо где-то в доменной зоне прописывать набор разрешенных шифров и пойдет еще один виток усложнения веба.
А веба уже и так непростой и много где сломанный.
Чтобы этого всего не было, надо просто не пущать туземные шифры.
Пусть туземцы сами разбираются со своими проблемами, раз они их и создают.
Лечить инфраструктуру, включая OpenSSL и прочие аналогичные проекты, не допуская какое-либо навязывание или дискриминацию национальных стандартов.
Это все туземные комлексы у вас.
Сорри за прямоту.
Это проблемы скорее из области психотерапии, чем криптографии.
Хотя есть и решение из области криптографии.
Несколько туземных стран предлагают свои шифры, и в SSL работает их комбинация (с защитой от возможного сговора двух и более туземных стран).
Будет тормозить, но зато секьюрно.
Будет дерьмовая ситуация, когда вам надо коннектиться к национальным сайтам стран N1 и N2 с шифрами K1 и K2, при этом вы не хотите использовать K1 и K2 на других сайтах.
Это не примерно неизбежная проблема "крипто-зоопарка".
То есть, надо где-то в доменной зоне прописывать набор разрешенных шифров и пойдет еще один виток усложнения веба.
А веба уже и так непростой и много где сломанный.
Чтобы этого всего не было, надо просто не пущать туземные шифры.
Пусть туземцы сами разбираются со своими проблемами, раз они их и создают.
Есть несколько технологических решений. Один из вариантов "международный сертификат".
Суть в том, что сертификат подписывается несколькими CA или международным ООН-CA, при этом внутри несколько подписей по нескольким крипто-схемам и несколько тегированых наборов шифров для разных стран.
Соответственно, на стороне клиента проверяется "родная" подпись и выбирается "правильный набор шифров". MITM может вклиниться только взломам соответствующую подпись.
А ничего, что колмогоровская сложность определяется с точностью до константы и невычислима?
Похоже на передергивание фактов наукообразным способом.
Для любой конечной последовательности существует интерпретатор, на котором программа, выводящая эту последовательность, занимает 1 бит.
Библиотеки под рукой нет, поэтому придётся сослаться на Википедию. В статье про колмогоровскую сложность написано: "С помощью принципа Дирихле легко показать, что для любой универсальной машины существуют алгоритмически случайные строки любой длины, однако свойство строки быть алгоритмически случайной зависит от выбора универсальной машины. "
Пока рекорд — 58 байт на языке Stax.Не байт, а символов.
А почему, собственно, так важен объем программы, генерирующей блок? Какую ценность для криптографической науки несёт выкидывание пробелов из программы?
И ещё вопрос по сути статьи — правильно ли я понимаю, что если бы авторы честно сказали, что использовали такой вот алгоритм генерации, то никаких претензий из тех, что к ним сейчас предъявляют, к ним бы сейчас не было?
1. А почему вы использовали именно это, а не что-то более простое? Откуда вы взяли магическую строку "@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8"? Это ФИО разработчиков, или что?
2. Почему вы считаете, что этот s-box достаточно нелинеен? Из текста генератора это, мягко говоря, не очевидно.
смешно когда наши доблестные ФСБшники включают школьников и говорят, что 11 лет назад этот алгоритм начинал разрабатываться чуть ли не в свободное время, поэтому они в итоге потеряли и сиды и скорее всего программу, которая генерировала таблицу подстановок.
А я в принципе верю. Это конечно не в плюс им.
Верю, глядя на некоторые сертифицированные (ФСБ) криптографические продукты рекомендованные для .....
Как вам например:
- Cпецификация с примерами на "C" с выражениями типа "int len = sizeof(str)", где "str" — указатель на строку!? (len дальше используется как размер строки для подписи!!)
- Или "аутентфикация" запроса (не шифрованного!) в протоколе (стандарта прошлого столения) внутри TCP/IP путем "секретного" константного пароля как одного из полей запроса. А что бы это секретный пароль вдруг не увидели в канале, то он XOR константной. И не строкой, а одним и тем же константным байтом каждого байта "секретного" б.ля пароля?
- А спецификация на протокол в внутри PDF. Которую 2 часа после copy|paste пришлось очищать от артефактов PDF?
И да… формуляры по документации все в лучших традициях. 90% воды и бюрократическ-военного стиля языка.
Честно… "За державу обидно".
Распилы сплошные.
Пока основные решения по криптографии принимаются в недрах закрытых
организаций, инсинуации на эту тему будут продолжаться, независимо от их
реальной достоверности.
Процесс шифрования в блочном шифре можно представить простой формулой
C = M х K
где C — шифротекст, M — открытый текст, K — ключ шифрования, а x — блочный шифр.
Эта формула визуально похожа на школьную формулу линейного уравнения y = kx+b, графиком которой является прямая линия.
Вот, блджад мне ни разу не понятно, как от одной «формулы», «визуально» похожей (на самом деле совсем нет) перескочили к другой. Тут либо ТС не обладает компетенциями, либо «не гоже вам знать лишку».
Претензия моего комментария в том, что правильное написание формулы
C=x(M,K)
грубо максируется под операцию умножения и притягивается «за уши» формула прямой на плоскости. Подозреваю, здесь идёт расчёт на то, что читатель запутается и бросит прослеживать ход рассуждений.
Но нет, въедливый читатель не бросит.
Ну не "полная хрень", а просто не совсем понятно зачем Leo Perrin, показав структуру в s-box, "еще раз" взялся убеждать всех в её наличии посредством хайп-чемпионата на поиск самого короткого генерирующего алгоритма.
Всё искусство программирования ведь построено именно на том, что люди находят более короткие алгоритмы для решения тех же самых задач.
Я не силён в криптографии, но более-менее шарю в теории алгоритмов, и у меня немножко волосы встают дыбом от безграмотности общей идеи изложенного.
Во-вторых, приятно видеть наконец-то четкие (на бумаге) слова создателей и обсуждение в международной комиссии. В то, что программа и сиды утеряны (если таковые вообще были), думаю, не верит тут никто, ибо в ФСБ такие материалы должны быть, как минимум, с грифом «секретно», и отдавать их на всеобщее обозрение никто не будет даже в интересах стандартизации в ИСО.
И в-третьих, сам факт того, что наш S-блок можно «сжать» в 4 раза, сделав его «сопоставимым по размеру» S-блоку AES, не может быть аргументом для запрета его использования. Порядок его нелинейности тоже вполне приличный и не сильно уступает аналогам. По «вскрытой» структуре он сложнее того же AES, если говорить о вычислительном аспекте. Например, гомоморфно вычислить функцию обращения достаточно легко (что сделано в 10-ках работ), а вот сделать тоже самое с показательной функцией гораздо сложнее (но такие работы уже ведутся, включая использование найденной алгебраической структуры). Кроме того, S-блок алгоритма BelT, на который похожа подстановка Pi^{-1}, известен, и известны его алгебраические свойства, которые ничем не уступают свойствам S-блока AES. Так что есть надежда на то, что все-таки наш S-блок все же примут в том виде, в котором он сейчас есть.
Перестановка — частный случай подстановки, — которая является линейным преобразованием и может быть задана намного проще (как умножение на матрицу, в общем случае). Например, циклический сдвиг на 11 в «Магме» — это тоже перестановка. В архитектуре SP-сети перестановка — это P-блок. Иногда он может быть несколько сложнее — не линейным, а аффинным (тогда архитектура SA). Но в любом случае, он вычисляется проще. Так что тут не может быть двоякого прочтения, если речь идет о нелинейном биективном преобразовании.
Я как алгебраист всегда называл перестановкой биективное отображение конечного множества в себя.
Википедия со мной вполне согласна.
В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.)
ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0
Ваши замечения — из области лингвистики, а не криптографии, и никак не отменяют результатов Leo Perrin.
С точки зрения алгебры, не буду с Вами спорить, как криптограф-алгебраист могу согласиться с тем, что в классической алгебре перестановки и подстановки рассматривают в едином контексте. Но в криптографии разница определяется однозначно. Посмотрите на докомпьютерную (классическую) криптографию. Там выделяется 2 общих класса шифров — подстановочные и перестановочные. Первый класс — шифры замены, в то время как второй включает только те, в которых буквы текста не заменяются, а перемешиваются в соответствии с ключом и алгоритмом. Далее это распространилось и на современные архитектуры, начиная с работы Клода Шеннона. Под перестановкой в криптографии понимают именно перемешивающее преобразование, а не замену.
А результаты Перрина мы тут и вовсе не обсуждаем — зачем Вы это написали, мне не понятно.
Тем, кто минусит — респект. Изучение матчасти — не ваше дело, видимо. Как показывает опыт, выпускники вузов практически не знают в итоге терминологии в области, в которой они получают дипломы.
Вы мне чем-то напоминаете ВАК-овских динозавров, которые готовы сожрать за немного корявую формулировку.
В школьной математике тоже подобные веения. Напридумывают терминов и заставляют их зубрить. Термины ради терминов.
Термины никак не помогают решать задачу сами по себе, а только замусоривают мозги.
Я выступаю за то, чтобы народ понимал суть, чтобы имел в голове модели того, что происходит.
Народ понимает суть — тоже хорошо.
Но человек, который посещает одну из самых сильных конференций по криптографии, просто обязан писать свои статьи грамотно. Да, он, возможно, не криптограф — но для того и нужны комментарии, чтобы «причесать» сей труд.
И некоторое время не понимал, почему перестановка — это не перемешивание массива, а именно отображение.
То есть, терминология криптографии ближе к кодингу.
Зато я узнал, что, то, что у нас называется группами подстановок, там называется группами перестановок.
Я понимаю ваше негодование, но цель статьи — донести смысл до неподготовленного читателя. Иногда ради этого приходится жертвовать точностью определений.
В целом, для нас важен результат. Конечно, есть большая вероятность того, что чиновники из ИСО не примут наш шифр и даже отзовут хэш. Но я не думаю, что это приведет к каким-либо существенным последствиям внутри РФ. Будем жить с «местным» стандартом, только и всего.
Indifferentiability of Confusion-Diffusion Networks, одним из авторов которого является Евгений Додис, получивший в этом году награду за лучшую работу по Fuzzy extractors. Вот слайд из этого доклада.
Либо статья без точной терминологии туда всё-таки попала, либо отношение к этим понятиям все-таки отличается у нас и у них.
Уууу….как тут все же все запущено в плане теории
Они предпочитают говорить о линейных и нелинейных слоях, так гораздо меньше путаницы.
Может, если российские криптографы поменьше бы сидели бы за закрытыми дверями и больше общались с живыми людьми, то и определения в литературе и разговорах были бы «поумней».
Взаимно однозначное отображение конечного множества в себя называется перестановкой (подстановкой) элементов этого множества.
Поэтому не исключена "терминологическая путаница" между перестановкой бит (в P-блоках) и биективным отображением множества (перестановкой элементов), которое (в частности) реализуется подстановкой в S-блоках.
Или еще больше запутал?
P.S.
Мимопроходил.
есть ненулевая вероятность выпиливания уже принятого в стандарт хэша Стрибог (с тем же SBox), а так же RFC 7801, в котором описан Кузнечик.
RFC 7801 тут зря упомянули. Во-первых, что-то «выпилить» из RFC вообще вряд ли возможно. Надо понимать, что RFC никого ни к чему не обязывает. Во-вторых, RFC 7801 вообще INFORMATIONAL. Это тоже самое, что предложить «выпилить» RFC 3514.
Хотел бы особо отметить, что я не вкладывают никакого особого смысла при выборе RFC 3514, он просто иллюстрирует абсурдность идеи «выпиливания» чего-либо из RFC.
Что можно почитать научно-популярного на тему алгоритмов, применяющихся для поиска структур?
К примеру, есть последовательность 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Как определить, можно ли её описать короткой формулой или нет?
Не работает, так что вопрос остаётся в силе.
Это все детский сад с точки зрения науки, но зато остальным понятно.
Наверное, для этого и написал. Такой хайп на Хабре разгорелся из-за ерунды.
Про ГОСТовский шифр Кузнечик, его SBox и потерянные сиды