Două piste-MAC

Two-Track-MAC este un cod de autentificare a mesajelor conceput pentru a verifica autenticitatea și integritatea datelor transmise. Cu alte cuvinte, ne putem asigura că datele au fost transferate din sursa corectă și că conținutul acestora nu s-a schimbat în timpul transferului.

Scopul principal : Preveniți modificarea mesajelor de către o terță parte în timpul transmiterii. Exemple de mesaje sunt plățile bancare electronice sau sistemele automate de control pentru obiectele în mișcare.

Dezvoltatori : Bart van Rompay , Bert den Boer .

Istoricul creației

Algoritmul Two-Track-MAC a fost ales în proiectul NESSIE (New European Electronic Signature Algorithms) în noiembrie 2000 și a fost conceput ca un analog mai rapid și mai fiabil al algoritmilor MAC disponibili la acea vreme. Bart van Rompay de la Universitatea din Leuven (Katholieke Universiteit Leuven) - Belgia și Bert den Boer de la debis AG (Germania) au participat la dezvoltare .

Descriere

Two-Track-MAC se bazează pe funcția hash RIPEMD-160 . Particularitatea constă în criptarea mesajului de-a lungul a două căi independente (indicate ca L și R în figură ). Această abordare vă permite să măriți dimensiunea stării interne. Ca rezultat, obținem mai multe valori posibile ale funcției de criptare internă. Acest lucru face posibilă complicarea atacurilor pe baza enumerarii tuturor valorilor posibile.

În comparație cu MDx-MAC, care se bazează și pe RIPEMD-160, Two-Track-MAC este mult mai eficient pentru mesajele scurte (512 sau 1024 biți) și, de asemenea, mai eficient pentru mesajele lungi.

Un alt avantaj important al TTMAC este capacitatea de a schimba rapid cheia de criptare. Acest lucru vă permite să creșteți stabilitatea sistemului, fără a reduce viteza. Cu o schimbare destul de frecventă a cheii, un atacator nu va putea colecta un număr mare de perechi mesaj-cod MAC, ceea ce reduce foarte mult probabilitatea de a ghici cheia sau codul MAC.

Cum funcționează

După cum sa menționat deja, Two-Track-MAC are două blocuri de transformare paralele L(K,M) și R(K,M) , care acceptă mesajul M și tasta K ca intrare . Ca rezultat, fiecare dintre blocuri funcționează independent unul de celălalt și creează două reprezentări diferite ( A și B în figură) ale acelorași date.

Să presupunem mai întâi că dimensiunea mesajului M este de 512 biți. Mărimea cheii K este întotdeauna fixă și este de 160 de biți. Pentru a complica transformările , L(K,M) scoate cinci cuvinte de 32 de biți ( ) ${\displaystyle A_{0},A_{1},A_{2},A_{3},A_{4))$ . Adică, împarte în mod oficial versiunea încă preliminară a cheii în 5 părți de aceeași dimensiune. În mod similar, mulțimea ( ) ${\displaystyle B_{0},B_{1},B_{2},B_{3},B_{4))$ dă rezultatul funcției R(K,M) . Apoi aceste cuvinte se scad modulo . Acesta este un fel de amestecare a două valori pentru a aduce de la o lungime fixă de 160 de biți. Rezultatul final: ) , unde . De fapt, pentru asta s-a făcut totul. E este codul de autentificare a mesajului M . $2^{{32}}$ $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$

Dacă mesajul depășește 512 biți, atunci M este împărțit în blocuri , unde are o lungime de 512 biți. Ca urmare a procesului, efectuăm aceleași operații pe fiecare bloc, amestecându-le pe rând. Un mesaj cu lungimea nu multiplu de 512 este umplut cu zerouri și unu la dimensiunea de care avem nevoie. ${\displaystyle M=M_{1}M_{2}M_{3}...M_{n))$ $M_{i}$

Mai multe despre amestecarea rezultatelor L și R

După ce fiecare ramură a algoritmului procesează următorul bloc al mesajului, rezultatele trebuie să fie cumva transformate, astfel încât rezultatul să fie o lungime fixă a cheii. Să luăm în considerare acest proces mai detaliat.

Să introducem notația: $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})$

Apoi, creăm două blocuri de 160 de biți și . Aceste blocuri sunt umplute cu diferite combinații cu ieșirea funcțiilor L și R. Și anume: $C=(C_{0},C_{1},C_{2},C_{3},C_{4})$ $D=(D_{0},D_{1},D_{2},D_{3},D_{4})$

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

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

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

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

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

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

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

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

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

Nu uitați că toate adunările și scăderile se fac modulo . $2^{32}$

Când mesajul este mai mare de 512 biți, blocurile C și D primite vor fi introduse în locul tastei pentru următorul bloc de mesaj. Aceasta continuă până când vom parcurge întregul mesaj.

