Fuga (hashovací funkce)

Fuga
Vývojáři	Shai Halevi , William E. Hall , Charanjit S. Jutla
Vytvořeno	2009
zveřejněno	října 2009
Velikost hash	224, 256, 384 nebo 512 bitů
Počet kol	čtyři
Typ	hashovací funkce

Fugue je hashovací algoritmus, který vyvinuli Shai Halevi , William E. Hall a Charanjit S. Jutla z IBM pro hashovací soutěž National Institute of Standards and Technology v roce 2009 , kde postoupil do druhého kola [1] . Algoritmus se však do třetího kola soutěže nedostal kvůli nedostatečné kryptografické analýze a nejistotě ohledně kryptografické síly. [2]

Pro vstupní zprávu o délce 1 až 264 −1 bitů algoritmus generuje 224, 256, 384 nebo 512 bitovou hash hodnotu, také nazývanou souhrn zprávy . Funkce pro příslušné výstupní délky jsou pojmenovány Fugue-224, Fugue-256, Fugue-384 a Fugue-512. Autoři také popsali parametrizovanou verzi algoritmu Fugue. Slabě chráněná verze Fugue-256, která běží dvakrát rychleji než standardní verze, je také popsána jako parametrizovaná verze.

Autoři uvádějí, že většina existujících strategií útoku na hashovací funkce je založena na diferenciální kryptoanalýze . Fugue byla navržena tak, aby snížila zranitelnost vůči těmto typům útoků. Podle jejich ujištění je algoritmus konkurenceschopný v efektivitě s hašovacími funkcemi SHA z hlediska softwaru a aplikací a dosahuje výkonu až 36,2 cyklů na bajt ( CPB ) u šesté rodiny procesorů Intel Xeon 5150 a až 25 cyklů na bajt. byte ( CPB ) na procesoru Intel Core 2 T7700. Na 45nm čipu Intel Core 2 T9400 Fugue-256 dosahuje pouze 16 cyklů na bajt ( CPB ) pomocí instrukcí SSE 4.1 . Na procesorech Westmere (32nm), jako je Intel Core i5, se Fugue-256 počítá se 14 cykly na bajt ( CPB ).

Algoritmus

Hlavní myšlenka

Fugue je založena na Grindahlově hash algoritmu, a proto používá S-boxy od AES , ale permutační matice 4x4 je nahrazena operací 16x16 "Super-Mix", což výrazně zlepšuje lavinový efekt . Zároveň je „super-permutace“ („Super-Mix“) operace jen o něco málo náročnější na práci než strategie permutace AES .

Super-Mix

Fugue-224, Fugue-256 pracují na stavu, který může být reprezentován maticí 4x30 bajtů bez znaménka, zatímco Fugue-384 a Fugue-512 pracují na matici 4x36 bajtů. Z tohoto stavu lze provádět operace bez další přípravy dat.

Algoritmus, známý jako "Super-Mix transformace", je založen na převzetí matice 4x4 jako vstupu a vrácení nové matice 4x4. Vstupem funkce jsou jednoduše první čtyři sloupce z aktuální matice (4x30 nebo 4x36) a výsledná nová matice je nahrazena použitými vstupními daty. Super permutace tedy ovlivňuje pouze první 4 sloupce matice stavu.

Funkce "Super-Mix" je definována takto:

$\text{SuperMix}(U) = \text{ROL} \left( M \cdot U + \begin{pmatrix} \sum_{j \ne 0} U_j^i & 0 & 0 & 0\\ 0 & \sum_ {j \ne 1} U_j^i & 0 & 0\\ 0 & 0 & \sum_{j \ne 2} U_j^i & 0\\ 0 & 0 & 0 & \sum_{j \ne 3} U_j^ i \end{pmatrix} \cdot M^T \right)$

kde:

M = \begin{pmatrix} 1 & 4 & 7 & 1\\ 1 & 1 & 4 & 7\\ 7 & 1 & 1 & 4\\ 4 & 7 & 1 & 1 \end{pmatrix}

