UMAC

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

. Определенный тип UMAC, также обычно называемый просто UMAC, указан в RFC 4418, он имеет доказуемую криптографическую стойкость и обычно требует гораздо меньше вычислительных ресурсов, чем другие MAC. Дизайн UMAC оптимизирован для 32-разрядных архитектур с поддержкой SIMD, с производительностью 1 цикл ЦП на байт (cpb) с SIMD и 2 cpb без SIMD. Тесно родственный вариант UMAC, оптимизированный для 64-битных архитектур, представлен VMAC, который был представлен в IETF в качестве черновика (draft-krovetz-vmac-01), но так и не привлек достаточного внимания. становится стандартизированным RFC.

• 1 Предпосылки
  • 1.1 Универсальное хеширование
  • 1.2 Сильно универсальное хеширование
  • 1.3 Пример
• 2 NH и RFC UMAC
  • 2.1 NH
  • 2.2 RFC 4418
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

Универсальное хеширование

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

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

Но это определение недостаточно строго - если возможные сообщения 0 и 1, D = {0,1} и H состоит из операции идентичности, а не, H универсален. Но даже если дайджест зашифрован путем добавления модулей, злоумышленник может изменить сообщение и дайджест одновременно, и получатель не заметит разницы.

Сильно универсальное хеширование

Класс хэш-функций H, который можно использовать, затруднит злоумышленнику угадать правильный дайджест d поддельного сообщения f после перехвата одного сообщения a с помощью переваривать c. Другими словами,

$Pr\; h\; \in \; H\; [h\; (f)\; =\; d\; |\; час\; (a)\; =\; c]\; \{\backslash \; displaystyle\; \backslash \; Pr\; \_\; \{h\; \backslash \; in\; H\}\; [h\; (f)\; =\; d\; |\; h\; (a)\; =\; c]\; \backslash ,\}$

должен быть очень маленьким, предпочтительно 1 / | D |,

Легко построить класс хэш-функций, когда D - это поле. Например, если | D | является простым, все операции выполняются по модулю | D |. Сообщение a затем кодируется как n-мерный вектор над D (a 1, a 2,..., a n). H тогда | D | члены, каждый из которых соответствует (n + 1) -мерному вектору над D (h 0, h 1,..., h n). Если мы положим

$h\; (a)\; =\; h\; 0\; +\; \sum \; i\; =\; 1\; nhiai\; \{\backslash \; displaystyle\; h\; (a)\; =\; h\_\; \{0\}\; +\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; h\_\; \{i\}\; a\_\; \{\; i\}\; \backslash ,\}$

мы можем использовать правила вероятностей и комбинаторику, чтобы доказать, что

$Pr\; h\; \in \; H\; [h\; (f)\; =\; d\; |\; h\; (a)\; =\; c]\; =\; 1\; |\; D\; |\; \{\backslash \; displaystyle\; \backslash \; Pr\; \_\; \{h\; \backslash \; in\; H\}\; [h\; (f)\; =\; d\; |\; h\; (a)\; =\; c]\; =\; \{1\; \backslash \; over\; |\; D\; |\}\}$

Если мы правильно зашифруем все дайджесты (например, с одноразовый блокнот ), злоумышленник ничего не может узнать от них, и одна и та же хеш-функция может использоваться для всего обмена данными между двумя сторонами. Это может быть неверно для шифрования ECB, потому что вполне вероятно, что два сообщения производят одно и то же значение хеш-функции. Затем следует использовать какой-то вектор инициализации , который часто называют nonce. Стало обычной практикой устанавливать h 0 = f (nonce), где f также является секретным.

Обратите внимание, что наличие огромной мощности компьютера совершенно не помогает злоумышленнику. Если получатель ограничивает количество принимаемых подделок (засыпая всякий раз, когда он их обнаруживает), | D | может быть 2 или меньше.

Пример

Следующая функция C генерирует 24-битный UMAC. Предполагается, что secretкратно 24 битам, msgне длиннее, чем secretи resultуже содержит 24 секретных бита, например. f (одноразовый номер). nonce не обязательно должен содержаться в msg.

