Данная статья напоминает о проблемах X.509 PKI и реализаций ASN.1. Предлагает компактный, быстрый, детерминированный, потоковый и простой формат кодирования данных KEKS, а также криптографические сообщения для подписи и шифрования данных с поддержкой пост-квантовых алгоритмов.
Представьте, что вам надо использовать инфраструктуру публичных ключей (PKI) в каком-то новом проекте. А он ещё и для встраиваемой системы.
Всем известен X.509. Существует масса библиотек реализующих его подмножество работы с сертификатами и проверками цепочек. Тот же OpenSSL. Но можно ли его с чистой совестью кому-либо порекомендовать? Лично я бы не смог ни при каких обстоятельствах. Чуть ли не каждый год в нём находят серьёзные проблемы и ошибки за более чем четверть века существования. Хуже кода по качеству, переусложнённости и аккуратности я пока не встречал среди более-менее крупных серьёзных свободных проектов. Видно, что изначально в нём предполагались красивые абстракции (EVP и подобное), но со временем весь код оброс сплошными if/ifdef. И довольно скудной документацией для разработчика.
Может быть есть другие адекватные реализации подмножества X.509? Можно ли вообще полноценно реализовать X.509 стандарт? Нам с коллегами не известно ни одно свободное/открытое решение. Большие сомнения и с проприетарными. Попробуйте поработать с link+cross сертификатами при наличии indirectCRL и name constraints. Дичайшая, никому не нужная переусложнённость (кроме членов комитетов её создавших). Неспроста появился WebPKI и CA/Browser Forum, в котором уже даже избавляются от CRL, донельзя стараясь всё упростить (правда, ценой централизации WWW в виде Let's Encrypt). X.509 и ASN.1 диктует бизнес, а не инженеры.
Может стоит использовать WebPKI и не париться с 99%+ возможностей X.509? Многие ошибки в OpenSSL были связаны не каким-то определённым функционалом, а напрямую с ASN.1 (BER/DER) кодеком. А также с вынужденно сложными структурами представляющими X.509 сертификаты.
Небольшое введение в ASN.1.
А давайте просто попробуем найти кто реализует ASN.1 DER? У всех есть BER (пускай и без REAL типа, не нужного в криптографии). Но для строгого DER необходимы дополнительные проверки после декодирования. Достаточно посмотреть на код библиотек и оценить:
Ни OpenSSL, ни Go crypto/tls, ни Mbed TLS, ни WolfSSL, ни GNU Libtasn1, ни Bouncy Castle, ни cryptlib, ни NSS не делают хотя бы что-то одно из этого. Соответственно, ни одна из перечисленных реализаций не имеет настоящего DER декодера и может успешно принять некорректные структуры.
Мы с коллегами неоднократно видели даже CA (!) сертификаты, в которых или регулярное несоответствие схемам ASN.1 (например выходящая за границы длина полей, особенно в российских сертификатах) или даже некорректное DER кодирование (неотсортированные SET). В реальном мире полно сертификатов, где внутри GeneralNames CHOICE чужеродные структуры с точки зрения схем.
Таким образом, за десятилетия существования X.509, у нас не то что нет ни одной его достойной well-known реализации, но даже ASN.1 DER декодеров. В моём проекте PyDERASN имеется строгая проверка DER, но он написан на Python, поэтому ни о каких embedded систем речи не идёт. Никогда заранее не известно будут ли X.509 или CMS реализации работать между собой, если только не используется крохотное подмножество стандарта.
Проблема с ASN.1 касается и распространённых CMS сообщений для подписи и шифрования данных. Там вообще смесь из BER и DER кодирования.
Сам факт наличия ASN.1 кодирования — огромная поверхность для атак, в виду его большой относительной сложности. Брюс Шнайер ещё в 1990-х в «Прикладной криптографии» давал совет: по возможности, лучше к нему не притрагиваться.
Какие альтернативы есть? CV-сертификаты, применяемые в паспортах с чипами — являются подмножеством ASN.1 DER с существенно упрощённой структурой сертификата. Но они покроют задачу только по работе с публичными ключами. Форматы основанные на JSON — безумие по нерационально используемому месту, и невозможность использовать во встраиваемых системах. Simple PKI тоже покрывает только PKI, но не CMS.
LibrePGP/OpenPGP существенно проще и по кодированию и по форматам, чем ASN.1 X.509, но в нём много архаичных рудиментов и своих сложностей. А сейчас ещё есть раскол между LibrePGP и OpenPGP, идущими параллельными несовместимыми между собой дорогами.
Но кто мешает сделать свой простой препростой формат для этих задач? Придумывать сложные вещи, особенно если соберётся комитет — легко. А простые вещи, легко и надёжно реализуемые — сложно. Факт известный всем инженерам.
Многие проекты идут по пути создания собственных форматов. Иногда просто передавая Си-структуры по сети. Где-то закодированые XDR кодеком. Где-то Protocol Buffers. Где-то MessagePack. Всё это уже относится к категории адекватных, разумных и де-факто выполнимых вещей, а не де-юре существующих только на бумажке.
Мы с коллегами принципиально хотели бы иметь формат кодирования не требующий схему. Схема безусловно даёт ряд неоспоримых преимуществ. Но удобство, как могло бы быть с schema-less форматом типа JSON, bencode, MessagePack — перевешивает. Видимо, после многолетней работы с ASN.1 не хочется никоим образом зависеть от них. Хотя мой опыт работы с protobuf был исключительно положительным.
Главнейшее требование к кодеку: простота реализации, малое количество кода, дабы сократить поверхность атаки. Если кодек достаточно прост, чтобы его можно было на любом другом языке реализовать за несколько часов/за день, то и вопросы совместимости отпадают. Если, предположим, в каком-нибудь Lua нет ASN.1, то проще выбрать другой язык. Если же вопрос реализации кодека на Lua — половина дня работы, то это уже не проблема.
Для криптографических задач критична детерминированность кодека. Единственно верное, каноничное представление данных. Хотя есть и вариант принятый в JSON-based криптографии: просто засовывать JSON внутрь строки другого JSON. Но это жуткий overhead и делается от безысходности и ограниченности web-экосистемы.
Для встраиваемых систем, для мест, где может быть bare metal без ОС: крайне желательно потоковое кодирование. Без него мы будем вынужденны иметь дело с буферизацией, динамической памятью и куда более сложным кодом из-за этого.
Приемлемая/достаточная компактность сериализованных данных. Объективной меры, что считать достаточно компактным — нет. Но если сертификат будет занимать в два раза больше чем X.509 ASN.1 DER версия, то неприятно, ведь мы не должны забывать и про какие-нибудь смарт-карты, где каждый килобайт на счету.
Пожеланием является и достаточное количество возможных типов данных, чтобы можно бы было прозрачно заменить JSON, как это часто делают BSON или MessagePack кодеками. Обязательная дифференциация бинарных строк и человекочитаемых текстовых! Крайне желательная возможность передачи строк более четырёх гибибайт, ибо какой же это general purpose кодек, если в нём нельзя содержимое относительно большого файла разом передать? Желательна родная поддержка datetime объектов: это очень часто используемый тип данных.
Поразительно, но удовлетворяющего всем требованиям кодека не нашлось! Какие принимались во внимание?
Netstrings позволяют закодировать только строки: printf("%d:%s,", len(s), s). Не потоковый. Чтобы передать списки или словари: нужно их эмулировать в виде NS(NS(s0) || NS(s1) || ...) и в коде преобразовывать в более высокоуровневые структуры.
Canonical S-expressions аналогичны Netstring, но, добавляя круглые скобочки, позволяют передавать списки. Но те, кто работал с csexp и SPKI, говорят о геморрое пост-обработки подобных данных.
Bencode придуман для BitTorrent.
При этом, в словарях ключи обязаны быть отсортированы. Потоковый (кроме строк), детерминированный, простой (реализация всего кодека на Python умещается на экран). Но не всегда компактен, нет дифференциации бинарных и человеческих строк.
JSON — сложная громоздкая реализация без поддержки бинарных данных.
BSON нередко занимает больше места чем JSON, не детерминирован, не потоковый,
нет datetime, нет длинных строк.
Universal Binary JSON не детерминирован, не потоковый, нет длинных строк, не дифференцирует строки.
MessagePack не потоковый, не детерминирован, нет datetime, нет длинных строк.
CBOR, судя по описанию, должен быть идеалом! Всё что нам нужно — упомянуто в его спецификации. Но при пристальном рассмотрении, он полностью отпадает. Это самый переусложнённый формат из всех что встречал (исключая ASN.1).
Может применять какой-нибудь MessagePack, как это сделал Saltpack? Добавить несколько if-ов для проверки детерминированного кодирования? Подправить для потоковой передачи хотя бы списков/словарей. 32-бит длины поменять на 64-бит? Но это в любом случае будет несовместимый с оригиналом кодек.
А раз ничего достаточно удовлетворительного (простота, детерминированность, потоковость, компактность, достаточное количество типов данных) нет, доделка существующих кодеков будет несовместима, то ничего не удерживает от реализации собственного кодека с нуля. Главное чтобы он был достаточно простым для реализации.
Так и появился KEKS формат:
Изначально фигурировало название YAC: «Yet Another Codec», «YAC Ain't CBOR».
Кодирование — банальный TLV-like (tag-length-value) подход, где «L» и «V» могут отсутствовать. Только детерминированное, только потоковое.
Принципиально не хотели ASCII-закодированных длин, varint или zig-zag кодирования int-ов — всё это требует нетривиального кода, в котором будут if-ы в циклах, что вредит производительности. Только строковые ключи в словарях! Никаких меток, тэгирования!
Какие типы данных KEKS поддерживает?
Само собой, для встраиваемых систем можно не включать поддержку MAGIC, BLOB и FLOAT. Также как и преобразование TAI⇔UTC далеко не всегда нужно.
А теперь нам бы ещё не помешала… схема. Декодировать мы можем и без неё, но почти всегда нужно сделать многочисленные проверки после.
Применять XML Schema или JSON Schema — не вариант, из-за безумной сложности этих стандартов и зоопарка реализаций, поддерживающий разные подмножества их функций. Да и запускать функции проверки на их основе на embedded системах — не вариант.
В чём заключаются проверка структур? В 90%+ случаев она сводится к однообразным простейшим командам «убедись, что есть поле XXX», «убедись, что длина поля равна XXX», «убедись, что тип данных у поля XXX», и т.д… Список подобных команд был бы одинаков для любой реализации кодека. Он, по сути, является неким байт-код представлением схемы. Нужен только интерпретатор подобного байт-кода команд проверки.
Схемы представляют из себя словарь, где ключами являются их названия, а значениями списки команд. Каждая команда тоже является списком, где первым элементом идёт строка с названием команды. Остальные элементы списка специфичны для каждой команды. Какие команды имеются?
Пока их хватает для всех поставленных нами задач. Но ничто не мешает добавить новые, дополнить свои интерпретаторы и схемы. Например проверку максимальной точности FLOAT элемента.
Например, есть схема записанная в CDDL формате:
Словарь «our» содержит опциональное текстовое «comment» поле, обязательное байтовое «v», не пустое текстовое «ai» и «fpr» длиной 32 байта. Его можно проверить так:
или так:
А CDDL схема со списком координат (предположим, что они INT):
может быть проверена так:
Но писать такие команды вручную — не самое приятное занятие для человека. Это просто совпадение, но исключительно just-for-fun был когда-то написан KEKS encoder на Tcl. Именно на нём я генерировал подобные списки команд.
Но на Tcl легко упростить себе жизнь в генерировании подобных вещей. Пара экранов кода и примеры выше можно описывать одной командой «field»:
А тело сертификата описать так:
На мой взгляд, это на порядок человечнее чем XML/JSON Schema. Кто работал с ASN.1 схемами — поймут без дополнительных объяснений. И вся эта запись с field:
превращается в KEKS-закодированный байт-код команд проверки.
Предполагается, что KEKS-закодированные команды можно встроить прямо во время компиляции в программу. Полная проверка структуры публичного ключа (сертификата) занимает 682 байта на данный момент. Причём даже gzip-ом это сожмётся в два раза.
Здесь нет аналога ASN.1 CHOICE-ов и DEFINED BY полей. Нет уверенности стоит ли его вводить и просто ли это будет сделать. Да и в библиотеках реализующих ASN.1 их поддержка редко имеется. Грубо говоря, всё равно в коде будет switch по полям с идентификаторами.
Так каким же получился формат сертификата? А точнее форматы криптографических сообщений, называемые KEKS/CM (cryptographic messages), по аналогии с CMS.
Чем сертификат принципиально отличается от других подписанных данных? Ничем. Поэтому почему бы не сделать сертификат просто одним из видов подписываемых данных? Рассмотрим «cm/signed» (значение MAGIC):
Всё это напоминает CMS SignedData. Так уж вышло, что SignedData оказалась одной из более-менее адекватных структур, в отличии от PKCS#12. А сам публичный ключ (pub-load) вкладывается в /load/v.
Подпись sig должна содержать дополнительные поля, специфичные для сертификата:
В структуре публичного ключа может быть несколько криптографических публичных ключей. Бывают application use-case, когда несколько алгоритмов используются всегда совместно. Поле имени («sub»ject) содержит одноуровневый MAP со строками. «id» по факту является хэшом от поля с публичными ключами, аналогично SubjectKeyIdentifier из X.509.
Возможно создание нескольких подписей над публичным ключом, так как все CA-specific данные вынесены из тела pub-load в pub-sig-tbs структуру подписи. Таким образом, можно иметь разные trust anchor.
«sid» подписи это «id» поле публичного ключа. «cid» является идентификатором сертификата в пределах данного подписанта/CA. UUIDv7 для этого хорошо и удобно подходит. Подпись создаётся над:
Пример подписанного публичного ключа (сертификата):
Наличие /load/v поля опционально. Данные можно предоставить вне cm/signature контейнера. В этом случае, подпись вычисляется над:
При этом, скорее всего, вы захотите сразу же производить хэширование данных. В этом случае, «включается» prehash режим. Многие алгоритмы подписи не имеют разницы между prehash режимом и «чистым», так как они идентичны. Но например в Ed25519 и SLH-DSA, это два отдельных случая, с разными значениями подписей, где prehash не имеет «collision resilience» свойства. Идентификатор алгоритма подписи явно указывает был ли включён особый prehash режим.
Этот режим хорош ещё и тогда, когда вы заранее не имеете на руках всего объёма подписываемых данных, хотите вычислить подпись потоково. В этом случае формирование файла с данными и подписью происходит так:
где prehash это:
Пример файла с 300KiB данными и prehashed подписью SLH-DSA алгоритмом:
тогда как его публичный ключ (cm/signed без подписи) проверки:
На данный момент, в спецификацию алгоритмов подписи внесены следующие:
Были мысли о создании гибридных PQ/T подписей, совмещая «традиционную» и «пост-квантовую» криптографию, но имея SPHINCS+ — традиционная бессмысленна. Eliminate the state! Насколько понимаю, можно было бы заменить SHA2 в SPHINCS+/SLH-DSA на Стрибог и это было бы сразу же готовое решение для ГОСТов.
Почему в KEKS/CM так часто используется BLAKE2, даже форсированно заменяя SHA2, как в случае с Ed25519? Он основан на одном из финалистов конкурса SHA3 — имеет отличные криптоанализы. Имеет огромный запас прочности — за столь много лет лишь незначительное количество раундов смогли сломать. Он имеет превосходную производительность и простоту/компактность реализации. Основой является HChaCha функция из ChaCha20 алгоритма — поэтому можно переиспользовать код/железо и для BLAKE2 и для ChaCha20 вычислений. Будучи поклонником Skein (тоже финалист SHA3), я много смотрел в его сторону, но не нашёл весомых аргументов за.
Я не вижу смысла в использовании SHA2. Да, его безопасность пока вне сомнений. Но он самый медленный среди хоть сколько то массово применяющихся криптографических алгоритмов. Отнюдь не компактен в реализации. Потенциально сильнее течёт по побочным каналам. В Keccak (SHA3 победитель) меньше примитивов используется. Его SHAKE вариант более чем достаточный для замены SHA2, работает быстрее (потенциально во много раз при наличии аппаратного ускорения). Из-за подверженности length-extension attack, с SHA2 надо быть аккуратным. Поэтому во всех новых стандартизованных алгоритмах мы регулярно видим SHAKE (или SHA3).
У всех трёх алгоритмов подписи (как и просто хэшей в cm/hashed) есть "-merkle" prehash вариант с использованием дерева Меркла. По умолчанию используется подход описанный в Certificate Transparency Просто навсего, данные разбиваются на блоки фиксированного размера (возможно кроме последнего), от каждого считается хэш, а затем пары хэшей до самого верха:
Всё это требует немного больше операций хэширования, но позволяет распараллеливать процесс расчёта. Даже неспешный ГОСТ Стрибог может достигать под ГиБ/сек пропускной способности на моём мобильном процессоре.
Необходима явная дифференциация хэшей для узлов dX и вышестоящих листьев. Certificate Transparency RFC просто предлагает добавлять 0x00 или 0x01 перед хэшируемыми данными. Для некоторых алгоритмов в KEKS/CM применяются чуть изменённые функции:
Так уж совпало, но после создания KEKS/CM, меня стал напрягать факт отсутствия каких-либо продвижений в сторону асимметричной пост-квантовой криптографии в age утилите шифрования, которой я заменил почти все use-case использования GnuPG: Libre/OpenPGP vs OpenSSH/age.
В Go crypto/tls поддержка пост-квантового ML-KEM имеется. В OpenSSH уже много лет назад появился Streamlined NTRU Prime (SNTRUP). В GnuPG добавили Kyber! А вот age никак не защищён от квантовой угрозы, если только не использовать с парольными фразами. В Saltpack нет пост-квантовых алгоритмов. Kryptor, WireGuard, HPKE обеспечивают PQ безопасность только при использовании PSK (pre-shared key).
Раз уже есть написанный KEKS и положено начало KEKS/CM, то почему бы не реализовать и «cm/encrypted» формат, по аналогии с CMS EnvelopedData?
Это незатейливая структура с опциональным payload. Если его нет, то полезная нагрузка идёт после encrypted:
Полезная нагрузка защищена (зашифрована) DEM (data encapsulation mechanism). DEM требует CEK (content encryption key) ключ, который, как правило, находится в защищённом (зашифрованном) виде в одном или более keywrap-контейнерах, ключ KEK (key encryption key) которых узнаётся из KEM (key encapsulation mechanism) функций. Терминология общепринята, ничего нового не изобретается.
Неужто так сложно передать зашифрованный файл?
DEM-ом может выступать просто функция (AEAD) шифрования. Одной из лучших по производительности, запасу прочности, простоте реализации и малом количестве потенциально утекаемых по стороннему каналу данных является Salsa20 и её обновлённый вариант ChaCha20. Вместе с ней чаще всего применяется Poly1305 алгоритм аутентификации сообщений. Совместное использование ChaCha20 и Poly1305 нередко обзывают «ChaPoly».
Шифровать разом всё сообщение не всегда возможно. Оно может быть огромным и нам захочется потоковой обработки. Кроме того, использование одного и того же ключа шифрования, может быть опасным с точки зрения утечек по побочным каналам. Поэтому мы разбиваем сообщение на кусочки фиксированной длины (по умолчанию 128КиБ) и каждый обрабатываем по отдельности. Да, это увеличит размер шифротекста каждых 128КиБ на длину MAC тэга, но не велика потеря. Кроме того, это позволит распараллеливать процесс шифрования.
Необходимо как-то явно сигнализировать о том, что последний chunk является оным. Иначе его можно просто отрезать и это останется незамеченным. Для этого используем один из битов nonce-а, аргумента к ChaPoly. Если аутентификация chunk-а не прошла, то пробуем другое значение бита (предполагая, что у нас на руках последний chunk), и снова пробуем дешифровать.
Таким образом, наш DEM алгоритм мог бы выглядеть так:
Постоянная односторонняя смена ключа и nonce/IV часто называется «key ratcheting» (храповик для ключа) — поэтому в названии DEM есть «kr».
Целесообразность использования XChaCha20 вместо ChaCha20 под вопросом, но он дороже менее чем шифрование одного лишнего блока. Детерминированно вырабатываемые длинные nonce безопасны, хотя и счётчик был бы удовлетворителен.
Но у Poly1305, как и GCM режима, часто используемого с AES, есть неприятная особенность: они не производят «key commitment». Можно довольно просто вычислить/подобрать такую пару (или больше) ключей шифрования, что значение одного MAC тэга для них будет действительным. Конечно, при дешифровании мы получим псевдослучайный мусор на всех ключах, кроме одного. Но MAC нам этого никак не покажет. Для протоколов, где симметричный ключ вырабатывается на основе интерактивного DH-обмена ключами, у атакующего, как правило, нет возможности подсунуть какой-то другой особый ключ — в этом случае отсутствие key commitment не проблема. Но CEK для нашего DEM приходит извне, из сформированного злоумышленником KEM-а. Invisible Salamanders Are Not What You Think. Fast Message Franking. Hybrid Encryption in the Multi-User Setting.
Применение hash-based MAC (HMAC) спасает от этой проблемы. Но тогда HMAC, скорее всего, станет бутылочным горлышком производительности (ChaPoly очень быстр!). Один из вариантов решения проблемы key commitment: добавление 16-32 нулевых байт в начало сообщения и проверка их наличия после дешифрования. Вероятность того, что под «некорректным» ключом данные дешифруются тоже в нужное количество нулей — незначительна.
Но решено делать явный key commitment хэш функцией, добавляя его после AEAD шифротекста. Захэшировать нужно всего несколько десятков байт, что делается быстро. «kc» в названии алгоритма и есть key commitment.
Здесь и далее часто применяется HKDF. Я уверен, что он много где избыточен, как и факт применения HMAC внутри него. Банальных XOF функций (BLAKE2X, SHAKE) было бы достаточно. Но у него есть ряд доказанных свойств о безопасности и это, скорее, просто консервативный подход, не сильно отражающийся на производительности. Плюс его API позволяет удобно указывать контексты применения.
Мы видели выше, что KEM-ов (получателей) может быть несколько. KEM «передаст» каждому из них наш общий CEK. Таким образом, размер сообщения при добавлении нового получателя увеличится только на размер KEM-а.
Но появляется опасность того, что любой из получателей может заменить полезную нагрузку на свою собственную. Он же знает общий для всех CEK! Если полезная нагрузка содержит дополнительную аутентифицирующую отправителя информацию (например cm/signed), то тогда это не страшно. В противном же случае, необходим другой DEM, который бы был безопасен в multi-recipient («mr» в названии алгоритма) условиях.
«Fast Message Franking» документ упоминает «compactly committing AEAD» схемы шифрования, где commitment результат работы ccAEAD можно включить внутрь контейнера каждого KEM-а, вместе с CEK-ом. Однако это неприменимо в условиях потоковой обработки данных, которые идут после cm/encrypted.
Поэтому решено пойти по пути меньшей производительности, но зато простоты и надёжности. Каждому получателю, в каждый KEM, мы вкладываем не только общий CEK, но и уникальный per-recipient MAC ключ (prMAC). А к каждому 128КиБ блоку данных, добавляем per-recipient MAC тэг.
MAC вычисляется над хэшом от шифротекста — таким образом нам не нужно для каждого получателя хэшировать полностью весь 128КиБ объём данных. Применять Poly1305 тут не имеет смысла. А за счёт использования hash-based MAC соблюдается и свойство key commitment-а.
Для ГОСТовых алгоритмов предлагается такой простой DEM с key commitment-ом за счёт использования HMAC:
Каждый KEM содержит зашифрованный KEK-ключом контейнер с ключевым материалом (как минимум CEK) для DEM. На данный момент предлагаются простейшие keywrap решения.
KEK ключ вырабатывается уже конкретным алгоритмом KEM.
Как правило, мы хотим зашифровать сообщение либо используя асимметричную криптографию, указывая публичные ключи получателей, либо используя симметричную криптографию, указывая парольную фразу в качестве ключа. Плюс варианты с разделением симметричных ключей на части.
Для выработки KEK-а на основе парольной фразы, предлагается Balloon алгоритм усиленного по памяти (memory hardened) хэширования паролей:
Balloon алгоритм появился позже password hashing competition, где выиграл Argon2. Но, судя по документу Balloon, у него меньше шероховатостей чем у Argon2. Кроме того, Balloon не диктует какую конкретно функцию хэширования использовать: он является таким же конструктором над хэшом, как PBKDF2. Argon2 же является полноценным алгоритмом хэширования. Применить Balloon совместно со Стрибогом должно быть значительно проще для сертифицирующих органов. Balloon довольно прост в реализации. Хоть для меня это и слабый аргумент, но именно он, а не Argon2, рекомендован NIST-ом к применению.
Не запрещено использование и нескольких KEM-ов на основе парольной фразы. Но стойкость, очевидно, будет равна стойкости самой слабой.
Пока самым простым KEM-ом является основанный на ГОСТ Р 34.10-2012. Потому что у нас пока нет стандартизованных пост-квантовых алгоритмов. gost3410-hkdf присутствует пока только для галочки. Это банальная передача эфемерного публичного ключа и его DH со статическим долгоживущим ключом получателя.
Выше мы увидели упоминание «sender» и поля «from».
Поле «to» используется исключительно чтобы не заставлять получателя перебирать свои ключевые пары при попытке дешифрования. Его отсутствие сделает получателя как бы анонимным.
Штатно cm/encrypted обеспечивает только целостность, аутентичность и конфиденциальность передаваемых данных. Если же нам важно ещё и аутентифицировать отправителя, то необходимо что-то дополнительно.
Аутентификацией может выступать подпись, cm/signed вложенный в cm/encrypted. Как это часто делается в CMS и PGP. Подпись cm/encrypted не всегда желательна: так мы показываем кто является отправителем. Кроме того, я же могу подписать и чей-то чужой шифротекст, а получатель сделает вывод как-будто я его сформировал. И наоборот: мой подписанный cm/signed кто-то может в зашифрованном виде отправить, а подумают что я был инициатором.
Необходимо связывать эти два действия (шифрование и подпись) вместе, делать «signcryption». Например заполняя поле /sigs/*/tbs/encrypted-to в cm/signed, явно и чётко указывая идентификаторы ключей получателей зашифрованного сообщения. Подпись явно аутентифицирует наше намерение отправки зашифрованного сообщения заданным получателям.
Однако, сам факт использования полноценной подписи тоже не всегда желателен, так как она non-repudiable и non-deniable: мы не можем отрицать факт её создания для сторонних третьих лиц.
Представьте, что я во время живого общения кому-то сказал что-то нелицеприятное: это сообщение было аутентифицировано для собеседника, так как он в живую видел меня бросающим слова. Однако он не может третьим лицам доказать, что я действительно их произнёс.
Представьте, что во время TLS/IPsec/whatever зашифрованного общения, где передаются сообщения аутентифицированные симметричным MAC-ом, мы будем публиковать MAC-ключи после. Принимающая сторона, получив сообщение прежде, будет уверена в аутентичности пакетов данных. Но сам факт наличия раскрытых MAC-ключей сделает возможность создания корректного MAC тэга любым сторонним человеком. Конфиденциальность же сообщений никто не нарушал при этом. Это будет deniable, repudiable аутентификация.
Так вот cm/encrypted KEM с «from» полем позволяет аутентифицировать отправителя по его KEM-ключу, без использования полноценных подписей. Кроме того, это будет и значительно дешевле по затратам. «from» содержит идентификатор публичного ключа отправителя. Его (скорее всего уже не публичный ключ, а сертификат) для удобства можно вложить и в cm/encrypted контейнер рядом. Можно заполнить нулями, явно сигнализируя об использовании долгоживущего ключа отправителя, но скрывая его значение, заставляя получателя перебирать возможные варианты, всё ради анонимности отправителя. Факт использования sender ключа это просто дополнительное DH вычисление.
Но не стоит забывать, что cm/encrypted это не интерактивный протокол с несколькими приёмо-передачами (round-trip). Тут не может участвовать эфемерный ключ получателя, а значит свойства «прямой секретности» (forward secrecy) не будет — ранее отправленные сообщения будут уязвимы при компрометации долгоживущих ключей. А также возможна key compromise impersonation атака (тут уж или подпись или интерактивный протокол спасут).
Это первый KEM сделанный в KEKS/CM, на замену age утилиты.
Использует гибридную PQ/T криптографию: одновременно «традиционный» X25519 с пост-квантовым Streamlined NTRU Prime. Просто навсего вычисляются общие секреты X25519 алгоритма и SNTRUP, которые затем комбинируются в единый общий секрет.
Есть множество предложений по тому, как стоит комбинировать ключи. Однозначный выбор был сделан в пользу Chempat, который явно хэширует весь контекст ключевого обмена, что возможно и избыточно для ряда участвующих алгоритмов, но не может не быть неправильным. X-Wing, предлагающийся при комбинирования с ML-KEM, не хэширует ни PQ шифротекст, ни его публичный ключ, полагаясь на учёт оных в ML-KEM алгоритме. Для одних KEM алгоритмов он будет безопасен, а для других под вопросом, в отличии от чуть более дорогого Chempat.
Хэширование публичных ключей внутри HKDF вызовах делается для того, чтобы можно было заранее однократно посчитать эти значения. Если для SNTRUP это ещё терпимые объёмы, то у Classic McEliece алгоритма публичные ключи занимают более мегабайта! Их хэширование может занимать больше времени, чем вычисление общих секретов. Хэш от публичного ключа можно сохранять прямо в cm/pub структуре.
Так как SNTRUP это не DH, а именно KEM, то мы не можем заставить его выполнить какое-то преобразование с использованием нашего долгоживущего приватного ключа, выполнив тем самым аутентификацию отправителя. API KEM не позволяет это сделать не в интерактивном режиме. Поэтому пока аутентификация отправителя производится только с использованием X25519. Но на безопасность конфиденциальности, даже при гипотетической компрометации ключей квантовыми компьютерами, это не влияет негативно.
Почему выбран SNTRUP, а не ML-KEM? Судя по: NTRU Prime: Warnings, Debunking NIST's calculation of the Kyber-512 security level, есть (очередные) сомнения в решении NIST. Серьёзных проблем в SNTRUP популярных реализациях, давно применявшихся в OpenSSH, не было найдено, тогда как критические в Kyber обнаружены уже после его победы.
Рекомендуемый к применению PQ/T гибридный KEM:
Classic McEliece. McEliece standardization. McEliece — один из старейших алгоритмов согласования ключей. За десятилетия существования в нём не нашлись сколь либо серьёзных проблем. Он также является устойчивым ко взлому на квантовых компьютерах. Консервативный и надёжный вариант.
Недостатком является размер его публичного ключа: 1047319 байт! Для интерактивных протоколов с эфемерными ключами это относительно болезненно. А вот для cm/encrypted задач, где используются долгоживущие статические ключи, которыми достаточно один раз заранее обменяться, это не проблема. Кроме того, у Classic McEliece 6960-119 очень компактный 194 байт шифротекст.
По сути, все вычисления Classic McEliece и X25519 можно было бы произвести по аналогии с sntrup761-x25519-hkdf-blake2b. Но глядя на подход DJB в PQConnect, где заявляется про больший порог безопасности McEliece, мы сначала вычисляем его общий ключ, затем шифруем эфемерный публичный X25519 и только после этого производим DH и комбинирование.
Предстоит ещё много работы по покрытию тестами и реализации на Си многого из всего вышеописанного. Но некий рабочий proof-of-concept уже доступен на KEKS сайте. Имеются:
В проектах применяется redo, а его goredo реализация вложена в tarball. Make на мыло, redo сила!
Конечно же, это всё является свободным программным обеспечением.
Представьте, что вам надо использовать инфраструктуру публичных ключей (PKI) в каком-то новом проекте. А он ещё и для встраиваемой системы.
Всем известен X.509. Существует масса библиотек реализующих его подмножество работы с сертификатами и проверками цепочек. Тот же OpenSSL. Но можно ли его с чистой совестью кому-либо порекомендовать? Лично я бы не смог ни при каких обстоятельствах. Чуть ли не каждый год в нём находят серьёзные проблемы и ошибки за более чем четверть века существования. Хуже кода по качеству, переусложнённости и аккуратности я пока не встречал среди более-менее крупных серьёзных свободных проектов. Видно, что изначально в нём предполагались красивые абстракции (EVP и подобное), но со временем весь код оброс сплошными if/ifdef. И довольно скудной документацией для разработчика.
Может быть есть другие адекватные реализации подмножества X.509? Можно ли вообще полноценно реализовать X.509 стандарт? Нам с коллегами не известно ни одно свободное/открытое решение. Большие сомнения и с проприетарными. Попробуйте поработать с link+cross сертификатами при наличии indirectCRL и name constraints. Дичайшая, никому не нужная переусложнённость (кроме членов комитетов её создавших). Неспроста появился WebPKI и CA/Browser Forum, в котором уже даже избавляются от CRL, донельзя стараясь всё упростить (правда, ценой централизации WWW в виде Let's Encrypt). X.509 и ASN.1 диктует бизнес, а не инженеры.
Может стоит использовать WebPKI и не париться с 99%+ возможностей X.509? Многие ошибки в OpenSSL были связаны не каким-то определённым функционалом, а напрямую с ASN.1 (BER/DER) кодеком. А также с вынужденно сложными структурами представляющими X.509 сертификаты.
Сложности с ASN.1
Небольшое введение в ASN.1.
А давайте просто попробуем найти кто реализует ASN.1 DER? У всех есть BER (пускай и без REAL типа, не нужного в криптографии). Но для строгого DER необходимы дополнительные проверки после декодирования. Достаточно посмотреть на код библиотек и оценить:
- Как декодируется BOOLEAN? TRUE это просто значение больше нуля?
- А проверяется ли сортировка элементов SET OF?
- Есть ли проверка на факт минимального кодирования INTEGER?
Ни OpenSSL, ни Go crypto/tls, ни Mbed TLS, ни WolfSSL, ни GNU Libtasn1, ни Bouncy Castle, ни cryptlib, ни NSS не делают хотя бы что-то одно из этого. Соответственно, ни одна из перечисленных реализаций не имеет настоящего DER декодера и может успешно принять некорректные структуры.
Мы с коллегами неоднократно видели даже CA (!) сертификаты, в которых или регулярное несоответствие схемам ASN.1 (например выходящая за границы длина полей, особенно в российских сертификатах) или даже некорректное DER кодирование (неотсортированные SET). В реальном мире полно сертификатов, где внутри GeneralNames CHOICE чужеродные структуры с точки зрения схем.
Таким образом, за десятилетия существования X.509, у нас не то что нет ни одной его достойной well-known реализации, но даже ASN.1 DER декодеров. В моём проекте PyDERASN имеется строгая проверка DER, но он написан на Python, поэтому ни о каких embedded систем речи не идёт. Никогда заранее не известно будут ли X.509 или CMS реализации работать между собой, если только не используется крохотное подмножество стандарта.
Проблема с ASN.1 касается и распространённых CMS сообщений для подписи и шифрования данных. Там вообще смесь из BER и DER кодирования.
Сам факт наличия ASN.1 кодирования — огромная поверхность для атак, в виду его большой относительной сложности. Брюс Шнайер ещё в 1990-х в «Прикладной криптографии» давал совет: по возможности, лучше к нему не притрагиваться.
Альтернативы ASN.1
Какие альтернативы есть? CV-сертификаты, применяемые в паспортах с чипами — являются подмножеством ASN.1 DER с существенно упрощённой структурой сертификата. Но они покроют задачу только по работе с публичными ключами. Форматы основанные на JSON — безумие по нерационально используемому месту, и невозможность использовать во встраиваемых системах. Simple PKI тоже покрывает только PKI, но не CMS.
LibrePGP/OpenPGP существенно проще и по кодированию и по форматам, чем ASN.1 X.509, но в нём много архаичных рудиментов и своих сложностей. А сейчас ещё есть раскол между LibrePGP и OpenPGP, идущими параллельными несовместимыми между собой дорогами.
Но кто мешает сделать свой простой препростой формат для этих задач? Придумывать сложные вещи, особенно если соберётся комитет — легко. А простые вещи, легко и надёжно реализуемые — сложно. Факт известный всем инженерам.
Многие проекты идут по пути создания собственных форматов. Иногда просто передавая Си-структуры по сети. Где-то закодированые XDR кодеком. Где-то Protocol Buffers. Где-то MessagePack. Всё это уже относится к категории адекватных, разумных и де-факто выполнимых вещей, а не де-юре существующих только на бумажке.
Требования к кодеку
Мы с коллегами принципиально хотели бы иметь формат кодирования не требующий схему. Схема безусловно даёт ряд неоспоримых преимуществ. Но удобство, как могло бы быть с schema-less форматом типа JSON, bencode, MessagePack — перевешивает. Видимо, после многолетней работы с ASN.1 не хочется никоим образом зависеть от них. Хотя мой опыт работы с protobuf был исключительно положительным.
Главнейшее требование к кодеку: простота реализации, малое количество кода, дабы сократить поверхность атаки. Если кодек достаточно прост, чтобы его можно было на любом другом языке реализовать за несколько часов/за день, то и вопросы совместимости отпадают. Если, предположим, в каком-нибудь Lua нет ASN.1, то проще выбрать другой язык. Если же вопрос реализации кодека на Lua — половина дня работы, то это уже не проблема.
Для криптографических задач критична детерминированность кодека. Единственно верное, каноничное представление данных. Хотя есть и вариант принятый в JSON-based криптографии: просто засовывать JSON внутрь строки другого JSON. Но это жуткий overhead и делается от безысходности и ограниченности web-экосистемы.
Для встраиваемых систем, для мест, где может быть bare metal без ОС: крайне желательно потоковое кодирование. Без него мы будем вынужденны иметь дело с буферизацией, динамической памятью и куда более сложным кодом из-за этого.
Приемлемая/достаточная компактность сериализованных данных. Объективной меры, что считать достаточно компактным — нет. Но если сертификат будет занимать в два раза больше чем X.509 ASN.1 DER версия, то неприятно, ведь мы не должны забывать и про какие-нибудь смарт-карты, где каждый килобайт на счету.
Пожеланием является и достаточное количество возможных типов данных, чтобы можно бы было прозрачно заменить JSON, как это часто делают BSON или MessagePack кодеками. Обязательная дифференциация бинарных строк и человекочитаемых текстовых! Крайне желательная возможность передачи строк более четырёх гибибайт, ибо какой же это general purpose кодек, если в нём нельзя содержимое относительно большого файла разом передать? Желательна родная поддержка datetime объектов: это очень часто используемый тип данных.
Рассматриваем варианты
Поразительно, но удовлетворяющего всем требованиям кодека не нашлось! Какие принимались во внимание?
Netstrings позволяют закодировать только строки: printf("%d:%s,", len(s), s). Не потоковый. Чтобы передать списки или словари: нужно их эмулировать в виде NS(NS(s0) || NS(s1) || ...) и в коде преобразовывать в более высокоуровневые структуры.
Canonical S-expressions аналогичны Netstring, но, добавляя круглые скобочки, позволяют передавать списки. Но те, кто работал с csexp и SPKI, говорят о геморрое пост-обработки подобных данных.
Bencode придуман для BitTorrent.
- printf(«i%de, i) — integer
- printf(»%d:%s", len(s), s) — строка
- «l» ||… ||… || «e» — списки
- «d» || str(key) ||… || «e» — словари
При этом, в словарях ключи обязаны быть отсортированы. Потоковый (кроме строк), детерминированный, простой (реализация всего кодека на Python умещается на экран). Но не всегда компактен, нет дифференциации бинарных и человеческих строк.
JSON — сложная громоздкая реализация без поддержки бинарных данных.
BSON нередко занимает больше места чем JSON, не детерминирован, не потоковый,
нет datetime, нет длинных строк.
Universal Binary JSON не детерминирован, не потоковый, нет длинных строк, не дифференцирует строки.
MessagePack не потоковый, не детерминирован, нет datetime, нет длинных строк.
CBOR, судя по описанию, должен быть идеалом! Всё что нам нужно — упомянуто в его спецификации. Но при пристальном рассмотрении, он полностью отпадает. Это самый переусложнённый формат из всех что встречал (исключая ASN.1).
- В нём есть система тэгирования данных, как в ASN.1. Многие реализации её вообще не поддерживали. В MessagePack есть extension поле, но оно в общем случае (почти?) не используется. В CBOR-е использование тэгированных данных встречается сплошь и рядом. Поддержка datetime производится только через тэги. Если реализация CBOR не поддерживает тэги, то и не будет datetime.
- В качестве ключей словарей могут выступать почти любые типы данных. Как же должен будет декодироваться словарь с int(1), «1», True и 1.0 ключами? Как это будет выглядеть в Python, Lua, Tcl?
- Каноничное представление CBOR по определению не может быть потоковым. Наши два требования — взаимоисключающие для CBOR. Кроме того, не всех устраивают недостаточно строгие правила каноничного представления и придуман ещё и dCBOR, который требует нормализации Unicode символов. Что не очень разумно для embedded систем.
- Какие реализации CBOR поддерживают строгое декодирование каноничного представления CBOR или dCBOR? Среди нескольких десятков библиотек на Си и Go не нашлось ни одной!
- Отдельной проблемой видится желание авторов структур для CBOR экономить на байтах. Вместо плюс-минус человекочитаемых названий ключей, используют целые числа или тэги. Почти старый добрый ASN.1 BER.
KEKS
Может применять какой-нибудь MessagePack, как это сделал Saltpack? Добавить несколько if-ов для проверки детерминированного кодирования? Подправить для потоковой передачи хотя бы списков/словарей. 32-бит длины поменять на 64-бит? Но это в любом случае будет несовместимый с оригиналом кодек.
А раз ничего достаточно удовлетворительного (простота, детерминированность, потоковость, компактность, достаточное количество типов данных) нет, доделка существующих кодеков будет несовместима, то ничего не удерживает от реализации собственного кодека с нуля. Главное чтобы он был достаточно простым для реализации.
Так и появился KEKS формат:
Kompakt (compact) Entschlossen (deterministic) Knapp (concise) Strömen/stream(able)
Изначально фигурировало название YAC: «Yet Another Codec», «YAC Ain't CBOR».
Кодирование — банальный TLV-like (tag-length-value) подход, где «L» и «V» могут отсутствовать. Только детерминированное, только потоковое.
Принципиально не хотели ASCII-закодированных длин, varint или zig-zag кодирования int-ов — всё это требует нетривиального кода, в котором будут if-ы в циклах, что вредит производительности. Только строковые ключи в словарях! Никаких меток, тэгирования!
Какие типы данных KEKS поддерживает?
- NIL (none, null), FALSE и TRUE кодируются одним только тэгом.
- HEXLET: тэг + 16 произвольных байт. В нём можно передать UUID, IPv6. Он не экономнее чем кодирование бинарной строкой, но присутствует ради удобства пользователя.
- у строк выставлен 8-й бит тэга.
7-й бит обозначает бинарная ли она или UTF-8. Оставшиеся 6 бит кодируют длину: Значения 0-60 используются как есть. 61 означает: значение следующих 8 бит + 61. 62: следующие 16-бит + 255 + 62. 63: следующие 64-бит + 65535 + 255 + 63.
Суммирование, вместо прямого использования 8/16/64 бит as-is, делается чтобы избежать наличия проверки на минимальность кодирования.
Для UTF-8 строк есть дополнительное условие: это должна быть последовательность корректных UTF-8 codepoint-ов. Да, для этого надо в цикле по каждому байту пройтись. Но UTF-8 строки вряд ли будут чересчур длинными. Код на Си для UTF-8 может занять менее экрана. Для удобства разработчика, в них запрещён нулевой байт. - для целых чисел выделено два тэга: положительные или отрицательные. После тэга идёт KEKS-закодированная бинарная строка содержащая big-endian значение числа. Отрицательные числа декодируются как (-1 — value). Так же, кстати, и в CBOR делается.
- FLOAT передаётся как тэг с двумя KEKS-закодированными INT-ами, содержащими произвольной длины мантиссу и экспоненту (по основанию 2). Не компактно, но этот тип данных редко где встречается в «общих» задачах.
- LIST: тэг + сконкатенированные произвольные элементы списка + EOC. EOC — нулевой байт.
- MAP кодируется аналогично, но парами key-value значений. Ключ — не пустая строка. Все ключи отсортированы побайтно по возрастанию, с учётом длины (короткие сначала).
- SET: это MAP, значения которого являются NIL-ами. В некоторых реализациях поддерживается для удобства человека.
- для кодирования datetime выделено три тэга: TAI64, TAI64N, TAI64NA. Это предложенный Дэниелем Бернштейном (DJB) формат. 64-бит big-endian количество TAI секунд с 1970-го года, плюс 2**62. «Смещение» значения времени относительно нуля — удобство для того, чтобы время до 1970 можно было указывать без преобразования в отрицательное число. TAI64N добавляет к TAI64 32-бит big-endian количество наносекунд. TAI64NA добавляет ещё 32-бит количество аттосекунд.
Главная особенность: это не UTC, а TAI — не астрономическое, а атомное время. TAI, в отличии от UTC, идёт монотонно. В UTC же есть добавочные секунды. Это означает, что для преобразования TAI⇔UTC нужна база данных leap seconds. Но на данный момент это всего лишь 27 32-бит чисел, что занимает чуть больше 100 байт и требует один простейший цикл. - BLOB: потоково закодированная бинарная строка:
тэг + 64-бит big-endian chunk-len + BIN(chunk) + ... + BIN(last-chunk).
last-chunk должен иметь меньшую длину чем chunk-len, пускай даже нулевую.
В формате типа ASN.1 CER, который тоже потоковый, все строки насильно разбиваются на кусочки (chunk), что создаёт неудобства для программиста, так как в памяти данные будут расположены не линейно. В KEKS же, чёткое разделение атомарных и потоковых строк. Как правило, мы заранее знаем, где у нас произвольные данные огромного размера могут пойти — там будем применять BLOB.
Размер chunk-а мы выбираем по собственному желанию, поэтому при декодировании BLOB, он превращается в кортеж из строки и длины chunk, чтобы детерминированно восстановить его закодированный вариант. chunk-и имеют длину chunk-len + 1 (опять же, чтобы избавиться от проверки chunk-len != 0). - MAGIC: 16 байт, начинающиеся с «KEKS» ASCII символов. 12 оставшихся байт могут содержать произвольные значения. Существует исключительно для удобства, чтобы в начале файлов указывать что за структура данных следует далее. Это аналог заголовка PEM-формата, благодаря которому, мы можем в одном файле хранить и ключ и сертификат.
Само собой, для встраиваемых систем можно не включать поддержку MAGIC, BLOB и FLOAT. Также как и преобразование TAI⇔UTC далеко не всегда нужно.
Проверка декодированных структур
А теперь нам бы ещё не помешала… схема. Декодировать мы можем и без неё, но почти всегда нужно сделать многочисленные проверки после.
Применять XML Schema или JSON Schema — не вариант, из-за безумной сложности этих стандартов и зоопарка реализаций, поддерживающий разные подмножества их функций. Да и запускать функции проверки на их основе на embedded системах — не вариант.
В чём заключаются проверка структур? В 90%+ случаев она сводится к однообразным простейшим командам «убедись, что есть поле XXX», «убедись, что длина поля равна XXX», «убедись, что тип данных у поля XXX», и т.д… Список подобных команд был бы одинаков для любой реализации кодека. Он, по сути, является неким байт-код представлением схемы. Нужен только интерпретатор подобного байт-кода команд проверки.
Схемы представляют из себя словарь, где ключами являются их названия, а значениями списки команд. Каждая команда тоже является списком, где первым элементом идёт строка с названием команды. Остальные элементы списка специфичны для каждой команды. Какие команды имеются?
- TAKE x — взять на «рассмотрение» элемент x. Если x это NIL, то берётся корневой элемент переданных данных. Если x это INT, то берётся x-ый элемент списка. Если x это STR, то берётся значение словаря по ключу x. Все последующие команды выполняются (делают проверки) над taken элементом. Он может и отсутствовать — это штатная ситуация.
- EXISTS — убедиться, что выбранный (taken) элемент существует.
- TYPE t0 t1… — убедиться, что тип данных выбранного элемента во множестве (t0, t1, ...).
- LT x (или GT x) — убедиться, что длина выбранного элемента меньше (или больше) x. Если выбранный элемент это INT, то проверяется его значение. Если это BIN/STR, то проверяется длина строки. Если LIST/MAP, то количество элементов контейнера.
- EQ x — убедиться, что строковое значение выбранного элемента равно x. Позволяет сравнивать BIN/STR, MAGIC, HEXLET, TAI.
- UTC — убедиться, что TAI элемент может быть преобразован в UTC.
- TP x — убедиться, что выбранный элемент TAI имеет точность (time precision) до 10**(-x) секунд. Где-то нам не нужны доли секунд, где-то не более чем миллисекунды.
- SCHEMA x — проверить выбранный элемент напротив схемы x. Реализация очень проста: вызов той же самой функции проверки, просто с ссылкой на другой элемент и другим названием схемы.
- EACH — «раскрыть» выбранный элемент LIST/MAP и последующие команды применять к каждому элементу контейнера. По сути, каждая команда применяется к списку taken элементов: TAKE заполняет список одним элементом, а EACH заменяет его множеством.
Пока их хватает для всех поставленных нами задач. Но ничто не мешает добавить новые, дополнить свои интерпретаторы и схемы. Например проверку максимальной точности FLOAT элемента.
Например, есть схема записанная в CDDL формате:
ai = text .gt 0
fpr = bytes .size 32
our = {a: ai, v: bytes/text, fpr: fpr, ?comment: text}
Словарь «our» содержит опциональное текстовое «comment» поле, обязательное байтовое «v», не пустое текстовое «ai» и «fpr» длиной 32 байта. Его можно проверить так:
{"our": [
["TYPE", "MAP"],
["TAKE", "a"],
["EXISTS"],
["TYPE", "STR"],
["GT", 0],
["TAKE", "v"],
["EXISTS"],
["TYPE", "BIN", "STR"],
["TAKE", "fpr"],
["EXISTS"],
["TYPE", "BIN"],
["GT", 31],
["LT", 33],
["TAKE", "comment"],
["TYPE", "STR"],
]}
или так:
{
"ai": [
["TYPE", "STR"],
["GT", 0],
],
"fpr": [
["TYPE", "BIN"],
["GT", 31],
["LT", 33],
],
"our": [
["TYPE", "MAP"],
["TAKE", "a"],
["EXISTS"],
["SCHEMA", "ai"],
["TAKE", "v"],
["EXISTS"],
["TYPE", "BIN", "STR"],
["TAKE", "fpr"],
["EXISTS"],
["SCHEMA", "fpr"],
["TAKE", "comment"],
["TYPE", "STR"],
]
}
А CDDL схема со списком координат (предположим, что они INT):
latitude = -90..90 longitude = -180..180 where = [latitude, longitude] wheres = [+ where]
может быть проверена так:
{
"where": [
["TYPE", "L"],
["GT", 1],
["LT", 3],
["EACH"],
["TYPE", "INT"],
["TAKE", 0],
["GT", -91],
["LT", 91],
["TAKE", 1],
["GT", -181],
["LT", 181],
],
"wheres": [
["TYPE", "LIST"],
["GT", 0],
["EACH"],
["SCHEME", "where"],
],
}
KEKS/Schema
Но писать такие команды вручную — не самое приятное занятие для человека. Это просто совпадение, но исключительно just-for-fun был когда-то написан KEKS encoder на Tcl. Именно на нём я генерировал подобные списки команд.
MAP {
wheres {LIST {
{LIST {{STR TYPE} {STR LIST}}}
{LIST {{STR GT} {INT 0}}}
{LIST {{STR EACH}}}
{LIST {{STR SCHEME} {STR where}}}
}}
...
}
Но на Tcl легко упростить себе жизнь в генерировании подобных вещей. Пара экранов кода и примеры выше можно описывать одной командой «field»:
ai {{field . {str} >0}}
fpr {{field . {bin} len=32}}
our {
{field . {map}}
{field a {with ai}}
{field v {bin str}}
{field fpr {with fpr}}
{field comment {str} optional}
}
latitude {{field . {int} >-91 <91}}
longitude {{field . {int} >-181 <181}}
where {
{field . {list} len=2}
{field 0 {with latitude}}
{field 1 {with longitude}}
}
wheres {{field . {list} {of where} >0}}
А тело сертификата описать так:
pub-load {
{field . {map}}
{field id {with fpr}}
{field crit {} !exists} {# critical extensions}
{field ku {set} >0 optional}
{field pub {list} {of av} >0}
{field sub {map} {of type str} >0}
}
av {
{field . {map}}
{field a {str} >0} {# algorithm identifier}
{field v {bin}}
}
На мой взгляд, это на порядок человечнее чем XML/JSON Schema. Кто работал с ASN.1 схемами — поймут без дополнительных объяснений. И вся эта запись с field:
{field N {T ...} [optional] [!exists] [{of type T}] [{of S}]
[>n] [<n] [len=n] [=v] [prec=p] [utc]}
превращается в KEKS-закодированный байт-код команд проверки.
Предполагается, что KEKS-закодированные команды можно встроить прямо во время компиляции в программу. Полная проверка структуры публичного ключа (сертификата) занимает 682 байта на данный момент. Причём даже gzip-ом это сожмётся в два раза.
Здесь нет аналога ASN.1 CHOICE-ов и DEFINED BY полей. Нет уверенности стоит ли его вводить и просто ли это будет сделать. Да и в библиотеках реализующих ASN.1 их поддержка редко имеется. Грубо говоря, всё равно в коде будет switch по полям с идентификаторами.
Сертификат
Так каким же получился формат сертификата? А точнее форматы криптографических сообщений, называемые KEKS/CM (cryptographic messages), по аналогии с CMS.
Чем сертификат принципиально отличается от других подписанных данных? Ничем. Поэтому почему бы не сделать сертификат просто одним из видов подписываемых данных? Рассмотрим «cm/signed» (значение MAGIC):
signed {
{field . {map}}
{field load {with load}}
{field sigs {list} {of sig} >0 optional}
{field pubs {list} {of type map} >0 optional}
}
load {
{field . {map}}
{field t {str} >0}
{# field v is optional, arbitrary type}
}
sig {
{field . {map}}
{field tbs {with tbs}}
{field sign {with av}}
}
tbs {
{field . {map}}
{field sid {with fpr}}
{field nonce {bin} >0 optional} {# random bytes}
{field when {tai} utc prec=ms optional}
}
Всё это напоминает CMS SignedData. Так уж вышло, что SignedData оказалась одной из более-менее адекватных структур, в отличии от PKCS#12. А сам публичный ключ (pub-load) вкладывается в /load/v.
Подпись sig должна содержать дополнительные поля, специфичные для сертификата:
pub-sig-tbs {
{field . {map}}
{field sid {with fpr}}
{field cid {hexlet}}
{field exp {with expiration}}
{field nonce {bin} >0 optional}
{field when {tai} utc prec=ms optional}
}
exp-tai {{field . {tai} prec=s utc}}
expiration {{field . {list} {of exp-tai} len=2}}
В структуре публичного ключа может быть несколько криптографических публичных ключей. Бывают application use-case, когда несколько алгоритмов используются всегда совместно. Поле имени («sub»ject) содержит одноуровневый MAP со строками. «id» по факту является хэшом от поля с публичными ключами, аналогично SubjectKeyIdentifier из X.509.
Возможно создание нескольких подписей над публичным ключом, так как все CA-specific данные вынесены из тела pub-load в pub-sig-tbs структуру подписи. Таким образом, можно иметь разные trust anchor.
«sid» подписи это «id» поле публичного ключа. «cid» является идентификатором сертификата в пределах данного подписанта/CA. UUIDv7 для этого хорошо и удобно подходит. Подпись создаётся над:
/load || /sig/./tbs
Пример подписанного публичного ключа (сертификата):
MAGIC cm/pub
MAP {
load {MAP {
t {STR pub}
v {MAP {
id {BIN "6aee..."}
pub {LIST {
{MAP {
a {STR ed25519-blake2b}
v {BIN "c1bf..."}
}}
}}
sub {MAP {
N {STR test}
}}
}}
}}
sigs {LIST {
{MAP {
tbs {MAP {
cid {HEXLET 01963308-1033-75a7-bfb6-7d3ab3db6d63}
exp {LIST {
{TAI64 "2025-04-14 06:41:28"}
{TAI64 "2026-04-14 06:41:28"}
}}
sid {BIN "0087..."}
}}
sign {MAP {
a {STR ed25519-blake2b}
v {BIN "7450..."}
}}
}}
}}
}
Prehashed signature
Наличие /load/v поля опционально. Данные можно предоставить вне cm/signature контейнера. В этом случае, подпись вычисляется над:
detached-data || /load || /sig/./tbs
При этом, скорее всего, вы захотите сразу же производить хэширование данных. В этом случае, «включается» prehash режим. Многие алгоритмы подписи не имеют разницы между prehash режимом и «чистым», так как они идентичны. Но например в Ed25519 и SLH-DSA, это два отдельных случая, с разными значениями подписей, где prehash не имеет «collision resilience» свойства. Идентификатор алгоритма подписи явно указывает был ли включён особый prehash режим.
Этот режим хорош ещё и тогда, когда вы заранее не имеете на руках всего объёма подписываемых данных, хотите вычислить подпись потоково. В этом случае формирование файла с данными и подписью происходит так:
MAGIC(cm/signed) || prehash || BLOB(detached-data) || cm/signed
где prehash это:
prehash {
{field . {map}}
{field t {str} =prehash}
{field algos {set} >0} {# set of hash algorithm identifiers}
}
Пример файла с 300KiB данными и prehashed подписью SLH-DSA алгоритмом:
Magic(cm/signed)
{ 2
t: "prehash"
algos: { 1
slh-dsa-shake-256s-ph: NIL
}
}
BLOB[ 3 l=131072
0: 131072:E2D457B7...
1: 131072:55C74080...
2: 45056:A7E604CD6...
]
{ 2
load: { 1
t: "some-type"
}
sigs: [ 1
0: { 2
tbs: { 3
sid: 32:A437...
when: TAI64N(2025-06-26 13:06:46.571000000 TAI,
2025-06-26 13:06:09.571000000 UTC)
}
sign: { 2
a: "slh-dsa-shake-256s-ph"
v: 29792:9E1...
}
}
]
}
тогда как его публичный ключ (cm/signed без подписи) проверки:
Magic(cm/pub)
{ 1
load: { 2
t: "pub"
v: { 4
id: 32:A437...
ku: { 1
sig: NIL
}
pub: [ 1
0: { 2
a: "slh-dsa-shake-256s"
v: 64:2AC6...
}
]
sub: { 1
what: "ever"
}
}
}
}
Алгоритмы подписи
На данный момент, в спецификацию алгоритмов подписи внесены следующие:
- Ed25519-BLAKE2b и его prehash вариант. Быстрый, компактный по коду, с высоким порогом безопасности. Вместо SHA2-512 используется BLAKE2b, чтобы было ещё компактнее и существенно быстрее. Рекомендуемый вариант для тех, кого не волнует пост-квантовая безопасность.
- ГОСТ Р 34.10-2012 с параметрами только на скрученных кривых Эдвардса. Отдельного prehash варианта нет, так как вычисления ничем не отличаются. Нужен для использования в РФ.
- SLH-DSA-SHAKE-256s (stateless hash-based digital signature algorithm), почти не изменённый SPHINCS+. Устойчив ко взлому на квантовых компьютерах, ибо полностью основан на использовании криптографических хэшей. Не очень быстрый, подписи размером под 30КБ, зато точно никаких сомнений в его безопасности.
Были мысли о создании гибридных PQ/T подписей, совмещая «традиционную» и «пост-квантовую» криптографию, но имея SPHINCS+ — традиционная бессмысленна. Eliminate the state! Насколько понимаю, можно было бы заменить SHA2 в SPHINCS+/SLH-DSA на Стрибог и это было бы сразу же готовое решение для ГОСТов.
Почему в KEKS/CM так часто используется BLAKE2, даже форсированно заменяя SHA2, как в случае с Ed25519? Он основан на одном из финалистов конкурса SHA3 — имеет отличные криптоанализы. Имеет огромный запас прочности — за столь много лет лишь незначительное количество раундов смогли сломать. Он имеет превосходную производительность и простоту/компактность реализации. Основой является HChaCha функция из ChaCha20 алгоритма — поэтому можно переиспользовать код/железо и для BLAKE2 и для ChaCha20 вычислений. Будучи поклонником Skein (тоже финалист SHA3), я много смотрел в его сторону, но не нашёл весомых аргументов за.
Я не вижу смысла в использовании SHA2. Да, его безопасность пока вне сомнений. Но он самый медленный среди хоть сколько то массово применяющихся криптографических алгоритмов. Отнюдь не компактен в реализации. Потенциально сильнее течёт по побочным каналам. В Keccak (SHA3 победитель) меньше примитивов используется. Его SHAKE вариант более чем достаточный для замены SHA2, работает быстрее (потенциально во много раз при наличии аппаратного ускорения). Из-за подверженности length-extension attack, с SHA2 надо быть аккуратным. Поэтому во всех новых стандартизованных алгоритмах мы регулярно видим SHAKE (или SHA3).
Деревья Меркла
У всех трёх алгоритмов подписи (как и просто хэшей в cm/hashed) есть "-merkle" prehash вариант с использованием дерева Меркла. По умолчанию используется подход описанный в Certificate Transparency Просто навсего, данные разбиваются на блоки фиксированного размера (возможно кроме последнего), от каждого считается хэш, а затем пары хэшей до самого верха:
hash
/ \
/ \
/ \
/ \
/ \
k l
/ \ / \
/ \ / \
/ \ / \
g h i j
/ \ / \ / \ |
a b c d e f d6
| | | | | |
d0 d1 d2 d3 d4 d5
Всё это требует немного больше операций хэширования, но позволяет распараллеливать процесс расчёта. Даже неспешный ГОСТ Стрибог может достигать под ГиБ/сек пропускной способности на моём мобильном процессоре.
Необходима явная дифференциация хэшей для узлов dX и вышестоящих листьев. Certificate Transparency RFC просто предлагает добавлять 0x00 или 0x01 перед хэшируемыми данными. Для некоторых алгоритмов в KEKS/CM применяются чуть изменённые функции:
- BLAKE2b инициализируется с ключом «NODE» или «LEAF», превращаясь в BLAKE2b-MAC. Спецификация BLAKE2b позволяет явно указывать режим хэширования деревьев, но не много реализаций поддерживают этот API
- Вместо SHAKE применяется cSHAKE, с personalisation string равным «NODE» или «LEAF»
cm/encrypted
Так уж совпало, но после создания KEKS/CM, меня стал напрягать факт отсутствия каких-либо продвижений в сторону асимметричной пост-квантовой криптографии в age утилите шифрования, которой я заменил почти все use-case использования GnuPG: Libre/OpenPGP vs OpenSSH/age.
В Go crypto/tls поддержка пост-квантового ML-KEM имеется. В OpenSSH уже много лет назад появился Streamlined NTRU Prime (SNTRUP). В GnuPG добавили Kyber! А вот age никак не защищён от квантовой угрозы, если только не использовать с парольными фразами. В Saltpack нет пост-квантовых алгоритмов. Kryptor, WireGuard, HPKE обеспечивают PQ безопасность только при использовании PSK (pre-shared key).
Раз уже есть написанный KEKS и положено начало KEKS/CM, то почему бы не реализовать и «cm/encrypted» формат, по аналогии с CMS EnvelopedData?
encrypted {
{field . {map}}
{field dem {with dem}}
{field kem {list} {of kem} >0}
{field id {hexlet} optional}
{field payload {bin} optional}
}
dem {
{field . {map}}
{field a {str} >0}
}
kem {
{field . {map}}
{field a {str} >0}
{field cek {bin} >0}
{# other fields depending on algorithm}
}
Это незатейливая структура с опциональным payload. Если его нет, то полезная нагрузка идёт после encrypted:
MAGIC(cm/encrypted) || encrypted || BLOB(payload)
Полезная нагрузка защищена (зашифрована) DEM (data encapsulation mechanism). DEM требует CEK (content encryption key) ключ, который, как правило, находится в защищённом (зашифрованном) виде в одном или более keywrap-контейнерах, ключ KEK (key encryption key) которых узнаётся из KEM (key encapsulation mechanism) функций. Терминология общепринята, ничего нового не изобретается.
KEM(recipient/passphrase) => KEK keywrap(KEK, CEK) => secured(CEK) DEM(CEK, payload) => secured(payload)
Неужто так сложно передать зашифрованный файл?
xchapoly-krkc DEM
DEM-ом может выступать просто функция (AEAD) шифрования. Одной из лучших по производительности, запасу прочности, простоте реализации и малом количестве потенциально утекаемых по стороннему каналу данных является Salsa20 и её обновлённый вариант ChaCha20. Вместе с ней чаще всего применяется Poly1305 алгоритм аутентификации сообщений. Совместное использование ChaCha20 и Poly1305 нередко обзывают «ChaPoly».
Шифровать разом всё сообщение не всегда возможно. Оно может быть огромным и нам захочется потоковой обработки. Кроме того, использование одного и того же ключа шифрования, может быть опасным с точки зрения утечек по побочным каналам. Поэтому мы разбиваем сообщение на кусочки фиксированной длины (по умолчанию 128КиБ) и каждый обрабатываем по отдельности. Да, это увеличит размер шифротекста каждых 128КиБ на длину MAC тэга, но не велика потеря. Кроме того, это позволит распараллеливать процесс шифрования.
Необходимо как-то явно сигнализировать о том, что последний chunk является оным. Иначе его можно просто отрезать и это останется незамеченным. Для этого используем один из битов nonce-а, аргумента к ChaPoly. Если аутентификация chunk-а не прошла, то пробуем другое значение бита (предполагая, что у нас на руках последний chunk), и снова пробуем дешифровать.
Таким образом, наш DEM алгоритм мог бы выглядеть так:
H = BLAKE2b
CK0 = CEK
CKi = HKDF-Extract(H, salt="", ikm=CK{i-1})
KEY = HKDF-Expand(H, prk=CKi, info="cm/encrypted/xchapoly-krkc/key")
IV = HKDF-Expand(H, prk=CKi, info="cm/encrypted/xchapoly-krkc/iv", len=24)
if {last chunk} then { IV[23] |= 0x01 } else { IV[23] &= 0xFE }
CIPHERTEXT || TAG = XChaCha20-Poly1305(key=KEY, ad="", nonce=IV, data=chunk)
Постоянная односторонняя смена ключа и nonce/IV часто называется «key ratcheting» (храповик для ключа) — поэтому в названии DEM есть «kr».
Целесообразность использования XChaCha20 вместо ChaCha20 под вопросом, но он дороже менее чем шифрование одного лишнего блока. Детерминированно вырабатываемые длинные nonce безопасны, хотя и счётчик был бы удовлетворителен.
Но у Poly1305, как и GCM режима, часто используемого с AES, есть неприятная особенность: они не производят «key commitment». Можно довольно просто вычислить/подобрать такую пару (или больше) ключей шифрования, что значение одного MAC тэга для них будет действительным. Конечно, при дешифровании мы получим псевдослучайный мусор на всех ключах, кроме одного. Но MAC нам этого никак не покажет. Для протоколов, где симметричный ключ вырабатывается на основе интерактивного DH-обмена ключами, у атакующего, как правило, нет возможности подсунуть какой-то другой особый ключ — в этом случае отсутствие key commitment не проблема. Но CEK для нашего DEM приходит извне, из сформированного злоумышленником KEM-а. Invisible Salamanders Are Not What You Think. Fast Message Franking. Hybrid Encryption in the Multi-User Setting.
Применение hash-based MAC (HMAC) спасает от этой проблемы. Но тогда HMAC, скорее всего, станет бутылочным горлышком производительности (ChaPoly очень быстр!). Один из вариантов решения проблемы key commitment: добавление 16-32 нулевых байт в начало сообщения и проверка их наличия после дешифрования. Вероятность того, что под «некорректным» ключом данные дешифруются тоже в нужное количество нулей — незначительна.
Но решено делать явный key commitment хэш функцией, добавляя его после AEAD шифротекста. Захэшировать нужно всего несколько десятков байт, что делается быстро. «kc» в названии алгоритма и есть key commitment.
COMMITMENT = BLAKE2b-256(KEY || IV || TAG) CIPHERTEXT || TAG || COMMITMENT
Здесь и далее часто применяется HKDF. Я уверен, что он много где избыточен, как и факт применения HMAC внутри него. Банальных XOF функций (BLAKE2X, SHAKE) было бы достаточно. Но у него есть ряд доказанных свойств о безопасности и это, скорее, просто консервативный подход, не сильно отражающийся на производительности. Плюс его API позволяет удобно указывать контексты применения.
xchacha-krmr DEM
Мы видели выше, что KEM-ов (получателей) может быть несколько. KEM «передаст» каждому из них наш общий CEK. Таким образом, размер сообщения при добавлении нового получателя увеличится только на размер KEM-а.
Но появляется опасность того, что любой из получателей может заменить полезную нагрузку на свою собственную. Он же знает общий для всех CEK! Если полезная нагрузка содержит дополнительную аутентифицирующую отправителя информацию (например cm/signed), то тогда это не страшно. В противном же случае, необходим другой DEM, который бы был безопасен в multi-recipient («mr» в названии алгоритма) условиях.
«Fast Message Franking» документ упоминает «compactly committing AEAD» схемы шифрования, где commitment результат работы ccAEAD можно включить внутрь контейнера каждого KEM-а, вместе с CEK-ом. Однако это неприменимо в условиях потоковой обработки данных, которые идут после cm/encrypted.
Поэтому решено пойти по пути меньшей производительности, но зато простоты и надёжности. Каждому получателю, в каждый KEM, мы вкладываем не только общий CEK, но и уникальный per-recipient MAC ключ (prMAC). А к каждому 128КиБ блоку данных, добавляем per-recipient MAC тэг.
H = BLAKE2b
CK0, prMACx0 = CEK || prMACx
CKi = HKDF-Extract(H, salt="", ikm=CK{i-1})
prMACxi = HKDF-Extract(H, salt="", ikm=prMACx{i-1})
KEY = HKDF-Expand(H, prk=CKi, info="cm/encrypted/xchacha-krmr/key")
IV = HKDF-Expand(H, prk=CKi, info="cm/encrypted/xchacha-krmr/iv", len=24)
if {last chunk} then { IV[23] |= 0x01 } else { IV[23] &= 0xFE }
CIPHERTEXT = XChaCha20(key=KEY, nonce=IV, data=chunk)
MACx = BLAKE2b-256-MAC(key=prMACxi, H(CIPHERTEXT))
CIPHERTEXT || MACx || MAC{x+1} [|| MAC{x+2} ...]
MAC вычисляется над хэшом от шифротекста — таким образом нам не нужно для каждого получателя хэшировать полностью весь 128КиБ объём данных. Применять Poly1305 тут не имеет смысла. А за счёт использования hash-based MAC соблюдается и свойство key commitment-а.
kuznechik-ctr-hmac-kr
Для ГОСТовых алгоритмов предлагается такой простой DEM с key commitment-ом за счёт использования HMAC:
H = Streebog-512
CK0 = CEK
CKi = HKDF-Extract(H, salt="", ikm=CK{i-1})
Kenc = HKDF-Expand(H, prk=CKi, info="cm/encrypted/kuznechik-ctr-hmac-kr/enc")
IV = HKDF-Expand(H, prk=CKi, len=8, info="cm/encrypted/kuznechik-ctr-hmac-kr/iv")
Kauth || KauthTail = HKDF-Expand(H, prk=CKi,
info="cm/encrypted/kuznechik-ctr-hmac-kr/auth")
CIPHERTEXT = Kuznechik-CTR(key=Kenc, ctr=IV, data=chunk)
CIPHERTEXT || HMAC(Streebog-256, key={Kauth|KauthTail}, data=CIPHERTEXT)
keywrap
Каждый KEM содержит зашифрованный KEK-ключом контейнер с ключевым материалом (как минимум CEK) для DEM. На данный момент предлагаются простейшие keywrap решения.
- «xchapoly»:
NONCE = random(24 bytes) NONCE || XChaCha20-Poly1305(key=KEK, ad="", nonce=NONCE, data=CEK)
- и стандартизованный для ГОСТов «kexp15»:
Kenc || IV || Kauth = KEK KExp15(Kenc, Kauth, IV, CEK) = Kuznechik-CTR( Kenc, CEK || Kuznechik-CMAC(Kauth, IV || CEK), IV=IV)
KEK ключ вырабатывается уже конкретным алгоритмом KEM.
balloon-blake2b-hkdf KEM
Как правило, мы хотим зашифровать сообщение либо используя асимметричную криптографию, указывая публичные ключи получателей, либо используя симметричную криптографию, указывая парольную фразу в качестве ключа. Плюс варианты с разделением симметричных ключей на части.
Для выработки KEK-а на основе парольной фразы, предлагается Balloon алгоритм усиленного по памяти (memory hardened) хэширования паролей:
kem-balloon-blake2b-hkdf {
{field a {str} =balloon-blake2b-hkdf}
{field cek {bin} >0} {# wrapped CEK}
{field salt {bin} >0}
{field cost {with balloon-cost}}
}
balloon-cost {
{field s {int} >0} {# space cost}
{field t {int} >0} {# time cost}
{field p {int} >0} {# parallel cost}
}
H = BLAKE2b
KEK = HKDF-Expand(H,
prk=Balloon(H, passphrase, /kem/salt, s, t, p),
info="cm/encrypted/balloon-blake2b-hkdf" || /id)
Balloon алгоритм появился позже password hashing competition, где выиграл Argon2. Но, судя по документу Balloon, у него меньше шероховатостей чем у Argon2. Кроме того, Balloon не диктует какую конкретно функцию хэширования использовать: он является таким же конструктором над хэшом, как PBKDF2. Argon2 же является полноценным алгоритмом хэширования. Применить Balloon совместно со Стрибогом должно быть значительно проще для сертифицирующих органов. Balloon довольно прост в реализации. Хоть для меня это и слабый аргумент, но именно он, а не Argon2, рекомендован NIST-ом к применению.
Не запрещено использование и нескольких KEM-ов на основе парольной фразы. Но стойкость, очевидно, будет равна стойкости самой слабой.
gost3410-hkdf KEM
Пока самым простым KEM-ом является основанный на ГОСТ Р 34.10-2012. Потому что у нас пока нет стандартизованных пост-квантовых алгоритмов. gost3410-hkdf присутствует пока только для галочки. Это банальная передача эфемерного публичного ключа и его DH со статическим долгоживущим ключом получателя.
kem-gost3410-hkdf {
{field . {map}}
{field a {str} =gost3410-hkdf}
{field cek {bin} >0} {# wrapped CEK}
{field ukm {bin} len=16} {# additional keying material}
{field pub {bin} >0} {# sender's ephemeral public key}
{field to {with fpr} optional} {# recipient's public key}
{field from {with fpr} optional} {# sender's public key}
}
H = Streebog-512
DH(sk, pk) = GOSTR3410-VKO(prv=sk, pub=pk, ukm=UKM)
PRK = HKDF-Extract(H, salt="", ikm=DH(e, s))
if {specified sender}
PRK = HKDF-Extract(H, salt=PRK, ikm=DH(s, s))
KEK = HKDF-Expand(H, prk=PRK, info="cm/encrypted/gost3410-hkdf" || /id)
Authcryption
Выше мы увидели упоминание «sender» и поля «from».
Поле «to» используется исключительно чтобы не заставлять получателя перебирать свои ключевые пары при попытке дешифрования. Его отсутствие сделает получателя как бы анонимным.
Штатно cm/encrypted обеспечивает только целостность, аутентичность и конфиденциальность передаваемых данных. Если же нам важно ещё и аутентифицировать отправителя, то необходимо что-то дополнительно.
Аутентификацией может выступать подпись, cm/signed вложенный в cm/encrypted. Как это часто делается в CMS и PGP. Подпись cm/encrypted не всегда желательна: так мы показываем кто является отправителем. Кроме того, я же могу подписать и чей-то чужой шифротекст, а получатель сделает вывод как-будто я его сформировал. И наоборот: мой подписанный cm/signed кто-то может в зашифрованном виде отправить, а подумают что я был инициатором.
Необходимо связывать эти два действия (шифрование и подпись) вместе, делать «signcryption». Например заполняя поле /sigs/*/tbs/encrypted-to в cm/signed, явно и чётко указывая идентификаторы ключей получателей зашифрованного сообщения. Подпись явно аутентифицирует наше намерение отправки зашифрованного сообщения заданным получателям.
Однако, сам факт использования полноценной подписи тоже не всегда желателен, так как она non-repudiable и non-deniable: мы не можем отрицать факт её создания для сторонних третьих лиц.
Представьте, что я во время живого общения кому-то сказал что-то нелицеприятное: это сообщение было аутентифицировано для собеседника, так как он в живую видел меня бросающим слова. Однако он не может третьим лицам доказать, что я действительно их произнёс.
Представьте, что во время TLS/IPsec/whatever зашифрованного общения, где передаются сообщения аутентифицированные симметричным MAC-ом, мы будем публиковать MAC-ключи после. Принимающая сторона, получив сообщение прежде, будет уверена в аутентичности пакетов данных. Но сам факт наличия раскрытых MAC-ключей сделает возможность создания корректного MAC тэга любым сторонним человеком. Конфиденциальность же сообщений никто не нарушал при этом. Это будет deniable, repudiable аутентификация.
Так вот cm/encrypted KEM с «from» полем позволяет аутентифицировать отправителя по его KEM-ключу, без использования полноценных подписей. Кроме того, это будет и значительно дешевле по затратам. «from» содержит идентификатор публичного ключа отправителя. Его (скорее всего уже не публичный ключ, а сертификат) для удобства можно вложить и в cm/encrypted контейнер рядом. Можно заполнить нулями, явно сигнализируя об использовании долгоживущего ключа отправителя, но скрывая его значение, заставляя получателя перебирать возможные варианты, всё ради анонимности отправителя. Факт использования sender ключа это просто дополнительное DH вычисление.
Но не стоит забывать, что cm/encrypted это не интерактивный протокол с несколькими приёмо-передачами (round-trip). Тут не может участвовать эфемерный ключ получателя, а значит свойства «прямой секретности» (forward secrecy) не будет — ранее отправленные сообщения будут уязвимы при компрометации долгоживущих ключей. А также возможна key compromise impersonation атака (тут уж или подпись или интерактивный протокол спасут).
sntrup761-x25519-hkdf-blake2b KEM
Это первый KEM сделанный в KEKS/CM, на замену age утилиты.
kem-sntrup761-x25519-hkdf-blake2b {
{field . {map}}
{field a {str} =sntrup761-x25519-hkdf-blake2b}
{field cek {bin} >0} {# wrapped CEK}
{field encap {bin} >0}
{field to {with fpr} optional} {# recipient's public key}
{field from {with fpr} optional} {# sender's public key}
}
Использует гибридную PQ/T криптографию: одновременно «традиционный» X25519 с пост-квантовым Streamlined NTRU Prime. Просто навсего вычисляются общие секреты X25519 алгоритма и SNTRUP, которые затем комбинируются в единый общий секрет.
Есть множество предложений по тому, как стоит комбинировать ключи. Однозначный выбор был сделан в пользу Chempat, который явно хэширует весь контекст ключевого обмена, что возможно и избыточно для ряда участвующих алгоритмов, но не может не быть неправильным. X-Wing, предлагающийся при комбинирования с ML-KEM, не хэширует ни PQ шифротекст, ни его публичный ключ, полагаясь на учёт оных в ML-KEM алгоритме. Для одних KEM алгоритмов он будет безопасен, а для других под вопросом, в отличии от чуть более дорогого Chempat.
H = BLAKE2b
PRK = HKDF-Extract(H, salt="", ikm=
sntrup761-shared-key || es-x25519-shared-key ||
H(sntrup761-sender-ciphertext || e-x25519-sender-public-key) ||
H(sntrup761-recipient-public-key || s-x25519-recipient-public-key))
if {specified sender}
PRK = HKDF-Extract(H, salt=PRK, ikm=
ss-x25519-shared-key ||
s-x25519-sender-public-key ||
s-x25519-recipient-public-key)
KEK = HKDF-Expand(H, prk=PRK,
info="cm/encrypted/sntrup761-x25519-hkdf-blake2b" || /id)
Хэширование публичных ключей внутри HKDF вызовах делается для того, чтобы можно было заранее однократно посчитать эти значения. Если для SNTRUP это ещё терпимые объёмы, то у Classic McEliece алгоритма публичные ключи занимают более мегабайта! Их хэширование может занимать больше времени, чем вычисление общих секретов. Хэш от публичного ключа можно сохранять прямо в cm/pub структуре.
Так как SNTRUP это не DH, а именно KEM, то мы не можем заставить его выполнить какое-то преобразование с использованием нашего долгоживущего приватного ключа, выполнив тем самым аутентификацию отправителя. API KEM не позволяет это сделать не в интерактивном режиме. Поэтому пока аутентификация отправителя производится только с использованием X25519. Но на безопасность конфиденциальности, даже при гипотетической компрометации ключей квантовыми компьютерами, это не влияет негативно.
Почему выбран SNTRUP, а не ML-KEM? Судя по: NTRU Prime: Warnings, Debunking NIST's calculation of the Kyber-512 security level, есть (очередные) сомнения в решении NIST. Серьёзных проблем в SNTRUP популярных реализациях, давно применявшихся в OpenSSH, не было найдено, тогда как критические в Kyber обнаружены уже после его победы.
mceliece6960119-x25519-hkdf-shake256 KEM
Рекомендуемый к применению PQ/T гибридный KEM:
kem-mceliece6960119-x25519-hkdf-shake256 {
{field . {map}}
{field a {str} =mceliece6960119-x25519-hkdf-shake256}
{field cek {bin} >0} {# wrapped CEK}
{field encap {bin} >0}
{field to {with fpr} optional} {# recipient's public key}
{field from {with fpr} optional} {# sender's public key}
}
Classic McEliece. McEliece standardization. McEliece — один из старейших алгоритмов согласования ключей. За десятилетия существования в нём не нашлись сколь либо серьёзных проблем. Он также является устойчивым ко взлому на квантовых компьютерах. Консервативный и надёжный вариант.
Недостатком является размер его публичного ключа: 1047319 байт! Для интерактивных протоколов с эфемерными ключами это относительно болезненно. А вот для cm/encrypted задач, где используются долгоживущие статические ключи, которыми достаточно один раз заранее обменяться, это не проблема. Кроме того, у Classic McEliece 6960-119 очень компактный 194 байт шифротекст.
По сути, все вычисления Classic McEliece и X25519 можно было бы произвести по аналогии с sntrup761-x25519-hkdf-blake2b. Но глядя на подход DJB в PQConnect, где заявляется про больший порог безопасности McEliece, мы сначала вычисляем его общий ключ, затем шифруем эфемерный публичный X25519 и только после этого производим DH и комбинирование.
mceliece-ciphertext || XChaCha20-Poly1305(
key=decapKey,
nonce=decapNonce,
data=e-x25519-sender-public-key,
ad=mceliece-ciphertext)
H = SHAKE256
mceliece-ciphertext, mceliece-shared-key = KEM-Encap(mceliece-recipient-public-key)
mceliece-shared-key = KEM-Decap(mceliece-recipient-private-key, mceliece-ciphertext)
decapKey, decapNonce = HKDF-Expand(H, prk=mceliece-shared-key,
info="cm/encrypted/mceliece6960119-x25519-hkdf-shake256/decap" || /id)
es-x25519-shared-key = X25519(e-x25519-sender-private-key,
s-x25519-recipient-public-key)
PRK = HKDF-Extract(H, salt="", ikm=
mceliece-shared-key || es-x25519-shared-key ||
H(mceliece-sender-ciphertext || e-x25519-sender-public-key) ||
H(mceliece-recipient-public-key || s-x25519-recipient-public-key))
if {specified sender}
ss-x25519-shared-key = X25519(s-x25519-sender-private-key,
s-x25519-recipient-public-key)
PRK = HKDF-Extract(H, salt=PRK, ikm=
ss-x25519-shared-key || s-x25519-sender-public-key)
KEK = HKDF-Expand(H, prk=PRK,
info="cm/encrypted/mceliece6960119-x25519-hkdf-shake256" || /id)
Где код?
Предстоит ещё много работы по покрытию тестами и реализации на Си многого из всего вышеописанного. Но некий рабочий proof-of-concept уже доступен на KEKS сайте. Имеются:
- C99: encoder, decoder, KEKS/Schema интерпретатор, функции и утилита парсинга и проверки цепочек сертификатов ГОСТ Р 34.10 и Ed25519, утилиты pretty-printing, fuzzing тесты. Может работать без malloc, в статическом буфере памяти. Скорость декодирования сравнима с MessagePack реализациями.
- Tcl: encoder, конвертер KEKS/Schema, интеграционные тесты валидаторов схем, утилиты для fuzzing.
- Go: encoder, потоковый decoder, KEKS/Schema интерпретатор, fuzzing тесты, KEKS/RPC, утилиты pretty-printing. cmkeytool: создание, выпуск и валидация сертификатов. cmhshtool: хэширование, включая режим с деревьями Меркла. cmsigtool: создание и проверка подписей, включая detached режим и деревья Меркла. cmenctool: шифрование и дешифрование на парольной фразе и асимметричных алгоритмах, с возможностью встраивания шифротекста. Хэширование и шифрование могут распараллеливаться. Скорость кодирования/декодирования сравнима с MessagePack реализациями.
- Python3: encoder, decoder, тесты.
В проектах применяется redo, а его goredo реализация вложена в tarball. Make на мыло, redo сила!
Конечно же, это всё является свободным программным обеспечением.
nin-jin
По поводу формата, гляньте ещё этот: https://page.hyoo.ru/#!=8i7ao7_xfyxah