UMAC

UMAC (англ. message authentication code based on universal hashing, universal MAC, код аутентификации сообщения на основе универсального хеширования) — один из видов кода аутентичности сообщений (MAC).

История

Данный алгоритм был отобран NESSIE в 2003 году, а в его разработке принимали участие: Intel Corp. (США), университет Невады (США), научно-исследовательская лаборатория IBM (США), Technion (Израиль) и университет Калифорнии в Дэвисе (США). Его авторами были John Black, Shai Halevi и Hugo Krawczyk, Ted Krovetz и Phillip Rogaway.

Описание

Быстрая «универсальная» функция используется, для того, чтобы хешировать входящее сообщение M в короткую строку. К этой строке потом применяется функция XOR с псевдослучайным значением, в результате чего мы получаем тег UMAC:

$Tag=H_{K1}\left(M\right)\oplus F_{K2}\left(Nonce\right)$

где K1 и K2 — секретные случайные ключи, которые имеют получатель и отправитель.

Отсюда видно, что безопасность UMAC зависит от того, каким случайным способом отправитель и получатель выбрали тайную хеш-функцию и псевдослучайную последовательность. При этом значение Nonce меняется каждый такт. Из-за использования Nonce, приемник и передатчик должны знать время отправки сообщения и принцип создания значения Nonce. Вместо этого можно использовать в качестве Nonce любое другое неповторяющееся значение, например порядковый номер сообщения. При этом данный номер не обязан быть секретным, главное чтобы он не повторялся.

UMAC рассчитан на использование 32-х, 64-х, 92-х, и 128-битовых тегов, в зависимости от требуемого уровня безопасности. UMAC обычно используется совместно с алгоритмом шифрования AES.

Функция создания ключа и псевдослучайной последовательности

Создание псевдослучайных байтов необходимо для работы UHASH и при создании тегов

Выбор блочного шифра

Для своей работы UMAC использует блочный шифр, выбор которого определяют следующие константы:

• BLOCLEN — длина, в байтах, блока с которым работает блочный шифр
• KEYLEN — длина, в байтах, ключа блочного шифра

При этом используется функция

• ENCIPHER(K,P) — зашифровать строку P из BLOCLEN байтов, используя ключ K.

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

KDF — функция создания ключа

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

Вход:

• К — строка длиной KEYLEN байт. / / Ключ блочного шифра
• Index — неотрицательное целое число меньше, чем 2 ^ 64.
• Numbytes — неотрицательное целое число меньше, чем 2 ^ 64.

Выход:

• Y — строку длины numbytes байт.

PDF: функция создания псевдослучайного числа

Эта функция принимает ключ и данное время и возвращает псевдослучайное числ для использования его в теге поколения. С помощью этой функции могут быть получены числа длиной 4, 8, 12 или 16 байт.

Вход:

• К — строка длиной KEYLEN байт.
• Nonce — строка длиной от 1 до BLOCKLEN байт.
• Taglen — целое число 4, 8, 12 или 16.

Выход:

• Y — последовательность байтов длины taglen.

Генерация UMAC-тегов

Генерация UMAC-тегов происходит с помощью UHASH функции при использовании Nonce значении и полученной до этого строчки(см. Описание). Их длина может быть 4, 8, 12 или 16 байт.

Вход:

• K — строка длиной KEYLEN байт
• M — строка длиной меньше 2^67 бит
• Nonce — случайное число от 1 до BLOCKLEN байт
• TagLen — целое 4, 8, 12 или 16

Выход:

• Тег, последовательность байтов длиной taglen

Алгоритм вычисление тегов:

HashedMassage = UHASH(K, M, TagLen)

Pad = PDF(K, nonce, TagLen)

Tag = Pad xor HashedMassage

UMAC-32 UMAC-64 UMAC-96 UMAC-128

Данные обозначения содержат в своем названии определенное значение длины тега:

• UMAC-32 (К, М, Nonce) = UMAC (K, M, Nonce, 4)
• UMAC-64 (К, М, Nonce) = UMAC (K, M, Nonce, 8)
• UMAC-96 (К, М, Nonce) = UMAC (K, M, Nonce, 12)
• UMAC-128 (K, M, Nonce) = UMAC (K, M, Nonce, 16)

Универсальная функция хеширования(UHASH)

UHASH(англ. Universal hashing) — универсальная функция хеширования, сердцевина алгоритма UMAC. UHASH — функция работает в три этапа. Сначала к входному сообщению применяется L1-HASH, потом к этому результату применяется L2-HASH и, наконец, к результату применяется L3-HASH . Если при этом длина входного сообщения не более 1024 бит, то L2-HASH не используется. Так как функция L3-Hash возвращает только слово длины 4 байта, то если требуется получить хеш длины больше 4 байт, осуществляется несколько итераций данной трехуровневой схемы.

Универсальная функция

Пусть функция хеширования выбирается из класса хеш-функций H, которые отображают сообщения в D, набор всевозможных образов сообщения. Этот класс называется универсальным, если для каких-либо отдельных пар сообщений, существует на множестве H/D функций, функция, которая отображает их в элемент D. Смысл этой функции в том, что если третья сторона хочет заменить одно сообщение другим, но при этом считает, что хеш-функция была выбрана абсолютно случайно, то вероятность не обнаружения подмены принимающей стороной стремится к 1/D.

