UMAC

Эта статья о коде криптографической аутентификации. Чтобы узнать о спортивной организации, см. Атлетическую конференцию Верхнего Среднего Запада . Чтобы узнать об университете в Макао, см. Университет Макао .

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

Конкретный тип 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 . Другими словами,

$\Pr _{h\in H}[h(f)=d|h(a)=c]\,$

должно быть очень маленьким, желательно 1/| Д |.

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

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

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

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

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

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

Пример

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

show

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

/* DUBIOUS: This does not seem to have anything to do with the (likely long) RFC
 * definition. This is probably an example for the general UMAC concept.
 * Who the heck from 2007 (Nroets) chooses 3 bytes in an example?
 *
 * We gotta move this along with a better definition of str. uni. hash into
 * uni. hash. */
#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, byte;
  
  while (len-- > 0) {
    /* Fetch new secret for every three bytes. */
    if (byteCnt-- == 0) {
      s1 = *secret++;
      s2 = *secret++;
      s3 = *secret++;
      byteCnt = 2;   
    }
    byte = *msg++;
    /* Each byte of the msg controls whether a bit of the secrets make it into the hash.、
     *
     * I don't get the point about keeping its order under 24, because with a 3-byte thing
     * it by definition only holds polynominals order 0-23. The "sec" code have identical
     * behavior, although we are still doing a LOT of work for each bit
     */
    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; /* (sec >>  8) & 0xff */
        r3 ^= s3; /* (sec      ) & 0xff */
      }
      byte >>= 1; /* next bit. */
      /* and multiply secret with x (i.e. 2), subtracting (by XOR)
         the polynomial when necessary to keep its order under 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 -- not a prime] */
      }
    } /* for each bit in the message */
  } /* for each byte in the message */
  *result++ ^= r1;
  *result++ ^= r2;
  *result++ ^= r3;
}

show

Код языка C (пересмотренный)

#define uchar     uint8_t
#define swap32(x) ((x) & 0xff) << 24 | ((x) & 0xff00) << 8 | ((x) & 0xff0000) >> 8 | (x) & 0xff000000) >> 24)
/* This is the same thing, but grouped up (generating better assembly and stuff).
   It is still bad and nobody has explained why it's strongly universal. */
void UHash24Ex (uchar *msg, uchar *secret, size_t len, uchar *result)
{
  uchar byte, read;
  uint32_t sec = 0, ret = 0, content = 0;

  while (len > 0) {
    /* Read three in a chunk. */
    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; /* next bit. */
      /* Shift register. */
      sec <<= 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;
  result[2] ^= (ret >> 16) & 0xff;
}

Хэмпшир и RFC

НХ

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

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

Следующее семейство хэшей $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 выполняется в целых числах без знака. Все умножения — по модулю 2^ w , все сложения — по модулю 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
for (i = 0; i < t; i += 8) do
    ${\begin{aligned}{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+0}+_{32}K_{i+0})*_{64}(M_{i+4}+_{32}K_{i+4}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+1}+_{32}K_{i+1})*_{64}(M_{i+5}+_{32}K_{i+5}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+2}+_{32}K_{i+2})*_{64}(M_{i+6}+_{32}K_{i+6}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+3}+_{32}K_{i+3})*_{64}(M_{i+7}+_{32}K_{i+7}))}}\end{aligned}}$
end for

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

show

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

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       ; load 4x32bit vals from memory *reg1 to vec1
vldr.4x32   vec2, reg2
vmul.4x64   vec3, vec1, vec2 ; vec3 = vec1 * vec2
uaddv.4x64  reg3, vec3       ; horizontally sum vec3 into reg3
add         regY, regY, reg3 ; regY = regY + reg3
add         regI, regI, $8
cmp         regI, regT
jlt         loop

См. также

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

Внешние ссылки

• Тед Кровец. «UMAC: быстрая и доказуемо безопасная аутентификация сообщений» .

• Миллер, Дэмиен; Валчев, Питер (3 сентября 2007 г.). «Использование UMAC в протоколе транспортного уровня SSH: Draft-miller-secsh-umac-01.txt» . IETF .