Шифруем по-русски, или отечественные криптоалгоритмы

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


Из новостей

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

До конца 2020 года планируется «закончить создание национального удостоверяющего центра — структуры, которая будет выдавать сайтам в Рунете отечественные цифровые сертификаты», пишет Медуза. Также, по данным этого издательства отечественные цифровые сертификаты будут использовать криптоалгоритмы Магма и Кузнечик. Кроме того, отечественные алгоритмы шифрования по требованию Центробанка станут обязательными к использованию в платежных системах уже с 2024 года, пишет РБК

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

Упомянутые выше и другие основные алгоритмы, используемые в отечественной криптографии стандартизованы и описаны в ГОСТах.

Направления ГОСТов

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

Цифровая подпись

ГОСТ 34.10-2018 описывает алгоритмы формирования и проверки электронной цифровой подписи с помощью операций в группе точек эллиптической кривой и функции хеширования. Длины секретного ключа 256 бит и 512 бит.

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

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

Эллиптической кривой над конечным простым полем F_p, где p>3, называется множество точек (x, y), x,y\ \epsilon\ F_p, удовлетворяющих уравнению (в форме Вейерштрасса) y^2 = x^3 + ax + b (mod\ p), где 4a^3+27b^2 \neq0 , a,\ b\  \epsilon\ F_p.

Альтернативный способ задать эллиптическую кривую

Отметим, что эллиптическую кривую можно задать уравнением не только в форме Вейерштрасса. Относительно новым способом задания эллиптической кривой является уравнение в форме Эдвардса x^2 + y^2 = 1+dx^2y^2, d\ \epsilon \ F_p\backslash  \{ 0,1 \}.

Суммой точек (x_1,y_1), (x_2,y_2)эллиптической кривой называется точка (x_3,y_3), координаты которой определяются, как x_3 = \lambda^2 -x_1 -x_2(mod\ p), y_3 = \lambda^2(x_1 -x_3) -y_1(mod\ p), где \lambda = \frac{y_2 - y_1}{x_2-x_1} (mod\ p).

Точка эллиптической кривой C = kP, может быть определена через сумму точек C = P+P+...+P.

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

Алгоритмы формирования и проверки электронной цифровой подписи.

Подпись создается по следующему алгоритму.

входные данные: сообщение Mи закрытый ключ подписи d.

— к сообщению применяется хеш-функция(Стрибог) и вычисляется хеш-код сообщения h=h(M), отметим, что хеш-код — это строка бит.

— определяется число e = \alpha(mod\ q), где \alpha— целое число, которое соответствует двоичному представлению хеш-кода h. Причем если \alpha(mod\ q) = 0, то eпринимается за 1.
q — это порядок порядок циклической подгруппы группы точек эллиптической кривой, который является одним из параметров цифровой подписи. Также среди параметров есть P— это базовая точка подгруппы.

— на основе случайно сгенерированного целого числа k, 0<k<q, это число называют секретным ключом. Затем вычисляется точка на эллиптической кривой C = kP. Точка C имеет координаты (x_c,y_c).

— из координаты точки на эллиптической кривой и преобразования хеша вычисляется электронная подпись (r, s), где r = x_c (mod\ q),\  s = (rd+ke)(mod\ q). Если либо r, либо s равняется 0, то нужно вернуться к предыдущему шагу.

выходные данные: цифровая подпись (r, s)которую добавляют к сообщению.

Теперь перейдем к алгоритму проверки подписи.

входные данные: сообщение Mc цифровой подписью (r, s) и ключ проверки подписи Q

— полученная цифровая подпись проходит первичную проверку, если проверка не пройдена, то есть не выполнены неравенства 0<r<q,\ 0<s<q , то подпись неверна.

— вычисляется хеш-код сообщения h=h(M) , опять же с помощью алгоритма Стрибог.

— определяется число e = \alpha(mod\ q), где \alphaцелое число, которое соответсвует двоичному представлению хеш-кода h. Причем если \alpha(mod\ q) = 0, то eпринимается за 1. Затем определяется \nu = e^{-1}(mod\ q).