/ * DUBIOUS: похоже, это не имеет ничего общего с (скорее всего, длинным) определением RFC *. Вероятно, это пример общей концепции UMAC. * Кто черт возьми из 2007 (Nroets) выбирает 3 байта в примере? * * Мы должны переместить это вместе с лучшим определением str. унив. хеш в * uni. хэш. * / #define uchar uint8_t void UHasdiv class="ht"4 (uchar * msg, uchar * secret, size_t len, uchar * result) {uchar r1 = 0, r2 = 0, r3 = 0, s1, s2, s3, byteCnt = 0, bitCnt, байт; while (len-->0) {/ * Получить новый секрет для каждых трех байтов. * / if (byteCnt-- == 0) {s1 = * secret ++; s2 = * секрет ++; s3 = * секрет ++; byteCnt = 2; } byte = * msg ++; / * Каждый байт сообщения контролирует, попадает ли часть секретов в хэш. 、 * * Я не понимаю, что нужно поддерживать его порядок ниже 24, потому что с 3-байтовым элементом * он по определению содержит только порядок полиномов 0-23. Код "sec" имеет идентичное * поведение, хотя мы по-прежнему делаем ОЧЕНЬ много работы для каждого бита * / for (uchar bitCnt = 0; bitCnt < 8; bitCnt++) { /* The last bit controls whether a secret bit is used. */ if (byte 1) { r1 ^= s1; /* (sec>>16) 0xff * / r2 ^ = s2; / * (сек>>8) 0xff * / r3 ^ = s3; / * (сек) 0xff * /} байт>>= 1; / * следующий бит. * / / * и умножаем секрет на x (т.е. 2), вычитая (с помощью XOR) полином, когда необходимо сохранить его порядок ниже 24 (?!) * / uchar doSub = s3 0x80; s3 <<= 1; if (s2 0x80) s3 |= 1; s2 <<= 1; if (s1 0x80) s2 |= 1; s1 <<= 1; if (doSub) { /* 0b0001 1011 -->* / s1 ^ = 0x1B; / * x ^ 24 + x ^ 4 + x ^ 3 + x + 1 [16777243 - не простое число] * /}} / * для каждого бита в сообщении * /} / * для каждого байта в сообщении * / * результат ++ ^ = r1; * результат ++ ^ = r2; * результат ++ ^ = r3; }

#define uchar uint8_t #define swap32 (x) ((x) 0xff) << 24 | ((x) 0xff00) << 8 | ((x) 0xff0000)>>8 | (x) 0xff000000)>>24) / * Это то же самое, но сгруппировано (генерируя лучшую сборку и прочее). Это все еще плохо, и никто не объяснил, почему он универсален. * / void UHasdiv class="ht"4Ex (uchar * msg, uchar * secret, size_t len, uchar * result) {uchar byte, read; uint32_t sec = 0, ret = 0, content = 0; while (len>0) {/ * Прочитать три в куске. * / content = 0; switch (read = (len>= 3? 3: len)) {case 2: content | = (uint32_t) msg ​​[2] << 16; /* FALLTHRU */ case 1: content |= (uint32_t) msg[1] << 8; /* FALLTHRU */ case 0: content |= (uint32_t) msg[0]; } len -= read; msg += read; /* Fetch new secret for every three bytes. */ sec = (uint32_t) secret[2] << 16 | (uint32_t) secret[1] << 8 | (uint32_t) secret[0]; secret += 3; /* The great compressor. */ for (bitCnt = 0; bitCnt < 24; bitCnt++) { /* A hard data dependency to remove: output depends * on the intermediate. * Doesn't really work with CRC byte-tables. */ if (byte 1) { ret ^= sec; } byte>>= 1; / * следующий бит. */ /* Регистр сдвига. * / сек <<= 1; if (sec 0x01000000) sec ^= 0x0100001B; sec = 0x00ffffff; } /* for each bit in the message */ } /* for each 3 bytes in the message */ result[0] ^= ret 0xff; result[1] ^= (ret>>8) 0xff; результат [2] ^ = (ret>>16) 0xff; }

NH

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

Семейство NH вдвое уменьшает количество умножений, что на практике дает двукратное ускорение. Для скорости UMAC использует семейство хэш-функций NH. NH специально разработан для использования инструкций SIMD, и, следовательно, UMAC является первой функцией MAC, оптимизированной для SIMD.

Следующее семейство хешей: $2\; -\; w\; \{\backslash \; displaystyle\; 2\; ^\; \{\; -w\}\}$-универсальный:

