POLY1305-AES

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

Poly1305-AES вычисляет 16-байтовый аутентификатор сообщения любой длины, используя 16-байтовый одноразовый номер (уникальный номер сообщения) и 32-байтовый секретный ключ.

AES используется для шифрования одноразового номера, чтобы получить уникальную (и секретную) 128-битную строку, но при желании AES-128 можно заменить любой другой функцией c гарантией безопасности, например ChaCha20.

Обзор

Аргументы POLY1305-AES

Poly1305-AES получает на вход

Сообщение произвольной длины $m$

16-байтовый ключ $\mathrm {AES} _{k}$

16-байтовый дополнительный ключ $r$

16-байтовое однократно используемое число $n$.

и вычисляет 16-байтовый аутентификатор $\operatorname {Poly1305} _{r}(m,AES_{k}(n))$.

Ключ $r$ представляет собой 128-битное целое число r с прямым порядком байтов от младшего к старшему (англ. little-endian ), т.е. $r=r[0]+2^{8}r[1]+...+2^{120}r[15]$. При этом ключ $r$ должен соответствовать определённым требованиям: у $r[3]$, $r[7]$, $r[11]$ и $r[15]$ первые 4 из 8 битов должны быть равны 0, а у $r[4]$, $r[8]$ и $r[12]$ последние 2 бита должны быть равны 0. Таким образом $r$ может принять $2^{106}$ различных значений

Алгоритм

1. Poly1305 разбивает сообщение $m=(m[0],m[1],\ldots ,m[L-1])$ на фрагменты длиной 16 байт.
2. К каждому 16-байтовому фрагмент сообщения добавляется единица до 17 байт для использования в качестве коэффициента полинома. Если последний фрагмент сообщения размером от 1 до 15 байт, то к фрагменту добавляется единица, а дальше до 17 байт всё заполняется нулями. Коэффициенты $c_{1},\ldots ,c_{q}$ полинома $c_{1}r^{q}+c_{2}r^{q-1}+\ldots +c_{q}r^{1}$ , где $q=\left[{L \over 16}\right]$ вычисляются по формуле:
   $c_{i}=m[16i-16]+2^{8}m[16i-15]+2^{16}m[16i-14]+\cdots +2^{120}m[16i-1]+2^{128}$.
   Если $L$ не делится нацело на 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)}.$
3. Полином вычисляется в точке $r$ по модулю $2^{130}-5$ и складывается с 16-байтной зашифрованной строкой , полученной на выходе $\mathrm {AES} _{k}(n)$, где $n$ -однократно используемое число.$(((c_{1}r^{q}+c_{2}r^{q-1}+\ldots +c_{q}r^{1})\mathrm {mod} 2^{130}-5)+\mathrm {AES} _{k}(n)$
4. Берём остаток от деления на $2^{128}$ и закодируем его, получив хэш длиной 16 байт.

Выбор стуктурных элементов при разработке алогритма

Изначально для деления по модулю рассматривались простые числа больше $2^{128}$ (128 битов – длина фрагмента сообщения). Для простоты вычислений было решено выбрать простое число $2^{130}-5$.

Причин, по которым алгоритм использует однократно используемое число $n$ несколько: Во-первых, вероятность взлома протоколов, не использующих такие числа $n$ можно выразить формулой: ${\frac {C(C+D)L}{2^{106}}}$, где $C$ количество сообщений, $D$ – количество попыток взлома, $L$ -максимальная длина сообщения. А с однократно используемым числом вероятность будет такая: ${\frac {DL}{2^{106}}}$. Во-вторых, одноразовые номера позволяют проводить выполнение алгоритма AES-128 параллельно с другими операциями Poly1305-AES, что уменьшает общее время вычисления аутентификатора. В-третьих, большинство протоколов так или иначе имеют такие одноразовые номера для более безопасного шифрования.

Длина дополнительного ключа $r$ была ограничена 16-ю байтами для ускорения вычислений. При этом возможен ключ длинее для усиления безопасности, но текущая вероятность взлома достаточно низкая, чтобы считать алгоритм при текущей длине ключа безопасным. Но при увеличении длины ключа, общее время вычисления будет слишком долгим, что лишит POLY1305-AES преимущества перед другими алгоритмами. Так же для ключа был выбран прямой порядок байтов, вместо обратного (англ. Big-endian), так как он экономит время на самых популярных процессорах.

Алгоритм POLY1305, написанный на псевдокоде

      clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
      poly1305_mac(msg, key):
         r = le_bytes_to_num(key[0..15])
         clamp(r)
         s = le_bytes_to_num(key[16..31])
         a = 0  /* a is the accumulator */
         p = (1<<130)-5
         for i=1 upto ceil(msg length in bytes / 16)
            n = le_bytes_to_num(msg[((i-1)*16)..(i*16)] | [0x01])
            a += n
            a = (r * a) % p
            end
         a += s
         return num_to_16_le_bytes(a)
         end

— ChaCha20 and Poly1305 for IETF Protocols, IRTF

Криптостойкость

Принято считать, что безопасность POLY1305-AES гарантирована, если можно гарантировать безопасность алгоритма AES. Если у злоумышленника есть $C$ зашифрованных сообщений и он совершает D попыток взлома сообщений длиной не больше $L$ байтов, $\delta$ - вероятность взлома AES, то вероятность взлома POLY1305-AES будет $$\delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.$$ Рассмотрим случай, когда сообщения представляют из себя пакеты длиной до 1536 байт, злоумышленник имеет $2^{64}$ сообщений зашифрованных POLY1305-AES и совершает $2^{64}$ попыток взломать, а вероятность взлома$\delta \leq 2^{-40}$ . В таком случае вероятность, что злоумышленник не сможет взломать код аутентификации послания $\geq 0.999999999998$. Для сравнения, при таких параметрах можно легко взломать другие 16-байтные MAC, например CBC-AES, HMAC-MD5 и DMAC-A.

Скорость

Poly1305-AES можно вычислять с чрезвычайно высокой скоростью, например для AMD Athlon требуется менее 3.1n + 780 циклов для сообщения длиной n байт. Даниэль Дж. Бернштейн опубликовал исходный код на SPARC, AIX, macOS, Pentium Pro/II/III/M и Athlon. А также эталонную реализацию алгоритма на C, C++, Python и Perl.

Иплементация

Ниже представлен список криптографических библиотек, в которых есть реализация Poly1305:

• Botan
• Bouncy Castle
• Crypto++
• Libgcrypt
• NaCl
• Nettle
• OpenSSL
• LibreSSL
• wolfCrypt
• GnuTLS
• mbed TLS
• MatrixSSL

Ссылки

• POLY1305-AES Домашняя страница
• Имплементация POLY1305-AES на C
• Таблицы скорости Poly1305-AES