Yet Another Codec. YAC is Ain't CBOR

Возня с форматом сериализации данных
(54996a124bd917fbe7a000bfd578030401ab40f2) затянулась ещё на неделю.
Это оказалась ну очень кропотливая работа с тьмой мелочей и постоянных
взвешиваний решений. Речь не только про само кодирование, но и форматы
созданные поверх него, форматы-альтернативные X.509 сертификатам, CMS и
подобному.

Начальство по факту отреагировало вопросом: ну а чем принципиально CBOR
не устраивает? Согласен -- он лучше чем любой ASN.1, наименьшее из зол.
Но в нём два способа кодирования длин (indefinite vs definite), есть
поддержка тэгированных значений. Всё это -- дополнительное усложнение
кодека. Потоковое кодирование упрощает кодирование, уменьшает код. Но
возможно звучит не очень убедительно?

На Wikipedia есть большой список библиотек реализаций CBOR. Я проверил
все Си-шные: ни одна из них не делает хоть какой-либо валидации формата
на тему его детерминированного кодирования. Я взял четыре Go реализации,
среди которых есть хвалящиеся что их используют чуть ли не половина
крупных компаний мира. Ни одна из них не делает хотя бы тривиальные
проверки что тот же integer/length закодированы в минимальном формате.
Дальше я уже проверять ничего не стал. За уйму лет существования CBOR:
проверив кучу реализаций с Wikipedia -- ни одной нет пригодной для
применения в криптографии. CBOR идёт в жопу как вариант для таких задач.

Я не хочу сказать что ASN.1 чем-то лучше: все ASN.1 реализации что я
видел -- в них тоже не все проверки на корректность DER кодирования
имелись. Но, многие хотя бы пытались проводить их! CBOR же создал
впечатление того, что вокруг него только какие-то хипстеры делающие это
всё на коленке. Может быть он просто не для темы криптографии? Возможно.

Видел draft RFC на то, чтобы X.509 сертификаты переложить на CBOR кодек.
Вовсю используются тэгированные значения, но например где поля validity:
просто голые integer-ы UNIX timestamp-ов. Причём многие библиотеки CBOR
что я видел -- не поддерживают тэгированные значения. То бишь... или не
полностью такие сертификаты будут декодированы, либо не декодированы
вовсе. Лень уже было разбираться.

После этого, начальство одобрило попытку применения YAC-а в ряде
проектов. Я долго думал над названием, но ничего лучше чем "Yet Another
Codec", "Yet Another enCoding" не пришло. А потом ещё увидел, что это
можно и как "YAC is Ain't CBOR", с которым я в первую очередь делаю
сравнение.

Также одобрили его публикацию как свободный проект. Пока настолько нет
времени, что руки ещё не доходят, но yac.cypherpunks.su уже вот вот
появится.

Написал реализации на Си, Go, Python (фу, бе, как же почти физически
неприятно было на нём писать, уже аллергия на этот язык). Тестов пока
нет, но есть тестовые вектора, которые у всех у них должны совпасть.
Когда пишешь на Си или Go, то понимаешь насколько он прост или не прост
выходит. А также какие решения по кодированию стоят или не стоят того.

Но вот пока со всем этим возился, то хотелось какой-то инструмент, чтобы
можно было написать "LIST[INT(123) STR("привет")]" и он бы мне выплюнул
YAC-закодированное представление этих данных. Хотел было написать штуку,
которая на вход бы приняла JSON, а на выходе YAC. Но в JSON нет
datetime, нет UUID, плюс дифференциации между разными integer-ами и
float-ами.