$NH\; K\; \; (M)\; =\; (\sum \; i\; =\; 0\; (n\; /\; 2)\; -\; 1\; ((m\; 2\; i\; +\; k\; 2\; i)\; mod\; 2\; w)\; \cdot \; ((м\; 2\; я\; +\; 1\; +\; К\; 2\; я\; +\; 1)\; по\; модулю\; 2\; ш))\; по\; модулю\; 2\; 2\; вес\; \{\backslash \; Displaystyle\; \backslash \; OperatorName\; \{NH\}\; \_\; \{K\}\; (M)\; =\; \backslash \; left\; (\backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{(n\; /\; 2)\; -1\}\; ((m\_\; \{2i\}\; +\; k\_\; \{2i\})\; \{\backslash \; bmod\; \{~\}\}\; 2\; ^\; \{w\})\; \backslash \; cdot\; ((m\_\; \{2i\; +\; 1\}\; +\; k\_\; \{2i\; +\; 1\})\; \{\backslash \; bmod\; \{~\}\}\; 2\; ^\; \{w\})\; \backslash \; right)\; \{\backslash \; bmod\; \{~\}\}\; 2\; ^\; \{2w\}\}$.

где

• Сообщение M закодировано как n-мерный вектор w-битовых слов (m 0, m 1, m 2,..., m n-1).
• Промежуточный ключ K кодируется как n + 1-мерный вектор w-битовых слов (k 0, k 1, k 2,..., k n). Генератор псевдослучайных чисел генерирует K из общего секретного ключа.

На практике NH выполняется в целых числах без знака. Все умножения выполняются по модулю 2 ^ w, все сложения - по модулю 2 ^ w / 2, и все входы as являются вектором полуслова ($w\; /\; 2\; =\; 32\; \{\backslash \; displaystyle\; w\; /\; 2\; =\; 32\}$-битные целые числа). Затем алгоритм будет использовать $\lceil \; k\; /\; 2\; \rceil \; \{\backslash \; displaystyle\; \backslash \; lceil\; k\; /\; 2\; \backslash \; rceil\}$умножения, где $k\; \{\backslash \; displaystyle\; k\}$было количество полуслов в векторе. Таким образом, алгоритм работает со «скоростью» одно умножение на слово ввода.

RFC 4418

RFC 4418 делает многое, чтобы обернуть NH, чтобы сделать его хорошим UMAC. Общая процедура UHASH («Универсальная хеш-функция») создает теги переменной длины, которая соответствует количеству итераций (и общей длине ключей), необходимых на всех трех уровнях ее хеширования. Несколько вызовов основанной на AES функции деривации ключа используются для предоставления ключей для всех трех хэшей с ключами.

• Уровень 1 (блоки по 1024 байта ->объединенные хэши по 8 байтов) использует NH, потому что он быстрый.
• Уровень 2 хеширует все до 16 байтов, используя функцию POLY, которая выполняет арифметику простого модуля с простым изменяется по мере увеличения размера входных данных.
• Уровень 3 хэширует 16-байтовую строку до фиксированной длины в 4 байта. Это то, что генерирует одна итерация.

В RFC 4418 NH перегруппировывается так, чтобы принимать форму:

Y = 0 for (i = 0; i < t; i += 8) do Y = Y +_64 ((M_{i+0} +_32 K_{i+0}) *_64 (M_{i+4} +_32 K_{i+4})) Y = Y +_64 ((M_{i+1} +_32 K_{i+1}) *_64 (M_{i+5} +_32 K_{i+5})) Y = Y +_64 ((M_{i+2} +_32 K_{i+2}) *_64 (M_{i+6} +_32 K_{i+6})) Y = Y +_64 ((M_{i+3} +_32 K_{i+3}) *_64 (M_{i+7} +_32 K_{i+7})) end for

Это определение разработан, чтобы побудить программистов использовать инструкции SIMD для накопления, поскольку только данные с четырьмя индексами, вероятно, не будут помещены в один и тот же регистр SIMD и, следовательно, быстрее умножатся в большом количестве. На гипотетической машине это могло бы просто преобразовать в :

Гипотетическая сборка

movq $ 0, regY; Y = 0 movq $ 0, regI; i = 0 loop: add reg1, regM, regI; reg1 = M + i add reg2, regM, regI vldr.4x32 vec1, reg1; загрузить 4x32bit vals из памяти * reg1 в vec1 vldr.4x32 vec2, reg2 vmul.4x64 vec3, vec1, vec2; vec3 = vec1 * vec2 uaddv.4x64 reg3, vec3; горизонтально суммировать vec3 в reg3 add regY, regY, reg3; regY = regY + reg3 добавить regI, regI, $ 8 cmp regI, regT jlt loop

См. также

• Poly1305 - еще один быстрый MAC, основанный на строго универсальном хешировании.

Ссылки

Внешний links

• Тед Кровец. "UMAC: Fast and Pr постоянно защищенная аутентификация сообщений ".

• " Использование UMAC в протоколе транспортного уровня SSH: draft-miller-secsh-umac-01.txt ". IETF. 3 сентября 2007 г.