L1-Hash — первый этап

L1-Hash разбивает сообщения на куски из 1024 байт и к каждому куску применяет алгоритм хеширования называемый NH. Выходной результат алгоритма NH в 128 раз меньше входного.

L2-Hash — второй этап

L2-Hash работает с выходом L1-Hash, использует полиномиальный алгоритм POLY. Второй этап хеширования используется, только если длина входного сообщения больше 16 мегабайт. Использование алгоритма POLY требуется для того, чтобы избежать временную атаку. На выходе из алгоритма POLY получается 16 байтное число.

L3-HASH — третий этап

Этот этап требуется для того чтобы из выходных 16 байтов алгоритма L2-Hash получить 4-байтное значение.

Вопросы безопасности

Стойкость криптоанализу

Стойкость UMAC зависит от её основных функций: функции создания ключа (KDF) и функции создания псевдослучайной последовательности(PDF). Именно поэтому обе функции реализованы с использованием блочного шифрования, обычно Advanced Encryption Standard (AES). Однако UMAC позволяет использовать другие блочные шифры. Основной плюс UMAC алгоритма и UHASH функции заключается в том, что их стойкость зависит только от математических свойств данного алгоритма и функции. Поэтому криптоанализ не влияет на стойкость UHASH-функции.

Длина псевдослучайных чисел и возможность подмены

Алгоритм MAC используется для проверки подлинности сообщений между двумя сторонами, которые знают общий секретный ключ K. Теги аутентификации вычисляются для сообщения с помощью ключа K, а в случае UMAC ключом является время. Взлом алгоритма MAC обозначает, что злоумышленник умеет сам генерировать сообщения без знания ключа. Теория Wegman-Carter и анализ UMAC показывает, что если используется алгоритм UMAC со случайными ключами и начальным значением Nonce, то вероятность того, что злоумышленник взломает сообщение равна: ${\frac {1}{2^{30}}}$, ${\frac {1}{2^{60}}}$, ${\frac {1}{2^{90}}}$, ${\frac {1}{2^{120}}}$ , если используются выходные теги длины 32, 64, 96, 128 соответственно. Если злоумышленник делает N попыток, то вероятность взлома увеличивается пропорционально числу попыток, то есть в N раз. При дополнительном использовании алгоритма AES, вероятность взлома значительно уменьшается.

Безопасность использования Nonce

UMAC использует текущее время в диапазоне от 1 до BLOCKLEN байт. При этом все значения Nonce в течение сессии должны быть равными по длине. Для обеспечения лучшей безопасности никакое значение Nonce не должно повторяться при использовании одного ключа сессии.

Если используется дуплексный канал передачи, то могут использоваться разные ключи для каждого направления. При использовании ключа в обоих направлениях очень важно, чтобы значение Nonce не повторялось, это можно реализовать путём использования четных ключей в одном и нечетных в другом направлении. При этом текущее значение Nonce не нужно держать в секрете.

Значение Nonce может создаваться и передаваться следующими вариантами:

1. Текущее значение Nonce является 8-байтовым беззнаковым числом, которое в начале сессии обнуляется и увеличивается на единицу после каждого посланного тега. При этом данный счетчик передается вместе с сообщением. Если в течение сессии передано более 2 ^ 64 сообщений, то возникает прерывание.
2. Текущее значение Nonce является BLOCKLEN-байтовым беззнаковым числом, которое в начале сессии обнуляется и увеличивается на единицу после каждого посланного тега. При этом счетчик явно не передается между отправителем и получателем, а каждый из них сам считает текущее значение.
3. Текущее значение Nonce является BLOCKLEN-байтовой псевдослучайной величиной. Но тогда важна синхронизация псевдослучайных последовательностей у отправителя и получателя.

Повторные атаки

Повторные атаки — это действия злоумышленника направленные на повторение сообщения, случайного числа, и аутентификации тега. В UMAC данная атака не принесет плодов так как каждое значение Nonce используется ровно один раз.

Проверка префикса тега.

Характер UMAC позволяет реализавать тег-префиксную проверку, например, приемник может проверить только 32-бит префикс от 64-битового тега. Это используется для оптимизации, если вычислительная нагрузка проверки высока. При этом приемник имеет возможность отклонения всего тега, если 32-битный префикс неверен. Данный алгоритм снижает безопасность сессии.

Литература

• J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, «UMAC: Fast and provably secure message authentication», Advances in Cryptology — CRYPTO '99, LNCS vol. 1666, pp. 216–233, Springer-Verlag, 1999.
• L. Carter and M. Wegman, «Universal classes of hash functions», Journal of Computer and System Sciences, 18 (1979), pp. 143–154.
• T. Krovetz, «Software-optimized universal hashing and message authentication», UMI Dissertation Services, 2000.
• M. Wegman and L. Carter, «New hash functions and their use in authentication and set equality», Journal of Computer and System Sciences, 22 (1981), pp. 265–279.