Poly1305

Poly1305 — это криптографический код аутентификации сообщения (MAC), разработанный Дэниелом Бернштейном. Он предназначен для проверки целостности и подлинности данных, обеспечивая защиту от подделки сообщений. Poly1305 работает в паре с симметричным шифром, чаще всего с AES (режим Poly1305-AES) или с потоковым шифром ChaCha20 (режим ChaCha20-Poly1305), образуя аутентифицированное шифрование.

История

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

В 2013 году алгоритм был стандартизирован в протоколе TLS (RFC 7905) как часть набора шифров ChaCha20-Poly1305. Позднее, в 2018 году, он был включён в стандарт IETF для протокола SSH (RFC 8332) и стал обязательным для реализации в протоколе WireGuard. В 2020 году Poly1305 вошёл в состав национального стандарта ГОСТ Р 34.12-2020 как часть кузнечикового режима аутентифицированного шифрования (Кузнечик-Поли1305).

Принцип работы

Poly1305 основан на арифметике в конечном поле GF(2^130 - 5). Это означает, что все вычисления производятся по модулю простого числа p = 2^130 - 5. Алгоритм обрабатывает сообщение блоками по 16 байт (128 бит), каждый из которых интерпретируется как 130-битное число (с учётом дополнительного бита для переноса).

Основные шаги

1. Инициализация: Генерируется секретный ключ длиной 32 байта. Первые 16 байт используются как одноразовый ключ (nonce), а вторые 16 байт — как множитель r. Множитель r маскируется: его младшие 4 бита каждого байта обнуляются, а старшие 5 бит — устанавливаются в ноль, что гарантирует, что r не является делителем нуля в поле.

1. Разбиение на блоки: Сообщение делится на блоки по 16 байт. Последний блок дополняется нулями до полного размера.

1. Преобразование блоков: Каждый блок преобразуется в 130-битное число: к байтам блока добавляется один бит (1) для обозначения конца блока, а затем число приводится по модулю p.

1. Вычисление полинома: Вычисляется полиномиальное значение:

• Начальное значение: 0
• Для каждого блока: value = (value + block) * r mod p
• После обработки всех блоков к результату добавляется ключ nonce.

1. Формирование тега: Полученное 128-битное значение (после приведения к 128 битам) является кодом аутентификации (тегом MAC).

Математическая основа

Алгоритм использует свойства полиномов над конечным полем. Если обозначить блоки сообщения как m1, m2, ..., mn, а множитель r, то тег вычисляется как:

tag = (m1 r^n + m2 r^(n-1) + ... + mn * r) + nonce mod p

Гарантия безопасности основана на том, что для двух разных сообщений вероятность совпадения тегов (коллизия) не превышает 2^-128, если ключ r и nonce выбираются случайно.

Характеристики

Производительность

Poly1305 демонстрирует высокую скорость работы на современных процессорах. В реализации на языке C для 64-битных архитектур он достигает пропускной способности около 2–3 Гбит/с на процессорах Intel Core i7 (2015 год). На ARM-процессорах (например, Cortex-A72) производительность составляет около 1–2 Гбит/с. Основное преимущество — отсутствие необходимости в аппаратной поддержке AES, что делает его идеальным для встраиваемых систем и устройств с ограниченными ресурсами.

Безопасность

Poly1305 обеспечивает 128-битную стойкость к атакам на подделку сообщений. Это означает, что злоумышленник, не знающий ключа, не может с вероятностью выше 2^-128 подделать сообщение или его тег. Алгоритм устойчив к атакам по сторонним каналам (например, по времени выполнения) при условии корректной реализации. Однако, как и любой MAC, Poly1305 требует уникального nonce для каждого сообщения при использовании с одним и тем же ключом; повторное использование nonce позволяет злоумышленнику вычислить ключ.

Совместимость

Poly1305 часто используется в паре с шифром ChaCha20, образуя аутентифицированное шифрование ChaCha20-Poly1305. Эта комбинация стандартизирована в RFC 8439 и широко применяется в протоколах TLS 1.3, SSH, WireGuard, а также в криптографических библиотеках (OpenSSL, libsodium, BoringSSL). В режиме Poly1305-AES используется AES в режиме CTR для шифрования, а Poly1305 — для аутентификации.

Применение

Протоколы безопасности

• TLS 1.3: ChaCha20-Poly1305 является одним из обязательных наборов шифров для обеспечения конфиденциальности и целостности данных.
• SSH: Используется в протоколе SSH-2 для защиты канала связи.
• WireGuard: Современный VPN-протокол, использующий ChaCha20-Poly1305 для шифрования и аутентификации.
• IPsec: В некоторых реализациях (например, в Linux) поддерживается ChaCha20-Poly1305 для ESP (Encapsulating Security Payload).

Криптографические библиотеки

• OpenSSL (начиная с версии 1.1.0)
• libsodium (рекомендуемая библиотека для приложений)
• BoringSSL (форк OpenSSL от Google)
• WolfSSL (для встраиваемых систем)

Российские стандарты

В 2020 году Poly1305 был включён в национальный стандарт ГОСТ Р 34.12-2020 как часть режима аутентифицированного шифрования «Кузнечик-Поли1305». В этом режиме используется блочный шифр «Кузнечик» (ГОСТ Р 34.12-2015) в режиме CTR для шифрования, а Poly1305 — для аутентификации. Режим предназначен для использования в государственных информационных системах Российской Федерации.

Интересные факты

• Poly1305 не требует предварительного вычисления таблиц, что делает его устойчивым к атакам по кэшу (cache-timing attacks), в отличие от некоторых реализаций AES.
• Название «Poly1305» происходит от «полиномиальный» (из-за использования полиномиальных вычислений) и числа 130 (размер поля 2^130 - 5).
• Алгоритм был разработан в рамках проекта «Curve25519» Дэниела Бернштейна, который также создал эллиптическую кривую Curve25519 и хеш-функцию Salsa20.
• Poly1305 может быть реализован на 8-битных микроконтроллерах с использованием только целочисленной арифметики, что делает его пригодным для устройств интернета вещей (IoT).

Критика

Основная критика Poly1305 связана с его зависимостью от уникальности nonce. Если nonce повторяется, злоумышленник может восстановить ключ и подделывать сообщения. В некоторых реализациях (например, в ранних версиях WireGuard) были обнаружены ошибки в генерации nonce, что приводило к уязвимостям. Кроме того, алгоритм не поддерживает аутентификацию без шифрования (только MAC), что ограничивает его применение в некоторых сценариях.

Источники

• Bernstein, D. J. (2004). «The Poly1305-AES message-authentication code». Proceedings of the 11th ACM Conference on Computer and Communications Security.
• RFC 8439 — «ChaCha20 and Poly1305 for IETF Protocols» (2018).
• ГОСТ Р 34.12-2020 — «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров».
• Langley, A. (2013). «ChaCha20 and Poly1305 for TLS». IETF Draft.
• Bernstein, D. J. (2005). «Curve25519: New Diffie-Hellman Speed Records». Public Key Cryptography — PKC 2006.