UMAC

Эта статья требует внимания эксперта в области криптографии . Конкретная проблема заключается в следующем: путаница между UMAC как общей концепцией и алгоритмом UMAC RFC 4418; Нужен кто-то, чтобы разделить это на «универсальное хеширование в MAC» и «UMAC и друзья». Подробности см. На странице обсуждения . Криптография WikiProject может помочь нанять эксперта. ( Сентябрь 2019 г. )

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

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

Фон [ править ]

Универсальное хеширование [ править ]

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

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

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

Сильно универсальное хеширование [ править ]

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

{\ Displaystyle \ Pr _ {час \ в час} [час (е) = d | час (а) = с] \,}

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

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

{\ displaystyle h (a) = h_ {0} + \ sum _ {i = 1} ^ {n} h_ {i} a_ {i} \,}

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

{\ Displaystyle \ Pr _ {час \ в H} [час (е) = d | час (а) = с] = {1 \ над | D |}}

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

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

Пример [ править ]

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

Код языка C (оригинал)

/ * DUBIOUS: Похоже, это не имеет ничего общего с (скорее всего, длинным) определением RFC *. Вероятно, это пример общей концепции UMAC. * Кто, чёрт возьми, из 2007 (Nroets) выбирает 3 байта в примере? * * Мы должны переместить это вместе с лучшим определением str. унив. хеш в * uni. хэш. * / #define uchar uint8_t void  UHash24  ( 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 ++ )  {  / * Последний бит контролирует, является ли секретный бит используется. * /  если  ( байт  &  1 )  {        r1  ^ =  s1 ;  / * (сек >> 16) & 0xff * /  r2  ^ =  s2;  / * (сек >> 8) & 0xff * /  r3  ^ =  s3 ;  / * (сек) & 0xff * /  }  байт  >> =  1 ;  / * следующий бит. * /  / * и умножаем секрет на x (т.е. 2), вычитая (с помощью XOR)  полином, когда необходимо сохранить его порядок ниже 24 (?!) * /  uchar  doSub  =  s3  &  0x80 ;       s3  << =  1 ;  если  ( s2  &  0x80 )  s3  | =  1 ;  s2  << =  1 ;  если  ( s1  &  0x80)  s2  | =  1 ;  s1  << =  1 ;      если  ( doSub )  {  / * 0b0001 1011 -> * /  s1  ^ =  0x1B ;  / * x ^ 24 + x ^ 4 + x ^ 3 + x + 1 [16777243 - не простое число] * /  }  }  / * для каждого бита в сообщении * /  }  / * для каждого байта в сообщении * /  * результат ++  ^ =  r1 ;  * результат ++  ^ =  r2 ;  * результат ++  ^ =  r3 ; }

Код языка C (измененный)

#define uchar uint8_t #define swap32 (x) ((x) & 0xff) << 24 | ((x) & 0xff00) << 8 | ((x) & 0xff0000) >> 8 | (x) & 0xff000000) >> 24) / * Это то же самое, но сгруппировано (генерируя лучшую сборку и прочее).  Это все еще плохо, и никто не объяснил, почему он универсален. * / void  UHash24Ex  ( uchar  * msg ,  uchar  * secret ,  size_t  len ,  uchar  * result ) {  uchar  byte ,  read ;  uint32_t  сек  =  0 ,  ret  =  0,  содержание  =  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  - =  читать ;  msg  + =  читать ;    / * Получить новый секрет для каждых трех байтов. * /  sec  =  ( uint32_t )  secret [ 2 ]  <<  16  |  ( uint32_t )  секрет [ 1 ]  <<  8  |  ( uint32_t )  секрет [ 0 ];  секрет  + =  3 ; / * Отличный компрессор. * /  for  ( bitCnt  =  0 ;  bitCnt  <  24 ;  bitCnt ++ )  {  / * Жесткая зависимость данных для удаления: вывод зависит  * от промежуточного.  * Не работает с байтовыми таблицами CRC. * /  if  ( byte  &  1 )  {        ret  ^ =  sec ;  }  байт  >> =  1 ;  / * следующий бит. * /  / * Сдвиговый регистр. * /  сек  << =  1 ;  если  ( сек  & 0x01000000 )  сек  ^ =  0x0100001B ;  сек  & =  0x00ffffff ;  }  / * для каждого бита в сообщении * /  }  / * для каждых 3 байтов в сообщении * /  result [ 0 ]  ^ =  ret  &  0xff ;  результат [ 1 ]  ^ =  ( ret  >>  8 )  &  0xff ;  результат [ 2 ]  ^ =  ( ret  >>  16 )  &  0xff ; }

NH и RFC UMAC [ править ]

NH [ править ]

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

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

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

\operatorname {NH} _{K}(M)=\left(\sum _{i=0}^{(n/2)-1}((m_{2i}+k_{2i}){\bmod {~}}2^{w})\cdot ((m_{2i+1}+k_{2i+1}){\bmod {~}}2^{w})\right){\bmod {~}}2^{2w}

.

где

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

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

RFC 4418 [ править ]

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

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

В RFC 4418 NH преобразован в следующую форму:

Y = 0для (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}))конец для

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

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

movq  $ 0 ,  regY  ; Y = 0 movq  $ 0 ,  regI  ; i = 0 цикл: добавить  reg1 , regM , regI ; reg1 = M + i добавить 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 добавить  regY ,  regY ,  reg3  ; regY = regY + reg3 добавить  regI ,  regI ,  $ 8 cmp  regI ,  regT jlt  loop

См. Также [ править ]

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

Ссылки [ править ]

^ Thorup, Миккель (2009). Хеширование строк для линейного зондирования . Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA) . С. 655–664. CiteSeerX 10.1.1.215.4253 . DOI : 10.1137 / 1.9781611973068.72 . Архивировано (PDF) из оригинала на 2013-10-12., раздел 5.3
^ а б Блэк, Дж .; Halevi, S .; Krawczyk, H .; Кровец, Т. (1999). UMAC: быстрая и безопасная проверка подлинности сообщений (PDF) . Достижения в криптологии (CRYPTO '99) . Архивировано из оригинального (PDF) 10 марта 2012 года. , Уравнение 1, а также раздел 4.2 «Определение NH».

Внешние ссылки [ править ]

Тед Кровец. «UMAC: быстрая и надежная проверка подлинности сообщений» .

«Использование UMAC в протоколе транспортного уровня SSH: draft-miller-secsh-umac-01.txt» . IETF . 2007-09-03.

[1] Thorup, Миккель (2009). Хеширование строк для линейного зондирования . Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA) . С. 655–664. CiteSeerX 10.1.1.215.4253 . DOI : 10.1137 / 1.9781611973068.72 . Архивировано (PDF) из оригинала на 2013-10-12., раздел 5.3

[black-2] а б Блэк, Дж .; Halevi, S .; Krawczyk, H .; Кровец, Т. (1999). UMAC: быстрая и безопасная проверка подлинности сообщений (PDF) . Достижения в криптологии (CRYPTO '99) . Архивировано из оригинального (PDF) 10 марта 2012 года. , Уравнение 1, а также раздел 4.2 «Определение NH».

[1]