În mod convențional, întregul proces de creare a unui cod de autenticitate poate fi reprezentat astfel:

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

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

apoi procesul se repetă, cu singura diferență că cheia este rezultatul calculului anterior.

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

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

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

În ultima iterație, schimbăm datele de intrare pentru R și L. Acest lucru se face pentru a crește puterea codului de autentificare. Cele finale sunt Two-track-MAC. $HL(n)$ $HR(n)$

Pseudocod

Mai jos este pseudocodul algoritmului.

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

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}

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)

Clarificări și posibile implementări

Acesta explică notația folosită în pseudocodul TTMAC și discută fezabilitatea implementării acestuia.

$f(j,x,y,z)$ este o funcție neliniară care funcționează cu biți. Pentru diferit j efectuează diferite operații pe x, y, z. Și anume:

$f(j; x; y; z) = x \otimes y \otimes z ~~~~~~~~~~~~~ (0 \le j \le 15)$
$f(j; x; y; z) = (x \wedge y) \lor (\neg x \wedge z)~~~ (16 \le j \le 31)$
$f(j; x; y; z) = (x \lor \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 \lor \neg z)~~~~~~~~~ (64 \le j \le 79)$

De exemplu, în C este convenabil să reprezentați aceste funcții ca macrocomenzi [1] :

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

Simbolurile denotă constante ale căror valori sunt determinate de intervalul 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)$

Funcțiile r(j) și r' dau unul dintre cele 16 blocuri posibile în care este împărțit mesajul original. Deoarece blocurile au o dimensiune de 512 biți, r(j) poate lua valori de la 0 la 15. Unde r(j) = 0 (r'(j) = 0) înseamnă biți 0...15 și r(j) = 15 (r'(j) = 15) sunt biții 495…511 respectiv.

r(j) = j pentru $(0\le j\le 15)$
r(16..31) = 7; patru; 13; unu; zece; 6; cincisprezece; 3; 12; 0; 9; 5; 2; paisprezece; unsprezece; opt
r(32..47) = 3; zece; paisprezece; patru; 9; cincisprezece; opt; unu; 2; 7; 0; 6; 13; unsprezece; 5; 12
r(48..63) = 1; 9; unsprezece; zece; 0; opt; 12; patru; 13; 3; 7; cincisprezece; paisprezece; 5; 6; 2
r(64..79) = 4; 0; 5; 9; 7; 12; 2; zece; paisprezece; unu; 3; opt; unsprezece; 6; cincisprezece; 13
r'(0..15) = 5; paisprezece; 7; 0; 9; 2; unsprezece; patru; 13; 6; cincisprezece; opt; unu; zece; 3; 12
r'(16..31) = 6; unsprezece; 3; 7; 0; 13; 5; zece; paisprezece; cincisprezece; opt; 12; patru; 9; unu; 2
r'(32..47) = 15; 5; unu; 3; 7; paisprezece; 6; 9; unsprezece; opt; 12; 2; zece; 0; patru; 13
r'(48..63) = 8; 6; patru; unu; 3; unsprezece; cincisprezece; 0; 5; 12; 2; 13; 9; 7; zece; paisprezece
r'(64..79) = 12; cincisprezece; zece; patru; unu; 5; opt; 7; 6; 2; 13; paisprezece; 0; 3; 9; unsprezece

Exemplu: Fiți mesajul:

M = "Hashing universal optimizat pentru software și autentificare a mesajelor."

Să atribuim un cod specific fiecărui personaj:

„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" , "pe", "." 32, 97, 117, 116, 104, 101, 110, 116, 105, 99, 97, 116, 105, 111, 110, 46

În reprezentare binară, textul mesajului va conține 512 zerouri și unu. Apoi este împărțit în 16 blocuri de 32 de biți:

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

Ca rezultat, funcția va returna: (00100000 01101000 01100001 01110011). A va da al treilea bit, adică 1. $M(r(16))$ $M_{2}(r(16))$

s(j) și - dați numărul de biți pentru operația de rotație a biților rol. $s^{'}(j)$

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

De fapt, toate expresiile descrise mai sus sunt împrumutate din algoritmul hash RIPEMD-160 . De aceea RIPEMD-160 este baza pentru Two-Track-MAC.

O implementare a algoritmului TTMAC a fost inclusă în biblioteca criptografică Crypto++ [2] .

Exemple

Să demonstrăm un exemplu despre cum funcționează algoritmul pentru diferite date de intrare. Primul parametru este o cheie de 160 de biți. Al doilea parametru este mesajul care trebuie trimis. La ieșire, obținem un cod de autentificare pe 160 de biți.

TTMAC(K,M) = TTMAC(00000000000000000000000000000000000000,"") = 46724343BDDF4A150009046D4CBF16F2A6378073 TTMAC(K,M) = TTMAC(0000000000000000000000000000000000000,„Bună lume”) = 5C8350FEEA6922C4E79F262A72603AA7F99C381D TTMAC(K,M) = TTMAC(00000000000000000000000000000000000001,"1") = 8B91136B35096C30C58FA17D7ADE882DBC1CC482

Probleme de utilizare

Codul de autentificare rezultat vă permite să verificați că datele nu au fost modificate în niciun fel de când au fost create, transmise sau stocate de o sursă de încredere. Există diverse scheme care efectuează acest tip de verificare.

De exemplu, două părți care au încredere una în cealaltă au convenit în avans să folosească o cheie secretă care este cunoscută doar de ei. Aceasta garantează autenticitatea sursei și a mesajului. Dezavantajul acestei abordări este evident. Este nevoie de două părți care să aibă încredere unul în celălalt.

De asemenea, este posibil să partajați codul de autentificare a mesajului împreună cu funcția de criptare simetrică conform uneia dintre schemele: $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)))$

Această abordare implică o diferență în chei și , precum și o diferență în algoritmii de criptare și calcul MAC. În caz contrar, există posibilitatea unor corelații suplimentare care pot fi folosite pentru a respinge cheile. $k_{2}$ $k_{1}$

În special, TTMAC poate fi utilizat pentru „autentificarea tranzacțiilor”. Aceasta înseamnă că mesajul este confirmat prin unicitate și transmitere în timp util. Acest tip de autentificare oferă capacitatea de a proteja împotriva reutilizarii mesajelor transmise anterior, ceea ce este necesar în cazurile în care o amenințare poate duce la consecințe nedorite.

Securitate

Succesul atacurilor pe Two-Track-MAC depinde de complexitatea tastei k, care ar trebui să aibă o lungime de 160 de biți, de lungimea codului de ieșire m, care poate fi de 32,64,.. și de 160 de biți și de lungimea l a starea internă, care este de 320 de biți.

Prima posibilitate este de a enumera toate cheile posibile. Dacă este posibil să ridicați cheia, atunci atacatorul are capacitatea de a falsifica orice mesaj. Pentru o cheie de lungime k și un cod de ieșire de lungime m, un astfel de atac necesită încercări și perechi cunoscute (text, MAC) pentru a testa. Deoarece dimensiunea stării interne TTMAC este de 360 de biți, probabilitatea de calculare a valorii codului de autenticitate este redusă la , în comparație cu pentru RIPEMD-160. $2^{k)$ ${\frac {k}{m)}$ $2^{160}$ $2^{80}$

Căutarea așa-numitelor [coliziune|coliziune] necesită cunoașterea perechilor (text,MAC), unde l este lungimea stării interne. Într-adevăr, acest rezultat rezultă din paradoxul „zilelor de naștere”. Pentru a detecta coliziunile interne folosind investigarea coliziunilor externe, este necesară ordinea de setare text-MAC. În plus, riscul poate fi redus prin reducerea duratei de viață a cheii. $2^{\frac {l}{2)}$ ${\displaystyle 2^{lm))$

Rezultatele sunt prezentate în tabel:

Tipuri de atac	Încercări	Posibil Succes	cupluri celebre
Găsirea unei chei	$2^{160}$	${\frac {160}{m)}$
MAC ghicit		${\frac {1}{2^{m)})$
Atacul bazat pe paradoxul zilei de naștere			$2^{160}$

Eficiență computațională

Numărul de operațiuni pentru TTMAC este doar cu câteva procente mai mare decât numărul de operațiuni necesare pentru calcularea RIPEMD-160. Să comparăm codul extrem de optimizat RIPEMD-160 și TTMAC. Primul necesită 1013 cicluri pe bloc, iar pentru același grad de optimizare TTMAC va avea nevoie de aproximativ 1044 cicluri pe bloc. Acest lucru se realizează prin proiectarea inițială a algoritmului pentru funcționare rapidă pe dispozitive de calcul.

Vezi și

Note

↑ implementare macro . - cod sursa. Arhivat din original la 1 iulie 2012.
↑ Structura implementării algoritmului TTMCA (engleză) ? . — Crypto++ TTMAC. Arhivat din original la 1 iulie 2012. (nedefinit)

Literatură

A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cheremushkin Fundamentele criptografiei: un ghid de studiu. a 3-a ed. - M .: Helios APB, 2005 - 480c., Ill.
Stinson, DR (Douglas Robert), 1956 - Criptografie: teorie și practică / DR Stinson. p. cm. — (Matematică discretă și aplicarea acesteia) Include referințe bibliografice și index. ISBN 0-8493-8521-0 .