Two-Track-MAC

Two-Track-MAC — код аутентификации сообщений, предназначенный для проверки подлинности и целостности передаваемых данных. Другими словами мы можем убедиться в том, что данные передавались от нужного источника и их содержание не менялось во время передачи.

Основная цель: предотвратить изменений сообщений третьей стороной во время передачи. Примером сообщений могут служить электронные банковские платежи или системы автоматизированного управления подвижными объектами.

Разработчики: Bart van Rompay^[англ.], Bert den Boer^[англ.].

Алгоритм Two-Track-MAC был избран в проект NESSIE (Новые европейские алгоритмы для электронной подписи) в ноябре 2000 года и задумывался как более быстрый и надежный аналог имевшихся в то время алгоритмов MAC. В разработке принимали участие Bart van Rompay^[англ.] из Лёвенского университета (Katholieke Universiteit Leuven) — Бельгия и Bert den Boer^[англ.] из debis AG^[нем.] (Германия).

В основе Two-Track-MAC лежит хеш-функция RIPEMD-160. Особенность заключается в шифровании сообщения по двум независимым путям (на рисунке обозначены как L и R). Такой подход позволяет увеличить размер внутреннего состояния. В результате чего мы получаем больше возможных значений внутренней функции шифрования. Это позволяет усложнить атаки, основанные на переборе всевозможных значений.

По сравнению с MDx-MAC, который так же основан на RIPEMD-160 Two-Track-MAC намного эффективнее для коротких сообщений (512 или 1024 бит), и также эффективней на длинных сообщениях.

Другое важное преимущество TTMAC является возможность быстрого изменения ключа шифрования. Это позволяет увеличить стойкость системы, без снижения скорости. При довольно частой смене ключа злоумышленнику не удастся собрать большого количества пар сообщение-MAC-код, что сильно снижает вероятность подбора ключа или MAC-кода.

Как уже отмечалось Two-Track-MAC имеет два параллельных блока преобразований L(K,M) и R(K,M), принимающие на вход сообщение M и ключ K. В результате каждый из блоков работает независимо друг от друга и создает два различных представления (А и В на рисунке) одних и тех же данных.

Предположим для начала, что размер сообщения M составляет 512 бит. Размер ключа K всегда фиксирован и составляет 160 бит. Для усложнения преобразований L(K,M) дает на выходе пять 32-битных слов (${\displaystyle A_{0},A_{1},A_{2},A_{3},A_{4}}$). То есть формально разделяет пока ещё предварительный вариант ключа на 5 частей одинаковых размеров. Аналогично набор (${\displaystyle B_{0},B_{1},B_{2},B_{3},B_{4}}$) дает на выходе функция R(K,M). Затем эти слова вычитаются по модулю ${\displaystyle 2^{32}}$. Это своего рода смешивание двух значений для приведения из к фиксированной длине 160 бит. Окончательный результат: ${\displaystyle E=~~(E_{0},E_{1},E_{2},E_{3},E_{4}}$), где ${\displaystyle E_{i}=A_{i}-B_{i}~~mod~~2^{32},~~i=0,1,2,3,4}$. Собственно это и есть то, ради чего все делалось. E является кодом аутентичности сообщения M.

Если сообщение превышает 512 бит, то M разбивается на блоки ${\displaystyle M=M_{1}M_{2}M_{3}...M_{n}}$, где ${\displaystyle M_{i}}$ имеет длину 512 бит. В результате процесс мы все те же операции проводим над каждым блоком, перемешивая их по очереди. Сообщение длиной не кратной 512 дополняется нулями и единицами до нужного нам размера.

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

Введем обозначения: ${\displaystyle A=(A_{0},A_{1},A_{2},A_{3},A_{4})=L^{(}K,M_{1})}$

${\displaystyle B=(B_{0},B_{1},B_{2},B_{3},B_{4})=R^{(}K,M_{1})}$

Далее создаем два 160-битных блоков ${\displaystyle C=(C_{0},C_{1},C_{2},C_{3},C_{4})}$ и ${\displaystyle D=(D_{0},D_{1},D_{2},D_{3},D_{4})}$. Эти блоки заполняются различными комбинациями с выходными данными функций L и R. А именно:

${\displaystyle C_{2}=A_{3}-B_{0}}$,

${\displaystyle C_{3}=A_{4}-B_{1}}$,

${\displaystyle C_{0}=(A_{1}+A_{4})-B_{3}}$,

${\displaystyle C_{1}=A_{2}-B_{4}}$,

${\displaystyle D_{1}=(A_{4}+A_{2})-B_{0}}$,

${\displaystyle D_{2}=A_{0}-B_{1}}$,

${\displaystyle D_{3}=A_{1}-B_{2}}$,

${\displaystyle D_{4}=A_{2}-B_{3}}$,

${\displaystyle D_{0}=A_{3}-B_{4}}$.

Не стоит забывать, что все сложения и вычитания производятся по модулю ${\displaystyle 2^{32}}$.

Когда сообщение больше 512 бит, полученные блоки C и D будут подаваться на вход вместо ключа для следующего блока сообщения. Так происходит пока мы не пройдем все сообщение.

Условно весь процесс создания создания кода аутентичности можно представляется как :

${\displaystyle HL(1)=A=L^{*}(K,M1)}$

${\displaystyle HR(1)=B=R^{*}(K,M1)}$

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

${\displaystyle (A,B)->(C,D)}$

${\displaystyle HL(i)=A=L^{*}(C,M_{i})}$

${\displaystyle HR(i)=B=R^{*}(D,M_{i})}$

На последней итерации получается мы меняем местами входные данные для R и L. Это делается для повышения стойкости кода аутентификации. Окончательные ${\displaystyle HL(n)}$ и ${\displaystyle HR(n)}$ представляют собой Two-track-MAC.

Ниже представлен псевдокод алгоритма.

${\displaystyle C_{0}:=K_{0};C_{1}:=K1;C_{2}:=K_{2};C_{3}:=K_{3};C_{4}:=K_{4};D_{0}:=K_{0};D_{1}:=K_{1};D_{2}:=K_{2};D_{3}:=K_{3};D_{4}:=K_{4};}$
FOR i:= 0 TO n-1 {
  ${\displaystyle A_{0}:=C_{0};A_{1}:=C_{1};A_{2}:=C_{2};A_{3}:=C_{3};A_{4}:=C_{4};}$
  ${\displaystyle B_{0}:=D_{0};B_{1}:=D_{1};B_{2}:=D_{2};B_{3}:=D_{3};B_{4}:=D_{4};}$
  IF (i!=n-1) FOR j:= 0 TO 79 {
     ${\displaystyle T:=rol_{s(j)}(A_{0}\oplus f(j,A_{1},A_{2},A_{3})\oplus M_{i}[r(j)]\oplus c(j))\oplus A_{4}}$;
     ${\displaystyle A_{0}:=A_{4};A_{4}:=A_{3};A_{3}:=rol_{10}(A_{2});A_{2}:=A_{1};A_{1}:=T;}$
     ${\displaystyle T:=rol_{s^{'}(j)}(B_{0}\oplus f(79-j,B_{1},B_{2},B_{3})\oplus M_{i}[r^{'}(j)]\oplus c^{'}(j))\oplus B_{4};}$
     ${\displaystyle B_{0}:=B_{4};B_{4}:=B_{3};B_{3}:=rol_{10}(B_{2});B_{2}:=B_{1};B_{1}:=T;}$
  }
  else FOR j:= 0 TO 79 {
     ${\displaystyle T:=rol_{s(j)}(A_{0}\oplus f(j,A_{1},A_{2},A_{3})\oplus M_{i}[r(j)]\oplus c(j))\oplus A_{4}}$
     ${\displaystyle A_{0}:=A_{4};A_{4}:=A_{3};A_{3}:=rol_{10}(A_{2});A_{2}:=A_{1};A_{1}:=T;}$
     ${\displaystyle T:=rol_{s^{'}(j)}(B_{0}\oplus 79-j,B_{1},B_{2},B_{3})\oplus M_{i}[r^{'}(j)]\oplus c^{'}(j))}$
     ${\displaystyle B_{0}:=B_{4};B_{4}:=B_{3};B_{3}:=rol_{10}(B_{2});B_{2}:=B_{1};B_{1}:=T;}$
  }
  ${\displaystyle A_{0}:=A_{0}\ominus C_{0};A_{1}:=A_{1}\ominus C_{1};A_{2}:=A_{2}\ominus C_{2};A_{3}:=A_{3}\ominus C_{3}}$
  ${\displaystyle A_{4}:=A_{4}\ominus C_{4}}$
  ${\displaystyle B_{0}:=B_{0}\ominus D_{0};B_{1}:=B_{1}\ominus D_{1};B_{2}:=B_{2}\ominus D_{2};B_{3}:=B_{3}\ominus D_{3}}$
  ${\displaystyle B_{4}:=B_{4}\ominus D_{4};}$
  IF (i != n-1) {
     ${\displaystyle C_{2}:=A_{3}\ominus B_{0};C_{3}:=A_{4}\ominus B_{1};C_{4}:=A_{0}\ominus B_{2};C_{0}:=(A_{1}/oplusA_{4})\ominus B_{3}}$
     ${\displaystyle C_{1}:=A_{2}\ominus B_{4}}$
     ${\displaystyle D_{1}:=(A_{4}\oplus A_{2})\ominus B_{0};D_{2}:=A_{0}\ominus B_{1};D_{3}:=A_{1}\ominus B_{2}}$
     ${\displaystyle D_{4}:=A_{2}\ominus B_{3};D_{0}:=A_{3}\ominus B_{4}}$
 }
}
${\displaystyle E_{0}:=A_{0}\ominus B_{0};E_{1}:=A_{1}\ominus B_{1};E_{2}:=A_{2}\ominus B_{2};E_{3}:=A_{3}\ominus B_{3};}$
${\displaystyle E_{4}:=A_{4}\ominus B_{4}}$;

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

${\displaystyle f(j,x,y,z)}$ — нелинейная функция, работающая с битами. Для различных j производит различные операции над x, y,z. А именно:

• ${\displaystyle f(j;x;y;z)=x\otimes y\otimes z~~~~~~~~~~~~~(0\leq j\leq 15)}$
• ${\displaystyle f(j;x;y;z)=(x\wedge y)\lor (\neg x\wedge z)~~~(16\leq j\leq 31)}$
• ${\displaystyle f(j;x;y;z)=(x\lor \neg y)\otimes z~~~~~~~~~~(32\leq j\leq 47)}$
• ${\displaystyle f(j;x;y;z)=(x\land z)\lor (y\land \neg z)~~~~(48\leq j\leq 63)}$
• ${\displaystyle f(j;x;y;z)=x\otimes (y\lor \neg z)~~~~~~~~~(64\leq j\leq 79)}$

Например на языке C удобно представить эти функции в виде макросов^[1]:

#define F1(x, y, z)	(x ^ y ^ z)
#define F2(x, y, z)	(z ^ (x & (y^z)))
#define F3(x, y, z)	(z ^ (x | ~y))
#define F4(x, y, z)	(y ^ (z & (x^y)))
#define F5(x, y, z)	(x ^ (y | ~z))

Символами ${\displaystyle c(j),c^{'}(j)}$ обозначены константы, значения которых определяется диапазоном j:

• с(j) = 00000000x ${\displaystyle (0\leq j\leq 15)}$
• с(j) = 5A827999x ${\displaystyle (16\leq j\leq 31)}$
• с(j) = 6ED9EBA1x ${\displaystyle (32\leq j\leq 47)}$
• с(j) = 8F1BBCDCx ${\displaystyle (48\leq j\leq 63)}$
• с(j) = A953FD4Ex ${\displaystyle (64\leq j\leq 79)}$
• с'(j) = 50A28BE6x ${\displaystyle (0\leq j\leq 15)}$
• с'(j) = 5C4DD124x ${\displaystyle (16\leq j\leq 31)}$
• с'(j) = 6D703EF3x ${\displaystyle (32\leq j\leq 47)}$
• с'(j) = 7A6D76E9x ${\displaystyle (48\leq j\leq 63)}$
• с'(j) = 00000000x ${\displaystyle (64\leq j\leq 79)}$

Функции r(j) и r' дают один из 16 возможных блоков, на которые делится исходное сообщение. Так как блоки имеют размер 512 бит, то r(j) может принимать значения от 0 до 15. Где r(j) = 0 (r'(j) = 0) означает биты 0…15, а r(j) = 15 (r'(j) = 15) — биты 495…511 соответственно.

• r(j) = j при ${\displaystyle (0\leq j\leq 15)}$
• r(16..31) = 7; 4; 13; 1; 10; 6; 15; 3; 12; 0; 9; 5; 2; 14; 11; 8
• r(32..47) = 3; 10; 14; 4; 9; 15; 8; 1; 2; 7; 0; 6; 13; 11; 5; 12
• r(48..63) = 1; 9; 11; 10; 0; 8; 12; 4; 13; 3; 7; 15; 14; 5; 6; 2
• r(64..79) = 4; 0; 5; 9; 7; 12; 2; 10; 14; 1; 3; 8; 11; 6; 15; 13
• r'(0..15) = 5; 14; 7; 0; 9; 2; 11; 4; 13; 6; 15; 8; 1; 10; 3; 12
• r'(16..31) = 6; 11; 3; 7; 0; 13; 5; 10; 14; 15; 8; 12; 4; 9; 1; 2
• r'(32..47) = 15; 5; 1; 3; 7; 14; 6; 9; 11; 8; 12; 2; 10; 0; 4; 13
• r'(48..63) = 8; 6; 4; 1; 3; 11; 15; 0; 5; 12; 2; 13; 9; 7; 10; 14
• r'(64..79) = 12; 15; 10; 4; 1; 5; 8; 7; 6; 2; 13; 14; 0; 3; 9; 11

Пример: Пусть сообщение:

M = "Software-optimized universal hashing and message authentication."

Поставим в соответствие каждому символу определённый код:

"S", "o", "f", "t", "w", "a", "r", "e", "-", "o", "p", "t", "i", "m", "i", "z"
 83, 111, 102, 116, 119, 97,  114, 101, 45,  111, 112, 116, 105, 109, 105, 122
"e", "d", " ", "u", "n", "i", "v", "e", "r", "s", "a", "l", " ", "h", "a", "s"
101, 100,  32, 117, 110, 105, 118, 101, 114, 115,  97, 108,  32, 104,  97, 115
"h", "i", "n", "g", " ", "a", "n", "d", " ", "m", "e", "s", "s", "a", "g", "e"
104, 105, 110, 103, 32,  97, 110,  100, 32,  109, 101, 115, 115,  97, 103, 101
" ", "a", "u", "t", "h", "e", "n", "t", "i", "c", "a", "t", "i", "o", "n", "."
 32,  97, 117, 116, 104, 101, 110, 116, 105,  99,  97, 116, 105, 111, 110,  46

В двоичном представлении текст сообщение будет содержать 512 нулей и единиц. Затем оно разбивается на 16 блоков по 32 бита:

${\displaystyle M_{0}=}$ = (01010011 01101111 01100110 01110100) 
${\displaystyle M_{1}=}$ = (01110111 01100001 01110010 01100101)
${\displaystyle M_{2}=}$ = (00101101 01101111 01110000 01110100)
${\displaystyle M_{3}=}$ = (01101001 01101101 01101001 01111010) 
${\displaystyle M_{4}=}$ = (01100101 01100100 00100000 01110101) 
${\displaystyle M_{5}=}$ = (01101110 01101001 01110110 01100101)
${\displaystyle M_{6}=}$ = (01110010 01110011 01100001 01101100) 
${\displaystyle M_{7}=}$ = (00100000 01101000 01100001 01110011)
${\displaystyle M_{8}=}$ = (01101000 01101001 01101110 01100111) 
${\displaystyle M_{9}=}$ = (00100000 01100001 01101110 01100100)
${\displaystyle M_{10}=}$ = (00100000 01101101 01100101 01110011) 
${\displaystyle M_{11}=}$ = (01110011 01100001 01100111 01100101)
${\displaystyle M_{12}=}$ = (00100000 01100001 01110101 01110100) 
${\displaystyle M_{13}=}$ = (01101000 01100101 01101110 01110100)
${\displaystyle M_{14}=}$ = (01101001 01100011 01100001 01110100) 
${\displaystyle M_{15}=}$ = (01101001 01101111 01101110 00101110)

В результате функция ${\displaystyle M(r(16))}$ выдаст: (00100000 01101000 01100001 01110011). А ${\displaystyle M_{2}(r(16))}$ даст третий бит, т.е 1.

s(j) и ${\displaystyle s^{'}(j)}$ — дают номер бита для операции битового поворота rol.

• s(0..15) = 11; 14; 15; 12; 5; 8; 7; 9; 11; 13; 14; 15; 6; 7; 9; 8
• s(16..31) = 7; 6; 8; 13; 11; 9; 7; 15; 7; 12; 15; 9; 11; 7; 13; 12
• s(32..47) = 11; 13; 6; 7; 14; 9; 13; 15; 14; 8; 13; 6; 5; 12; 7; 5
• s(48..63) = 11; 12; 14; 15; 14; 15; 9; 8; 9; 14; 5; 6; 8; 6; 5; 12
• s(64..79) = 9; 15; 5; 11; 6; 8; 13; 12; 5; 12; 13; 14; 11; 8; 5; 6
• s'(0..15) = 8; 9; 9; 11; 13; 15; 15; 5; 7; 7; 8; 11; 14; 14; 12; 6
• s'(16..31) = 9; 13; 15; 7; 12; 8; 9; 11; 7; 7; 12; 7; 6; 15; 13; 11
• s'(32..47) = 9; 7; 15; 11; 8; 6; 6; 14; 12; 13; 5; 14; 13; 13; 7; 5
• s'(48..63) = 15; 5; 8; 11; 14; 14; 6; 14; 6; 9; 12; 9; 12; 5; 15; 8
• s'(64..79) = 8; 5; 12; 9; 12; 5; 14; 6; 8; 13; 6; 5; 15; 13; 11; 11

На самом деле все выше описанные выражения заимствованны из алгоритма хеш-функции RIPEMD-160. Собственно поэтому RIPEMD-160 и является основой для Two-Track-MAC.

Реализация алгоритма TTMAC была включена в криптографическую библиотеку Crypto++^[2].

Продемонстрируем пример работы алгоритма для различных входных данных. Первый параметр — 160-битный ключ. Второй параметр — передаваемое сообщение. На выходе мы получаем 160 битный код аутентификации.

TTMAC(K,M) = TTMAC(0000000000000000000000000000000000000000,"") = 46724343BDDF4A150009046D4CBF16F2A6378073

TTMAC(K,M) = TTMAC(0000000000000000000000000000000000000000,"Hello World") = 5C8350FEEA6922C4E79F262A72603AA7F99C381D

TTMAC(K,M) = TTMAC(0000000000000000000000000000000000000001,"1") = 8B91136B35096C30C58FA17D7ADE882DBC1CC482

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

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

Возможно так же совместное использование кода аутентификации сообщения совместно с функцией симметричного шифрования по одной из схем: ${\displaystyle E_{k_{1}}(M,TTMAC_{k_{2}}(M))}$

${\displaystyle (E_{k_{1}}(M),TTMAC_{k_{2}}(M))}$

${\displaystyle (E_{k_{1}}(M),TTMAC_{k_{2}}(E_{k_{1}}(M)))}$

Такой подход предполагает различие в ключах ${\displaystyle k_{2}}$ и ${\displaystyle k_{1}}$,а также различие в алгоритмах шифрования и вычисления MAC. Иначе есть вероятность возникновения дополнительных соотношений, которые можно использовать для отбраковки ключей.

В частности TTMAC может использоваться для «аутентификации транзакций». Это означает, что сообщение подтверждается единственностью и своевременной передачей. Такой тип аутентификации предоставляет возможность защиты от повторного использования ранее переданных сообщений, что необходимо в тех случаях, когда угроза может привести к нежелательным последствиям.

Успешность атак на Two-Track-MAC зависит от сложности ключа k, длина которого должна составляет 160 бит, длины выходного кода m, которая может составлять 32,64,.. и 160 бит и длины l внутреннего состояния, которая составляет 320 бит.

Первая возможность — перебор всех возможных ключей. Если удается подобрать ключ, то злоумышленник имеет возможность подделать любое сообщение. Для ключа длины k и выходного кода длины m, такая атака требует ${\displaystyle 2^{k}}$ попыток и ${\displaystyle {\frac {k}{m}}}$ известных пар (текст, MAC) для проверки. Так как размер внутреннего состояния TTMAC составляет 360 бит, то вероятность вычислить значение кода аутентичности снижается до ${\displaystyle 2^{160}}$, по сравнению с ${\displaystyle 2^{80}}$ для RIPEMD-160.

Поиск так называемых [Коллизия|коллизий] требует знания ${\displaystyle 2^{\frac {l}{2}}}$ пар (текст,MAC), где l — длина внутреннего состояния. В самом деле это результат следует из парадокса «дней рождений». Для обнаружения внутренних коллизий с помощью исследования внешний коллизий, требуется порядка ${\displaystyle 2^{l-m}}$ наборов текст-MAC. Кроме того риск может быть уменьшен уменьшением времени жизни ключа.

Результаты приведены таблице:

Типы атак	Попытки	Возможный успех	Известные пары
Поиск ключа	${\displaystyle 2^{160}}$	${\displaystyle {\frac {160}{m}}}$
Угадывание MAC		${\displaystyle {\frac {1}{2^{m}}}}$
Атака основанная на парадоксе дней рождения			${\displaystyle 2^{160}}$

Число операции для TTMAC всего лишь на несколько процентов превосходит число операций требуемых для вычисление RIPEMD-160. Сравним высоко оптимизированный код RIPEMD-160 и TTMAC. Первый требует 1013 циклов на блок, а для TTMAC такой же степени оптимизации понадобится около 1044 цикла на блок. Это достигается благодаря изначальному проектированию алгоритма для быстрой работы на вычислительных устройствах.

• Hash-based message authentication code
• Message authentication code
• RIPEMD-160

• А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин Основы криптографии: Учебное пособие. 3-е изд. — М.: Гелиос APB,2005 — 480c.,ил.
• Stinson, D.R. (Douglas Robert), 1956 — Cryptography: theory and practice /D.R. Stinson. p. cm. — (Discreete mathematics and its application) Includes bibliographical references and index. ISBN 0-8493-8521-0.

• http://portal.acm.org/citation.cfm?id=646557.694750&coll=&dl=
• https://www.cosic.esat.kuleuven.be/nessie/reports/
• http://www.wordiq.com/definition/Katholieke_Universiteit_Leuven