Fugue (hash-funktion)

Fuge
Udviklere	Shai Halevi , William E. Hall , Charanjit S. Jutla
Oprettet	2009
offentliggjort	oktober 2009
Hash størrelse	224, 256, 384 eller 512 bit
Antal runder	fire
Type	hash funktion

Fugue er en hashing- algoritme udviklet af Shai Halevi , William E. Hall og Charanjit S. Jutla fra IBM til 2009 National Institute of Standards and Technology hashkonkurrencen , hvor den nåede til anden runde [1] . Algoritmen nåede dog ikke videre til tredje runde af konkurrencen på grund af utilstrækkelig kryptografisk analyse og usikkerhed om kryptografisk styrke. [2]

For en inputmeddelelse med længden 1 til 264 −1 bit genererer algoritmen en hashværdi på 224, 256, 384 eller 512 bit, også kaldet en beskedsammendrag . Funktionerne for de respektive udgangslængder hedder henholdsvis Fugue-224, Fugue-256, Fugue-384 og Fugue-512. Forfatterne beskrev også en parameteriseret version af Fugue-algoritmen. En svagt beskyttet version af Fugue-256, der kører dobbelt så hurtigt som standardversionen, er også beskrevet i form af en parameteriseret version.

Forfatterne udtaler, at de fleste eksisterende angrebsstrategier for hash-funktioner er baseret på differentiel kryptoanalyse . Fugue blev designet på en sådan måde at reducere sårbarheden over for disse typer angreb. Også ifølge deres forsikringer er algoritmen konkurrencedygtig i effektivitet med SHA-hash-funktioner i software- og applikationsbetingelser, og når ydeevne op til 36,2 cyklusser pr. byte ( CPB ) på den sjette familie af Intel Xeon 5150-processorer og op til 25 cyklusser pr. byte ( CPB ) på processoren Intel Core 2 T7700. På 45nm Intel Core 2 T9400 Fugue-256-chippen opnår den kun 16 cyklusser pr. byte ( CPB ) ved hjælp af SSE 4.1 -instruktioner . På Westmere (32nm) processorer, såsom Intel Core i5, er Fugue-256 beregnet til 14 cyklusser pr. byte ( CPB ).

Algoritme

Hovedidé

Fugue er baseret på Grindahl hash-algoritmen og bruger derfor S-bokse fra AES , men 4x4 permutationsmatricen er erstattet af en 16x16 "Super-Mix" operation, hvilket i høj grad forbedrer lavineeffekten . Samtidig er "super-permutation" ("Super-Mix") kun en lidt mere arbejdskrævende operation end AES -permutationsstrategien .

Super-Mix

Fugue-224, Fugue-256 fungerer på tilstand, som kan repræsenteres af en 4x30 matrix af usignerede bytes, mens Fugue-384 og Fugue-512 opererer på en 4x36 byte matrix. Fra denne tilstand kan operationer udføres uden yderligere dataforberedelse.

Kendt som "Super-Mix transformationen", er algoritmen baseret på at tage en 4x4 matrix som input og returnere en ny 4x4 matrix. Funktionsinputtet er simpelthen de første fire kolonner fra den aktuelle matrix (4x30 eller 4x36), og den resulterende nye matrix erstattes af de anvendte inputdata. Så superpermutationen påvirker kun de første 4 kolonner i tilstandsmatrixen.

Funktionen "Super-Mix" er defineret som følger:

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

hvor:

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

;

U

er en 4x4 matrix af bytes (det vil sige en matrix efter S-blok substitution);

M^T

er den transponerede matrix M.

Transformationen tager en 4x4 matrix og flytter den -te række til venstre af en byte, dvs. $ROL$ $jeg$ $jeg$

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

Super-permutationen er en reversibel funktion.

Hash-funktion F-256

F-256-funktionen er kernen i Fugue-256. F-256 tager en 4-byte streng og en 32-byte initialiseringsvektor (IV256) som input og udsender 32 bytes hashed værdi.

