UMAC - UMAC

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

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

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

Фон

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

Основная статья: универсальное хеширование

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

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

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

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

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

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

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

Легко построить класс хеш-функций, когда D является поле. Например, если |D| является основной, все операции выполняются по модулю |D|, Сообщение а затем кодируется как п-мерный вектор D (а₁, а₂, ..., а_п). ЧАС то есть |D|^п+1 члены, каждый из которых соответствует (п + 1) -мерный вектор над D (час₀, час₁, ..., час_п). Если мы позволим

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

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

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

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

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

Пример

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

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

/ * DUBIOUS: похоже, это не имеет ничего общего с (вероятно, длинным) RFC * определение. Вероятно, это пример общей концепции UMAC. * Кто черт возьми из 2007 (Nroets) выбирает 3 байта в примере? * * Мы должны переместить это вместе с лучшим определением str. унив. хэш в * уни. хэш. * /#define uchar uint8_tпустота UHash24 (учар *сообщение, учар *секрет, size_t len, учар *результат){  учар r1 = 0, r2 = 0, r3 = 0, s1, s2, s3, byteCnt = 0, bitCnt, байт;    пока (len-- > 0) {    / * Получить новый секрет для каждых трех байтов. * /    если (byteCnt-- == 0) {      s1 = *секрет++;      s2 = *секрет++;      s3 = *секрет++;      byteCnt = 2;       }    байт = *сообщение++;    / * Каждый байт сообщения определяет, попадает ли часть секретов в хэш. 、     *     * Я не понимаю, как поддерживать порядок ниже 24, потому что с 3-байтовым     * он по определению содержит только полиномы порядка 0-23. Код «сек» идентичен     * поведение, хотя мы все еще делаем МНОГО работы для каждого бита     */    за (учар bitCnt = 0; bitCnt < 8; bitCnt++) {      / * Последний бит определяет, используется ли секретный бит. * /      если (байт & 1) {        r1 ^= s1; / * (сек >> 16) & 0xff * /        r2 ^= s2; / * (сек >> 8) & 0xff * /        r3 ^= s3; / * (сек) & 0xff * /      }      байт >>= 1; / * следующий бит. * /      / * и умножаем секрет на x (т.е. 2), вычитая (с помощью XOR)         многочлен, если необходимо сохранить его порядок меньше 24 (?!) * /      учар 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)/ * Это то же самое, но сгруппировано (улучшая сборку и прочее).   Это все еще плохо, и никто не объяснил, почему он универсален. * /пустота UHash24Ex (учар *сообщение, учар *секрет, size_t len, учар *результат){  учар байт, читать;  uint32_t сек = 0, Ret = 0, содержание = 0;  пока (len > 0) {    / * Прочитать три куска. * /    содержание = 0;    выключатель (читать = (len >= 3 ? 3 : len)) {      дело 2: содержание |= (uint32_t) сообщение[2] << 16; / * FALLTHRU * /      дело 1: содержание |= (uint32_t) сообщение[1] << 8;  / * FALLTHRU * /      дело 0: содержание |= (uint32_t) сообщение[0];    }    len -= читать; сообщение += читать;    / * Получить новый секрет для каждых трех байтов. * /    сек = (uint32_t) секрет[2] << 16 | (uint32_t) секрет[1] << 8 | (uint32_t) секрет[0];    секрет += 3;    / * Отличный компрессор. * /    за (bitCnt = 0; bitCnt < 24; bitCnt++) {      / * Жесткая зависимость данных для удаления: вывод зависит       * на промежуточном.       * Не работает с байтовыми таблицами CRC. * /      если (байт & 1) {        Ret ^= сек;      }      байт >>= 1; / * следующий бит. * /      /* Регистр сдвига. * /      сек <<= 1;      если (сек & 0x01000000)        сек ^= 0x0100001B;      сек &= 0x00ffffff;    } / * для каждого бита в сообщении * /  } / * для каждых 3 байтов в сообщении * /  результат[0] ^= Ret & 0xff;  результат[1] ^= (Ret >>  8) & 0xff;  результат[2] ^= (Ret >> 16) & 0xff;}

NH и RFC UMAC

NH

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

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

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

${\displaystyle \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 закодировано как п-мерный вектор ш-битовые слова (м₀, м₁, м₂, ..., м_п-1).
• Промежуточный ключ K кодируется как п + 1-мерный вектор ш-битовые слова (k₀, k₁, k₂, ..., k_п). А псевдослучайный генератор генерирует K из общего секретного ключа.

Практически NH выполняется в целых числах без знака. Все умножения по модулю 2 ^ш, все дополнения по модулю 2 ^ш/ 2, а все входы as представляют собой вектор полуслов (${\displaystyle w/2=32}$-битовые целые числа). Затем алгоритм будет использовать ${\displaystyle \lceil k/2\rceil }$ умножения, где ${\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 для (i = 0; i 
Это определение призвано побудить программистов использовать инструкции SIMD для накопления, поскольку только данные с четырьмя индексами, скорее всего, не будут помещены в один и тот же регистр SIMD и, следовательно, быстрее умножатся в большом количестве. На гипотетической машине это можно было бы просто перевести как:
Гипотетическая сборка
movq        $0,   regY  ; Y = 0movq        $0,   regI  ; я = 0петля:Добавить         reg1, regM, regI ; reg1 = M + яДобавить         reg2, regM, regIvldr.4x32   vec1, reg1       ; загрузить 4x32bit vals из памяти * reg1 в vec1vldr.4x32   vec2, reg2вмул.4x64   vec3, vec1, vec2 ; vec3 = vec1 * vec2uaddv.4x64  reg3, vec3       ; горизонтально суммировать vec3 в reg3Добавить         regY, regY, reg3 ; regY = regY + reg3Добавить         regI, regI, $8cmp         regI, regTjlt         петля
Смотрите также









Поли1305 еще один быстрый MAC, основанный на строго универсальном хешировании.
Рекомендации









 Торуп, Миккель (2009). Хеширование строк для линейного зондирования. Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA). С. 655–664. CiteSeerX  10.1.1.215.4253. Дои:10.1137/1.9781611973068.72. В архиве (PDF) из оригинала 2013-10-12., раздел 5.3
 Black, J .; 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.