И вспомнил про Tcl. На нём у меня по сути только один проект написан, на
полтора экрана кода. Больше я для этого языка применений хороших пока
ещё не находил (ну кроме Tk). А очень хотел. И вот почти ничего не помня
из этого языка, за несколько часов у меня готов YAC encoder. Я могу
написать:

    MAP {
        ints {MAP {
            pos {LIST {
                {INT 0}
                {INT 1}
                {INT [expr {1 << 80}]}
            }}
            neg {LIST { {INT -1} {INT -2} }}
        }}
        nil NIL
        bool {LIST {TRUE FALSE}}
        str {MAP {
            utf8 {STR "привет мир"}
            bin {LIST {
                {BIN ""}
                {BIN [string repeat "0" 60]}
            }}
        }}
        blob {BLOB 5 "1234567890-"}
        dates {LIST {
            {ToTAI64 1234567890}
            {ToTAI64N 1234567890 456000}
            {ToTAI64 [UTCFromISO "2024-10-02 12:13:14"]}
        }}
        uuid {UUID 0e875e3f-d385-49eb-87b4-be42d641c367}
    }

и у меня будет сформирована структура со всеми этими словарями,
списками, разными числами, TAI64-датами и прочими вещами. Вовсю это
использовал, жутко доволен насколько легко это получилось сделать и
удобно мне было с этим работать. Формировать произвольные структуры
в Си или Go -- не так тривиально быстро.

Сам кодек YAC-а уже по сути заморожен. Вообще никаких планов что-то
менять. Сложно сравнивать сложность реализации кодека для него и для
CBOR, но из-за отсутствия тэгов и только применяя потоковое кодирование
-- YAC должен быть попроще. Сама спецификация кодека для него --
считанные страницы. Во многих случаях его формат будет покомпактнее чем
у deterministic CBOR.

Понимаю что многовато форматов данных наизобретено. Но реально
schemaless онных -- не так уж и много. Чтобы детерминированно
кодировались, чтобы можно было в криптографии применять -- ещё меньше.
CBOR шёл правильной дорогой, имел правильные цели, но мне кажется что
они как-будто резко не туда свернули и пошли по пути усложнения формата,
причём не решив проблему с передачей datetime объектов. Делали, делали,
но не доделали. Плюс запрещают потоковое формирование при использовании
детерминированного кодирования.

YAC же, кроме форматов поддерживаемых JSON-ом (как бы он мне не
нравился, но хотелось бы иметь возможность прозрачно его заменять на
более быстрый/компактный кодек, как это можно сделать с MessagePack и
BSON), ещё имеет datetime (в виде TAI64[N[A]]), UUID, int-ы вплоть до
int128, float16 -- float256, бинарные строки. Что покрывает массу
возможных контекстов применения.

комментарий 0:

From: kmeaw
Date: 2024-10-04 12:34:43Z

А почему был отвергнут вариант доработки CBOR? Аргумент с качеством
реализаций не очень понятен - ведь если сравнивать со своим кодеком, то
для него и вовсе нет ни одной реализации. Или хотелось сознательно
внести несовместимость (то есть уменьшить множество осмысленных байтовых
последовательностей, которые одновременно могут быть декодирированы как
CBOR и YAC), чтобы никто (по незнанию) не смог взять готовую
некачественную библиотеку и создать уязвимость в своём приложении?

Ещё могу порекламировать github.com/google/wuffs для написания
C-библиотек - это memory-safe язык с корутинами, пригодный для работы в
pledge/seccomp-подобных окружениях, транспилируется в single-header file
library на C.

комментарий 1:

From: Sergey Matveev
Date: 2024-10-04 19:52:51Z

*** kmeaw [2024-10-04 13:33]:
>А почему был отвергнут вариант доработки CBOR?

Среди MessagePack, BSON, bencode (хотя он мало что умеет) -- CBOR во
много раз более сложен. Его решения в виде запрета streaming-а
(indefinite length) при deterministic encoding -- выглядит крайне
неразумным, только усложняющим encoder. В нём нет чёткого
запрета/условия на недопустимость дубликатов ключей в map-ах -- вместо
того, они просто говорят, что это проблема вышестоящей программы. Всё
это говорит о том, что не ясно что в головах у людей его разрабатывавших.

>Аргумент с качеством реализаций не очень понятен - ведь если сравнивать
>со своим кодеком, то для него и вовсе нет ни одной реализации.

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

