Поли1305

Poly1305 — это универсальное семейство хэшей, разработанное Дэниелом Дж. Бернштейном для использования в криптографии .

Как и любое универсальное семейство хешей, Poly1305 можно использовать в качестве одноразового кода аутентификации сообщения для аутентификации одного сообщения с использованием секретного ключа, совместно используемого отправителем и получателем. аналогично тому, как одноразовый блокнот можно использовать для сокрытия содержимого одного сообщения с использованием секретного ключа, совместно используемого отправителем и получателем.

Первоначально Poly1305 был предложен как часть Poly1305-AES. аутентификатор Картера-Вегмана который сочетает в себе хэш Poly1305 с AES-128 для аутентификации многих сообщений с использованием одного короткого ключа и отдельных номеров сообщений.Позже Poly1305 был применен с одноразовым ключом, сгенерированным для каждого сообщения с использованием XSalsa20 в аутентифицированном шифре NaCl crypto_secretbox_xsalsa20poly1305, а затем использовать ChaCha в ChaCha20-Poly1305. аутентифицированном шифре развернут в TLS в Интернете.

Описание

Определение Poly1305

Poly1305 принимает 16-байтовый секретный ключ. $r$ и $L$-байтовое сообщение $m$ и возвращает 16-байтовый хэш $\operatorname {Poly1305} _{r}(m)$.Для этого Poly1305:

1. интерпретирует $r$ как 16-байтовое целое число с прямым порядком байтов.
2. Нарушает сообщение $m=(m[0],m[1],m[2],\dotsc ,m[L-1])$ на последовательные 16-байтовые фрагменты.
3. Интерпретирует 16-байтовые фрагменты как 17-байтовые целые числа с прямым порядком байтов, добавляя 1 байт к каждому 16-байтовому фрагменту, который будет использоваться в качестве коэффициентов полинома.
4. Оценивает полином в точке $r$ по модулю простого числа $2^{130}-5$.
5. Уменьшает результат по модулю $2^{128}$ закодированные с прямым порядком байтов, возвращают 16-байтовый хэш.

Коэффициенты $c_{i}$ полинома $c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r$, где $q=\lceil L/16\rceil$, являются:

$$c_{i}=m[16i-16]+2^{8}m[16i-15]+2^{16}m[16i-14]+\cdots +2^{120}m[16i-1]+2^{128},$$

за исключением того, что если $L\not \equiv 0{\pmod {16}}$, затем:

$$c_{q}=m[16q-16]+2^{8}m[16q-15]+\cdots +2^{8(L{\bmod {1}}6)-8}m[L-1]+2^{8(L{\bmod {1}}6)}.$$

Секретный ключ $r=(r[0],r[1],r[2],\dotsc ,r[15])$ ограничено наличием байтов $r[3],r[7],r[11],r[15]\in \{0,1,2,\dotsc ,15\}$, т. е . очистить четыре старших бита; и иметь байты $r[4],r[8],r[12]\in \{0,4,8,\dotsc ,252\}$, т. е . очистить два младших бита.Таким образом, существуют $2^{106}$ различные возможные значения $r$.

Использовать в качестве одноразового аутентификатора

Если $s$ — это секретная 16-байтовая строка, интерпретируемая как целое число с прямым порядком байтов, затем

$$a:={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}$$

называется аутентификатором сообщения $m$.Если отправитель и получатель используют общий 32-байтовый секретный ключ $(r,s)$ заранее выбран равномерно случайным образом, тогда отправитель может передать аутентифицированное сообщение $(a,m)$.Когда получатель получает предполагаемое проверенное сообщение $(a',m')$ (который мог быть изменен противником при передаче), они могут проверить его подлинность, проверив, является ли

$$a'\mathrel {\stackrel {?}{=}} {\bigl (}\operatorname {Poly1305} _{r}(m')+s{\bigr )}{\bmod {2}}^{128}.$$

Без знания $(r,s)$, у противника есть вероятность $8\lceil L/16\rceil /2^{106}$ найти какой-либо $(a',m')\neq (a,m)$ который пройдет проверку.