;

U

je matice 4x4 bytů (tj. matice po substituci S-bloku );

M^T

je transponovaná matice M.

Transformace vezme matici 4x4 a posune -tý řádek doleva o bajt, tzn. $ROL$ $i$ $i$

\text{ROL}(W)_j^i = W_{ji \pmod 4}^{i}

Super-permutace je reverzibilní funkce.

Hashovací funkce F-256

Funkce F-256 je srdcem Fugue-256. F-256 přijímá 4bajtový řetězec a 32bajtový inicializační vektor (IV256) jako vstup a vydává 32 bajtů hašované hodnoty.

Hashovací funkce F-256 ukládá stav třiceti 4bajtových sloupců, počínaje inicializačním stavem získaným z inicializačního vektoru (IV256). Vstupní tok o velikosti 4 m bajtů ( m ≥ 0) je rozdělen na m čtyřbajtových slov a předává se po jednom slově do kruhové transformační funkce R , která mění vnitřní stav. Po všech kruhových transformacích je vnitřní stav odeslán do závěrečného kola transformace G . Celkem je vráceno 8 stavových sloupců jako výsledek funkce F-256.

Inicializační vektor pro F-256:

$\text{IV256} = \begin{pmatrix} e9 & 66 & e0 & d2 & f9 & fb & 91 & 34\\ 52 & 71 & d4 & b0 & 6c & f9 & 49 & f8\\ bd & 13 & f6 & b5 & 62 & 29 & e8 & c2\\ de & 5f & 68 & 94 & 1d & de & 99 & 48 \end{pmatrix}$

Kulatá transformace R

Kruhová transformace R přijímá 30 sloupců stavu S a jedno 4bajtové slovo I jako vstup a vrací nový stav 30 sloupců. Transformace R se skládá z následujících kroků:

TIX ( I ); ROR3 ; CMIX ; SuperMix ; ROR3 ; CMIX ; SuperMix ;

kde:

TIX ( I ) je „snížit pro XOR“, „vymazat“ (zkrátit), „vložit“ (vložit), „exkluzivně nebo“ ( XOR ), skládá se z následujících kroků:

S10 + = SO; SO = I; S8 + = SO; S1 + = S24.

ROR3 je jen posun stavu o 3 sloupce doprava,

CMIX je kolonové míchání (Column MIX), sestává z následujících kroků:

SO+= S4; SI + = S5; S2+= S6; S15+= S4; S16+= S5; S17+= S6;

SuperMix (nebo SMIX ) je "super-permutace" ("Super-Mix")

Závěrečné kolo transformace G

Poslední kolo transformace G vezme 30 sloupců stavu S jako vstup a vrátí konečný stav 30 sloupců. Vypadá to takto:

Opakujte 5x { ROR3;CMIX; SMIX ROR3;CMIX; SMIX } Opakuje se 13krát { S4+= SO; S15+= SO;ROR15; SMIX; S4+= SO; S16+= SO;ROR14; SMIX; } S4+= SO; S15 + = SO; Implementace hashovacího algoritmu F-256 v pseudokódu

Níže je implementace hashovacího algoritmu F-256 v pseudokódu, všechny zápisy jsou jako výše:

pro j = 0..21 nastavte Sj = 0; pro j = 0..7 nastavte S(22+j) = IVj. pro i = 1..m { TIX(Pi); Opakuje se 2x { ROR3;CMIX; SMIX; } } Opakuje se 10krát { ROR3;CMIX; SMIX; } Opakuje se 13krát { S4+= SO; S15+= SO;ROR15; SMIX; S4+= SO; S16+= SO;ROR14; SMIX; } S4+= SO; S15 + = SO; Vrací: S1 S2 S3 S4 S15 S16 S17 S18.

Po závěrečném kole G jsou vráceny tyto sloupce: S 1 S 2 S 3 S 4 S 15 S 16 S 17 S 18 , tedy pokud výsledný stav vypadá takto:

