Fuga (hashfunktion)

Fuga
Utvecklare	Shai Halevi , William E. Hall , Charanjit S. Jutla
Skapad	2009
publiceras	oktober 2009
Hash storlek	224, 256, 384 eller 512 bitar
Antal omgångar	fyra
Sorts	hash-funktion

Fugue är en hashalgoritm utvecklad av Shai Halevi , William E. Hall och Charanjit S. Jutla från IBM för 2009 National Institute of Standards and Technologys hashtävling , där den tog sig till den andra omgången [1] . Algoritmen tog sig dock inte till den tredje omgången av tävlingen på grund av otillräcklig kryptografisk analys och osäkerhet om kryptografisk styrka. [2]

För ett ingångsmeddelande med längden 1 till 264 −1 bitar genererar algoritmen ett hashvärde på 224, 256, 384 eller 512 bitar, även kallat meddelandesammandrag . Funktionerna för respektive utgångslängder heter Fugue-224, Fugue-256, Fugue-384 respektive Fugue-512. Författarna beskrev också en parametriserad version av Fugue-algoritmen. En svagt skyddad version av Fugue-256, som går dubbelt så snabbt som standardversionen, beskrivs också i termer av en parametrerad version.

Författarna uppger att de flesta befintliga attackstrategier för hashfunktioner är baserade på differentiell kryptoanalys . Fugue designades på ett sådant sätt att det minskade sårbarheten för dessa typer av attacker. Enligt deras försäkringar är algoritmen dessutom konkurrenskraftig i effektivitet med SHA-hashfunktioner i mjukvaru- och applikationstermer, och når prestanda upp till 36,2 cykler per byte ( CPB ) på den sjätte familjen av Intel Xeon 5150-processorer och upp till 25 cykler per byte byte ( CPB ) på processorn Intel Core 2 T7700. På 45nm Intel Core 2 T9400 Fugue-256-chipet uppnår den bara 16 cykler per byte ( CPB ) med SSE 4.1 -instruktioner . På Westmere (32nm)-processorer, som Intel Core i5, beräknas Fugue-256 till 14 cykler per byte ( CPB ).

Algoritm

Huvudidé

Fugue är baserad på Grindahls hash-algoritm och använder därför S-boxar från AES , men 4x4 permutationsmatrisen ersätts av en 16x16 "Super-Mix" operation, vilket avsevärt förbättrar lavineffekten . Samtidigt är "super-permutation" ("Super-Mix") bara en något mer arbetsintensiv operation än AES -permutationsstrategin .

Super-Mix

Fugue-224, Fugue-256 fungerar på tillstånd, som kan representeras av en 4x30-matris av osignerade bytes, medan Fugue-384 och Fugue-512 fungerar på en 4x36-byte-matris. Från detta tillstånd kan operationer utföras utan ytterligare dataförberedelser.

Känd som "Super-Mix-transformationen" är algoritmen baserad på att ta en 4x4-matris som indata och returnera en ny 4x4-matris. Funktionsinmatningen är helt enkelt de fyra första kolumnerna från den aktuella matrisen (4x30 eller 4x36) och den resulterande nya matrisen ersätts med indata som används. Så superpermutationen påverkar bara de första 4 kolumnerna i tillståndsmatrisen.

Funktionen "Super-Mix" definieras enligt följande:

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

var:

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

;

U

är en 4x4 matris av bytes (det vill säga en matris efter S- blocksubstitution);

M^T

är den transponerade matrisen M.

Transformationen tar en 4x4-matris och flyttar den -th raden vänster av en byte, dvs. $ROL$ $i$ $i$

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

Superpermutationen är en reversibel funktion.

Hash-funktion F-256

F-256-funktionen är kärnan i Fugue-256. F-256 tar en 4-byte sträng och en 32-byte initialiseringsvektor (IV256) som inmatning och matar ut 32 byte av hashat värde.

Hashfunktion F-256 lagrar tillståndet för trettio 4-byte-kolumner, med början från initialiseringstillståndet som erhålls från initialiseringsvektorn (IV256). Ingångsströmmen på 4m byte ( m ≥ 0) delas upp i m fyra-byte ord och skickas ett ord åt gången till den runda transformationsfunktionen R , som ändrar det interna tillståndet. Efter alla cirkulära transformationer skickas det interna tillståndet till den sista omgången av transformation G . Totalt returneras 8 statuskolumner som ett resultat av funktionen F-256.

Initialiseringsvektor för 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}$

Runda transformation R

Cirkulär transformation R tar 30 kolumner av tillstånd S och ett 4-byte ord I som indata och returnerar ett nytt tillstånd med 30 kolumner. R -transformationen består av följande steg:

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

var:

TIX ( I ) är "reducera för XOR", "clear" (Truncate), "insert" (Insert), "exclusive or" ( XOR ), består av följande steg:

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

ROR3 är bara ett tillståndsskifte 3 kolumner till höger,

CMIX är kolonnblandning (Column MIX), består av följande steg:

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

SuperMix (eller SMIX ) är en "super-permutation" ("Super-Mix")

Sista omgången av G:s transformation

Den sista omgången av transformation G tar 30 kolumner av tillstånd S som indata och returnerar ett slutligt tillstånd på 30 kolumner. Så här ser det ut:

Upprepa 5 gånger { ROR3;CMIX; SMIX ROR3;CMIX; SMIX } Upprepas 13 gånger { S4 += SO; S15 += SO; ROR15; SMIX; S4 += SO; S16 += SO; ROR14; SMIX; } S4 += SO; S15 += SO; Implementering av F-256 hash-algoritmen i pseudokod

Nedan är en implementering av F-256 hash-algoritmen i pseudokod, alla notationer är enligt ovan:

för j = 0..21, sätt Sj = 0; för j = 0..7, sätt S(22+j) = IVj. för i = 1..m { TIX(Pi); Upprepas 2 gånger { ROR3;CMIX; SMIX; } } Upprepas 10 gånger { ROR3;CMIX; SMIX; } Upprepas 13 gånger { S4 += SO; S15 += SO; ROR15; SMIX; S4 += SO; S16 += SO; ROR14; SMIX; } S4 += SO; S15 += SO; Returer: S1 S2 S3 S4 S15 S16 S17 S18.

Efter sista omgången G returneras följande kolumner: S 1 S 2 S 3 S 4 S 15 S 16 S 17 S 18 , det vill säga om sluttillståndet ser ut så här:

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

då blir de första 16 byten av utdata: 04 05 06 07 08 09 ... 12 13

Fuga-224

Algoritmen Fugue-224 skiljer sig praktiskt taget inte från Fugue-256. Resultatet av F-224-funktionen är bytes S 1…4 S 15…17 istället för S 1…4 S 15…18 i Fugue-256, och initialiseringsvektorn (IV224) är också annorlunda:

$\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}$

Fugue-384

Skillnader Fugue-384 från Fugue-256

Fugue-384-algoritmen skiljer sig praktiskt taget inte från Fugue-256. Denna algoritm åsidosätter funktionerna TIX ( I ) och CMIX , använder en annan initieringsvektor (IV384) och en något annorlunda ordning av operationer i F-384, och returnerar ett hashvärde på 48 byte.

Implementering av F-384 hash-algoritmen i pseudokod

Följande är en implementering av F-384 hash-algoritmen i pseudokod:

För j = 0..23, sätt Sj = 0; För j = 0..11, sätt S(24+j) = IVj. För i = 1..m { TIX(Pi); Upprepad 3 gånger: { ROR3;CMIX; SMIX; } } Upprepad 18 gånger: { ROR3;CMIX; SMIX; } Upprepad 13 gånger: { 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; Returer: S1..4 S12..15 S24..27.

var:

TIX ( I ) är "reducera för XOR", "clear" (Truncate), "insert" (Insert), "exclusive or" ( XOR ), består av följande steg:

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

CMIX är kolonnblandning (Column MIX), består av följande steg:

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

Fugue-512

Skillnader Fugue-512 från Fugue-256

Fugue-512-algoritmen, liksom Fugue-384, skiljer sig praktiskt taget inte från Fugue-256. Denna algoritm omdefinierar också funktionerna TIX ( I ) och CMIX och använder en annan initieringsvektor (IV512) och en något annorlunda ordningsföljd i F-512. Fugue-512 returnerar ett hashvärde på 64 byte.

Implementering av F-512 hash-algoritmen i pseudokod

Följande är en implementering av F-512 hash-algoritmen i pseudokod:

För j = 0..19, sätt Sj = 0; För j = 0..15, sätt S(20+j) = IVj. För i = 1..m { TIX(Pi); Upprepad 4 gånger: { ROR3;CMIX; SMIX; } } Upprepas 32 gånger: { ROR3;CMIX; SMIX; } Upprepad 13 gånger: { 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; Returer: S1..4 S9..12 S18..21 S27..30

var:

TIX ( I ) består av följande steg:

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

CMIX (kolumn MIX) består av följande steg:

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

Varieties of Fugue-256

"Pseudo-random" hashfunktion PR-Fugue-256

PR-Fugue-256 accepterar binär data från 0 till 2 64 −1 bitar som indata, såväl som en 32-byte nyckel. Denna nyckel används i huvudsak som en initialiseringsvektor istället för en fast IV256, vilket är den enda skillnaden från Fugue-256.

"Komprimerad" C-Fugue-256 funktion

C-Fugue-256 är definierad för bakåtkompatibilitet för applikationer som måste använda Merkle-Damgard- komprimering . Utvecklarna hävdar att denna användning av Fugue inte är optimal vad gäller prestanda och säkerhet, men det gör att Fugue kan användas i applikationer som behöver det.

HMAC-Fugue-256

Fugue-256 kan ersätta SHA-256 i många driftlägen, inklusive HMAC , utan att använda den bakåtkompatibla C-Fugue-256-funktionen.

Till exempel tar HMAC-Fugue-256 data X och nyckel K som indata och beräknar:

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

Prestanda

Oberoende prestandatester av Fugue-algoritmen, utförda med eBASH benchmark , visade följande resultat (hastigheten anges i cykler per byte ( cpb )) [3] :

CPU	Core i5	Core 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

Fugue-funktionen har en delvis parallell arkitektur, vilket gör att du kan skapa effektiva implementeringar av algoritmen. Vissa instruktioner finns tillgängliga på många välkända arkitekturer ( x86 , PowerPC , ARM ).

När det gäller RAM- krav behöver Fugue-hashfunktionen mycket minne för att lagra internt tillstånd.

Fugue 2.0

Fugue 2.0 [4] är en förlängning av den ursprungliga Fugue-hashalgoritmen, förberedd av författarna för den andra omgången av SHA-3-tävlingen , som är dubbelt så snabb för en 256-bitars hash. Designerna har bevisat förbättrat skydd mot differentiella kryptoanalysattacker i den nya versionen.

Anteckningar

↑ SHA-3 omgång 2 kandidater .
↑ http://csrc.nist.gov/publications/nistir/ir7764/nistir-7764.pdf Arkiverad 15 februari 2013 på Wayback Machine Status Report på den andra omgången av SHA-3 Cryptographic Hash Algorithm Competition
↑ eBASH benchmark officiella webbplats .
↑ Fugue 2.0 hashfunktion officiell dokumentation .

Litteratur

Hash Function Fugues officiella webbplats . Hämtad: 20 december 2013.

SHA-3-tävling (2007-2012 ) . Hämtad: 20 december 2013.

Hash Function Fugue officiella dokument . Hämtad: 20 december 2013.

Hash Function Fugue 2.0 officiella dokument . Hämtad: 20 december 2013.

eBASH: Kryptera den officiella webbplatsen för benchmark (engelska) (nedlänk) . Datum för åtkomst: 20 december 2013. Arkiverad från originalet 4 december 2013.

SHA-3 andra omgångskandidater . Hämtad: 20 december 2013.

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H 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 Hud Snefru Tiger Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA