Message authentication algorithm

Message authentication algorithm (MAA, алгоритм аутентификации сообщений) — один их первых алгоритмов имитозащиты электронных сообщений. Был разработан Дональдом Девисом (англ. Donald Davies) и Дэвидом Клейденом из Национальной физической лаборатории Великобритании и опубликован в 1983 году. Это был один из первых подобных алгоритмов, получивших широкое распространение.

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

История

Оригинальное описание алгоритма было дано на естественном языке и снабжено несколькими таблицами и двумя исходными кодами на языках Си и Бейсик. Алгоритм был стандартизирован ISO в 1987 году и стал частью стандартов ISO 8730 и ISO 8731-2, направленных на защиту аутентичности и целостности банковских транзакций.

Дальнейший криптоанализ алгоритма показал ряд уязвимостей, включая возможность взлома «грубой силой», существование коллизий и возможность восстановления ключей. По этим причинам ISO отказался от алгоритма в 2002 году. Сейчас алгоритм продолжает использоваться в основном академической среде как база для оценки различных формальных методов, а также в образовательных целях.

Описание алгоритма

Входные данные

Сообщение S — битовая строка длины 32L, где L принимает значения от 0 до $10^{6}$
Секретный ключ Z длины 64 бита. Ключ состоит из двух 32 разрядных чисел J и K.

Выходные данные

Message authentication code длиной 32 бита

Расширение ключа

Первой частью работы алгоритма является расширение 64-битного ключа (два 32-битных слова J и K) до 192 бит (шесть 32-битных слов: X, Y, W, V, S, T). Эти значения находятся следующим образом:
1. X<- [ $j^{4}$ mod (2³² — 1)] xor [ $j^{4}$ mod (2³² — 2)]
2. Y<- [ $k^{5}$ mod (2³² — 1) xor $k^{5}$ mod (2³² — 2)]*(1+p)² mod (2³² — 2)
3. V<- [ $j^{6}$ mod (2³² — 1)] xor [ $j^{6}$ mod (2³² — 2)]
4. W<- [ $k^{7}$ mod (2³² — 1) xor $k^{7}$ mod (2³² — 2)]*(1+p)² mod (2³² — 2)
5. S<- [ $j^{8}$ mod (2³² — 1)] xor [ $j^{8}$ mod (2³² — 2)]
6. T<- [ $k^{9}$ mod (2³² — 1) xor $k^{9}$ mod (2³² — 2)]*(1+p)² mod (2³² — 2)
На следующем шаге работы алгоритма происходит замена «слабых» битов (то есть равных 00х или FFх) путём логического сложения их с P.

Константы

Константа А,B,C,D определены следующим образом:
A <- 0x02040801
B <- 0x00804021
C <- 0xbfef7fdf
D <- 0x7dfefbff

Главный цикл

Цикл проходит по всем элементам $X_{i}\,(1\leq i\leq L)$ и его результатом являются значения H1 и H2. На первом шаге цикла переменные H11 и H21 инициализируются значениями X и Y соответственно.

Шаг1

Циклический сдвиг V на 1 бит влево.
Ki= V xor W.

Шаг2

T1= H1i xor X_i;
T2= H2i xor X_i;
M1= ((Ki xor T1) or B) and D
M1= ((Ki xor T2) or A) and C

Шаг3

H1(i+1) = (M2 * T1) mod (2³² — 1)
H2(i+1) = (M1 * T2) mod (2³² — 2)

В результате получаем значения H1 и H2 равные H1l и H2l соответственно.

The Coda

MAC код формируется следующим образом: H=H1 xor H2.

Литература

Preneel, Bart. MAA // Encyclopedia of Cryptography and Security. — 2nd. — Springer, 2011. — P. 741–742. — ISBN 978-1-4419-5905-8. — doi:10.1007/978-1-4419-5906-5_591.
D. W. Davies, D. O. Clayden «The Message Authenticator Algorithm (MAA) and its Implementation»
Bart Preneel, Paul C. van Oorschoty «On the Security of Two MAC Algorithms»