$\begin{pmatrix} 00 & 04 & 08 & 0c & 10\\ 01 & 05 & 09 & 0d & 11\\ 02 & 06 & 0a & 0e & 12 & ...\\ 03 & 07 & 0b & 0f & 13 \end{pmatrix}$ ,

pak prvních 16 bajtů výstupu bude: 04 05 06 07 08 09 ... 12 13

Fuga-224

Algoritmus Fugue-224 se prakticky neliší od Fugue-256. Výsledkem funkce F-224 jsou bajty S 1…4 S 15…17 místo S 1…4 S 15…18 ve Fugue-256 a inicializační vektor (IV224) je také odlišný:

$\text{IV224} = \begin{pmatrix} f4 & 62 & ee & e0 & a1 & 9a & bd\\ c9 & 86 & 39 & 74 & 12 & 43 & 8d\\ 12 & f7 & e0 & e3 & 7c & d2 & 67\\ 0d & 57 & 1c & cb & 62 & 15 & 9a \end{pmatrix}$

Fuga-384

Rozdíly Fugue-384 od Fugue-256

Algoritmus Fugue-384 se prakticky neliší od Fugue-256. Tento algoritmus potlačuje funkce TIX ( I ) a CMIX , používá jiný inicializační vektor (IV384) a mírně odlišné pořadí operací v F-384 a vrací 48bajtovou hodnotu hash.

Implementace hashovacího algoritmu F-384 v pseudokódu

Následuje implementace hashovacího algoritmu F-384 v pseudokódu:

Pro j = 0..23 nastavte Sj = 0; Pro j = 0..11 nastavte S(24+j) = IVj. Pro i = 1..m { TIX(Pi); Opakováno 3x: { ROR3;CMIX; SMIX; } } Opakováno 18krát: { ROR3;CMIX; SMIX; } Opakováno 13krát: { S4+ = SO; S12+ = SO; S24+ = SO; ROR12; SMIX; S4+ = SO; S13+ = SO; S24+ = SO; ROR12; SMIX; S4+ = SO; S13+ = SO; S25+ = SO; ROR11; SMIX; } S4+ = SO; S12+ = SO; S24+ = SO; Vrátí: S1..4 S12..15 S24..27.

kde:

TIX ( I ) je „snížit pro XOR“, „vymazat“ (zkrátit), „vložit“ (vložit), „exkluzivně nebo“ ( XOR ), skládá se z následujících kroků:

S16+= SO; SO = I; S8 + = SO; SI+= S27; S4+= S30;

CMIX je kolonové míchání (Column MIX), sestává z následujících kroků:

SO+= S4; SI + = S5; S2+= S6; S18+= S4; S19+= S5; S20+= S6;

Fuga-512

Rozdíly Fugue-512 od Fugue-256

Algoritmus Fugue-512, stejně jako Fugue-384, se prakticky neliší od Fugue-256. Tento algoritmus také nově definuje funkce TIX ( I ) a CMIX a používá jiný inicializační vektor (IV512) a mírně odlišné pořadí operací v F-512. Fugue-512 vrací hash hodnotu 64 bajtů.

Implementace hashovacího algoritmu F-512 v pseudokódu

Následuje implementace hashovacího algoritmu F-512 v pseudokódu:

Pro j = 0..19 nastavte Sj = 0; Pro j = 0..15 nastavte S(20+j) = IVj. Pro i = 1..m { TIX(Pi); Opakováno 4x: { ROR3;CMIX; SMIX; } } Opakuje se 32krát: { ROR3;CMIX; SMIX; } Opakováno 13krát: { S4+ = SO; S9+ = SO; S18+ = SO; S27+ = SO; ROR9; SMIX; S4+ = SO; S10+ = SO; S18+ = SO; S27+ = SO; ROR9; SMIX; S4+ = SO; S10+ = SO; S19+ = SO; S27+ = SO; ROR9; SMIX; S4+ = SO; S10+ = SO; S19+ = SO; S28+ = SO; ROR8; SMIX; } S4+ = SO; S9+ = SO; S18+ = SO; S27+ = SO; Vrácení: S1..4 S9..12 S18..21 S27..30

