Dvoustopý MAC

Two-Track-MAC je ověřovací kód zprávy určený k ověření pravosti a integrity přenášených dat. Jinými slovy, můžeme se ujistit, že data byla přenesena ze správného zdroje a jejich obsah se během přenosu nezměnil.

Primární účel : Zabraňte tomu, aby byly zprávy během přenosu upravovány třetí stranou. Příkladem zpráv jsou elektronické bankovní platby nebo automatizované kontrolní systémy pro pohyb objektů.

Vývojáři : Bart van Rompay , Bert den Boer .

Historie vytvoření

Algoritmus Two-Track-MAC byl zvolen do projektu NESSIE (New European Electronic Signature Algorithms) v listopadu 2000 a byl koncipován jako rychlejší a spolehlivější analog v té době dostupných MAC algoritmů. Na vývoji se podíleli Bart van Rompay z University of Leuven (Katholieke Universiteit Leuven) - Belgie a Bert den Boer z debis AG (Německo) .

Popis

Two-Track-MAC je založen na hashovací funkci RIPEMD-160 . Zvláštnost spočívá v šifrování zprávy dvěma nezávislými cestami (na obrázku označeny jako L a R ). Tento přístup umožňuje zvětšit velikost vnitřního stavu. V důsledku toho získáme více možných hodnot funkce vnitřního šifrování. To umožňuje komplikovat útoky na základě výčtu všech možných hodnot.

Ve srovnání s MDx-MAC, který je také založen na RIPEMD-160, je Two-Track-MAC mnohem efektivnější pro krátké zprávy (512 nebo 1024 bitů) a také efektivnější pro dlouhé zprávy.

Další důležitou výhodou TTMAC je schopnost rychle změnit šifrovací klíč. To vám umožní zvýšit stabilitu systému bez snížení rychlosti. Při poměrně časté změně klíče nebude útočník schopen shromáždit velké množství párů zpráva-MAC kód, což výrazně snižuje pravděpodobnost uhodnutí klíče nebo MAC kódu.

Jak to funguje

Jak již bylo uvedeno, Two-Track-MAC má dva paralelní transformační bloky L(K,M) a R(K,M) , které přijímají zprávu M a klíč K jako vstup . Výsledkem je, že každý z bloků pracuje nezávisle na sobě a vytváří dvě různé reprezentace ( A a B na obrázku) stejných dat.

Předpokládejme nejprve, že velikost zprávy M je 512 bitů. Velikost klíče K je vždy pevná a je 160 bitů. Aby se transformace zkomplikovaly , L(K,M) vydává pět 32bitových slov ( ) ${\displaystyle A_{0},A_{1},A_{2},A_{3},A_{4))$ . To znamená, že formálně rozděluje dosud předběžnou verzi klíče na 5 stejně velkých částí. Podobně množina ( ) $B_{0},B_{1},B_{2},B_{3},B_{4}$ dává výstup funkce R(K,M) . Potom se tato slova odečítají modulo . Jedná se o jakési smíchání dvou hodnot, které mají být přeneseny na pevnou délku 160 bitů. Konečný výsledek: ) , kde . Ve skutečnosti se kvůli tomu všechno dělalo. E je ověřovací kód zprávy M . $2^{{32}}$ ${\displaystyle E=~~(E_{0},E_{1},E_{2},E_{3},E_{4))$ $E_{i}=A_{i}-B_{i}~~mod~~2^{32},~~i=0,1,2,3,4$

Pokud zpráva přesáhne 512 bitů, pak se M rozdělí na bloky , kde má délku 512 bitů. Výsledkem tohoto procesu je, že na každém bloku provádíme stejné operace a střídáme je. Zpráva s délkou, která není násobkem 512, je doplněna nulami a jedničkami na velikost, kterou potřebujeme. ${\displaystyle M=M_{1}M_{2}M_{3}...M_{n))$ $M_{i}$

Více o míchání výsledků L a R

Poté, co každá větev algoritmu zpracuje další blok zprávy, musí být výsledky nějakým způsobem transformovány tak, aby výstup měl pevnou délku klíče. Zvažme tento proces podrobněji.

Představme si notaci: $A=(A_{0},A_{1},A_{2},A_{3},A_{4})=L^{(}K,M_{1})$

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

Dále vytvoříme dva 160bitové bloky a . Tyto bloky jsou vyplněny různými kombinacemi s výstupem funkcí L a R. Konkrétně: $C=(C_{0},C_{1},C_{2},C_{3},C_{4})$ $D=(D_{0},D_{1},D_{2},D_{3},D_{4})$

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

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

$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))$ .

Nezapomeňte, že všechna sčítání a odčítání se provádějí modulo . $2^{32}$

Když je zpráva větší než 512 bitů, budou přijaté bloky C a D vloženy místo klíče pro další blok zprávy. Toto pokračuje, dokud neprojdeme celou zprávu.

Obvykle může být celý proces vytváření kódu pravosti reprezentován jako:

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

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

poté se proces opakuje, jen s tím rozdílem, že klíč je výsledkem předchozího výpočtu.

$(A,B)->(C,D)$

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

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

V poslední iteraci vyměníme vstupní data za R a L. To se provádí pro zvýšení síly autentizačního kódu. Poslední jsou Two-track-MAC. $HL(n)$ $HR(n)$

Pseudokód

Níže je pseudokód algoritmu.

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 { IF (i!=n-1) FOR j:= 0 TO 79 { ; } else FOR j:= 0 AŽ 79 { } IF (i != n-1) { } } ;

A_{0}:=C_{0};A_{1}:=C_{1};A_{2}:=C_{2};A_{3}:=C_{3};A_{4 }:=C_{4};

B_{0}:=D_{0};B_{1}:=D_{1};B_{2}:=D_{2};B_{3}:=D_{3};B_{4 }:=D_{4};

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}

A_{0}:=A_{4};A_{4}:=A_{3};A_{3}:=role_{10}(A_{2});A_{2}:=A_{ 1};A_{1}:=T;

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};

B_{0}:=B_{4};B_{4}:=B_{3};B_{3}:=rol_{10}(B_{2});B_{2}:=B_{ 1};B_{1}:=T;

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}

A_{0}:=A_{4};A_{4}:=A_{3};A_{3}:=role_{10}(A_{2});A_{2}:=A_{ 1};A_{1}:=T;

T:=rol_{s^{'}(j)}(B_{0}\oplus 79-j,B_{1},B_{2},B_{3})\oplus M_{i}[ r^{'}(j)]\oplus c^{'}(j))

B_{0}:=B_{4};B_{4}:=B_{3};B_{3}:=rol_{10}(B_{2});B_{2}:=B_{ 1};B_{1}:=T;

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}

A_{4}:=A_{4}\ominus C_{4}

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}

B_{4}:=B_{4}\ominus D_{4};

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))

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))

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};

E_{4}:=A_{4}\ominus B_{4}

Vysvětlení a možné implementace

Vysvětluje zápis používaný v pseudokódu TTMAC a diskutuje proveditelnost jeho implementace.

$f(j,x,y,z)$ je nelineární funkce, která pracuje s bity. Pro různé j provádí různé operace na x, y, z. A to:

$f(j; x; y; z) = x \otimes y \otimes z ~~~~~~~~~~~~~ (0 \le j \le 15)$
$f(j; x; y; z) = (x \klín y) \lor (\neg x \klín z)~~~ (16 \le j \le 31)$
$f(j; x; y; z) = (x \nebo \neg y) \otimes z ~~~~~~~~~~ (32 \le j \le 47 )$
$f(j; x; y; z) = (x \land z) \lor (y \land \neg z)~~~~ (48 \le j \le 63)$
$f(j; x; y; z) = x \otimes (y \nebo \neg z)~~~~~~~~~ (64 \le j \le 79)$

Například v C je vhodné reprezentovat tyto funkce jako makra [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))

Symboly označují konstanty, jejichž hodnoty jsou určeny rozsahem j: $c(j),c^{'}(j)$

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

Funkce r(j) a r' dávají jeden z 16 možných bloků, do kterých je původní zpráva rozdělena. Protože bloky mají velikost 512 bitů, r(j) může nabývat hodnot od 0 do 15. Kde r(j) = 0 (r'(j) = 0) znamená bity 0…15 a r(j) = 15 (r'(j) = 15) jsou bity 495…511.

r(j) = j pro $(0\le j\le 15)$
r(16..31) = 7; čtyři; 13; jeden; deset; 6; patnáct; 3; 12; 0; 9; 5; 2; čtrnáct; jedenáct; osm
r(32..47) = 3; deset; čtrnáct; čtyři; 9; patnáct; osm; jeden; 2; 7; 0; 6; 13; jedenáct; 5; 12
r(48..63) = 1; 9; jedenáct; deset; 0; osm; 12; čtyři; 13; 3; 7; patnáct; čtrnáct; 5; 6; 2
r(64..79) = 4; 0; 5; 9; 7; 12; 2; deset; čtrnáct; jeden; 3; osm; jedenáct; 6; patnáct; 13
r'(0..15) = 5; čtrnáct; 7; 0; 9; 2; jedenáct; čtyři; 13; 6; patnáct; osm; jeden; deset; 3; 12
r'(16..31) = 6; jedenáct; 3; 7; 0; 13; 5; deset; čtrnáct; patnáct; osm; 12; čtyři; 9; jeden; 2
r'(32..47) = 15; 5; jeden; 3; 7; čtrnáct; 6; 9; jedenáct; osm; 12; 2; deset; 0; čtyři; 13
r'(48..63) = 8; 6; čtyři; jeden; 3; jedenáct; patnáct; 0; 5; 12; 2; 13; 9; 7; deset; čtrnáct
r'(64..79) = 12; patnáct; deset; čtyři; jeden; 5; osm; 7; 6; 2; 13; čtrnáct; 0; 3; 9; jedenáct

Příklad: Nechť zpráva je:

M = "Softwarově optimalizované univerzální hashování a ověřování zpráv."

Přiřaďme každému znaku specifický kód:

"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

V binární reprezentaci bude text zprávy obsahovat 512 nul a jedniček. Poté je rozdělen do 16 bloků po 32 bitech:

M_{0}=

= (01010011 01101111 01100110 01110100) = (01110111 01100001 01110010 01100101) = (00101101 01101111 01110000 01110100) = (01101001 01101101 01101001 01111010) = (01100101 01100100 00100000 01110101) = (01101110 01101001 01110110 01100101) = (01110010 01110011 01100001 01101100) = (00100000 01101000 01100001 01110011) = (01101000 01101001 01101110 01100111) = (00100000 01100001 01101110 01100100) = (00100000 01101101 01100101 01110011) = (01110011 01100001 01100111 01100101) = (00100000 01100001 01110101 01110100) = (01101000 01100101 01101110 01110100) = ( 01101001 01100011 01100001 01110100) = (01101001 01101111 01101110 00101110)

M_{1}=

M_{2}=

M_{3}=

M_{4}=

M_{5}=

M_{6}=

M_{7}=

M_{8}=

M_{9}=

M_{10}=

M_{11}=

M_{12}=

M_{13}=

M_{14}=

M_{15}=

V důsledku toho funkce vrátí: (00100000 01101000 01100001 01110011). A dá třetí bit, tedy 1. $M(r(16))$ $M_{2}(r(16))$

s(j) a - uveďte číslo bitu pro operaci rotace bitu rol. $s^{'}(j)$

s(0..15) = 11; čtrnáct; patnáct; 12; 5; osm; 7; 9; jedenáct; 13; čtrnáct; patnáct; 6; 7; 9; osm
s(16..31) = 7; 6; osm; 13; jedenáct; 9; 7; patnáct; 7; 12; patnáct; 9; jedenáct; 7; 13; 12
s(32..47) = 11; 13; 6; 7; čtrnáct; 9; 13; patnáct; čtrnáct; osm; 13; 6; 5; 12; 7; 5
s(48..63) = 11; 12; čtrnáct; patnáct; čtrnáct; patnáct; 9; osm; 9; čtrnáct; 5; 6; osm; 6; 5; 12
s(64..79) = 9; patnáct; 5; jedenáct; 6; osm; 13; 12; 5; 12; 13; čtrnáct; jedenáct; osm; 5; 6
s'(0..15) = 8; 9; 9; jedenáct; 13; patnáct; patnáct; 5; 7; 7; osm; jedenáct; čtrnáct; čtrnáct; 12; 6
s'(16..31) = 9; 13; patnáct; 7; 12; osm; 9; jedenáct; 7; 7; 12; 7; 6; patnáct; 13; jedenáct
s'(32..47) = 9; 7; patnáct; jedenáct; osm; 6; 6; čtrnáct; 12; 13; 5; čtrnáct; 13; 13; 7; 5
s'(48..63) = 15; 5; osm; jedenáct; čtrnáct; čtrnáct; 6; čtrnáct; 6; 9; 12; 9; 12; 5; patnáct; osm
s'(64..79) = 8; 5; 12; 9; 12; 5; čtrnáct; 6; osm; 13; 6; 5; patnáct; 13; jedenáct; jedenáct

Ve skutečnosti jsou všechny výše popsané výrazy vypůjčeny z hashovacího algoritmu RIPEMD-160 . Proto je RIPEMD-160 základem pro Two-Track-MAC.

Implementace algoritmu TTMAC byla zahrnuta do kryptografické knihovny Crypto++ [2] .

Příklady

Ukažme si příklad, jak algoritmus funguje pro různá vstupní data. Prvním parametrem je 160bitový klíč. Druhým parametrem je zpráva k odeslání. Na výstupu získáme 160bitový ověřovací kód.

TTMAC(K,M) = TTMAC(0000000000000000000000000000000000000,"") = 46724343BDDF4A150009046D4CBF16F2A6378073 TTMAC(K,M) = TTMAC(000000000000000000000000000000000000,"Hello World") = 5C8350FEEA6922C4E79F262A72603AA7F99C381D TTMAC(K,M) = TTMAC(0000000000000000000000000000000000001,"1") = 8B91136B35096C30C58FA17D7ADE882DBC1CC482

Problémy s používáním

Výsledný autentizační kód umožňuje ověřit, že data nebyla žádným způsobem změněna od doby, kdy byla vytvořena, přenesena nebo uložena důvěryhodným zdrojem. Existují různé systémy, které provádějí tento druh ověřování.

Například dvě strany, které si navzájem důvěřují, se předem dohodly na použití tajného klíče, který znají pouze oni. Tím je zaručena autentičnost zdroje a sdělení. Nevýhoda tohoto přístupu je zřejmá. Jsou potřeba dvě strany, které si důvěřují.

Je také možné sdílet ověřovací kód zprávy ve spojení s funkcí symetrického šifrování podle jednoho ze schémat: $E_{k_{1}}(M,TTMAC_{k_{2}}(M))$

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

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

Tento přístup znamená rozdíl v klíčích a , stejně jako rozdíl v algoritmech pro šifrování a výpočet MAC. V opačném případě existuje možnost dalších korelací, které lze použít k odmítnutí klíčů. ${\displaystyle k_{2))$ ${\displaystyle k_{1))$

TTMAC lze použít zejména pro „autentizaci transakce“. To znamená, že zpráva je potvrzena jedinečností a včasným přenosem. Tento typ autentizace poskytuje možnost ochrany proti opětovnému použití dříve přenesených zpráv, což je nezbytné v případech, kdy hrozba může vést k nežádoucím následkům.

Zabezpečení

Úspěšnost útoků na Two-Track-MAC závisí na složitosti klíče k, který by měl být dlouhý 160 bitů, délce výstupního kódu m, který může být 32,64,.. a 160 bitů, a délce l vnitřní stav, který je 320 bitů.

První možností je vyjmenovat všechny možné klíče. Pokud je možné klíč vyzvednout, pak má útočník možnost zfalšovat jakoukoli zprávu. Pro klíč délky k a výstupní kód délky m takový útok vyžaduje pokusy a známé páry (text, MAC) k testování. Protože velikost vnitřního stavu TTMAC je 360 bitů, je pravděpodobnost výpočtu hodnoty kódu pravosti snížena na , ve srovnání s RIPEMD-160. $2^{k}$ ${\frac {k}{m))$ $2^{160}$ $2^{80}$

Hledání tzv. [Collision|collisions] vyžaduje znalost dvojic (text,MAC), kde l je délka vnitřního stavu. Tento výsledek skutečně vyplývá z paradoxu „narozenin“. Pro detekci vnitřních kolizí pomocí externího vyšetřování kolizí je vyžadováno pořadí text-MAC. Riziko lze navíc snížit snížením životnosti klíče. $2^{\frac {l}{2))$ ${\displaystyle 2^{lm))$

Výsledky jsou uvedeny v tabulce:

Typy útoků	Pokusy	Možný úspěch	slavné páry
Hledání klíče	$2^{160}$	${\frac {160}{m))$
hádání MAC		${\displaystyle {\frac {1}{2^{m))))$
Útok na základě narozeninového paradoxu			$2^{160}$

Výpočetní účinnost

Počet operací pro TTMAC je pouze o několik procent větší než počet operací požadovaných pro výpočet RIPEMD-160. Porovnejme vysoce optimalizovaný kód RIPEMD-160 a TTMAC. První vyžaduje 1013 cyklů na blok a pro stejný stupeň optimalizace bude TTMAC potřebovat asi 1044 cyklů na blok. Toho je dosaženo prostřednictvím počátečního návrhu algoritmu pro rychlý provoz na výpočetních zařízeních.

Viz také

Poznámky

↑ implementace makra . - zdrojový kód. Archivováno z originálu 1. července 2012.
↑ Struktura implementace algoritmu TTMCA (anglicky) ? . — Crypto++ TTMAC. Archivováno z originálu 1. července 2012. (neurčitý)

Literatura

A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cheremushkin Fundamentals of Cryptography: A Studijní průvodce. 3. vyd. - M .: Helios APB, 2005 - 480c., Ill.
Stinson, DR (Douglas Robert), 1956 - Kryptografie: teorie a praxe / DR Stinson. p. cm. — (Diskrétní matematika a její aplikace) Zahrnuje bibliografické odkazy a rejstřík. ISBN 0-8493-8521-0 .