Message authentication code

Имитовста́вка (MAC, англ. message authentication code — код аутентификации послания) — средство обеспечения имитозащиты в протоколах аутентификации сообщений с доверяющими друг другу участниками — специальный набор символов, который добавляется к сообщению и предназначен для обеспечения его целостности и аутентификации источника данных.

Имитовставка обычно применяется для обеспечения целостности и защиты от фальсификации передаваемой информации.

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

Для защиты от фальсификации (имитации) сообщения применяется имитовставка, выработанная с использованием секретного элемента (ключа), известного только отправителю и получателю.

Обзор

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

Другим способом является выработка имитовставки (MAC) с помощью специализированного алгоритма имитозащиты на основе симметричного алгоритма шифрования.

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

Имитовставка по ГОСТ 28147-89

ГОСТ 28147-89 предусматривает выработку имитовставки в соответствующем режиме. Длина имитовставки от 1 до 32 бит. Её выработка происходит по следующей схеме.

Открытый текст ${\displaystyle T_{O}}$ разбивается на блоки длиной 64 бита. Последний блок в случае необходимости дополняется нулями.

${\displaystyle T_{O}=T_{O}^{(1)}\,T_{O}^{(2)}\,\ldots \,T_{O}^{(N)}}$

Первый блок ${\displaystyle T_{O}^{(1)}}$ шифруется в режиме (ECB) тем же ключом, что и сообщение, но с применением 16 циклов вместо 32. Результат складывается побитово по модулю 2 со вторым блоком ${\displaystyle T_{O}^{(2)}}$ и так же шифруется. Результат складывается с третьим блоком, и так далее.