— вычисляется точка эллиптической кривой C = s\nu P -r\nu Q, из которой получается R = x_c (mod\ q).

— если r = R , то подпись верна

выходные данные: подпись вена/неверна

Хеш-функция

ГОСТ 34.11-2018 посвящен функции хеширования. В данном документе содержится описание алгоритма вычисления хеш-функции, известной из предыдущих версий стандарта, как Стрибог.

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

Подробное описание алгоритма вместе с разбором используемых в нем преобразований можно найти в статье @NeverWalkAloner.

Шифры

ГОСТ 34.12-2018 охватывает блочные шифры. Именно в этом ГОСТе описаны алгоритмы шифрования Кузнечик и Магма — алгоритмы блочного шифрования с длинами шифруемых блоков 128 бит и 64 бита соответсвенно и длиной ключа шифрования 256 бит у обоих.

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

Приведем упрощенную схему работы Кузнечика при зашифровании.

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

@sevastyan01 в своей статье подробно описал алгоритм Кузнечик.

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

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

Режимы работы шифров

ГОСТ 34.13-2018 содержит описание следующих режимов работы блочных шифров.

Режим простой замены

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

Расшифрование происходит аналогичным образом. Причем если при зашифровании было применено дополнение, то при расшифровании применяется обратная операция.

Режим гаммирования

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

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

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

Режимы гаммирования с обратной связью: по выходу, по шифротексту

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

Отличие режимов можно увидеть на схеме.

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

Режим простой замены с зацеплением

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

Режим выработки имитовставки

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

Каждый из стандартов действителен с 1 июня 2019 года в соответствии с приказом Федерального агентства по техническому регулированию и метрологии. Актуальные ГОСТы наследуют разработки, прописанные в предыдущих версиях.

Реализации алгоритмов ГОСТов

@ru_crypt в своей статье собрал множество вариантов реализации ГОСТовских алгоритмов на любой вкус.

Интерес к таблице подстановок

Рассмотрим ГОСТ 34.10-2018. В алгоритмах формирования и проверки цифровой подписи на начальных шагах используется хеш-функция Стрибог, которая определена в ГОСТ 34.11-2018.

Заглянем теперь в ГОСТ 34.12-2018. В данном документе в качестве параметра алгоритма Кузнечик для нелинейного биективного преобразования приводится таблица подстановок

\pi. Эта же таблица приведена в ГОСТ 34.11-2018, то есть используется и при хешировании.

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

Разработчики Кузнечика и Стрибога утверждают, что сгенерировали таблицу \piслучайным образом. Однако в ряде работ был проведен криптоанализ таблицы подстановок и выявлено несколько способов ее генерации, причем не случайным образом.

Статьи с алгоритмами генерации таблицы \pi:

Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 — Alex Biryukov, L ́eo Perrin, and Aleksei Udovenko

Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog — Léo Perrin and Aleksei Udovenko

Partitions in the S-Box of Streebog and Kuznyechik — Léo Perrin

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

Заключение