Однако тот же ключ $(r,s)$ не должен использоваться повторно для двух сообщений.Если противник узнает

$${\begin{aligned}a_{1}&={\bigl (}\operatorname {Poly1305} _{r}(m_{1})+s{\bigr )}{\bmod {2}}^{128},\\a_{2}&={\bigl (}\operatorname {Poly1305} _{r}(m_{2})+s{\bigr )}{\bmod {2}}^{128},\end{aligned}}$$

для $m_{1}\neq m_{2}$, они могут вычесть

$$a_{1}-a_{2}\equiv \operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2}){\pmod {2^{128}}}$$

и найдите корень полученного полинома, чтобы восстановить небольшой список кандидатов на секретную оценочную точку. $r$, и оттуда секретный блокнот $s$.Затем злоумышленник может использовать это для подделки дополнительных сообщений с высокой вероятностью.

Картера-

Исходное предложение Poly1305-AES использует структуру Картера – Вегмана для аутентификации многих сообщений, принимая $a_{i}:=H_{r}(m_{i})+p_{i}$ быть аутентификатором i- го сообщения $m_{i}$, где $H_{r}$ является универсальным семейством хешей и $p_{i}$ — это независимое однородное случайное значение хеш-функции, которое служит одноразовым блокнотом для его сокрытия.Poly1305-AES использует AES-128 для генерации $p_{i}:=\operatorname {AES} _{k}(i)$, где $i$ кодируется как 16-байтовое целое число с прямым порядком байтов.

В частности, ключ Poly1305-AES представляет собой 32-байтовую пару. $(r,k)$ 16-байтовой оценочной точки $r$, как указано выше, и 16-байтовый ключ AES. $k$.Аутентификатор Poly1305-AES в сообщении $m_{i}$ является

$$a_{i}:={\bigl (}\operatorname {Poly1305} _{r}(m_{i})+\operatorname {AES} _{k}(i){\bigr )}{\bmod {2}}^{128},$$

где 16-байтовые строки и целые числа идентифицируются с помощью кодировки с прямым порядком байтов.Обратите внимание, что $r$ повторно используется между сообщениями.

Без знания $(r,k)$, злоумышленник имеет низкую вероятность подделать любые аутентифицированные сообщения, которые получатель примет за подлинные.Предположим, противник видит $C$ аутентифицированные сообщения и попытки $D$ подделки и может отличить $\operatorname {AES} _{k}$ из равномерной случайной перестановки с преимуществом не более $\delta$.(Если AES не сломан, $\delta$ очень маленький.)Шансы противника на успех при одной подделке не превышают:

$$\delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.$$

Номер сообщения $i$ никогда не должно повторяться с одним и тем же ключом $(r,k)$.Если это так, злоумышленник может восстановить небольшой список кандидатов на $r$ и $\operatorname {AES} _{k}(i)$, как и в случае с одноразовым аутентификатором, и использовать его для подделки сообщений.

Использование в NaCl и ChaCha20-Poly1305

Аутентифицированный шифр NaCl crypto_secretbox_xsalsa20poly1305 использует номер сообщения. $i$ с помощью потокового шифра XSalsa20 для каждого сообщения для генерации потока ключей , первые 32 байта которого принимаются как одноразовый ключ Poly1305 $(r_{i},s_{i})$ а остальная часть используется для шифрования сообщения.Затем он использует Poly1305 в качестве одноразового аутентификатора зашифрованного текста сообщения. ChaCha20-Poly1305 делает то же самое, но с ChaCha вместо XSalsa20 .

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

Безопасность Poly1305 и его производных от подделки вытекает из его ограниченной вероятности разности как универсального хеш-семейства :Если $m_{1}$ и $m_{2}$ являются сообщениями до $L$ байт каждый, и $d$ любая 16-байтовая строка, интерпретируемая как целое число с прямым порядком байтов, тогда

$$\Pr[\operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2})\equiv d{\pmod {2^{128}}}]\leq {\frac {8\lceil L/16\rceil }{2^{106}}},$$

где $r$ — это единый случайный ключ Poly1305.