По сути: CBOR просто лжёт о том, что их целью является простота. Он куда
более сложен чем тот же MessagePack. Да, в курсе что CBOR чуть ли не как
fork MessagePack родился, потому что тот не поддерживал дифференциацию
binary строк от человекочитаемых. Но проще бы было расширить MessagePack.
В текущей его версии я вижу и наличие datetime и UTF-8 строк. CBOR
выглядит как поделие созданное комитетом: собралось много людей, каждый
со своими желаниями и поэтому они воплощены все в полном объёме.

>Или хотелось сознательно внести несовместимость (то есть уменьшить
>множество осмысленных байтовых последовательностей, которые
>одновременно могут быть декодирированы как CBOR и YAC), чтобы никто (по
>незнанию) не смог взять готовую некачественную библиотеку и создать
>уязвимость в своём приложении?

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

Если и расширять, то стоило бы какой-нибудь MessagePack. Но добавлять
новые типы данных для поддержки строк более 4GiB -- выглядит уж совсем
как костыль. Лучше поменять сам кодек и убрать hard-coded 32-бит длины.
А раз совместимость всё равно потеряется при этом, то почему бы не
сделать его с нуля.

>Ещё могу порекламировать github.com/google/wuffs для написания
>C-библиотек - это memory-safe язык с корутинами, пригодный для работы в
>pledge/seccomp-подобных окружениях, транспилируется в single-header file
>library на C.

Спасибо за наводку. Обязательно посмотрю. Хотя с ходу мне кажется, что
раз там надо делать доказательства безопасности ("proofs of safety" в
README), то у меня не хватит мозгов чтобы с этим работать.

комментарий 2:

From: David Rabkin
Date: 2024-10-14 22:45:17Z

Зачем в названии is? YAC Ain't CBOR — это уже хорошо! Круто, что на
работе тебе доверяют такие проекты. Любой начальник скажет: ты завтра
уйдёшь, кто будет этот формат поддерживать? Протобафом я пользовался,
очень был доволен. Из Вики понял, что CBOR — это следующий шаг. Про
YAC не понял, чем он отличается от CBOR, я не в теме, из описания
здесь отличия не понял. Кстати, лет пятнадцать назад я в коммерческой
компании писал свою версию сериализации и десириалиазации на С++,
прямо как на первом курсе, с таким же, примерно, качеством :-)

комментарий 3:

From: Sergey Matveev
Date: 2024-10-15 04:29:29Z

*** David Rabkin [2024-10-15 01:42]:
>Зачем в названии is?

Да, мне уже сказали что излишне. Убрал.

>Любой начальник скажет: ты завтра
>уйдёшь, кто будет этот формат поддерживать?

Согласен с этой позицией. Но, видимо, действительно, доверяют. Если
достаточно просто и понятно всё сделано, то вопросов о поддержке не
должно возникать. Ну и YAC это маленький проект и начальство должны
беспокоить мои другие :-)

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

Protobuf мне тоже нравился, но с CBOR-ом нельзя сравнивать.
Один -- со схемой, другой -- без. Они для разных задач, разных подходов.

>Про YAC не понял, чем он отличается от CBOR, я не в теме, из описания
>здесь отличия не понял.

Существенно более простой (CBOR -- вообще самый сложный кодек из всех
schemaless что я видел), детерминированный (можно считать что
детерминированного CBOR (или dCBOR) на практике нет (нет реализаций
на том же Си)), в том числе который можно потоково формировать
(детерминированный CBOR даже в теории это запрещает).

Я бы сказал что (d)CBOR это прям ASN.1 из мира schemaless кодеков, по
безумию сложности. Одна их только тема с map-ами, где ключами может быть
тьма типов данных, среди которых ещё и numeric reduction (где float
может превратиться в integer), а UTF-8 строчки надо проверять что они
Unicode-нормализованы.

>Кстати, лет пятнадцать назад я в коммерческой
>компании писал свою версию сериализации и десириалиазации на С++,
>прямо как на первом курсе, с таким же, примерно, качеством :-)

Да я думаю что все это делали. Обычно то это просто application
specific, как правило.