Поли1305

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

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

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

Описание

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

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

интерпретирует $r$ как 16-байтовое целое число с прямым порядком байтов.
Разбивает сообщение $m=(m[0],m[1],m[2],\dotsc ,m[L-1])$ на последовательные 16-байтовые фрагменты.
Интерпретирует 16-байтовые фрагменты как 17-байтовые целые числа с прямым порядком байтов, добавляя 1 байт к каждому 16-байтовому фрагменту, который будет использоваться в качестве коэффициентов полинома.
Оценивает полином в точке $r$ по модулю простого числа $2^{130}-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 в качестве аутентификатора Картера – Вегмана.

Исходное предложение Poly1305-AES ^[3] использует структуру Картера – Вегмана ^[4]^[5] для аутентификации многих сообщений, принимая $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 в качестве одноразового аутентификатора зашифрованного текста сообщения. ^[6]ChaCha20-Poly1305 делает то же самое, но с ChaCha вместо XSalsa20 . ^[8]

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

Безопасность 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. ^[3]^{: Теорема 3.3, с. 8}

Это свойство иногда называют $\epsilon$ -почти-Δ-универсальность по $\mathbb {Z} /2^{128}\mathbb {Z}$ , или $\epsilon$ -АΔU , ^[10]где $\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}}}.$

Поли1305-AES

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

$\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) ^[3]

Скорость

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

Реализации

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

См. также

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

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с ^д Омассон, Жан-Филипп (2018). «Глава 7: Хеширование с ключами». Серьезная криптография: практическое введение в современное шифрование . Нет крахмального пресса. стр. 136–138. ISBN 978-1-59327-826-7 .
^ Бернштейн, Дэниел Дж. (1 мая 2008 г.). «Защита коммуникаций от подделки». В Бюлере, Джо; Стивенхаген, Питер (ред.). Алгоритмическая теория чисел: решетки, числовые поля, кривые и криптография . Публикации НИИ математических наук. Том. 44. Издательство Кембриджского университета. стр. 535–549. ISBN 978-0521808545 . Проверено 14 октября 2022 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Бернштейн, Дэниел Дж. (29 марта 2005 г.). «Код аутентификации сообщения Poly1305-AES» . В Гилберте, Анри; Хандшу, Хелена (ред.). Быстрое программное шифрование: 12-й международный семинар . ФШЭ 2005. Конспекты лекций по информатике. Париж, Франция: Спрингер. дои : 10.1007/11502760_3 . ISBN 3-540-26541-4 . Проверено 14 октября 2022 г.
^ Jump up to: Перейти обратно: ^а ^б Вегман, Марк Н.; Картер, Дж. Лоуренс (1981). «Новые хэш-функции и их использование для аутентификации и установления равенства». Журнал компьютерных и системных наук . 22 (3): 265–279. дои : 10.1016/0022-0000(81)90033-7 .
^ Jump up to: Перейти обратно: ^а ^б Боне, Дэн ; Шуп, Виктор (январь 2020 г.). Аспирантура по прикладной криптографии (PDF) (изд. версии 0.5). §7.4 MAC Картера-Вегмана, стр. 262–269 . Проверено 14 октября 2022 г.
^ Jump up to: Перейти обратно: ^а ^б Бернштейн, Дэниел Дж. (10 марта 2009 г.). Криптография в NaCl (Технический отчет). Идентификатор документа: 1ae6a0ecef3073622426b3ee56260d34.
^ Нир, Ю.; Лэнгли, А. (май 2015 г.). ChaCha20 и Poly1305 для протоколов IETF . дои : 10.17487/RFC7539 . РФК 7539 .
^ Jump up to: Перейти обратно: ^а ^б Нир, Ю.; Лэнгли, А. (июнь 2018 г.). ChaCha20 и Poly1305 для протоколов IETF . дои : 10.17487/RFC8439 . RFC 8439 .
^ Лэнгли, А.; Чанг, В.; Маврояннопулос, Н.; Стромбергсон, Дж.; Йозефссон, С. (июнь 2016 г.). ChaCha20-Poly1305 Наборы шифров для безопасности транспортного уровня (TLS) . дои : 10.17487/RFC7905 . РФК 7905 .
^ Халеви, Шай ; Кравчик, Хьюго . «MMH: Программная аутентификация сообщений со скоростью Гбит/секунда». В Бихаме, Эли (ред.). Быстрое программное шифрование . ФШЭ 1997. Конспекты лекций по информатике. Спрингер. дои : 10.1007/BFb0052345 . ISBN 978-3-540-63247-4 .
^ Бернштейн, Дэниел Дж. (27 февраля 2005 г.). «Более строгие границы безопасности для аутентификаторов Вегмана-Картера-Шоупа» . В Крамере, Рональде (ред.). Достижения в криптологии — EUROCRYPT 2005, 24-я ежегодная международная конференция по теории и применению криптографических методов . EUROCRYPT 2005. Конспекты лекций по информатике. Орхус, Дания: Springer. дои : 10.1007/11426639_10 . ISBN 3-540-25910-4 .
^ Современный код аутентификации сообщений на cr.yp.to.

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

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

