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

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

История

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

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

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

Входные данные Сообщение S — битовая строка длины 32L, где L принимает значения от 0 до Секретный ключ Z длины 64 бита. Ключ состоит из двух 32 разрядных чисел J и K. Выходные данные Message authentication code длиной 32 бита

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

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

Главный цикл Цикл проходит по всем элементам и его результатом являются значения H1 и H2. На первом шаге цикла переменные H11 и H21 инициализируются значениями X и Y соответственно. Шаг1 Циклический сдвиг V на 1 бит влево. Ki= V xor W. Шаг2 T1= H1i xor Xi; T2= H2i xor Xi; 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.

Литература

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»

Категория:Криптографические хеш-функции