${\displaystyle I=E'_{k}(T_{O}^{(N)}\oplus E'_{k}(T_{O}^{(N-1)}\oplus E'_{k}(\,\ldots \,E'_{k}(T_{O}^{(2)}\oplus E'_{k}(T_{O}^{(1)}))\,\ldots \,))}$

Первые 32 бита получившегося блока составляют имитовставку. Спецификация шифра предусматривает использование в качестве имитовставки, по желанию, меньшего количества бит, но не большего.

Имитовставка обычно передаётся в конце сообщения и может вычисляться либо отдельно от шифрования/расшифрования, либо в процессе оного.

MAA

MAA (Message Authenticator Algorithm) — алгоритм проверки подлинности сообщений.

Этот алгоритм является стандартом ISO. Он выдаёт 32-битовое хэш-значение и был спроектирован для (мэйнфреймов) с быстрыми инструкциями умножения.

v=v<<<1

e=v xor w

x=((((e+y) mod 2^32)۷A۸C)*(x xor Mi))mod 2^32-1

y=((((e+x) mod 2^32)۷B۸D)*(y xor Mi))mod 2^32-1

Эти действия повторяются для каждого блока сообщений, Mi, и результирующее хэш-значение получается с помощью XOR x и y. Переменные v и e зависят от ключа. A, B, C и D являются константами. Возможно, этот алгоритм широко используется, но он недостаточно безопасен. Он разработан давно и не слишком сложен.

Методы Джунемана

Сначала сообщение делится на m-битовые блоки. Затем:

${\displaystyle H_{0}=I}$, где ${\displaystyle I}$ — секретный ключ ${\displaystyle H_{i}=(H_{i-1}+M_{i})^{2}\mod p}$, где ${\displaystyle p}$ — простое число меньше ${\displaystyle 2^{m}-1}$. 

Джунеман предложил значения ${\displaystyle n=16}$ и ${\displaystyle p=2^{31}-1}$. Также он предложил, чтобы ${\displaystyle H_{1}}$ использовался в качестве дополнительного ключа, а действительное сообщение начиналось бы с ${\displaystyle H_{2}}$.

Из-за множества вскрытий типа "дня рождения", было предложено вычислять QCMDC 4 раза, используя результат одной итерации в качестве 4 для следующей итерации^{[уточнить]}, а затем результаты объединялись бы в 128-битовое хэш-значение. В дальнейшем эта идея была усилена за счёт параллельного выполнения 4-х итераций с поперечными связями между ними.

Данная^[] схема была взломана (Доном Копперсмитом).

Другие методы

CBC-MAC

В качестве MAC берётся последний блок сообщения зашифрованного блочным алгоритмом в режимах CBC или СFB.

Недостатком является тот факт, что получатель должен знать ключ, что позволит ему генерировать сообщение с тем же MAC.

RIPE-MAC

Был придуман (Бартом Пренель) в рамках проекта RIPE. Использует DES в качестве функции блочного шифрования. Существует две модификации данного алгоритма:

• RIPE-MAC 1 — использует одно шифрование DES на каждый 64-битный блок сообщения;
• RIPE-MAC 3 — использует тройное шифрование DES на каждый 64-битный блок сообщения.

Свойства:

1. Длина сообщения увеличивается, так, чтобы она была кратна 64.
2. Сообщение разбивается на 64-битные блоки.
3. К сообщению применяется хэш-функция зависящая от ключа (DES или тройной DES).
4. Значение хеш-функции полученное на 3-м шаге ещё раз шифруется DES-алгоритмом, с ключом полученным из ключа, который использовался на 3-м шаге.

IBC-MAC

Также использовалась в рамках проекта RIPE. Вероятность вскрытия IBC-MAC может быть оценена количественно. Ядром функции является

 Hi = ((Mi mod p) + v) mod 2n 

Секретный ключ представляет собой пару чисел p и v:

• p — n-битное простое число
• v — случайное число меньше 2n

Mi — получается с помощью процедуры дополнения.

Каждое сообщение должно хэшироваться новым ключом.

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

Минус в том, что выбранный уровень безопасности ограничивает размер хэшируемого сообщения.

Двунаправленный MAC

Этот MAC выдаёт хэш-значение, которое в два раза длиннее блока алгоритма.

Сначала для сообщения вычисляется CBC-MAC. Затем вычисляется CBC-MAC сообщения с обратным порядком блоков. Двунаправленный MAC просто является объединением этих двух значений.

Данная схема не безопасна^[].

Однонаправленная хэш-функция MAC

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

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

С методами MD-усиления^[] этот способ работает, но есть серьёзные проблемы. Пользователь С всегда может добавить новые блоки к концу сообщения и вычислить правильный MAC. Это вскрытие может быть предотвращено, если к началу сообщения добавить его длину, но это тоже небезопасно. Лучше добавлять ключ к концу сообщения, Н(М,К), но при этом также возникают проблемы. Если Н — однонаправленная функция, которая не защищена от столкновений^[], С может подделывать сообщения. Ещё лучше Н(К,М,К) или Н(К1,М,К2), где К1 и К2 различны. Безопасными кажутся^[] следующие конструкции:

Н(К1, Н(К2,М))

Н(К, Н(К,М))

Н(К, р, М, К)), где р дополняет К до полного блока сообщения.

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

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

MAC с использованием потокового шифра

Эта схема MAC использует потоковые шифры. Криптографический безопасный генератор псевдослучайных битов демультиплексирует поток сообщения на два подпотока. Если на выходе генератора битов ki единиц, то текущий бит сообщения mi отправляется в первый подпоток, если ноль, то mi отправляется во второй подпоток. Каждый подпоток отправляется на свой LFSR. Выходом MAC просто является конечное состояние обоих регистров.

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

Примечания

1. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: Триумф, 2002. — .
2. Методы Джунемана  (неопр.). Studopedia.org. Дата обращения: 1 января 2021.
3. хэшировать — Викисловарь  (неопр.). ru.wiktionary.org. Дата обращения: 1 января 2021.
4. демультиплексирование — Викисловарь  (неопр.). ru.wiktionary.org. Дата обращения: 1 января 2021. Архивировано 20 июня 2017 года.

Литература

• Словарь криптографических терминов / Под ред. Б. А. Погорелова и В. Н. Сачкова. — М.: МЦНМО, 2006. — С. 94. — .

См. также

• (UMAC)