Poly1305-AES¶

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

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

Алгоритм Poly1305-AES относится к семейству полиномиальных MAC-кодов. Его работа основана на вычислении полиномиального хеша от сообщения с последующим шифрованием результата. Основные компоненты:

• Секретный ключ AES (16 байт) — используется для шифрования блока nonce.
• Одноразовый nonce (16 байт) — уникальное значение, которое не должно повторяться для разных сообщений при одном и том же ключе.
• 128-битное простое число p = 2^130 − 5 — модуль для арифметических операций в поле.

Процесс генерации тега:

1. Сообщение разбивается на 16-байтные блоки, каждый блок дополняется единичным битом и нулями до 17 байт.
2. Каждый блок интерпретируется как число в little-endian представлении.
3. Вычисляется полиномиальная сумма: r^2·c1 + r·c2 + c3 (где ci — блоки сообщения, r — секретный ключ-часть).
4. Результат приводится по модулю p.
5. К результату прибавляется значение AES_k(nonce), зашифрованное на ключе AES.
6. Итоговое 128-битное число является тегом аутентификации.

Секретный ключ r имеет ограничения: некоторые биты должны быть нулевыми (например, биты 4, 12, 20 и т.д.), что упрощает реализацию и предотвращает атаки, связанные с переносами.

¶Отличия от Poly1305

В 2005 году Бернстайн представил вариант Poly1305, который использует вместо AES функцию ChaCha20 (или другую потоковую) для шифрования nonce. В оригинальном Poly1305-AES используется именно AES, что делает его зависимым от наличия реализации AES в системе. Poly1305, напротив, стал более популярным благодаря комбинации с ChaCha20 в протоколе TLS 1.3 и в составе библиотек libsodium и OpenSSH.

Ключевое различие:

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

Безопасность Poly1305-AES основана на двух предположениях:

• AES является псевдослучайной функцией (PRF).
• Полиномиальное хеширование по модулю p является универсальным семейством хешей.

При соблюдении требования уникальности nonce для каждого сообщения вероятность подделки тега не превышает 2^−106 для сообщений длиной до 2^64 бит. Это делает алгоритм провозразимо безопасным при правильном использовании.

Известные атаки на Poly1305-AES отсутствуют, однако алгоритм чувствителен к повторному использованию nonce: при повторном использовании одного и того же nonce с разными сообщениями злоумышленник может восстановить ключ r и подделывать теги.

¶Применение

Poly1305-AES использовался в ранних версиях протокола NaCl (Networking and Cryptography Library) Бернстайна, однако впоследствии был заменён на Poly1305 с ChaCha20. На сегодняшний день алгоритм представляет в основном исторический интерес и используется в образовательных целях для демонстрации принципов полиномиального MAC. В актуальных криптографических библиотеках (libsodium, OpenSSL, BoringSSL) реализован именно вариант Poly1305-ChaCha20, который стандартизирован в RFC 8439.

¶Критика и ограничения

Основным недостатком Poly1305-AES является жёсткая привязка к AES. На процессорах без аппаратной поддержки AES (AES-NI) скорость работы алгоритма значительно ниже, чем у вариантов на основе потоковых шифров. Кроме того, необходимость хранить отдельный ключ AES и nonce усложняет реализацию по сравнению с более современными конструкциями. Криптографическое сообщество также отмечает, что использование одного ключа для полиномиального хеширования и для шифрования nonce требует особой аккуратности в реализации, чтобы избежать утечек через побочные каналы.