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

    Привет, %username%!



    Недавно мы вернулись с конференции EuroCrypt 2019, где познакомились с чрезвычайно умными людьми и заодно узнали новые, чрезвычайно обидные факты о ГОСТовском SBox.

    Так что, это второй подход к снаряду. Исправленный и дополненный.

    В этот раз не будет непонятных красно-синих слайдов, зато будут оригинальные документы из комитета ISO c объяснениями авторов Кузнечика.

    И даже челлендж в конце!

    Поехали.

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

    Chosen Plaintext Attack (CPA)


    Начнем мы с базовой модели атаки на блочные шифры.

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

    Блочный шифр в данной ситуации можно рассматривать как псевдослучайную подстановку. Функцию, которая блоку открытого текста сопоставляет блок шифротекста таким образом, что связь между ними определить невозможно.

    Идеальный блочный шифр можно представить себе как большую таблицу, где по горизонтали будут все возможные ключи от 000...000 до 111...111, по вертикали — все возможные открытые тексты тоже от 000...000 до 111...111, а на месте их пересечения — случайным образом сгенерированные шифротексты, которые однозначно связывали бы пару «ключ — открытый текст». Создать такую таблицу в реальной жизни не представляется возможным из-за её размеров, поэтому её эмулируют с помощью различных алгоритмов блочного шифрования.

    Атаку на блочный шифр можно назвать успешной если мы можем определить «неслучайность», с которой алгоритм выбирает шифротексты, соответствующие открытым текстам. Эта неслучайность и позволяет в самых худших случаях вычислить ключ шифрования.

    (Не)линейность


    Процесс шифрования в блочном шифре можно представить простой формулой
    C = M х K
    где C — шифротекст, M — открытый текст, K — ключ шифрования, а x — блочный шифр.

    Эта формула визуально похожа на школьную формулу линейного уравнения y = kx+b, графиком которой является прямая линия.

    Любую прямую линию можно восстановить всего по двум точкам. И в то же время мы очень не хотим, чтобы по двум парам открытый текст — шифротекст можно было восстановить ключ шифрования. Для этого в алгоритмы шифрования добавляют специальные прослойки, отвечающие за нелинейность. Эти прослойки призваны не допустить возможность вычисления связи между открытым текстом, шифротекстом и ключом.

    Их качество критически важно для безопасности алгоритма.

    Что такое SBox?


    Это та самая нелинейная прослойка. Функция, которая в случае Кузнечика и некоторых других шифров однозначно сопоставляет одному байту другой байт.

    Очень часто она задаётся простой таблицей соответствия, например такой:



    Потому что иначе её не описать. На первый взгляд.

    Почему SBox важен?


    Потому что это единственная нелинейная функция во всём шифре. Без неё взломать шифр будет не просто, а очень просто, представив его в виде системы линейных уравнений. Поэтому к функции подстановки так много внимания. Есть даже практические задания по взлому AES с линейным SBox.

    Почему нельзя создать один безопасный SBox на всех?


    Проблема в том, что криптография не является точной наукой. Единственным доказуемо стойким алгоритмом шифрования является одноразовый блокнот. Всё остальное — робкие попытки уместиться в диапазон доступных нам знаний, набор которых не так уж велик.
    Мы точно не знаем, стоек ли RSA или AES или эллиптические кривые, но мы знаем, что такие-то и такие-то вещи делать точно нельзя. Всё что между — творчество.

    Отсюда и постоянная паранойя по поводу различных «магических констант» и прочих моментов, которые авторы алгоритмов преподносят как безопасные, но не могут это доказать.

    Как создают SBox?


    Различных вариантов SBox — 256!, это примерно 21684. Выбор большой и за годы криптоанализа были выработаны метрики и характеристики, которыми должен обладать SBox, стойкий к известным на сегодня атакам. Конечно, создатели таблиц думают на годы вперед и пытаются создать подстановки, которые были бы стойки даже к атакам, придуманными через 5-10 лет. Но это уже больше из разряда магии и шаманства.

    Есть два принципиально разных подхода к созданию SBox.

    Первый — случайный поиск. Разработчики генерируют случайные таблицы, смотрят на их характеристики и отсеивают те, которые не подходят. Так продолжается до тех пор, пока разработчики не удовлетворятся найденным.

    В цивилизованном мире это происходит, например, следующим образом:

    1. Берется некоторое начальное значение, например цитата из книги или первые несколько цифр числа Pi
    2. Прогоняется через хэш
    3. Результат хэширования используется как данные для формирования SBox
    4. Если SBox не подошел — берем текущий хэш и возвращаемся к п.2

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

    Знаете, куда делись сиды от главного симметричного алгоритма страны? Потерялись! Я думал их специально не выдают, секрет там или что, но российские коллеги на EuroCrypt рассказали, что во время разработки алгоритма в 2007м году никто почему-то не думал, что придётся обосновывать дизайн таблицы подстановок, и значения из которых она получилась, были навсегда утеряны. История красивая, вот только не стоит забывать, что алгоритм создавался не в школе на перемене, а в недрах ФСБ.

    Второй способ — создать SBox самим, руководствуясь доступным математическим аппаратом. Так поступили авторы AES и у них неплохо получилось. Если сравнить нелинейность SBox AES, SM4(китайский стандарт) и Кузнечика (он использует тот же SBox, что и хэш Стрибог), то результат будет не в пользу последнего
    AES non-linearity (min, max) = (112.0, 112.0)
    SM4 non-linearity (min, max) = (112.0, 112.0)
    Streebog non-linearity (min, max) = (102.0, 110.0)
    Код вычисления нелинейности использует Walsh Transform и доступен здесь

    Документы


    В моё распоряжение попали два документа из ISO. В первом дизайнеры Кузнечика объясняют как создавали SBox, в другом комитет обсуждает их доводы.



    из первого документа нам интересны две цитаты:



    и



    Надеюсь, тема с «Лео Перрин сам придумал, что авторы искали SBox случайным образом» теперь закрыта.

    Из объяснений дизайнеров следует, что

    1. Они действительно искали SBox псевдослучайным образом (учитывая критерии безопасности)
    2. Никакой скрытой структуры в нём якобы заложено не было.

    И вот в этом месте они капитально облажались.

    Что такое структура?


    Структура, применительно к таблице подстановки — некий алгоритм, который эту таблицу описывает.

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

    Напротив, если вы ищите SBox случайным образом, то таких структур в нём быть не должно и проблема с SBox Кузнечика в том, что слова дизайнеров алгоритма очень сильно расходятся с фактами. Про саму структуру кузнечика под названием TKLog я писал в предыдущей статье, в этот раз поговорим о структурах вообще.

    Колмогоровская сложность


    Это результат исследований из последней статьи Лео Перрина на тему Кузнечика.

    Основной контраргумент к статьям про структуры в SBox Кузнечика в том, что «практически в любом SBox можно найти какую-то структуру, если захотеть». И «хоть вероятность нахождения структуры, которую нашел Лео, ничтожна мала, если бы был другой SBox, то нашлась бы другая, тоже с ничтожной вероятностью».

    Допустим, это так. Но. Как оказалось, можно вывести некую «степень заструктурированности» SBox, которая не зависит от вероятности попадания в ту или иную структуру.

    Зато она зависит от размера алгоритма, который нужен для генерации данного SBox!

    Это и называется Колмогоровской сложностью.

    Если представить SBox как строку байт, то в случае случайной строки не должно быть алгоритма, который генерирует эту строку и при этом сам меньше этой строки.

    Применительно к кузнечику


    Итак, размер SBox — 256 байт. Перед вами читабельная версия кода авторства Лео Перрина, которая реализует таблицу Кузнечика. На входе — исходный байт, на выходе — соответствующий ему байт из SBox Кузнечика. Главным условием для такого алгоритма является запрет на использование языковых или платформенных структур, читерски сокращающих размер программы. К примеру, если где-то внутри стандартной библиотеки есть константа, содержащая половину SBox, то использовать её нельзя.

    Челлендж — написать программу, размер которой будет меньше, чем SBox.

    unsigned char p(unsigned char x){
        unsigned char
            s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
            k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};    
        if(x) {
            unsigned char l=1, a=2;
            while(a!=x) {
                a=(a<<1)^(a>>7)*29;
                l++;
            }
            if (l%17) return 252^k[l%17]^s[l/17];
            else return 252^k[l/17];
        }
        else return 252;
    }
    

    Наша задача показать, что в SBox Кузнечика заложена «сильная» структура, такая, что её размер сильно меньше размера самого SBox. Код выше занимает 416 символов, что пока многовато.

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

    p(x){
      unsigned char
          *t="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",
          a=2,l=0,b=17;
      while(x && (l++,a^x)) a=2*a^a/128*29;
      return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
    }
    

    Этот исходник занимает уже 196 байт, что уже на 23% меньше чем сам SBox. Но мы идём дальше. Если убрать лишние пробелы и переносы строк, то лучшая на сегодняшний день рабочая версия С кода выглядит так:

    p(x){char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}
    

    Чтобы вывести на экран SBox можно воспользоваться следующим простым кодом:

    int main() {
       for(int i = 0; i < 256; i++){
           if (i % 16 == 0){
               printf("\n");
           }
        printf("%d, ", (unsigned char)p(i));    
       }
    }
    

    Можете запустить и убедиться, что код действительно работает и соответствует SBox Кузнечика.
    Эта версия С кода занимает 153 символа. Поскольку все символы кода — валидные ANSI, то можно считать каждый символ равным 7 битам, а не 8. Таким образом имеем 1071 бит или ~134 байта. А это уже почти половина от размера таблицы, хоть и всё еще текстовый исходник.

    Что касается скомпилированного кода, то для архитектуры Cortex-M4 Лео удалось скомпилировать код размером всего 80 байт (ассемблерный код есть в статье).

    Это тоже не предел, уже есть рабочие имплементации размером меньше чем 64 байта.

    И что, это означает бекдор?


    Нет, мы не можем говорить о наличие бекдора в Кузнечике, пока он не будет стопроцентно найден.

    Но и структура, в 4 раза меньшая чем Sbox, не может попасть в SBox случайно, что бы там ни говорили авторы и защитники Кузнечика.

    Только вдумайтесь. Реальный размер таблицы подстановки Кузнечика, найденной «псевдослучайным поиском» сравним с размером таблицы AES (60 символов, GolfScript), у которого структура была известна с самого начала.

    Есть или нет бекдор в Кузнечике — мы не знаем. Но в том, что авторы соврали — сомнений не осталось.

    Выводы


    Дизайнеры Кузнечика неоднократно декларировали отсутствие скрытых структур в важнейшем элементе алгоритма — SBox. Но исследования показали, что процесс создания таблицы подстановки был далёк от случайного поиска. Даже с теми критериями, которые описали авторы в своём объяснении.

    Если авторам верить (а по эту сторону границы им безоговорочно верят), то они случайно наткнулись на структуру, размер которой в 4 раза меньше, чем сам SBox. Повторюсь, криптография — не точная наука и достаточно малейшего повода для сомнения, чтобы разбудить в людях паранойю. В данной ситуации размер повода в 4 раза более чем достаточный, чтобы считать алгоритм, разработанный в недрах наших прославленных силовых структур, очень подозрительным. Нет, ну правда, смешно когда наши доблестные ФСБшники включают школьников и говорят, что 11 лет назад этот алгоритм начинал разрабатываться чуть ли не в свободное время, поэтому они в итоге потеряли и сиды и скорее всего программу, которая генерировала таблицу подстановок. Просто так получилось, что side project стал национальным стандартом ¯\_(ツ)_/¯.

    Послесловие


    Сейчас в ISO идёт полугодовой период исследования Кузнечика на наличие бекдора. По его результатам будет принято решение о дальнейшей судьбе алгоритма как международного стандарта. Либо процесс будет продлён еще на пол года.

    Со слов людей, лично знакомых с дизайнерами Кузнечика, алгоритм был разработан в то время, когда никто не требовал объяснять почему SBox имеет именно заданный ими вид. Поэтому никто не сохранил стартовые значения для перебора. Аргумент, как по мне, слабоват.

    На конференции я поговорил с автором Curve25519 Daniel J. Bernstein и Tanja Lange, которые являются членами комитета ISO по стандартизации новых алгоритмов. Они сказали, что предоставлять сиды не обязательно, достаточно показать саму программу, которая генерировала этот злосчастный SBox. Этого сделано до сих не было и вероятность этого события не слишком большая. Ибо секрет.

    Вообще в протоколе обсуждения можно найти много интересных деталей и реплик, позволяющих понять ход мыслей членов комитета.

    Что касается дальнейшей судьбы алгоритма, вероятность принять его как международный стандарт довольно низкая. Это признают как члены ISO, так и сотрудники российских компаний, с которыми я познакомился на EuroCrypt.

    Более того, по последним данным есть ненулевая вероятность выпиливания уже принятого в стандарт хэша Стрибог (с тем же SBox), а так же RFC 7801, в котором описан Кузнечик.

    Можно было бы создать новый, правильный по всем канонам SBox, этим даже ради интереса занялись в одной из российских компаний (кстати, обещали результаты показать). Но проблема в том, что в России Кузнечик уже стандартизирован, реализован в железе и внедрён везде, где только можно. Замена Кузнечика на Кузнечик V2 обойдется в очень круглую сумму.

    Девяностые и нулевые давно позади. Пора перестать создавать алгоритмы шифрования в подвальных шарашках и говорить, что «а кроме ФСБ никто ничего подобного создать в России не может, у нас выбора нет».

    Может хотя бы попробовать конкурс провести перед тем, как бросаться такими словами? И не забывать, что AES вообще-то не в США был придуман.

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

    Challenge!


    Нужно написать реализацию функции SBox Кузнечика, которая была бы по возможности еще меньше, чем найденная Лео и его коллегами. Но пойдут и те, что просто меньше 256 байт. Технические детали тут. Там же несколько примеров на разных языках. Самым успешным — слава, респект и уважуха за вклад в честную криптографию.

    Пока рекорд — 58 байт на языке Stax. Это меньше чем четверть от размера «случайно найденного» SBox.

    Спасибо за внимание.
    Virgil Security, Inc.
    106.64
    Мы превращаем программистов в криптографов.
    Share post

    Comments 138

      0

      Я же верно понимаю, что это таблица подстановок генерируется каждый раз снова при установке защищённого канала? (По типу приватных ключей) или же она единая на всю систему/страну? И при определении (подборе) данной таблицы можно говорить о компрометации вообще любой криптографии основанной на кузнечике?

        +13
        Эта таблица — константа. Она зафиксирована и общеизвестна. Но вот её характеристики вызывают много вопросов, т.к. это самый важный элемент всего алгоритма
          0

          Понятно, т.е она константа вычисляемая кодом
          на основе алгоритма, который (предположительно) выдаёт прогнозируемый результат?

            +9
            Таблица была встроена в Кузнечик просто как магический набор чисел. То, что внутри неё есть структура или «алгоритм» выяснилось позже благодаря реверс инжинирингу. Мы не знаем зачем он там, в этом вся загвоздка
              0

              А, понятно, т.е там даже не кодом вшита а прямо массивом чисел, это удивительно.

                +1
                Это распространенная практика, но от неё потихоньку уходят
                  0
                  Я бы так не сказал, Sbox'ы как раз обычно (в софте) большой таблицей вбивают, а не вычисляют. Или вы про «от неё потихоньку уходят» имеете в виду «как была сгенерирована таблица»?
                    +1
                    именно
                      +1

                      А каким образом если будет установлено, что sbox не случайный — это поможет взлому или докажет Бэкдор? Мне кажется этого не хватает в посте.

                        +6

                        Собственно уже установлено что sbox не случайный, ибо вероятность подобных совпадений — примерно как выиграть во все лотереи по одному билету (набору цифр).


                        Говорить о бекдоре и "поможет взлому" — нельзя без доказательств, т.е. будет крайней желтизной. Надо отдать должное Scratch за то что не перешел эту грань (хотя рядом) и в статье всё есть, включая основной вопрос — Зачем отрицалось наличие структуры.




                        Тем не менее, всё таки стоит явно отметить, что наличие структуры в sbox — это не плохо и не хорошо само по себе, а не-идеальные mix/max нелинейности не облегчают атаки.

            0
            Если таблица «не секрет», зафиксирована и общеизвестна. В чем опасность что ее можно сгенерить алгоритмом в четверть самой SBox?
            Для задачи дешифрования/поиска ключа эта часть уже известна. Только экономия кода для программы.
              +5
              Где гарантия, что этот алгоритм при определенных условиях не превратит SBox в линейный?
                0
                Кстати, я, видимо, полный тупица. Почему не применяются методы оптимизации при создании SBox? Если у нас есть одна или несколько loss functions (результат преобразования Уэлша, или оценка энтропии, или какая-нибудь корреляция со сдвигом), почему нельзя взять генератор шума (квантовый, атомарный, да хоть КВ-приёмник) и получать с него блоки по 256 байт в течение некоторого времени и взять имеющий наибольшую энтропию?
                  0
                  А ещё можно посадить миллион обезьян за пишущие машинки и ждать пока они напишут войну и мир. По эффективности будет примерно то же самое.
                    +2
                    Методы применяются самые разные. В некоторых случаях даже используют генетические алгоритмы. Свойств S-box'ов очень много и не в энтропии дело, а в первую очередь в линейности и диффиренциальном «поведении» S-box. Ещё есть много работ по оптимизации S-box для аппаратной реализации и даже для атак по сторонним каналам. Вот S-box для PRESENT просто перебрали все возможные 4х4 S-box. Короче, всё очень сложно :)
                  +7
                  Если я правильно понимаю ситуацию, опасность в том, что авторы соврали насчёт алгоритма получения таблицы. Из этого запросто может следовать, что реально использованный алгоритм реализует ещё какие-то ограничения на таблицу. В качестве одного такого ограничения — и вот тут опасность переходит в практическую плоскость — может быть существование «линеаризации» S-Box с помощью того же или иного известного (тому, кому надо) алгоритма.
                    +5
                    Проблема в том, что неслучайность SBox может оказаться намеренной и остаблять сам алгоритм шифрования например создавая целый класс слабых ключей.
                      –6

                      Осмелюсь повторить, что умеренное ослабление — крайне маловероятно, мягко говоря, ибо 275 УК как "Деятельность, направленной против безопасности Российской Федерации").


                      Т.е. вижу примерно один сценарий (авторы Стриборг/Кузненик получили готовый или исправленный SBOX и были не в курсе его структуры). Как вариант, возможно повторение истории.

                        +1

                        Безопасность страны и безопасность отдельных ее граждан — мягко говоря, немного разные вещи.

                      +7
                      Когда разработчики DES (Да, того самого 1977 года) отправили алгоритм в АНБ, то АНБ полностью переработало все SBox (коих, к слову, 8 штук). Лет через 10, после того как был открыт дифференциальный криптоанализ (ну или стал общеизвестен) выяснилось что переработанные SBox устойчивы и к нему, а вот изначальные снижали стойкость шифра к этому методу. Так что структура всё таки важна. Кроме того есть целая система оценки нелинейности SBox и там требований и матана чуть больше чем… очень много.
                        +1

                        Проблема в том, что специально подобранный SBox превращается в маленький "асимметричный" шифр. Который снижает стойкость всего алгоритма шифрования.
                        Если это так, то тот, у кого находится "закрытый" ключ от SBox, может проводить эффективную атаку на криптоалгоритм.
                        Если SBox можно сгенерировать с помощью 58 байт, то, возможно, придется перебирать только 2^58 вариантов для поиска ключа вместо 2^256 вариантов.

                    +2
                    А что если авторы алгоритма не врут и действительно использовали первый подход со случайной генерацией таблиц? Но по какой-то причине вместо случайных чисел взяли слабый, предсказуемый ГПСЧ.

                    «Миром правит не тайная ложа, а явная лажа» (с).
                      +4

                      В таком случае авторам надо посыпать голову пеплом, сдать все регалии на склад и пойти заново учиться, перед этим явно указав, какой именно ГСПЧ они брали и что это за "какая-то причина". А не отмахиваться со словами "идите нахуйпрочь, я фея"

                      +2
                      Что касается дальнейшей судьбы алгоритма, вероятность принять его как международный стандарт довольно низкая. Это признают как члены ISO, так и сотрудники российских компаний

                      Похоже так и не дождаться шифрсьютов для TCL/HTTPS с российскими криптоалгоритмами, и не увидим мы этой поддержки в браузерах от Google, Mozilla и других.

                        –7

                        Это будет означать наличие двойных стандартов и дискриминации.

                          +6

                          Это будет означать, что он им не нужен — не более.

                            0

                            Не согласен с формулировкой.
                            Подобное противопоставление (они — мы) просто еще один шаг к "чебурнету".
                            В итоге просто будут функциональные форки/клоны OpenSSL (и других библиотек), отдельные версии браузеров и т.д.


                            Хотя такой сценарий нельзя назвать совсем плохим — будет создан спрос на соответствующие компетенции и их локальную наработку.

                          +4

                          Жалко то как!
                          (На самом деле — нет)

                            0
                            Помните про предложение обязать гос. сайты использовать российскую криптографию? Если зарубежные УЦ, в т. ч. Let's Encrypt, не будут её поддерживать, то многие из этих сайтов перейдут обратно на нешифрованный HTTP, потому что необходимость HTTPS/TLS зачастую не указывается в ТЗ. Будут перс. данные россиян нешифрованные ходить по сетям, как десять лет назад.
                              +3

                              На зло маме отморозить уши? Ну и что в этом плохого? В чем проблема использовать не зарубежного УЦ а местного, но сертификаты с нормальным шифрованием?

                                +1
                                В том, что они захотят денег и автоматизация уровня certbot будет роскошью.
                                  –1
                                  «Как это, вы не хотите поддерживать отечественную экономику?»
                          +1

                          Scratch, мне кажется стоит аккуратно обозначить в статье возможные причины "мухлежа со структурой".


                          Уместно вспомнить об истории с таблицей замен в Магме, где таблица замен была загружаемым параметром.


                          IMHO для Стрибог авторы взяли уже готовый S-BOX, либо он был им предоставлен в какой-то момент. Соответственно, я допускаю, что авторы не знали об алгоритме генерации, т.е. не являются авторами S-BOX. Поэтому и решились давать объяснения в виде "поиска от случайного" и затем "потеряли сиды".


                          В принципе это соответствует практическим традициям применения крипто-схем с таблицами замен. Причем как с отечественными традициями (явная выдача разных таблиц), так и с зарубежными (тоже самое, только "не столь публично" как у нас).


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


                          Думаю, стало неожиданным, что алгоритм генерации был восстановлен так быстро. Предполагаю был с умом запущен подбор набора уравнений в GPU-кластере и т.п., но и утечки нельзя исключать. Ну а для авторов Стриборга и Кузненича это стало facepalm-ом.




                          Крики "бэкдор" и "мы все умрем" IMHO только от "около диванных" аналитиков. Тут у меня несколько тезисов:


                          • Наличие структуры не говорит о бэкдоре или слабости. В массе S-BOX-ов есть структура. Нужен глубокий анализ с выводами/доказательствами и никак иначе. Мягко говоря, крайне маловероятно, что в S-BOX умышленно внесли слабость (ибо 275 УК). IMHO структура как-раз от обратного, т.е. для стойкости (но безусловно хотелось-бы увидеть доказательства).
                          • Факт замалчивания структуры неприятен и по-хорошему заставляет ждать публичных результатов криптоанализа "еще три года" после раскрытия алгоритма генерации S-BOX. Т.е. если вы НЕ попадаете под требования регулятора и вольны не использовать Стрибог/Кузненик, то еще года три (видимо) будете относится к ним как к молодым (не проверенными временем) крипто-схемам.
                          • К заявлениям "в наших SBOX не структуры" стоит относится очень осторожно. Это примерно невозможно доказать. Соответственно, утверждение "в SBOX не структуры" никогда не означает что структуры действительно нет, и нас ждет еще несколько каминг-аутов.



                          Гипотетическая смена таблицы замен не должна стать проблемой, поскольку AFAIK чуть менее чем во всех отечественных "железных" реализациях предусматривается такая возможность (закладывается в требования).

                            0
                            Основная проблема в том, что «структура» S-box Кузнечика коррелирует со «структурами» других шагов алгоритма.
                            Это повышает вероятность того, что существует достаточно простое алгебраическое описание работы шифра.
                            Тот, кому известно просто алгебраическое описание, может взламывать шифр.
                            Направление мысли понятно?
                              +1

                              Не-не, там ещё хуже — только два возможных значения у каждого бита и только две базовые операции с ними (причем одна вообще унарная!).


                              ;)

                                0
                                К вашему сведению, алгебра не ограничивается бинарной логикой.
                                Начнем с простых примеров.
                                Какая система уравнений проще, на ваш взгляд?

                                Вот эта: 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)))
                                  –1

                                  Тут вы немного путаете "божий дар с яичницей".


                                  Очевидно, что для анализа удобнее иметь "алгебраическое описание" компактно отражающее ход мыслей авторов (т.е. дизайн), а не реверсить его из таблицы чисел.
                                  И как уже писал, сокрытие факта наличия структуры (это в первую очередь) и самой структуры (это во вторую очередь) не является плюсом для публичного стандарта.


                                  Однако, мыслимое вами "алгебраическое описание" не будет доказательством наличия/отсутствия тех или иных свойств, хотя (возможно!) позволит легче выполнить такое доказательство (публичный аудит).

                                    0
                                    Я ничего не путаю.
                                    Алгебраическое описание — это также инструмент оптимизации системы уравнений в целях взлома.

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

                                    Наличие простого (и согласованного!) алгебраического описания для двух последовательных шагов алгоритма (к тому же, скрытого авторами) — это очень подозрительно, я бы сказал.
                                    В случае Стрибог так и есть. Читаем Leo Perrin.
                                    Два последовательных шага алгоритма описываются операциями по модулю одного и того же полинома, представляете?
                                    Просто нет слов.
                                    Наверняка, кто-то в недрах секретных НИИ получил медаль за это… ну или пулю в затылок.
                                      +1
                                      Я ничего не путаю.
                                      Алгебраическое описание — это также инструмент оптимизации системы уравнений в целях взлома.

                                      Нет, вы всё-таки путаете "описание алгебраической структуры" с чем-то из списка: "описание алгебраической атаки", "доказательство стойкости против таких-то видов атак", "системой уравнений или её выводом".


                                      Вам накидать статей, как шифры семейства 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.

                                        0
                                        Но из наличия структуры не следует, что какая-то атака становится проще.

                                        В ваших постах очень много фраз «не доказано/не следует».
                                        А давайте тогда просто считать надежными все шифры, которые еще не взломаны.
                                        Вы же любите бинарную логику? Шифр либо уже взломан, либо надежен. Классно, да?

                                        Только вот криптоанализ — дело длинное и дорогое.
                                        От первого подозрения до полноценного взлома иной раз проходят десятки лет.
                                        Криптоанализировать все шифры нет возможности, не хватит спецов.
                                        Поэтому подход «не доказано/не следует» не прокатывает.

                                        Прокатывает отбрасывать шифры при первых подозрениях.
                                        Шифров не жалко, новых нарожают.
                                        В первую очередь стоит отбрасывать шифры, разработчики которых лгут.

                                        Термин «подозрительно» тут не совсем уместен, это FUD.

                                        Предлагаете вообще убрать FUD из криптографии?
                                        И сразу заживем?
                                          0
                                          В ваших постах очень много фраз «не доказано/не следует».
                                          А давайте тогда просто считать надежными все шифры, которые еще не взломаны.
                                          Вы же любите бинарную логику? Шифр либо уже взломан, либо надежен. Классно, да?

                                          Давайте еще раз переформулирую.
                                          Наличие структуры в s-box может равновероятно говорить как о стойкости к каким-то атакам, так и о бекдоре.
                                          Поэтому без аналитических доказательств говорить что наличие структуры "подозрительно" или "плохо" — это либо FUD и манипуляция, либо недопонимание.
                                          В массе других случаев это может быть "подозрительным", но не здесь.


                                          Другое дело — сам факт "отрицания" наличия структуры при заходе в международный комитет. Но свои варианты причин уже озвучивал.


                                          Только вот криптоанализ — дело длинное и дорогое.
                                          От первого подозрения до полноценного взлома иной раз проходят десятки лет.
                                          Криптоанализировать все шифры нет возможности, не хватит спецов.
                                          Поэтому подход «не доказано/не следует» не прокатывает.

                                          Тут явная манипуляция — попытка навязать неверные выводы озвучив пару верных утверждений.


                                          Прокатывает отбрасывать шифры при первых подозрениях.
                                          Шифров не жалко, новых нарожают.

                                          «А сегодня криптоанализом не все могут заниматься. Вернее заниматься могут не только лишь все, мало кто может это делать» — вот буквально это и наблюдаем ;)


                                          Хотя никто не запрещает заниматься анализом (каких угодно шифров) и публиковать результаты, что и сделал Leo Perrin. Кто угодно может оценивать эти результаты, делать выводы и т.д.


                                          Однако, часть работы регулятора связанных с ним структур в том, чтобы обеспечить выполнение соответствующих протоколов, в том числе обеспечить криптоанализ и доказательство стойкости для национальных крипто-стандартов со стороны "специально обученных людей". При этом соответствующие обсуждения и доказательства не обязаны быть публичными.


                                          В первую очередь стоит отбрасывать шифры, разработчики которых лгут.
                                          Ложь — это преднамеренное искажение информации.
                                          Как уже писал, я не склонен считать что "официальные" разработчики Стрибог/Кузненик знали о структуре s-box. Проще говоря, думаю, они не являются авторами s-box.
                                          А вот вопрос "как так получилось" — как раз становится более интересным.
                                0

                                Если без шуток, то ваше "направлением мысли" НЕ в сторону логики, алгебры и метематики.

                                  –1
                                  Будьте добры пояснить, куда же по-вашему идет мое направление мысли.
                                  А то я теряюсь в догадках.
                                    0
                                    Основная проблема в том, что «структура» S-box Кузнечика коррелирует со «структурами» других шагов алгоритма.

                                    Для точности: Этот многострадальный S-box был сделан для Стрибога, а потом использован в Кузнечике.


                                    Не могли бы мы чуть более подробнее пояснить, какие именно, на ваш взгляд, преобразования, структуры или шаги в Стрибог или Кузнечике "коррелируют" с процедурой генерации S-Box?


                                    Это повышает вероятность того, что существует достаточно простое алгебраическое описание работы шифра.

                                    Как уже писал "про лотерею" — наличие структуры можно считать доказанным фактом. Поэтому "достаточно простое алгебраическое описание" существует с такой достоверностью, что её вероятность крайне сложно повысить.


                                    Тот, кому известно просто алгебраическое описание, может взламывать шифр.

                                    Нет, это неверный вывод. Пока нет доказательств (наличия/отсутствия тех или иных свойств), никакое знание "просто формулы" не позволяет сделать подобных выводов (как и обратных).
                                    Т.е. видя формулу модульной экспоненты, но не зная всего что "стоит за" RSA и самой проблемы факторизации (и её отсутствия в некоторых случаях), вы не сможете ничего сказать о стойкости.


                                    Направление мысли понятно?
                                    Нет (
                                      0
                                      Нет, это неверный вывод. Пока нет доказательств (наличия/отсутствия тех или иных свойств), никакое знание «просто формулы» не позволяет сделать подобных выводов (как и обратных).
                                      Т.е. видя формулу модульной экспоненты, но не зная всего что «стоит за» 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
                                        +1
                                        Вам не кажется, что требования к асимметричным шифрам сильно отличаются от требований к симметричным шифрам и хеш-функциям?
                                        А у хеш функций вообще не должно быть простого описания.
                                        И вроде как это всем понятно, даже самим авторам 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 и (пока) НЕ объяснили его происхождение после раскрытия структуры.

                                +1
                                Мягко говоря, крайне маловероятно, что в S-BOX умышленно внесли слабость (ибо 275 УК).
                                Да шо ж вы всё со своим УК уже в какой раз носитесь, детский сад, ей-бо. Такие вещи делаются не штатным программистом втихушку и по личной инициативе, чисто ради ловли лулзов или скрытого профита, а самой государственной корпорацией или по её прямому заказу (а при методах работы ведомства-заказчика, если копнуть, по множеству статей в принципе противоречащих Конституции, уровень какого-то там УК — это вообще ни о чём).
                                –1
                                Непонятно, почему нельзя просто взять шумящий диод, и нагенерировать с его помощью этот злосчастный S-Box.
                                  +3
                                  Потому что сгенерированный случайно не обязательно будет равен хорошему. Случайность она на то и случайность, что там может попасться что-нибудь вроде «1,2,3,4,50», и это снизит стойкость. Поэтому случайно сгенерированные данные надо еще проверять.
                                    +1
                                    Это-то как раз можно. Но при этом нужно что-то ответить на вопрос «А чем докажете, что вы туда бекдор не вставили?». Наши на этот вопрос отвечают что-то вроде «мамой клянёмся». Ок, такой ответ в принципе тоже возможен, хоть и не слишком убедителен. Но как тогда объяснить нашедшуюся структуру? Шумящий диод такого не генерирует.
                                    По сути, если раньше просто не было оснований верить в отсутствие закладок в этом s-box, то сейчас появились серьёзные основания считать, что закладки таки есть.
                                      +5
                                      Государство — гражданам:
                                      У суда нет оснований не доверять сотруднику полиции…
                                      Технически подкованные граждане — государству:
                                      У нас нет оснований доверять любым «алгоритмам» от государственных структур, не прошедшим независимый аудит.
                                        +1
                                        Шумящий диод такого не генерирует

                                        случайность на то и случайность, что там может быть вообще что угодно, а человек очень силён в поисках структур, последовательностей и алгоритмов
                                          0
                                          Где-то я эту отмазку уже слышал. Ага, вот: dilbert.com/strip/2001-10-25
                                          image

                                          Этот аргумент разбирается в разделе «Колмогоровская сложность».
                                      +1
                                      Кто бы мне популярно объяснил, что такое массивы s[] и k[] и какова их роль в алгоритме генерации и случайность происхождения?
                                        +1
                                        Если совсем в двух словах — эти два массива параметризуют структуру под названием TKLog, о которой я писал в предыдущей статье. Разные значения в массивах дадут нам разные варианты структуры TKLog
                                          0
                                          Ну, в прошлой статье, вы толком ничего не объяснили, сослались на «оригинал», причем не авторов стрибога, а того самого реверсера. Та статья совсем для узкого круга понятна, из неё я только понял, что алгоритм TKLOG как-то связан с Пи. Возможно, эти два массива констант вынуты оттуда же?
                                          Не то, чтобы я придираюсь и занудствую. Но, эти два массива вынуты вами непонятно откуда, в оригинальной статье я таких последовательностей не нашел. Возможно, там был простенький их рассчет, но тогда не понятно, почему бы именно такой расчет не включить в программу?
                                            +1
                                            Чтобы объяснить, почему TKLog генерирует таблицу Pi, пришлось бы перевести почти весь whitepaper. Возможно, станет немного понятней из объяснений Лео. По ссылке есть частичное объяснение кода и формул, которые к этому коду привели.
                                              +1
                                              Ну вот по этой ссылке стало гораздо понятнее, спасибо.
                                              +2

                                              Рискну пока идут тесты ;)


                                              Leo Perrin нашел "структуру", из чего следует что у Стрибог/Кузнечик есть определенные "свойства".
                                              Эти свойства изложены в разделе 2.2 его статьи.
                                              Что в этом "плохого" описано в разделе 2.3.
                                              Если из предыдущего раздела и заключительного 2.4 попытаться сделать выводы, то:


                                              1. Основная проблема в том, что "структура есть", а авторы Стрибог/Кузнечник утверждали обратное.
                                              2. Условия для бэкдора (по методу из диссертации Арно Банье) в Кузненике не найдены.
                                              3. Взаимодействия s-box c линейныйм слоем (всем остальным) в Стрибог не понято.
                                              4. Векторы атак не найдены, но "подозрительно, ибо не понятно".
                                              5. Ай-я-яй, так нельзя...
                                                –2
                                                Основная проблема в том, что «структура есть», а авторы Стрибог/Кузнечник утверждали обратное.

                                                Авторы шифра/хеша всего лишь соврали о его дизайне.
                                                Подумаешь, проблема, правда? Это все культурные традиции.
                                                И вообще, хватит распространять FUD.
                                                Давайте поскорее стандартизируем его и включим во все реализации SSL.
                                                Ведь чем больше разных шифров поддерживается в стандарте SSL, тем секьюрнее.

                                                  +2
                                                  Авторы шифра/хеша всего лишь соврали о его дизайне.
                                                  Подумаешь, проблема, правда?

                                                  IMHO вы пытаетесь "громче хайпануть", а НЕ разобраться в ситуации,
                                                  Свое отношение к этой ситуации и возможные причины уже излагал.


                                                  Это все культурные традиции.

                                                  Теперь точно один минус от меня.


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

                                                  Стрибог/Кузнечик уже "стандартизированы" в документах российского регулятора и RFC.
                                                  Этого уже IMHO достаточно как для включения реализации в существующие открытые реализации SSL/TLS, так и для разработки отечественных.
                                                  При этом Стрибог/Кузнечик вовсе не обязаны быть международным стандартом, быть одобренными или всем нравиться.


                                                  Тем не менее, попытка "зайти в ISO/IEC" со скрытой алгебраической структурой, дискуссии об отсутствии такой структуры и попытка объяснить её обнаружение "просто совпадением" — для меня выглядят (мягко говоря) странными и нерациональными. Поэтому я склонен предполагать наличие каких-то (пока) скрытых причин или обстоятельств, начиная от банального незнания авторами факта наличия структуры (получили готовый s-box), до 275 УК и даже игр разведок.


                                                  Но всё это, до аналитических доказательств, не говорит о наличии бэкдора или, наоборот, о какой-то стойкости к (пока) нераскрытым атакам.

                                                    0
                                                    Теперь точно один минус от меня.

                                                    Да пожалуйста.
                                                    Затыкать рот неугодным — это тоже ваши культурные традиции.
                                                    Я минусы не ставлю принципиально, это мои традиции.

                                                    IMHO вы пытаетесь «громче хайпануть», а НЕ разобраться в ситуации,
                                                    Свое отношение к этой ситуации и возможные причины уже излагал.

                                                    Хайпанул Leo Perrin. Чувака ждет прекрасная карьера. Мне-то чего хайповать?

                                                    Меня поражают ваши упорные попытки оправдать Стрибог/Кузнечик, все эти «не следует», «не доказано», рассуждения про алгебру уровня форумного тролля, поэтому я и высказался.
                                                    Ведь авторы реально соврали, осознанно или нет.
                                                    Мне интересно, что бы вы сказали, если бы в шифре разработки US такое нашли.
                                                    Орали бы на весь хабр.

                                                    Стрибог/Кузнечик уже «стандартизированы» в документах российского регулятора и RFC.
                                                    Этого уже IMHO достаточно как для включения реализации в существующие открытые реализации SSL/TLS, так и для разработки отечественных.

                                                    Серьезно?
                                                    Будем включать всякие туземные шифры в продукты, которыми пользуется весь
                                                    мир?
                                                    Что дальше? Индийские шифры, пакистанские шифры?
                                                    Это очень стремно, с учетом возможности downgrade attack.
                                                    Или может добавим лишние ключи для сборки, типа CONFIG_RU_CRYPTO?
                                                    Тем самым усложняя и так непростой продукт и жертвуя безопасностью?
                                                    Может, вообще сделаем локализованные сборки OpenSSL, для каждой страны своя?
                                                      0
                                                      Я минусы не ставлю принципиально, это мои традиции.
                                                      Хм, то есть вы признаете, что вы дубль чьего-то полноправного аккаунта?
                                                        0
                                                        Не знаю, с чего вы это взяли.
                                                        Я лишь имел ввиду, что минусы в карму ограничивают мою возможность писать комменты.
                                                          0
                                                          Я минусы не ставлю принципиально, это мои традиции.
                                                          неполноценный ак не может ставить оценки
                                                          Ещё никогда Штирлиц не был так близок к провалу
                                                            0
                                                            Ещё никогда Штирлиц не был так близок к провалу

                                                            А может быть я просто ни разу не пробовал минусовать на Хабре?
                                                            Ваш бы уровень паранои — да в лоно криптоанализа.
                                                            Никому не верить, во всем сомневаться.
                                                              0
                                                              И правила ресурса не читали, я так и понял.
                                                                –2
                                                                Инструкций я тоже не читаю, если что.
                                                                Просветите же меня насчет правил.
                                                        0
                                                        Меня поражают ваши упорные попытки оправдать Стрибог/Кузнечик, все эти «не следует», «не доказано».

                                                        Оправдывать нет необходимости, ибо (еще раз) показанные структуры могут примерно равновероятно говорить как о стойкости к каким-то атакам, так и о наличии бэкдора.


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

                                                        Вам достаточно корректно были даны простые пояснения (aka vulgarized explanation) о том, что по критерию насколько "много букв" или "мало букв" в "описании" (системе уравнений) нельзя судить о трудоемкости решения и стойкости крипто-схемы.


                                                        Ведь авторы реально соврали, осознанно или нет.

                                                        Опять манипуляция, нельзя "соврать несознательно".
                                                        Свое мнение относительно авторов и происхождения s-box уже многократно озвучивал.


                                                        Мне интересно, что бы вы сказали, если бы в шифре разработки US такое нашли.

                                                        Ни разу не было и вот опять.
                                                        Т.е. "если бы" — не то склонение.


                                                        Орали бы на весь хабр.

                                                        Обычно я просто спокойно доношу свое мнение — в критических местах не должно быть недоверенных алгоритмов, софта и железа. А к RC6 у меня доверия гораздо больше чем к Rijndael.


                                                        Будем включать всякие туземные шифры в продукты, которыми пользуется весь
                                                        мир?

                                                        Это что, крипто-шовинизм?


                                                        Что дальше? Индийские шифры, пакистанские шифры?

                                                        Да, если они соответствующим образом сформируют/оформят свои национальные стандарты и RFC.
                                                        Иначе говоря и в том числе, если регуляторы в этих странах перестанут доверять AES и т.д.


                                                        Это очень стремно, с учетом возможности downgrade attack.

                                                        Стремно — это когда вы не можете выбрать набор шифров и приоритет их использования из-за ограничений инфраструктуры.
                                                        "downgrade attack" — здесь это манипуляция, FUD или недопонимание.


                                                        Или может добавим лишние ключи для сборки, типа CONFIG_RU_CRYPTO?
                                                        Тем самым усложняя и так непростой продукт и жертвуя безопасностью?

                                                        Продукт усложнили до нас, мягко говоря — это отдельная боль и история.
                                                        "Жертвовать безопасностью" — здесь это манипуляция, FUD или недопонимание.


                                                        Может, вообще сделаем локализованные сборки OpenSSL, для каждой страны своя?

                                                        Если координаторы "сообщества разработчиков" OpenSSL (и других проектов) будут против подключения национальных крипто-схем (не важно по каким причинам), то это неизбежно.

                                                          +1
                                                          к RC6 у меня доверия гораздо больше чем к Rijndael

                                                          Если не секрет, почему?
                                                            0

                                                            Циклически сдвиги зависящие от данных.

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

                                                                Всё верно.
                                                                Говоря о "зависящих от данных циклических сдвигах" именно это я и имел в виду.
                                                                Умножение тоже хорошо добавляет диффузии, из расчета "попугаев на операцию".


                                                                Тем не менее, условно "при прочих равных", сдвиги и умножения дают более "широкие S-блоки", т.е. больше диффузии.
                                                                Соответственно, условно "при прочих равных", достаточно меньшего количества раундов.

                                                                  0
                                                                  Логично. Меня только слегка смущает что в таких алгоритмах (с переменным размером дифузии зависящей от входных данных) нельзя сказать что-то вроде «не зависимо от исходных данных (ключ, сообщение) полная дифузия будет за N раундов». В алгоритмах с фиксированными смещениями и перестановками можно сказать что полная дивузия будет через 2 раунда (например) с любым значением ключа и любым текстом. Но это всё к слову о сложности анализа дифузии, и тот и другой метод по своему хороши.
                                                                    +1

                                                                    Немного не так.


                                                                    Сдвиги и умножения дают больше конфузии (по Шеннону), т.е. сильно усложняют алгебраическую зависимость выхода от входа.
                                                                    А так как операции за раунд не вносят (не должны) статистических сдвигов, то на следующем раунде диффузия как-бы "домножается" на конфузию. Проще говоря, диффузия во втором раунде также зависит от данных, то теперь эти данные перемешаны сами с собой.


                                                                    Проще говоря, имеется мощнейший лавинный эффект, который обеспечивает взаимное "домножение" диффузии и конфузии на каждом следующем раунде.


                                                                    Если посмотреть на это "со стороны данных", то можно подать на вход нечто, что отравит сдвиги или умножение в первом раунде. Но уже на следующем раунде это будет не возможно (не должно быть) при правильной процедуре разворота ключа. Таким образом, слабым ключом и подобранным текстом, можно отравить только первых два раунда, но дальше диффузия и конфузия будут примерно стабильны.


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

                                                            0
                                                            Стремно — это когда вы не можете выбрать набор шифров и приоритет их использования из-за ограничений инфраструктуры.
                                                            «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.
                                                              0

                                                              Ох, этак мы скоро смысл жизни будем обсуждать.


                                                              Давайте обозначим как Т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 умрет как международный проект. Т.е. будет форкнут или станет внутренним проектом страны "с самыми правильными шифрами".

                                                                0
                                                                Хорошо, мы пришли к какому-то общему знаменателю в технической части.
                                                                По части остального откомменчусь.

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

                                                                Будет дерьмовая ситуация, когда вам надо коннектиться к национальным сайтам стран N1 и N2 с шифрами K1 и K2, при этом вы не хотите использовать K1 и K2 на других сайтах.

                                                                То есть, надо где-то в доменной зоне прописывать набор разрешенных шифров и пойдет еще один виток усложнения веба.
                                                                А веба уже и так непростой и много где сломанный.
                                                                Чтобы этого всего не было, надо просто не пущать туземные шифры.
                                                                Пусть туземцы сами разбираются со своими проблемами, раз они их и создают.

                                                                Лечить инфраструктуру, включая OpenSSL и прочие аналогичные проекты, не допуская какое-либо навязывание или дискриминацию национальных стандартов.

                                                                Это все туземные комлексы у вас.
                                                                Сорри за прямоту.
                                                                Это проблемы скорее из области психотерапии, чем криптографии.

                                                                Хотя есть и решение из области криптографии.
                                                                Несколько туземных стран предлагают свои шифры, и в SSL работает их комбинация (с защитой от возможного сговора двух и более туземных стран).
                                                                Будет тормозить, но зато секьюрно.
                                                                  0
                                                                  Будет дерьмовая ситуация, когда вам надо коннектиться к национальным сайтам стран N1 и N2 с шифрами K1 и K2, при этом вы не хотите использовать K1 и K2 на других сайтах.

                                                                  Это не примерно неизбежная проблема "крипто-зоопарка".


                                                                  То есть, надо где-то в доменной зоне прописывать набор разрешенных шифров и пойдет еще один виток усложнения веба.
                                                                  А веба уже и так непростой и много где сломанный.
                                                                  Чтобы этого всего не было, надо просто не пущать туземные шифры.
                                                                  Пусть туземцы сами разбираются со своими проблемами, раз они их и создают.

                                                                  Есть несколько технологических решений. Один из вариантов "международный сертификат".
                                                                  Суть в том, что сертификат подписывается несколькими CA или международным ООН-CA, при этом внутри несколько подписей по нескольким крипто-схемам и несколько тегированых наборов шифров для разных стран.


                                                                  Соответственно, на стороне клиента проверяется "родная" подпись и выбирается "правильный набор шифров". MITM может вклиниться только взломам соответствующую подпись.

                                                            +2
                                                            В OpenSSL уже сегодня есть куча параметров, включающих и выключающих те или иные алгоритмы — в том числе по юридическим соображениям.
                                                +1

                                                А ничего, что колмогоровская сложность определяется с точностью до константы и невычислима?
                                                Похоже на передергивание фактов наукообразным способом.

                                                  0
                                                  Можете пояснить?
                                                    0

                                                    Для любой конечной последовательности существует интерпретатор, на котором программа, выводящая эту последовательность, занимает 1 бит.

                                                      0
                                                      Мы разве использовали такие интерпретаторы?
                                                        +1

                                                        Дело не в том, какой интерпретатор вы использовали, а в том, что колмогоровская сложность здесь не в тему.

                                                          0
                                                          Так себе у вас аргумент
                                                            0

                                                            Согласен, не одноходовочка. Желающим разобраться придётся напрячься.

                                                              0
                                                              Как видите, уже разобрались и написали научную работу, и не одну. Куда им всем до гениев с хабра
                                                                +1

                                                                За всю работу не отвечу. Но в тот момент, когда зафиксировали интерпретатор (какой и как написано в статье), с колмогоровской сложности они перешли к чему-то другому. Причём они сами пишут, что язык играет критическую роль.

                                                        0
                                                        Полагаю, такой вариант программы попадает под упомянутый в статье запрет использовать встроенные в язык и стандартную библиотеку константы, функции и прочее.
                                                          0

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

                                                    0
                                                    Пока рекорд — 58 байт на языке Stax.
                                                    Не байт, а символов.
                                                      +1
                                                      Минусующие не знают в чём разница?
                                                      +2

                                                      А почему, собственно, так важен объем программы, генерирующей блок? Какую ценность для криптографической науки несёт выкидывание пробелов из программы?


                                                      И ещё вопрос по сути статьи — правильно ли я понимаю, что если бы авторы честно сказали, что использовали такой вот алгоритм генерации, то никаких претензий из тех, что к ним сейчас предъявляют, к ним бы сейчас не было?

                                                        +1
                                                        По всей видимости это подтверждает неслучайных характер выбранных чисел. Вроде достаточно очевидно, что для полностью случайной последовательности минимальная программа должна внутри себя просто содержать всю эту последовательность (так как закономерности нет). То есть для случайной последовательности генерирующая программа не может быть меньше последовательности (с оговоркой на читерство). А тут получается сделать меньше, да ещё в несколько раз.
                                                          0

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

                                                            +3
                                                            Так авторы AES этого не скрывают. Штука в том, что в случае ГОСТа утверждается, что это не так.
                                                          +3
                                                          Для криптографической науки несёт ценность тот факт, что таблица подстановок не была сгенерирована случайно. Чем меньше размер программы, тем более «неслучайно» она была сгенерирована
                                                            –2
                                                            Тогда к ним были бы другие вопросы:
                                                            1. А почему вы использовали именно это, а не что-то более простое? Откуда вы взяли магическую строку "@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8"? Это ФИО разработчиков, или что?
                                                            2. Почему вы считаете, что этот s-box достаточно нелинеен? Из текста генератора это, мягко говоря, не очевидно.
                                                            +1
                                                            Для расчета S-Box Кузнечика удалось написть алгоритм который в 4 раза меньше самого S-Box. А что насчет AES и SM4, какие у них результаты?
                                                              +4
                                                              AES и SM4 изначально описаны как структуры, а не как последовательность байт
                                                                –5

                                                                Вы не ответили на вопрос.

                                                              +5
                                                              смешно когда наши доблестные ФСБшники включают школьников и говорят, что 11 лет назад этот алгоритм начинал разрабатываться чуть ли не в свободное время, поэтому они в итоге потеряли и сиды и скорее всего программу, которая генерировала таблицу подстановок.

                                                              А я в принципе верю. Это конечно не в плюс им.
                                                              Верю, глядя на некоторые сертифицированные (ФСБ) криптографические продукты рекомендованные для .....


                                                              Как вам например:


                                                              • Cпецификация с примерами на "C" с выражениями типа "int len = sizeof(str)", где "str" — указатель на строку!? (len дальше используется как размер строки для подписи!!)
                                                              • Или "аутентфикация" запроса (не шифрованного!) в протоколе (стандарта прошлого столения) внутри TCP/IP путем "секретного" константного пароля как одного из полей запроса. А что бы это секретный пароль вдруг не увидели в канале, то он XOR константной. И не строкой, а одним и тем же константным байтом каждого байта "секретного" б.ля пароля?
                                                              • А спецификация на протокол в внутри PDF. Которую 2 часа после copy|paste пришлось очищать от артефактов PDF?

                                                              И да… формуляры по документации все в лучших традициях. 90% воды и бюрократическ-военного стиля языка.


                                                              Честно… "За державу обидно".
                                                              Распилы сплошные.

                                                                0
                                                                Довольно странным выглядит подход с представлением алгоритма генерации на произвольном языке. Гораздо логичнее было бы для этой цели придумать некую специальную виртуальную машину с максимально компактным байт-кодом, и всем использовать её для подобных оценок.
                                                                  –1
                                                                  Пока основные решения по криптографии принимаются в недрах закрытых
                                                                  организаций, инсинуации на эту тему будут продолжаться, независимо от их
                                                                  реальной достоверности.
                                                                    0
                                                                    Процесс шифрования в блочном шифре можно представить простой формулой
                                                                    C = M х K
                                                                    где C — шифротекст, M — открытый текст, K — ключ шифрования, а x — блочный шифр.
                                                                    Эта формула визуально похожа на школьную формулу линейного уравнения y = kx+b, графиком которой является прямая линия.


                                                                    Вот, блджад мне ни разу не понятно, как от одной «формулы», «визуально» похожей (на самом деле совсем нет) перескочили к другой. Тут либо ТС не обладает компетенциями, либо «не гоже вам знать лишку».
                                                                      0
                                                                      Можете объяснить нелинейность на пальцах проще и понятнее? Задача была передать смысл
                                                                        0
                                                                        Я — не могу.
                                                                        Претензия моего комментария в том, что правильное написание формулы
                                                                        C=x(M,K)
                                                                        грубо максируется под операцию умножения и притягивается «за уши» формула прямой на плоскости. Подозреваю, здесь идёт расчёт на то, что читатель запутается и бросит прослеживать ход рассуждений.

                                                                        Но нет, въедливый читатель не бросит.
                                                                          +1
                                                                          Так что в итоге, я обманул кого-то? Это не научная статья, а её вольный пересказ для неподкованных читателей.
                                                                          Критикуя — предлагай. Дайте мне лучшее объяснение и я заменю им своё, в чем проблема?
                                                                            0
                                                                            Читая статью, немного странно видеть смешение понятий линейности уравнений и линейности их отображений (графиков). Более того, нам на лекции 20 минут выделили на подробное объяснение разницы в свое время. Причем даже неподкованный читатель понять может (уж если 2 курс понимает).
                                                                      0
                                                                      Поправьте меня, если я неправ, но по-моему, здесь написана полная хрень. Очевидно, что для любой не трансцендентной (в частности, для любой конечной) последовательности может быть написан алгоритм, порождающий её путём вычисления алгебраических функций. В чём здесь сенсация и какое отношение к криптостойкости имеет длина записи этого алгоритма на языке Си???
                                                                        0
                                                                        А также каким образом наличие одного алгоритма генерации (например, для AES) гарантирует отсутствие другого алгоритма? По-моему, ясно, что количество таких алгоритмов бесконечно, в том числе многие из них могут быть очень короткими.
                                                                          0

                                                                          Ну не "полная хрень", а просто не совсем понятно зачем Leo Perrin, показав структуру в s-box, "еще раз" взялся убеждать всех в её наличии посредством хайп-чемпионата на поиск самого короткого генерирующего алгоритма.

                                                                            +1
                                                                            Неужели никому не пришло в голову провести такой чемпионат для AES? В смысле, найти алгоритм короче того, который официально порождает соответствующую последовательность?

                                                                            Всё искусство программирования ведь построено именно на том, что люди находят более короткие алгоритмы для решения тех же самых задач.

                                                                            Я не силён в криптографии, но более-менее шарю в теории алгоритмов, и у меня немножко волосы встают дыбом от безграмотности общей идеи изложенного.
                                                                              +1
                                                                              Полагаю, что этого не делали так как в Rijndael S-box уже была «с объяснениями» от куда она взялась и на каком принципе построена. Другими словами уже и так понятно как она сгенерирована и ч как можно её описать через алгоритм.
                                                                                0
                                                                                Вы внимательно прочли мой вопрос? Какая связь между посылкой и выводом? Ну, кроме того, что людей вообще притягивает неизвестность.

                                                                                Я вам могу офигенно сложным алгоритмом построить обычную последовательность натуральных чисел.
                                                                        +1
                                                                        Во-первых, поправьте, пожалуйста, текст — в середине статьи везде говорится «перестановка» вместо «подстановка». Это два различных понятия, к тому же перестановка — это линейное преобразование бит в двоичном векторе. Кроме того, термин «устойчивый» не применяется в криптографии — используйте «стойкий».

                                                                        Во-вторых, приятно видеть наконец-то четкие (на бумаге) слова создателей и обсуждение в международной комиссии. В то, что программа и сиды утеряны (если таковые вообще были), думаю, не верит тут никто, ибо в ФСБ такие материалы должны быть, как минимум, с грифом «секретно», и отдавать их на всеобщее обозрение никто не будет даже в интересах стандартизации в ИСО.

                                                                        И в-третьих, сам факт того, что наш S-блок можно «сжать» в 4 раза, сделав его «сопоставимым по размеру» S-блоку AES, не может быть аргументом для запрета его использования. Порядок его нелинейности тоже вполне приличный и не сильно уступает аналогам. По «вскрытой» структуре он сложнее того же AES, если говорить о вычислительном аспекте. Например, гомоморфно вычислить функцию обращения достаточно легко (что сделано в 10-ках работ), а вот сделать тоже самое с показательной функцией гораздо сложнее (но такие работы уже ведутся, включая использование найденной алгебраической структуры). Кроме того, S-блок алгоритма BelT, на который похожа подстановка Pi^{-1}, известен, и известны его алгебраические свойства, которые ничем не уступают свойствам S-блока AES. Так что есть надежда на то, что все-таки наш S-блок все же примут в том виде, в котором он сейчас есть.
                                                                          +1
                                                                          Спасибо за замечания, однако справедливости ради, применительно к S-Box кузнечика справедливо и то и то, т.к. он биективный. Вот у DES да, S-Box исключительно от слова substitute
                                                                            0
                                                                            Уууу….как тут все же все запущено в плане теории. Вы почитайте определение подстановки — это биективное отображение конечного множества в себя. У DES-а расширяющие и соответствующие сужающие S-блоки (для справки), которые вместе образуют тоже биективное преобразование. Без биективности нельзя вообще построить шифр, так как необходимо получить преобразование расшифрования.

                                                                            Перестановка — частный случай подстановки, — которая является линейным преобразованием и может быть задана намного проще (как умножение на матрицу, в общем случае). Например, циклический сдвиг на 11 в «Магме» — это тоже перестановка. В архитектуре SP-сети перестановка — это P-блок. Иногда он может быть несколько сложнее — не линейным, а аффинным (тогда архитектура SA). Но в любом случае, он вычисляется проще. Так что тут не может быть двоякого прочтения, если речь идет о нелинейном биективном преобразовании.
                                                                              +1
                                                                              Вы несколько драматизируете.
                                                                              Я как алгебраист всегда называл перестановкой биективное отображение конечного множества в себя.

                                                                              Википедия со мной вполне согласна.
                                                                              В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.)

                                                                              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.
                                                                                +3
                                                                                Боюсь, что мои замечания как раз из области криптографии, а не из области лингвистики, и вообще из области формальной математики. Википедия, в этом смысле, вообще не то, на что надо ссылаться — там гораздо больше неправильного с точки зрения формальной теории, нежели верного.

                                                                                С точки зрения алгебры, не буду с Вами спорить, как криптограф-алгебраист могу согласиться с тем, что в классической алгебре перестановки и подстановки рассматривают в едином контексте. Но в криптографии разница определяется однозначно. Посмотрите на докомпьютерную (классическую) криптографию. Там выделяется 2 общих класса шифров — подстановочные и перестановочные. Первый класс — шифры замены, в то время как второй включает только те, в которых буквы текста не заменяются, а перемешиваются в соответствии с ключом и алгоритмом. Далее это распространилось и на современные архитектуры, начиная с работы Клода Шеннона. Под перестановкой в криптографии понимают именно перемешивающее преобразование, а не замену.

                                                                                А результаты Перрина мы тут и вовсе не обсуждаем — зачем Вы это написали, мне не понятно.

                                                                                Тем, кто минусит — респект. Изучение матчасти — не ваше дело, видимо. Как показывает опыт, выпускники вузов практически не знают в итоге терминологии в области, в которой они получают дипломы.
                                                                                  0
                                                                                  У нас тут не экзамен по криптографии, чтобы требовать от всех строгого соблюдения терминологии.
                                                                                  Вы мне чем-то напоминаете ВАК-овских динозавров, которые готовы сожрать за немного корявую формулировку.
                                                                                  В школьной математике тоже подобные веения. Напридумывают терминов и заставляют их зубрить. Термины ради терминов.
                                                                                  Термины никак не помогают решать задачу сами по себе, а только замусоривают мозги.
                                                                                  Я выступаю за то, чтобы народ понимал суть, чтобы имел в голове модели того, что происходит.
                                                                                    +1
                                                                                    Насчет ВАК-их буквоедов — полностью Вас поддерживаю, к ним не отношусь (слава Богу).

                                                                                    Народ понимает суть — тоже хорошо.

                                                                                    Но человек, который посещает одну из самых сильных конференций по криптографии, просто обязан писать свои статьи грамотно. Да, он, возможно, не криптограф — но для того и нужны комментарии, чтобы «причесать» сей труд.
                                                                                      0
                                                                                      Вообще я помню как, имея опыт кодинга, начал читать книжки по алгебре.
                                                                                      И некоторое время не понимал, почему перестановка — это не перемешивание массива, а именно отображение.
                                                                                      То есть, терминология криптографии ближе к кодингу.
                                                                                        0
                                                                                        Человек, который посещает одну из самых сильных конференций по криптографии, своими ушами слышал как Permutation так и Substitution применительно к S-Box. Видимо, конференция не такая уж и сильная.

                                                                                        Зато я узнал, что, то, что у нас называется группами подстановок, там называется группами перестановок.

                                                                                        Я понимаю ваше негодование, но цель статьи — донести смысл до неподготовленного читателя. Иногда ради этого приходится жертвовать точностью определений.
                                                                                          +2
                                                                                          Думаю, на этом можно ставить точку. Везде есть те, кто знает теорию и те, кто занимается прикладными аспектами, не сильно вдаваясь в терминологию. Однако, если говорить о том же Еврокрипте, то ни одна научная статься, в которой не соблюдена точная терминология, туда не попадет.

                                                                                          В целом, для нас важен результат. Конечно, есть большая вероятность того, что чиновники из ИСО не примут наш шифр и даже отзовут хэш. Но я не думаю, что это приведет к каким-либо существенным последствиям внутри РФ. Будем жить с «местным» стандартом, только и всего.
                                                                                            0
                                                                                            В 2016 году на Еврокрипте был доклад под названием
                                                                                            Indifferentiability of Confusion-Diffusion Networks, одним из авторов которого является Евгений Додис, получивший в этом году награду за лучшую работу по Fuzzy extractors. Вот слайд из этого доклада.


                                                                                            Либо статья без точной терминологии туда всё-таки попала, либо отношение к этим понятиям все-таки отличается у нас и у них.
                                                                                              +1
                                                                                              Да, это пример того, как все-таки понятия путают в том числе и докладчики. Ошибки в слайдах допустимы, я говорил о статьях, которые публикуются в LNCS. Как правило, там все «вылизывается» до пунктуации. На слайды это не распространяется, поскольку каждый докладчик сам готовит их и не предоставляет рецензентам.
                                                                                                0
                                                                                                Если глянете саму статью eprint.iacr.org/2015/680.pdf, то там слово substitution встречается всего 5 раз из которых 0 имеют непосредственное отношение к теме. Я не говорю, что вы зря придираетесь, просто на западе даже лучшие криптографы действительно не видят ничего криминального в том, чтобы считать S-Box перестановкой. Уж точно не
                                                                                                Уууу….как тут все же все запущено в плане теории

                                                                                                Они предпочитают говорить о линейных и нелинейных слоях, так гораздо меньше путаницы.

                                                                                                Может, если российские криптографы поменьше бы сидели бы за закрытыми дверями и больше общались с живыми людьми, то и определения в литературе и разговорах были бы «поумней».
                                                                                                  0

                                                                                                  Взаимно однозначное отображение конечного множества в себя называется перестановкой (подстановкой) элементов этого множества.


                                                                                                  Поэтому не исключена "терминологическая путаница" между перестановкой бит (в P-блоках) и биективным отображением множества (перестановкой элементов), которое (в частности) реализуется подстановкой в S-блоках.


                                                                                                  Или еще больше запутал?


                                                                                                  P.S.
                                                                                                  Мимопроходил.

                                                                                                    +1
                                                                                                    Дело все в том, что есть большая разница между англоязычной криптографической терминологией и русской. В данном конкретном случае я забыл сказать (не обратил внимания), что на западе теперь почти все биективные преобразования называют термином permutation. Это возникло после того, как развилась теория доказуемой стойкости. Из нее мы узнали такие аббревиатуры, как PRP — pseudo-random permutation и PRF — pseudo-random function. Поэтому на западе что S-блок, что P-блок, теперь часто называют одинаково, хотя изначально с момента появления этой архитектуры (Шеннон) нелинейную часть называли именно substitution. Российские же криптографы не стали менять терминологию, предложенную изначально, и в русскоязычной криптографии S-блок — это подстановка, а P-блок — перестановка (как правило, линейная). Надеюсь, такое пояснение теперь развеет путаницу.
                                                                                                      +1
                                                                                                      О чем и речь. А то «Запущено в плане теории», «Запущено в плане теории»… Это еще большой вопрос где что запущено
                                                                              +1
                                                                              есть ненулевая вероятность выпиливания уже принятого в стандарт хэша Стрибог (с тем же SBox), а так же RFC 7801, в котором описан Кузнечик.

                                                                              RFC 7801 тут зря упомянули. Во-первых, что-то «выпилить» из RFC вообще вряд ли возможно. Надо понимать, что RFC никого ни к чему не обязывает. Во-вторых, RFC 7801 вообще INFORMATIONAL. Это тоже самое, что предложить «выпилить» RFC 3514.

                                                                              Хотел бы особо отметить, что я не вкладывают никакого особого смысла при выборе RFC 3514, он просто иллюстрирует абсурдность идеи «выпиливания» чего-либо из RFC.
                                                                                0

                                                                                Что можно почитать научно-популярного на тему алгоритмов, применяющихся для поиска структур?
                                                                                К примеру, есть последовательность 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. Как определить, можно ли её описать короткой формулой или нет?

                                                                                  –1
                                                                                  Проще всего использовать The On-Line Encyclopedia of Integer Sequences.
                                                                                    +1

                                                                                    Не работает, так что вопрос остаётся в силе.

                                                                                      0
                                                                                      Ну, если простой способ с обращением к базе знания, накопленного за много лет, не подошёл, придётся пойти сложным способом — придумать краткий способ описания самому.
                                                                                    +1
                                                                                    Я не знаю, зачем Leo Perrin написал эту фигню с Колмогоровской сложностью.
                                                                                    Это все детский сад с точки зрения науки, но зато остальным понятно.
                                                                                    Наверное, для этого и написал. Такой хайп на Хабре разгорелся из-за ерунды.

                                                                                  Only users with full accounts can post comments. Log in, please.