kde:

TIX ( I ) se skládá z následujících kroků:

S22+= SO; SO = I; S8 + = SO; SI+= S24; S4+= S27; S7+=S30;

CMIX (Column MIX) se skládá z následujících kroků:

SO+= S4; SI + = S5; S2+= S6; S18+= S4; S19+= S5; S20+= S6;

Odrůdy Fugy-256

"Pseudonáhodná" hashovací funkce PR-Fugue-256

PR-Fugue-256 přijímá binární data od 0 do 2 64 −1 bitů jako vstup, stejně jako 32bajtový klíč. Tento klíč se v podstatě používá jako inicializační vektor namísto pevného IV256, což je jediný rozdíl od Fugue-256.

"Komprimovaná" funkce C-Fugue-256

C-Fugue-256 je definován pro zpětnou kompatibilitu pro aplikace, které musí používat kompresi Merkle-Damgard . Vývojáři tvrdí, že toto použití Fugue není optimální z hlediska výkonu a bezpečnosti, ale umožňuje Fugue používat v aplikacích, které to potřebují.

HMAC-Fugue-256

Fugue-256 může nahradit SHA-256 v mnoha režimech provozu, včetně HMAC , bez použití zpětně kompatibilní funkce C-Fugue-256.

Například HMAC-Fugue-256 bere data X a klíč K jako vstup a vypočítává:

$\text{HMAC-Fugue-256}(K, X) = \text{Fuga-256}(K \oplus \text{opad } | \text{ Fuga-256}(K \oplus \text{ipad } | \ text{ } X))$

Výkon

Nezávislé výkonnostní testy algoritmu Fugue, provedené pomocí benchmarku eBASH , ukázaly následující výsledky (rychlost je uvedena v cyklech na byte ( cpb )) [3] :

procesor	Core i5	Jádro 2 (45nm)	Core 2 (65nm)
Fuga 2.0	12,81 cbp	15,31 cbp	15,35 cbp
Fuga-256	16,75 cbp	18,42 cbp	21,41 cbp
Fuga-512	46,20 cbp	56,91 cbp	56,82 cbp

Funkce Fugue má částečně paralelní architekturu, která umožňuje vytvářet efektivní implementace algoritmu. Některé instrukce jsou dostupné na mnoha známých architekturách ( x86 , PowerPC , ARM ).

Pokud jde o požadavky na RAM , hashovací funkce Fugue potřebuje hodně paměti pro uložení vnitřního stavu.

Fuga 2.0

Fugue 2.0 [4] je rozšířením původního hashovacího algoritmu Fugue, který autoři připravili pro druhé kolo soutěže SHA-3 , který je dvakrát rychlejší pro 256bitový hash. Návrháři v nové verzi prokázali zlepšenou ochranu proti útokům diferenciální kryptoanalýzy .

Poznámky

↑ Kandidáti 2. kola SHA-3 .
↑ http://csrc.nist.gov/publications/nistir/ir7764/nistir-7764.pdf Archivováno 15. února 2013 ve zprávě o stavu stroje Wayback o druhém kole soutěže kryptografických hashových algoritmů SHA-3
↑ Oficiální stránky benchmarku eBASH .
↑ Oficiální dokumentace hashovací funkce Fugue 2.0 .

Literatura

Oficiální web hash Function Fugue . Staženo: 20. prosince 2013.

Soutěž SHA-3 (2007-2012 ) . Staženo: 20. prosince 2013.

Oficiální dokumenty Hash Function Fugue . Staženo: 20. prosince 2013.

Oficiální dokumenty Hash Function Fugue 2.0 . Staženo: 20. prosince 2013.

eBASH: Oficiální stránka šifrování benchmarku (anglicky) (downlink) . Datum přístupu: 20. prosince 2013. Archivováno z originálu 4. prosince 2013.

Kandidáti druhého kola SHA-3 . Staženo: 20. prosince 2013.

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA