Fuga (funcția hash)

Fugue este un  algoritm de hashing dezvoltat de Shai Halevi , William E. Hall și Charanjit S. Jutla de la IBM pentru competiția de hash a Institutului Național de Standarde și Tehnologie din 2009 , unde a ajuns în runda a doua [1] . Cu toate acestea, algoritmul nu a ajuns în a treia rundă a competiției din cauza analizei criptografice insuficiente și a incertitudinii cu privire la puterea criptografică. [2]

Pentru un mesaj de intrare cu lungimea de la 1 la 264 −1 biți, algoritmul generează o valoare hash de 224, 256, 384 sau 512 biți, numită și rezumat de mesaje . Funcțiile pentru lungimile de ieșire respective sunt denumite Fugue-224, Fugue-256, Fugue-384 și, respectiv, Fugue-512. Autorii au descris, de asemenea, o versiune parametrizată a algoritmului Fugue. O versiune slab protejată a lui Fugue-256, care rulează de două ori mai repede decât versiunea standard, este, de asemenea, descrisă în termeni de versiune parametrizată.

Autorii afirmă că majoritatea strategiilor de atac existente pentru funcțiile hash se bazează pe criptoanaliza diferențială . Fugue a fost concepută astfel încât să reducă vulnerabilitatea la aceste tipuri de atacuri. De asemenea, conform asigurărilor acestora, algoritmul este competitiv în eficiență cu funcțiile hash SHA în termeni de software și aplicație, atingând performanțe de până la 36,2 cicluri pe octet ( CPB ) pe cea de-a șasea familie de procesoare Intel Xeon 5150 și până la 25 de cicluri pe octet. octet ( CPB ) pe procesorul Intel Core 2 T7700. Pe cipul Intel Core 2 T9400 Fugue-256 de 45 nm, acesta realizează doar 16 cicluri pe octet ( CPB ) folosind instrucțiuni SSE 4.1 . Pe procesoarele Westmere (32nm), cum ar fi Intel Core i5, Fugue-256 este calculat la 14 cicluri pe octet ( CPB ).

Algoritm

Ideea principală

Fugue se bazează pe algoritmul hash Grindahl și, prin urmare, utilizează S-box-uri din AES , dar matricea de permutare 4x4 este înlocuită cu o operațiune „Super-Mix” de 16x16, îmbunătățind foarte mult efectul de avalanșă . În același timp, „super-permutarea” („Super-Mix”) este doar o operație puțin mai intensă de muncă decât strategia de permutare AES .

Super-Mix

Fugue-224, Fugue-256 operează pe stare, care poate fi reprezentată printr-o matrice 4x30 de octeți nesemnați, în timp ce Fugue-384 și Fugue-512 operează pe o matrice de 4x36 octeți. Din această stare, operațiunile pot fi efectuate fără pregătirea suplimentară a datelor.

Cunoscută sub numele de „Transformarea Super-Mix”, algoritmul se bazează pe luarea unei matrice 4x4 ca intrare și returnarea unei noi matrice 4x4. Intrarea funcției este pur și simplu primele patru coloane din matricea curentă (4x30 sau 4x36), iar noua matrice rezultată este înlocuită cu datele de intrare utilizate. Deci super-permutarea afectează doar primele 4 coloane ale matricei de stare.

Funcția „Super-Mix” este definită după cum urmează:

Unde:

Transformarea ia o matrice 4x4 și deplasează rândul --lea rămas cu un octet, adică.

Super-permutarea este o funcție reversibilă.

Funcția hash F-256

Caracteristica F-256 se află în centrul Fugue-256. F-256 preia un șir de 4 octeți și un vector de inițializare de 32 de octeți (IV256) ca intrare și scoate 32 de octeți de valoare hashed.

Funcția hash F-256 stochează starea a treizeci de coloane de 4 octeți, pornind de la starea de inițializare obținută din vectorul de inițializare (IV256). Fluxul de intrare de 4 m octeți ( m ≥ 0) este împărțit în m cuvinte de patru octeți și este transmis câte un cuvânt la funcția de transformare rotundă R , care schimbă starea internă. După toate transformările circulare, starea internă este trimisă în runda finală a transformării G . În total, 8 coloane de stare sunt returnate ca rezultat al funcției F-256.

Vector de inițializare pentru F-256: