Bijou64: новое каноническое кодирование целых чисел от Ink & Switch

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

Bijou64: каноническое кодирование для безопасного парсинга

Проблема неканонических кодировок хорошо известна в индустрии. Например, в стандарте PKCS1, используемом в криптографии с открытым ключом, неоднозначное представление длины приводило к уязвимостям. Аналогичные проблемы возникали в библиотеках для JWT (JSON Web Token) и даже в реализации Bitcoin. Во всех этих случаях злоумышленники могли подсунуть число в нестандартном, но валидном формате, что приводило к неожиданному поведению при парсинге. Bijou64 решает эту проблему на уровне формата: любое целое число от 0 до 2^64-1 кодируется единственным способом. Это делает парсинг детерминированным и безопасным, устраняя целый класс атак, связанных с неоднозначностью.

Дизайн bijou64 вдохновлён LEB128 — популярным форматом, используемым в WebAssembly, DWARF и других системах. Однако LEB128 не является каноническим: одно и то же число можно закодировать с разным количеством байтов, добавляя ведущие нули. Это открывает вектор для атак, когда парсер ожидает короткое представление, а получает длинное, что может привести к переполнению буфера или некорректной обработке. Bijou64 устраняет эту неоднозначность, используя специальный префиксный код, который однозначно определяет длину кодировки. Таким образом, разработчики получают не только безопасность, но и предсказуемость поведения.

Как работает bijou64?

Кодирование bijou64 основано на простой схеме: первые биты первого байта указывают на количество последующих байтов. Для чисел от 0 до 63 используется один байт (старшие два бита — 00). Для чисел до 16383 — два байта (префикс 01), до 1 048 575 — три байта (префикс 10), и для чисел до 2^64-1 — четыре байта (префикс 11). Таким образом, максимальная длина кодировки — 4 байта, что делает bijou64 компактнее LEB128, который может занимать до 10 байт для 64-битных чисел. При этом декодирование происходит в 2–10 раз быстрее, как показали тесты авторов. Эта эффективность достигается за счёт фиксированной длины для каждого диапазона, что упрощает циклы и позволяет использовать современные процессорные оптимизации.

Какие преимущества bijou64 перед LEB128 в производительности?

Авторы провели бенчмарки, сравнив bijou64 с LEB128 и другими форматами. На процессоре Apple M1 bijou64 показал пропускную способность декодирования около 1.2 миллиарда чисел в секунду для однобайтовых значений, что в 10 раз быстрее LEB128. Для более длинных кодировок разница сокращается, но bijou64 всё равно остаётся быстрее в 2–4 раза. Это достигается за счёт того, что bijou64 использует фиксированное количество байтов для каждого диапазона, что упрощает цикл декодирования и позволяет эффективно использовать спекулятивное выполнение и SIMD-инструкции. Впрочем, на Hacker News развернулась дискуссия о том, что на практике SIMD-оптимизации для bijou64 могут быть не столь эффективны из-за необходимости проверки границ диапазона. Тем не менее, даже без SIMD bijou64 показывает впечатляющие результаты.

Кого затронет новая технология?

Bijou64 в первую очередь интересен разработчикам, работающим с протоколами сериализации, форматами файлов и сетевыми протоколами. Поскольку кодирование переменной длины используется повсеместно — от телеметрии до баз данных, — канонический формат может снизить количество ошибок и уязвимостей. Уже появились порты сообщества на Elixir, Go, Perl и Java, что говорит о живом интересе. Для бизнеса, использующего JWT или PKI, внедрение bijou64 может повысить безопасность без существенных накладных расходов. В России и СНГ технология пока малоизвестна, но может найти применение в финтехе и криптографии, где безопасность и производительность критичны.

Что будет дальше?

Ink & Switch опубликовали спецификацию и эталонную реализацию на Rust. Ожидается, что сообщество продолжит портирование на другие языки. Возможно, bijou64 будет предложен в качестве стандарта IETF или войдёт в состав популярных библиотек сериализации, таких как Protocol Buffers или FlatBuffers. Пока рано говорить о массовом внедрении, но потенциал у формата высокий, особенно в контексте безопасного программирования. Разработчикам стоит следить за развитием bijou64, чтобы быть готовыми к его интеграции в свои проекты.

Итог

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