[aumasson2018seriouscrypto-1] Jump up to: Перейти обратно: ^а ^б ^с ^д Омассон, Жан-Филипп (2018). «Глава 7: Хеширование с ключами». Серьезная криптография: практическое введение в современное шифрование . Нет крахмального пресса. стр. 136–138. ISBN 978-1-59327-826-7 .

[djb2001forgery-2] Бернштейн, Дэниел Дж. (1 мая 2008 г.). «Защита коммуникаций от подделки». В Бюлере, Джо; Стивенхаген, Питер (ред.). Алгоритмическая теория чисел: решетки, числовые поля, кривые и криптография . Публикации НИИ математических наук. Том. 44. Издательство Кембриджского университета. стр. 535–549. ISBN 978-0521808545 . Проверено 14 октября 2022 г.

[djb2005poly1305-3] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Бернштейн, Дэниел Дж. (29 марта 2005 г.). «Код аутентификации сообщения Poly1305-AES» . В Гилберте, Анри; Хандшу, Хелена (ред.). Быстрое программное шифрование: 12-й международный семинар . ФШЭ 2005. Конспекты лекций по информатике. Париж, Франция: Спрингер. дои : 10.1007/11502760_3 . ISBN 3-540-26541-4 . Проверено 14 октября 2022 г.

[carter-wegman1981hashautheq-4] Jump up to: Перейти обратно: ^а ^б Вегман, Марк Н.; Картер, Дж. Лоуренс (1981). «Новые хэш-функции и их использование для аутентификации и установления равенства». Журнал компьютерных и системных наук . 22 (3): 265–279. дои : 10.1016/0022-0000(81)90033-7 .

[boneh-shoup-course-5] Jump up to: Перейти обратно: ^а ^б Боне, Дэн ; Шуп, Виктор (январь 2020 г.). Аспирантура по прикладной криптографии (PDF) (изд. версии 0.5). §7.4 MAC Картера-Вегмана, стр. 262–269 . Проверено 14 октября 2022 г.

[djb2009naclcrypto-6] Jump up to: Перейти обратно: ^а ^б Бернштейн, Дэниел Дж. (10 марта 2009 г.). Криптография в NaCl (Технический отчет). Идентификатор документа: 1ae6a0ecef3073622426b3ee56260d34.

[rfc7539-7] Нир, Ю.; Лэнгли, А. (май 2015 г.). ChaCha20 и Poly1305 для протоколов IETF . дои : 10.17487/RFC7539 . РФК 7539 .

[rfc8439-8] Jump up to: Перейти обратно: ^а ^б Нир, Ю.; Лэнгли, А. (июнь 2018 г.). ChaCha20 и Poly1305 для протоколов IETF . дои : 10.17487/RFC8439 . RFC 8439 .

[rfc7905-9] Лэнгли, А.; Чанг, В.; Маврояннопулос, Н.; Стромбергсон, Дж.; Йозефссон, С. (июнь 2016 г.). ChaCha20-Poly1305 Наборы шифров для безопасности транспортного уровня (TLS) . дои : 10.17487/RFC7905 . РФК 7905 .

[halevi-krawczyk1997mmh-10] Халеви, Шай ; Кравчик, Хьюго . «MMH: Программная аутентификация сообщений со скоростью Гбит/секунда». В Бихаме, Эли (ред.). Быстрое программное шифрование . ФШЭ 1997. Конспекты лекций по информатике. Спрингер. дои : 10.1007/BFb0052345 . ISBN 978-3-540-63247-4 .

[djb2005securitywcs-11] Бернштейн, Дэниел Дж. (27 февраля 2005 г.). «Более строгие границы безопасности для аутентификаторов Вегмана-Картера-Шоупа» . В Крамере, Рональде (ред.). Достижения в криптологии — EUROCRYPT 2005, 24-я ежегодная международная конференция по теории и применению криптографических методов . EUROCRYPT 2005. Конспекты лекций по информатике. Орхус, Дания: Springer. дои : 10.1007/11426639_10 . ISBN 3-540-25910-4 .

[12] Современный код аутентификации сообщений на cr.yp.to.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]