POLY1305-AES

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

[править | править код]

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

Сообщение произвольной длины
16-байтовый ключ
16-байтовый дополнительный ключ
16-байтовое однократно используемое число .

и вычисляет 16-байтовый аутентификатор .

Ключ представляет собой 128-битное целое число r с прямым порядком байтов от младшего к старшему (англ. little-endian ), т.е. . При этом ключ должен соответствовать определённым требованиям: у , , и первые 4 из 8 битов должны быть равны 0, а у , и последние 2 бита должны быть равны 0. Таким образом может принять различных значений

  1. Poly1305 разбивает сообщение на фрагменты длиной 16 байт.
  2. К каждому 16-байтовому фрагмент сообщения добавляется единица до 17 байт для использования в качестве коэффициента полинома. Если последний фрагмент сообщения размером от 1 до 15 байт, то к фрагменту добавляется единица, а дальше до 17 байт всё заполняется нулями. Коэффициенты полинома , где вычисляются по формуле:
    .
    Если не делится нацело на 16, то используют формулу:
  3. Полином вычисляется в точке по модулю и складывается с 16-байтной зашифрованной строкой , полученной на выходе , где -однократно используемое число.
  4. Берём остаток от деления на и закодируем его, получив хэш длиной 16 байт.

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

[править | править код]

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

Причин, по которым алгоритм использует однократно используемое число несколько: Во-первых, вероятность взлома протоколов, не использующих такие числа можно выразить формулой: , где количество сообщений, – количество попыток взлома, -максимальная длина сообщения. А с однократно используемым числом вероятность будет такая: . Во-вторых, одноразовые номера позволяют проводить выполнение алгоритма AES-128 параллельно с другими операциями Poly1305-AES, что уменьшает общее время вычисления аутентификатора. В-третьих, большинство протоколов так или иначе имеют такие одноразовые номера для более безопасного шифрования.

Длина дополнительного ключа была ограничена 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

[3]

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

[править | править код]

Принято считать, что безопасность POLY1305-AES гарантирована, если можно гарантировать безопасность алгоритма AES. Если у злоумышленника есть зашифрованных сообщений и он совершает D попыток взлома сообщений длиной не больше байтов, - вероятность взлома AES, то вероятность взлома POLY1305-AES будет Рассмотрим случай, когда сообщения представляют из себя пакеты длиной до 1536 байт, злоумышленник имеет сообщений зашифрованных POLY1305-AES и совершает попыток взломать, а вероятность взлома . В таком случае вероятность, что злоумышленник не сможет взломать код аутентификации послания [4]. Для сравнения, при таких параметрах можно легко взломать другие 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[5].

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

[править | править код]

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

Примечания

[править | править код]
  1. Chapter 7: Keyed Hashing // Serious Cryptography: A Practical Introduction to Modern Encryption. — No Starch Press, 2018. — P. 136-138. — ISBN 978-1-59327-826-7.
  2. The Poly1305-AES message-authentication code. — 2005. Архивная копия от 1 сентября 2022 на Wayback Machine
  3. Y. Nir. 2.5.1 // ChaCha20 and Poly1305 for IETF Protocols / Y. Nir, Dell EMC, A. Langley. — Internet Research Task Force, 2018. — P. 16.
  4. The Poly1305-AES message-authentication code 5. Дата обращения: 7 ноября 2022. Архивировано 12 июля 2022 года.
  5. How does the Poly1305-AES implementation work? Дата обращения: 7 ноября 2022. Архивировано 10 октября 2018 года.