Это свойство иногда называют $\epsilon$-почти-Δ-универсальность по $\mathbb {Z} /2^{128}\mathbb {Z}$, или $\epsilon$-АΔU , где $\epsilon =8\lceil L/16\rceil /2^{106}$ в этом случае.

Одноразового аутентификатора

С одноразовым аутентификатором $a={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}$, вероятность успеха злоумышленника при любой попытке подделки $(a',m')$ в сообщении $m'$ до $L$ байты:

$${\begin{aligned}\Pr[&a'=\operatorname {Poly1305} _{r}(m')+s\mathrel {\mid } a=\operatorname {Poly1305} _{r}(m)+s]\\&=\Pr[a'=\operatorname {Poly1305} _{r}(m')+a-\operatorname {Poly1305} _{r}(m)]\\&=\Pr[\operatorname {Poly1305} _{r}(m')-\operatorname {Poly1305} _{r}(m)=a'-a]\\&\leq 8\lceil L/16\rceil /2^{106}.\end{aligned}}$$

Здесь арифметика внутри $\Pr[\cdots ]$ считается, что он находится в $\mathbb {Z} /2^{128}\mathbb {Z}$ для простоты.

NaCl и ChaCha20-Poly1305

Для NaCl crypto_secretbox_xsalsa20poly1305 и ChaCha20-Poly1305 вероятность успеха злоумышленника при подделке одинакова для каждого сообщения независимо, как и для одноразового аутентификатора, плюс отличительное преимущество злоумышленника. $\delta$ против XSalsa20 или ChaCha как псевдослучайных функций, используемых для генерации ключа для каждого сообщения.Другими словами, вероятность того, что злоумышленнику удастся совершить одну подделку после $D$ попытки сообщений до $L$ байт не более:

$$\delta +{\frac {8D\lceil L/16\rceil }{2^{106}}}.$$

Poly1305-AES

Безопасность Poly1305-AES от подделки следует из структуры Картера-Вегмана-Шоупа, которая создает экземпляр аутентификатора Картера-Вегмана с перестановкой для создания панели для каждого сообщения. Если противник увидит $C$ аутентифицированные сообщения и попытки $D$ подделки сообщений размером до $L$ байт, и если противник имеет отличительное преимущество не более $\delta$ против AES-128 как псевдослучайной перестановки , то вероятность того, что противник добьется успеха в любом из $D$ подделки – это максимум:

$$\delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.$$

Например, если предположить, что сообщения представляют собой пакеты размером до 1024 байт; что злоумышленник видит 2 ⁶⁴ сообщения, аутентифицированные ключом Poly1305-AES; что злоумышленник пытается совершить колоссальные 2 ⁷⁵ подделки; и что злоумышленник не может взломать AES с вероятностью выше δ; тогда с вероятностью не менее 0,999999 − δ все 2 ⁷⁵ отклонены

- Бернштейн, Дэниел Дж. (2005)

Скорость

Poly1305-AES может вычисляться с высокой скоростью на различных процессорах: для n не более 3,1 n + 780 тактов Athlon, -байтового сообщения необходимо например.Автор выпустил оптимизированный исходный код для Athlon , Pentium Pro/II/III/M, PowerPC и UltraSPARC , а также неоптимизированные эталонные реализации на C и C++ в качестве общедоступного программного обеспечения .

Реализации

Ниже приведен список библиотек шифрования, поддерживающих Poly1305:

• Ботан
• Надувной замок
• Крипто++
• Libgcrypt
• либнатрий
• Крапива
• OpenSSL
• LibreSSL
• волкСклеп
• ГнуTLS
• mbed TLS
• МатрицаSSL

См. также

• ChaCha20-Poly1305 - схема AEAD, сочетающая поточный шифр ChaCha20 с вариантом Poly1305.

Внешние ссылки

• Эталон Poly1305-AES и оптимизированная реализация автора DJ Bernstein
• Быстрая реализация Poly1305 на C на github.com
• NaCl Одноразовый аутентификатор и шифр с аутентификацией с использованием Poly1305