В данной статье мы познакомились с основными криптоалгоритмами, которые приняты в качестве стандартов ГОСТ и получили базовое представление об их работе. А также, привели примеры работ по криптоанализу Кузнечика и Стрибога.

Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 51

    +3
    Не одними ГОСТами регламентируется отечественная крипта, там еще тьма рекомендаций по стандартизации, которые не менее важны.

    Отдадим дань уважение первоисточнику ТК 26 (https://tc26.ru/), где со все это добро разрабатывалось.
      0

      Прежде чем принудительно всех пересаживать на ГОСТ-шифрование сайтов, обеспечивая заказами особоприближенных, необходимо внедрить шифрование в популярные браузеры, .net, java и другие фреймворки. С диким ужасом вспоминаю реализацию xml подписи на ГОСТ для СМЭВа, дело было лет 9 назад, но осадок никуда не делся. Раньше я тратил 4 часа жизни на настройку браузера для работы с ГОСТ-шифрованием, сейчас час, но и это дико. ЯБраузер заявляет, что будет работать из коробки, но и в других браузерах должна быть поддержка.
      Я помню о скандалах с rsa и бекдорах реализации и понимаю необходимость подобного шага, но, камон, не верю в бесшовность перехода.
      А еще нас заставят делать два домена с сертификатами:


      1. Католическими на rsa для остального мира
      2. Православными по ГОСТ — для своих.
        0

        Гм, если не ошибаюсь все работает через плагин, установка плагина занимает пару минут.


        Опять же есть версии огнелиса и хрома с интегрированным ГОСТом.

          +1
          Зачем два домена? Nginx позволяет указать несколько сертификатов для одного домена.
          ssl_certificate example.com.rsa.crt;
          ssl_certificate_key example.com.rsa.key;

          ssl_certificate example.com.ecdsa.crt;
          ssl_certificate_key example.com.ecdsa.key;
          +5

          На всякий случай напоминаю о проблемах, которые могут всплыть при использовании open-source реализациях хэш-функции Стрибога и их влиянии на электронную подпись ГОСТ Р 34.10-2012:


          И тут случился шок! Хэш, подсчитанный «знаменитой реализацией Дегтярева» совпадал с хэшом, подсчитанным в openssl с ГОСТ-ым endine, но не совпадал со значением хэш, посчитанным с помощью libgcrypt и libressl.
            +1
            www.gost.cypherpunks.ru/Russian.html — а вот тут собраны ссылки и на другие стандартизованные алгоритмы, тоже активно используемые в «наших» TLS/CMS протоколах, типа MGM, ACPKM, SESPAKE.
              0
              Спасибо за статью! Хочется послушать презентацию на следующем симпозиуме!
                0
                До встречи в пятницу!
                –8
                Не увидел плашки, что они не безопасны. Насколько я помню, их же не включают в международные стандарты именно по этому. И не включат, да.

                Так что не будет их никогда не в каких Хромах до тех пор, пока не подтвердят Безопасность.
                  +2
                  Ну как бы…
                  хэш
                  подпись
                    –3
                    habr.com/ru/company/virgilsecurity/blog/439788

                    Шифров нет в библиотеках OpenSSL и boringssl, собственно они там и не должны быть. Т.к зачем они нужны если есть TLS?
                      +2
                      Вы какой конкретно TLS имеете ввиду: есть несколько десятков вариантов, с китайскими, японскими, корейскими, российскими алгоритмами?
                        0
                        Я говорю о том, который используется в консюмерcком софте — например в iOS/os x/windows/chrome
                        +2
                        В LibreSSL ГОСТовые есть, в GnuTLS тоже. В OpenBSD, DragonflyBSD, HardenedBSD и ряде GNU/Linux дистрибутивов вообще LibreSSL по умолчанию ставится, соответственно и наши алгоритмы из коробки идут.
                      +2

                      Понятие безопасности растяжимое, я пытался прочитать все статьи про уязвимости ГОСТа, там в основном упирают на тайно выбранные константы. В итоге никакой явной атаки никто не предоставил, кроме фразы, что теоретически существуют слабые константы, а про "секретные" константы оказалось, что это ФИО авторов алгоритма в кодировке, что не тянет на супер уязвимые константы.


                      А почему не включают в стандарт? Ну а зачем им конкуренты? У них есть свои стандарты, своя контора NSA, которая эти стандарты продвигает, типа Dual_EC_DRBG, который закончился скандалом, так как там был явный бэкдор.


                      Может я и не прав, но можно статью в студию с примером реализации по взлому?

                        +1
                        Кому им? Camellia — японский шифр, ARIA — корейский, оба «включены в стандарт». Другой вопрос, что не очень уперлись кому-то на уровне практического внедрения, но тут — вольному воля, никому не запрещено создать свой Интернет со своими шифрами… и затем попытаться объяснить остальному миру, зачем ему это нужно. Впрочем, скоро нам похоже предстоит наблюдать ровно это: суверенный TLSЪ, разъяснения Соловьева про вражьи происки в AES (этот выпуск я не только послушаю, но и запишу)…
                          0

                          Не понял смысл примера про корейскую и японскую крипту, так как судя по докам кроме американских в винде, к примеру, ничего из коробки не поддерживается если я правильно понял, получается что по факту ГОСТ в таком же положении, не хуже и не лучше, не зависимо от того одобрил их кто-то на бумаге или нет
                          https://docs.microsoft.com/en-us/windows/win32/secauthn/tls-cipher-suites-in-windows-10--version-1507


                          Хотя, зачем вообще поддерживать какие-либо алгоритмы других стран, когда это не требуется софту в стране выпуска, тем более что разработка криптографии как и поиск уязвимостей и прочего в ней довольно трудоемкий процесс, так что нет ГОСТа из коробки нигде и хорошо, почему к нему должно быть особое отношение, а так хоть обязать через силу на него перейти всем сложнее

                            +1
                            Условный стандарт в данной области — реестр IANA, на который выше давали ссылку www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-4 Он, в свою очередь, опирается на RFC от IETF. Японцы с корейцами этот путь прошли — стандартизировали свои алгоритмы в IETF, их включили в реестр IANA. Применять ли их в «выпускаемой продукции» — это уже дело производителей, тем же Майкам никто не может приказать поддерживать все стандартные шифронаборы.

                            ГОСТ сейчас в положении prpposed draft datatracker.ietf.org/doc/draft-smyshlyaev-tls12-gost-suites и будет в нем находится до тех пор, пока авторы не ответят удовлетворительно на возникшие к ним вопросы вместо того, чтобы как попугаи повторять «патамушта!» Но что-то мне подсказывает, что ответов от них не будет, а вместо них Захарова расскажет про очередной всемирный заговор против молодой советской республики и выразит очередную порцию озабоченностей в лужу.
                              0

                              Ну я не припомню у нас какой-то пример взаимодействия гос в ИТ, где была нормальная связь с общественностью, всё делается как будто специально чем хуже, тем лучше, а по поводу констант кто знает в итоге четные они или нет, это как генераторы случайных чисел, требуются отдельно физические, так как встроенному в проц от Интел полного доверия быть не может, тем более что предложенных констант на каждый алгоритм обычно несколько сразу, возможно смотря какую выбрать?


                              Я вообще не уверен, что им реально хочется в этот стандарт попасть, это ничего не даст

                                0
                                А это тот случай, когда проблемы негров шерифа в лице IETF и IANA совершенно не колышут в эротическом ключе. Хотите стандартизации — вот публичный порядок, один для всех, действуйте по нему. Не устраивает — делайте свой Интернет, с Роскомпозором и ятями, к чему и идем.
                                  0

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


                                  Ну а какой государству смысл от интернета без контроля над ним, за обычным интернетом контроль через то, что все компании либо в США, либо контролируются через санкции США, так что свой интернет карманный звучит как логичный шаг, вообще не понимаю почему не могли начать с того, что сделать свой корневой УЦ на RSA/ECDSA и постепенно смотреть что получится, было бы логично гос. сайтам иметь свою цепочку доверия, хотя бы как быстрый запасной план.

                                    –2
                                    А для этого мозги должны развернутся в другую сторону: от откатов и распилов в сторону реальной госбезопасности.
                      +3

                      Отечественные криптоалгоритмы прямо как отечественная физика или математика… скрепная и сакральная. А если без сарказма, что особенного в российских алгоритмах по сравнению с нероссийскими?

                        +3
                        В любой стране есть области, в которых власти определяют условия применения тех или иных алгоритмов. Есть области в которых в Японии применяются японские, в Корее — корейские, в США — американские, у нас, соответственно, — российские. Это общемировая практика (ну если в стране есть криптографическая индустрия)
                          +2
                          И давно в Корее, Японии и в «любой стране» свои шифры настойчиво пытаться использовать не в B2G/G2G сегменте а в B2C? Т.е в обычном интернете?
                            +2
                            С самого начала, именно для этого их и тянут в международные стандарты — чтобы упростить такое использование.
                              0
                              Повторяю вопрос — зачем? Функцию защиты уровня транспорта прекрасно выполняет TLS последней версии. Никакая виза или другие серьезные ребята (типа Apple или Гугл) чисто для 1 страны не будут менять шифрование.

                              Получаеться, что это «шифрование» нужно 2,5 пользователям — тогда ему не место в стандарте и поставке всем.
                                0
                                1. Давайте разберёмся с терминологией. «TLS последней версии» — это протокол, а не криптоалгоритм. Конкретные криптоалгоритмы выбираются на этапе Cryptographic negotiation.
                                2. Добавить в софт (в ОС, популярные браузеры и популярные библиотеки) возможность работы с российскими алгоритмами не сложно, и обратная совместимость при этом не поломается. Спрос есть, и даже финансирование найдётся, если будет принципиальное согласие.
                                3. А вот с принципиальным согласием есть проблемы. Никто не горит желанием добавлять поддержку алгоритмов, стойкость которых сомнительна: это не то что не соответствует целям разработчиков софта, а прямо им противоречит.
                          –2
                          Никто никому не доверяет, опасаются backdoor, который известен только разработчикам.

                          На мой взгляд, браузеры должны поддерживать весь набор шифров. А на серверной стороне можно отключать шифры, которым нет доверия.
                          0
                          Очередное изобретение колеса, лишь бы было отечественным
                            +2
                            Напомним, что в феврале текущего года СМИ сообщили о том, что ЦРУ и разведка Германии с помощью швейцарской компании Crypto AG имели доступ к секретной переписке более 120 стран мира в течение почти 50 лет. Компания производила шифровальное оборудование со времен Второй мировой войны, а операция по его распространению получила название «Рубикон». Когда компания стала лидером на рынке шифровальной техники, в числе ее клиентов были правительства Ирана, Аргентины, Индии, Пакистана, Ватикана, Ливии и других государств. СССР и Китай не сотрудничали с Crypto AG, а пользовались своим оборудованием.
                              0
                              Но только все равно нет гарантии, что отечественное не будет следить за мной или кем-то другим
                            0
                            Я вот только одного не понял: чисто теоретически для определенной перестановки можно найти алгоритм ее формирования. Мне почему-то кажется что даже для любой перестановки можно создать такой алгоритм (пусть даже не слишком красивый и компактный). Но в чем тут проблема (что об этом надо писать статьи)? Это что, как-то упрощает атаки на алгоритмы в которых используется этот блок перестановок?

                            Кто-нибудь может раскрыть этот момент?
                              +2

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


                              Пример — сама таблица 256 байт, самая короткая программа на C для её генерации — 134 байта, на ассемблере есть реализация в 80 байт. Вероятность, что авторы выбрали случайную таблицу, а для неё случайно нашлась программа, в три раза её короче — ну, очень небольшая, это уж точно.


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


                              В криптографии так не принято, когда автор одновременно выдвигает алгоритм в качестве стандарта и скрывает внутреннее устройство. Либо крестик (т.е. объяснить аномалию), либо трусы (т.е. идти и шифровать в недрах ФСБ, там такое любят). Они бы еще бинарник обфусцированный дали и предложили стандартизировать, а что — алгоритм? Алгоритм!


                              Возможно, что эта структура в таблице усиливает какие-то свойства алгоритма, а рассказать об этом не могут, т.к. раскрыть принцип формирования таблицы == раскрыть саму атаку. Такое уже было с DES, и тогда тоже все говорили о том, что возможно NSA вставила бекдор. Вопрос доверия ФСБ полагаю оставить за рамками этого комментария, лично у меня этого доверия нет. И в целом основывать защищенность на доверии одной спецслужбе — не самая лучшая идея.

                                0
                                Ну вот вы про политику и доверие, а я про математику спрашивал.

                                И вот это ваше «случайно — следовательно — нет алгоритма» совершенно неправильно с точки зрения логики. Случайно может (теоретически) так лечь что вообще не будет перестановки (алгоритм 0-й длинны).

                                Но если отбросить всю эту «политико/заговорную тему» и ответить по существу: Снижает ли наличие алгоритма (путь даже короче чем сама таблица) крипто-стойкость алгоритмов, в которых эта таблица использована?

                                ЗЫ На сколько я помню историю с DES там вовсе не наличие алгоритма для таблицы перестановок роль играла, а дифференциальный криптоанализ выявил недостатки этих таблиц (не важно как они были составлены). Т.е. сравнивать ситуации с наличием алгоритма для создания блока перестановок и слабостью этого блока выявленную методами диф. криптоанализа — это как теплое с мягким сравнивать.
                                  +2

                                  Нет, про DES было ровно так же. Пришла NSA и сказала "ваши таблицы плохие, берите мои таблицы, они хорошие". И только спустя много лет выяснилось, почему же они были хорошие. А до этого все тоже гадали, что они в этих таблицах спрятали (но да, тогда там не смогли найти структуру, просто обмусоливали факт таблиц, хз откуда взявшихся). Но DES был очень давно и был единственным. А сейчас этих алгоритмов много, хочешь AES, хочешь Blowfish, хочешь ChaCha20-Poly1305.


                                  И да, криптография в основном не является точной наукой. Там точно известны способы, как делать не надо, а способы, как делать надо — эмпирические, "вроде не поломали" и "на данный момент нет известных атак". Случаи, когда у примитивов есть доказанная стойкость, немногочисленны, и в основном опираются на (недоказанную) стойкость нижестоящего примитива. Единственный шифр с доказанной абсолютной стойкостью — вообще одноразовый блокнот. Обычно доказывают стойкость режимов шифрования или подписи (OAEP, XTS) в предположении, что нижележащий шифр (RSA, AES) соответствует какой-то модели безопасности.


                                  "Случайно — нет алгоритма" правильно с точки зрения статистики. В среднем на случайную перестановку не найдется эффективные алгоритма, но да, есть некоторые вырожденные случаи — например, перестановка 1-2-3-4-5..., или та, что у ГОСТа. Вероятность попасть на вырожденный случай маленькая, а длина алгоритмов — как раз неплохая метрика для оценки вырожденности этого случая. Математически это называется "энтропия".


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


                                  И да, я не говорю что ГОСТ плохой, я просто говорю, что при таких вводных им пользоваться никто не будет. Сфера его применения — офицеры ФСБ, которые темной ночью будут закрываться в кабинете и шифровать друг другу пакеты. Ну и все, кто от них зависит.


                                  Аналогично сейчас так же обмусоливают эллиптические NIST-овые кривые, говоря о том, что они в общем-то хз откуда взялись и возможно принадлежат к какому-то секретному классу слабых кривых. И именно потому есть понятие "curve rigidity" и альтернативы в виде X25519 и X488. Заметьте — и это в сторону американских кривых, никаких скреп и новичков. Абсолютно те же самые принципы. Просто криптография так работает, вся. Вот оно, выделено жирным красным цветом — абсолютно те же заявления — "непонятно как получено".


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

                                    0
                                    «Случайно — нет алгоритма» правильно с точки зрения статистики.

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

                                    Т.е. «Случайно — нет алгоритма» — просто ложное утверждение априори. Как из той мухи раздуть слона — вы прекрасно описали.

                                    И да, я не оправдываю разработчиков ГОСТ-овских алгоритмов шифрования. Но и делать выводы о надежности алгоритмов на основе домыслов — тоже не поддерживаю.
                                      0
                                      Возможно он будет длиннее самой таблицы, но такой алгоритм всегда найдется.

                                      Это подразумевалось, да, из контекста первого сообщения. Имелся в виду "алгоритм короче, чем запись константой", который существует не всегда.


                                      Но и делать выводы о надежности алгоритмов на основе домыслов — тоже не поддерживаю.

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


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


                                      Плюс, как я вон выше про кривые NIST привел, заменять возможно ненадежные алгоритмы — стандартная практика, даже если ненадежность не доказана (или доказана, но вычислительно недостижима).

                                        –1
                                        факта, что авторы врут
                                        — высосано из пальца.

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

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

                                          Разумеется, не делает. Зато длина алгоритма позволяет говорить о вероятностях.


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


                                          Вероятность первого оценивается математически, учитывая, что каждый сэкономленный байт влияет на эту вероятность экспоненциально, она очень маленькая. Вероятность второго предлагаю каждому оценить самостоятельно, учитывая, что даже в США был пример с DES.


                                          Если для вас это не так, то мне искренне жаль.

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


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

                                            0
                                            Я вас тоже не осуждаю за то что вы приписываете мне всемирный заговор головного мозга которыми сами страдаете.

                                            Я то все надеялся что общаюсь с человеком, для которого причинно следственные связи в рассуждениях важнее домыслов и страхов перед товарищем майфором… и да мне искренне жаль, что я потратил столько времени на разговор из разряда слепого с глухим…
                                            0
                                            Объём алгоритма, чтобы сгенерировать какую-то последовательность, можно оценить при помощи Колмогоровской сложности. Она не вычислима, но тесно связана снизу.

                                            Если строка длины N достаточно случайна (близка к строке аналогичного состава и длины с максимальной энтропией) то её колмогоровская сложность ~ N, т.е. алгоритма, короче её, не существует.

                                            С другой стороны можно почитать про ограничение архивирования, если вдруг стало интересно. В любом случае — это хороший тон задавать процедуру генерации «случайных» элементов, которые гарантируют, что там нет умышленных уязвимостей. А давать бинарные куски с формулировкой «как вы не можете верить государству» — плохой.
                                              0
                                              Если строка длины N достаточно случайна (близка к строке аналогичного состава и длины с максимальной энтропией) то её колмогоровская сложность ~ N, т.е. алгоритма, короче её, не существует.


                                              А на основе чего делается такое заключение? Есть где про это почитать.

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

                                              И тут еще один вопрос — а так ли важна максимально возможная энтропия в блоках перестановки? Кто-то оценивал ее в тех же S-блоках AES например?
                                                0
                                                И тут мы плавно подходим к стандартному вопросу на экзамене по теории вероятностей: какая из следующих двух последовательностей длины 10 более случайная:

                                                0000011111
                                                или
                                                1010110010

                                                Правильный ответ, разумеется, они обе одинаково случайны, поскольку если мы рассмотрим множество всех последовательностей длины 10 то каждая из указанных выше последовательностей может быть выбрана оттуда с одинаковой вероятностью 2^-10.

                                                Аналогично вводится и понятие случайной подстановки — как случайного объекта, заданного на множестве всех подстановок.

                                                С колмогоровской сложностью тоже не все просто — это величина асимптотическая — именно поэтому все пишут, что она примерно должна быть равна длине последовательности, но если мы посмотрим непосредственно на теорему, которая формулирует это утверждение, то там сказано, что сложность отличается на некоторую константу С. И тут мы приходим к двум вопросам для конкретной последовательности выполнены условия асимптотики (256 — это уже бесконечность или еще нет), ну и какое значение для этой длины имеет константа C? 1,2, 100, 256?

                                                Ну а на тему всемирного заговора вот хорошая задачка:

                                                Институт стандартов NIST проводит два конкурса. В первом конкурсе AES участвуют 15 алгоритмов от различных авторов со всего мира, во втором, SHA-3 — 51 алгоритм. Какова вероятность того, что в обоих конкурсах победят алгоритмы от одного и того же автора? ;)
                                                  0
                                                  Аналогично вводится и понятие случайной подстановки — как случайного объекта, заданного на множестве всех подстановок.


                                                  Ну это ровно то о чем я и говорю:
                                                  0,1,2,3,4,5....254,255 — точно также «случайна» как и все остальные перестановки для 256 элементов. А для ее алгоритм воспроизводства по сути 0-вой длинны (если не считать операцию копирования со входа на выход).

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

                                                  Почти уверен, что число раундов снижает требования к блоку перестановок потому как тот же DES предлагали лечить именно увеличением числа раундов (по мимо увеличения длинны ключа).

                                                  А темой всемирного заговора я как-то не интересуюсь. Но как проводятся всякого рода конкурсы — немного представляю… поэтому… задачка ваша с кучей подвохов. Ну типа не содержит уточнений на тему кто с кем спит/играет в гольф/и т.п. подковерных нюансов, которые… ну скажем так: очень редко не влияют на принятия решений :).
                                                    0
                                                    какая из следующих двух последовательностей длины 10 более случайная:

                                                    Речь таки идет о вероятности попадания в узкий класс. Какая из последовательностей длины десять более вероятна — где идет пять нулей подряд или где есть просто пять нулей в любых местах?


                                                    Институт стандартов NIST проводит два конкурса. В первом конкурсе AES участвуют 15 алгоритмов от различных авторов со всего мира, во втором, SHA-3 — 51 алгоритм. Какова вероятность того, что в обоих конкурсах победят алгоритмы от одного и того же автора? ;)

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


                                                    Sly_tom_cat


                                                    Однако такая перестановка позволяет радикально упростить линейные и дифферинциальные методы криптоанализа.

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


                                                    И вот тут гораздо интереснее другое: существует ли набор метрик или тестов, который бы говорил о качестве блока перестановок в плане противостояния методам криптоанализа? Или это еще зависит от окружающего блок перестановк алгоритма?

                                                    Существует, например, корреляционная характеристика и дифференциальная характеристика. И это, кстати, один из ответов на вопрос "почему случайный s-box не всегда хорош" — если бы DES был со случайными S-Box-ами, он был бы сильно слабее.


                                                    И ведь вы таки снова уехали от темы. Авторы заявляют, что S-Box генерируется случайно (и заявляют, что потеряли программу, которая его генерировала), а по факту очень аккуратно попали в узкий осмысленный (!) класс перестановок.


                                                    Ведь там не только программа на ассемблере длиной в 80 байт. Программой просто пытались получить численные оценки сложности, которыми можно меряться. Перестановка осмысленная с точки зрения математики. Случайно там оказалось дискретное логарифмирование. Случайно она отображает регулярные множества. Всего перестановок 256! ≈ 2^1684, а перестановок TKlog ≈ 2^76. Различных программ на ассемблере длиной 80 байт ≤2^640 (не все из них валидны, многие из них делают одно и то же, но да ладно).


                                                    Масштаб удачи просто поражает. Случайно выбить событие с вероятностью порядка 10^-315 — это уметь надо.


                                                    Т.е. более предметно рассматривать вопрос, что авторы хотели вложить в перестановку. Я лично вижу три варианта:


                                                    • бекдор (тогда не скажут)
                                                    • анти-бекдор, перестановка защищает от какой-то секретной атаки на блочные шифры, известной ФСБ (тогда тоже не скажут)
                                                    • быстрая аппаратная реализация за счет регулярности (такие действительно есть). Но этот вариант маловероятный — тогда бы так и сказали, а не говорили бы, что это случайность и программу потеряли.
                                  +2

                                  Настоящее российское шифрование — это когда офицер ФСБ шифрует твой файл

                                    0

                                    В подобных статьях ссылаются на утверждение разработчиков ГОСТ алгоритмов о случайном выборе значений, а потом эту случайность "разоблачают".
                                    Есть ли ссылка публикацию этого утверждения от разработчтков? Не домыслы, не пересказ с чьих-то слов.

                                      0

                                      https://www.ruscrypto.ru/resource/archive/rc2013/files/03_shishkin.pdf


                                      Слайд 10, красным помечено выбранное разработчиками (например, см. предыдущие слайды — шифр представляет из себя SP-сеть, и она тоже помечена красным, ровно как и "Выбор пространства V8").

                                        0

                                        Имеется ввиду — "Случайный поиск с заданными ограничениями по параметрам" ?

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

                                  Самое читаемое