Hash-funktion F-256 gemmer tilstanden af tredive 4-byte kolonner, startende fra initialiseringstilstanden opnået fra initialiseringsvektoren (IV256). Indgangsstrømmen på 4m bytes ( m ≥ 0) opdeles i m fire-byte ord og sendes et ord ad gangen til den runde transformationsfunktion R , som ændrer den interne tilstand. Efter alle cirkulære transformationer sendes den interne tilstand til den sidste runde af transformation G . I alt returneres 8 statuskolonner som resultat af funktion F-256.

Initialiseringsvektor for 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}$

Rund transformation R

Cirkulær transformation R tager 30 kolonner af tilstand S og et 4-byte ord I som input og returnerer en ny tilstand på 30 kolonner. R -transformationen består af følgende trin:

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

hvor:

TIX ( I ) er "reducer for XOR", "clear" (Truncate), "insert" (Insert), "exclusive or" ( XOR ), består af følgende trin:

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

ROR3 er kun et tilstandsskift 3 kolonner til højre,

CMIX er kolonneblanding (Column MIX), består af følgende trin:

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

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

Sidste runde af G's transformation

Den sidste runde af transformation G tager 30 kolonner af tilstand S som input og returnerer en endelig tilstand på 30 kolonner. Sådan ser det ud:

Gentag 5 gange { ROR3;CMIX; SMIX ROR3;CMIX; SMIX } Gentages 13 gange { S4+= SO; S15 += SO; ROR15; SMIX; S4+= SO; S16 += SO; ROR14; SMIX; } S4+= SO; S15+= SO; Implementering af F-256 hash-algoritmen i pseudokode

Nedenfor er en implementering af F-256 hash-algoritmen i pseudokode, alle notationer er som ovenfor:

for j = 0..21, sæt Sj = 0; for j = 0..7, sæt S(22+j) = IVj. for i = 1..m { TIX(Pi); Gentages 2 gange { ROR3;CMIX; SMIX; } } Gentages 10 gange { ROR3;CMIX; SMIX; } Gentages 13 gange { S4+= SO; S15 += SO; ROR15; SMIX; S4+= SO; S16 += SO; ROR14; SMIX; } S4+= SO; S15+= SO; Returnering: S1 S2 S3 S4 S15 S16 S17 S18.

Efter sidste runde G returneres følgende kolonner: S 1 S 2 S 3 S 4 S 15 S 16 S 17 S 18 , altså hvis sluttilstanden ser sådan ud:

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

så vil de første 16 bytes af outputtet være: 04 05 06 07 08 09 ... 12 13

Fugue-224

Fugue-224-algoritmen er praktisk talt ikke forskellig fra Fugue-256. Resultatet af F-224-funktionen er bytes S 1…4 S 15…17 i stedet for S 1…4 S 15…18 i Fugue-256, og initialiseringsvektoren (IV224) er også anderledes:

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

Forskelle Fugue-384 fra Fugue-256

Fugue-384-algoritmen er praktisk talt ikke forskellig fra Fugue-256. Denne algoritme tilsidesætter funktionerne TIX ( I ) og CMIX , bruger en anden initialiseringsvektor (IV384) og en lidt anderledes rækkefølge af operationer i F-384 og returnerer en 48-byte hashværdi.

Implementering af F-384 hash-algoritmen i pseudokode

Følgende er en implementering af F-384 hash-algoritmen i pseudokode:

For j = 0..23, sæt Sj = 0; For j = 0..11, sæt S(24+j) = IVj. For i = 1..m { TIX(Pi); Gentaget 3 gange: { ROR3;CMIX; SMIX; } } Gentaget 18 gange: { ROR3;CMIX; SMIX; } Gentaget 13 gange: { 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; Returnering: S1..4 S12..15 S24..27.

hvor:

TIX ( I ) er "reducer for XOR", "clear" (Truncate), "insert" (Insert), "exclusive or" ( XOR ), består af følgende trin:

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

CMIX er kolonneblanding (Column MIX), består af følgende trin:

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

Fugue-512

Forskelle Fugue-512 fra Fugue-256

Fugue-512-algoritmen er ligesom Fugue-384 praktisk talt ikke forskellig fra Fugue-256. Denne algoritme omdefinerer også TIX ( I )- og CMIX- funktionerne og bruger en anden initialiseringsvektor (IV512) og en lidt anden rækkefølge af operationer i F-512. Fugue-512 returnerer en hashværdi på 64 bytes.

Implementering af F-512 hash-algoritmen i pseudokode

Følgende er en implementering af F-512 hash-algoritmen i pseudokode:

For j = 0..19, sæt Sj = 0; For j = 0..15, sæt S(20+j) = IVj. For i = 1..m { TIX(Pi); Gentaget 4 gange: { ROR3;CMIX; SMIX; } } Gentages 32 gange: { ROR3;CMIX; SMIX; } Gentaget 13 gange: { 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; Returnering: S1..4 S9..12 S18..21 S27..30

hvor:

TIX ( I ) består af følgende trin:

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

CMIX (Column MIX) består af følgende trin:

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

Varieties of Fugue-256

"Pseudo-tilfældig" hash-funktion PR-Fugue-256

PR-Fugue-256 accepterer binære data fra 0 til 2 64 −1 bits som input, såvel som en 32-byte nøgle. Denne nøgle bruges i det væsentlige som en initialiseringsvektor i stedet for en fast IV256, hvilket er den eneste forskel fra Fugue-256.

"Komprimeret" C-Fugue-256 funktion

C-Fugue-256 er defineret til bagudkompatibilitet for applikationer, der skal bruge Merkle-Damgard- komprimering . Udviklerne hævder, at denne brug af Fugue ikke er optimal med hensyn til ydeevne og sikkerhed, men den gør det muligt for Fugue at blive brugt i applikationer, der har brug for det.

HMAC-Fugue-256

Fugue-256 kan erstatte SHA-256 i mange driftstilstande, inklusive HMAC , uden at bruge den bagudkompatible C-Fugue-256-funktion.

For eksempel tager HMAC-Fugue-256 data X og nøgle K som input og beregner:

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

Ydeevne

Uafhængige præstationstest af Fugue-algoritmen, udført ved hjælp af eBASH- benchmark , viste følgende resultater (hastighed er angivet i cyklusser pr. byte ( cpb )) [3] :

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

Fugue-funktionen har en delvis parallel arkitektur, som giver dig mulighed for at skabe effektive implementeringer af algoritmen. Nogle instruktioner er tilgængelige på mange velkendte arkitekturer ( x86 , PowerPC , ARM ).

Med hensyn til RAM - krav, har Fugue hash-funktionen brug for meget hukommelse til at gemme intern tilstand.

Fugue 2.0

Fugue 2.0 [4] er en udvidelse af den originale Fugue hash-algoritme, udarbejdet af forfatterne til anden runde af SHA-3-konkurrencen , som er dobbelt så hurtig for en 256-bit hash. Designerne har bevist forbedret beskyttelse mod differentielle kryptoanalyseangreb i den nye version.

Noter

↑ SHA-3-runde 2-kandidater .
↑ http://csrc.nist.gov/publications/nistir/ir7764/nistir-7764.pdf Arkiveret 15. februar 2013 på Wayback Machine Status Report på anden runde af SHA-3 Cryptographic Hash Algorithm Competition
↑ eBASH benchmark officielle hjemmeside .
↑ Fugue 2.0 hashfunktion officiel dokumentation .

Litteratur

Hash Function Fugue officielle hjemmeside . Hentet: 20. december 2013.

SHA-3 konkurrence (2007-2012 ) . Hentet: 20. december 2013.

Hash Function Fugue officielle dokumenter . Hentet: 20. december 2013.

The Hash Function Fugue 2.0 officielle dokumenter . Hentet: 20. december 2013.

eBASH: Krypter benchmark officielt websted (engelsk) (downlink) . Dato for adgang: 20. december 2013. Arkiveret fra originalen 4. december 2013.

SHA-3 anden runde kandidater . Hentet: 20. december 2013.

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge 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 Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE