Fuuga (hash-funktio)

Fuuga
Kehittäjät	Shai Halevi , William E. Hall , Charanjit S. Jutla
Luotu	2009
julkaistu	lokakuuta 2009
Hash-koko	224, 256, 384 tai 512 bittiä
Kierrosten lukumäärä	neljä
Tyyppi	hash-toiminto

Fuuga on tiivistysalgoritmi, jonka ovat kehittäneet Shai Halevi , William E. Hall ja Charanjit S. Jutla IBM : stä vuoden 2009 National Institute of Standards and Technology hash - kilpailua varten, jossa se pääsi toiselle kierrokselle [1] . Algoritmi ei kuitenkaan päässyt kilpailun kolmannelle kierrokselle riittämättömän kryptografisen analyysin ja kryptografisen vahvuuden epävarmuuden vuoksi. [2]

Tuloviestille, jonka pituus on 1 - 264 −1 bittiä, algoritmi luo 224-, 256-, 384- tai 512-bittisen hash-arvon, jota kutsutaan myös sanoman tiivisteeksi . Vastaavien lähtöpituuksien funktiot ovat vastaavasti nimetty Fugue-224, Fugue-256, Fugue-384 ja Fugue-512. Kirjoittajat kuvasivat myös parametrisoidun version fuuga-algoritmista. Fugue-256:n heikosti suojattu versio, joka toimii kaksi kertaa tavallista versiota nopeammin, kuvataan myös parametroidulla versiolla.

Kirjoittajat väittävät, että useimmat olemassa olevat hyökkäysstrategiat hash-funktioille perustuvat differentiaaliseen kryptausanalyysiin . Fugue on suunniteltu vähentämään haavoittuvuutta tämäntyyppisille hyökkäyksille. Heidän vakuutuksensa mukaan algoritmi on myös kilpailukykyinen tehokkuudessaan SHA-hajautustoimintojen kanssa ohjelmisto- ja sovellustermeissä ja saavuttaa suorituskyvyn jopa 36,2 sykliä tavua kohden ( CPB ) kuudennessa Intel Xeon 5150 -suorittimien perheessä ja jopa 25 sykliä per tavu. tavua ( CPB ) Intel Core 2 T7700 -prosessorilla. 45 nm Intel Core 2 T9400 Fugue-256 -sirulla se saavuttaa vain 16 sykliä tavua kohden ( CPB ) käyttämällä SSE 4.1 -ohjeita . Westmeren (32 nm) prosessoreissa, kuten Intel Core i5:ssä, Fugue-256:n nopeus on 14 sykliä tavua kohden ( CPB ).

Algoritmi

Pääidea

Fuuga perustuu Grindahlin hash-algoritmiin ja käyttää siksi AES :n S-laatikoita , mutta 4x4-permutaatiomatriisi korvataan 16x16 "Super-Mix"-operaatiolla, mikä parantaa huomattavasti lumivyöryvaikutusta . Samaan aikaan "superpermutaatio" ("Super-Mix") on vain hieman työvoimavaltaisempi toimenpide kuin AES -permutaatiostrategia .

Super-Mix

Fugue-224, Fugue-256 toimivat tilassa, joka voidaan esittää etumerkittömien tavujen 4x30 matriisilla, kun taas Fugue-384 ja Fugue-512 toimivat 4x36 tavun matriisilla. Tästä tilasta lähtien toiminnot voidaan suorittaa ilman lisätietojen valmistelua.

"Super-Mix-muunnokseksi" tunnettu algoritmi perustuu 4x4-matriisin ottamista syötteeksi ja uuden 4x4-matriisin palauttamiseen. Toimintosyöttö on yksinkertaisesti neljä ensimmäistä saraketta nykyisestä matriisista (4x30 tai 4x36) ja tuloksena oleva uusi matriisi korvaa käytetyt syöttötiedot. Joten superpermutaatio vaikuttaa vain tilamatriisin neljään ensimmäiseen sarakkeeseen.

"Super-Mix"-toiminto määritellään seuraavasti:

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

missä:

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

;

U

on 4x4 tavumatriisi (eli matriisi S- lohkokorvauksen jälkeen );

M^T

on transponoitu matriisi M.

Muunnos ottaa 4x4 matriisin ja siirtää -: nnen rivin tavulla vasemmalle, ts. $ROL$ $i$ $i$

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

Superpermutaatio on palautuva funktio.

Hash-funktio F-256

F-256-ominaisuus on Fugue-256:n ydin. F-256 ottaa 4-tavun merkkijonon ja 32-tavuisen alustusvektorin (IV256) syötteenä ja tulostaa 32 tavua haja-arvoa.

Hash-funktio F-256 tallentaa kolmenkymmenen 4-tavuisen sarakkeen tilan, alkaen alustusvektorista (IV256) saadusta alustustilasta. 4 m tavun ( m ≥ 0) syötevirta jaetaan m nelitavuiseksi sanaksi ja välitetään sana kerrallaan pyöreälle muunnosfunktiolle R , joka muuttaa sisäistä tilaa. Kaikkien ympyrämuunnosten jälkeen sisäinen tila lähetetään muunnoksen G viimeiselle kierrokselle . Yhteensä 8 tilasaraketta palautetaan funktion F-256 tuloksena.

F-256:n alustusvektori:

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

Pyöreä muunnos R

Ympyrämuunnos R ottaa syötteeksi 30 saraketta tilasta S ja yhden 4-tavuisen sanan I ja palauttaa uuden 30 sarakkeen tilan. R - muunnos koostuu seuraavista vaiheista:

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

missä:

TIX ( I ) on "reduce for XOR", "clear" (Truncate), "insert" (Insert), "exclusive or" ( XOR ), koostuu seuraavista vaiheista:

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

ROR3 on vain tilasiirtymä 3 saraketta oikealle,

CMIX on kolonnin sekoitus (Column MIX), joka koostuu seuraavista vaiheista:

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

SuperMix (tai SMIX ) on "superpermutaatio" ("Super-Mix")

G:n muunnoksen viimeinen kierros

Viimeinen muunnos G ottaa syötteeksi 30 saraketta tilassa S ja palauttaa 30 sarakkeen lopullisen tilan. Tältä se näyttää:

Toista 5 kertaa { ROR3;CMIX; SMIX ROR3;CMIX; SMIX } Toistuu 13 kertaa { S4 += S0; S15 += S0; ROR15; SMIX; S4 += S0; S16 += S0;ROR14; SMIX; } S4 += S0; S15 += S0; F-256-hajautusalgoritmin toteutus pseudokoodissa

Alla on F-256-hajautusalgoritmin toteutus pseudokoodissa, kaikki merkinnät ovat kuten yllä:

jos j = 0...21, aseta Sj = 0; jos j = 0..7, aseta S(22+j) = IVj . for i = 1..m { TIX(Pi); Toistuu 2 kertaa { ROR3;CMIX; SMIX; } } Toistaa 10 kertaa { ROR3;CMIX; SMIX; } Toistuu 13 kertaa { S4 += S0; S15 += S0; ROR15; SMIX; S4 += S0; S16 += S0;ROR14; SMIX; } S4 += S0; S15 += S0; Palautus: S1 S2 S3 S4 S15 S16 S17 S18.

Viimeisen kierroksen G jälkeen palautetaan seuraavat sarakkeet: S 1 S 2 S 3 S 4 S 15 S 16 S 17 S 18 , eli jos lopputila näyttää tältä:

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

silloin lähdön ensimmäiset 16 tavua ovat: 04 05 06 07 08 09 ... 12 13

Fuuga-224

Fugue-224-algoritmi ei käytännössä eroa Fuuga-256:sta. F-224-funktion tulos on tavut S 1…4 S 15…17 S 1…4 S 15…18 sijasta Fugu-256:ssa, ja alustusvektori (IV224) on myös erilainen:

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

Fuuga-384

Erot Fugue-384 ja Fugue-256

Fugue-384-algoritmi ei käytännössä eroa Fugue-256:sta. Tämä algoritmi ohittaa TIX- ( I )- ja CMIX- funktiot , käyttää eri alustusvektoria (IV384) ja hieman erilaista toimintojen järjestystä F-384:ssä ja palauttaa 48-tavun hajautusarvon.

F-384-hajautusalgoritmin toteutus pseudokoodissa

Seuraava on F-384-hajautusalgoritmin toteutus pseudokoodissa:

Jos j = 0...23, aseta Sj = 0; Jos j = 0...11, aseta S(24+j) = IVj . Jos i = 1..m { TIX(Pi); Toistettu 3 kertaa: { ROR3;CMIX; SMIX; } } Toistettu 18 kertaa: { ROR3;CMIX; SMIX; } Toistettu 13 kertaa: { 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; Palautus: S1..4 S12..15 S24..27.

missä:

TIX ( I ) on "reduce for XOR", "clear" (Truncate), "insert" (Insert), "exclusive or" ( XOR ), koostuu seuraavista vaiheista:

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

CMIX on kolonnin sekoitus (Column MIX), joka koostuu seuraavista vaiheista:

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

Fuuga-512

Erot Fugue-512 ja Fugue-256

Fugue-512-algoritmi, kuten Fugue-384, ei käytännössä eroa Fugue-256:sta. Tämä algoritmi myös määrittelee uudelleen TIX ( I ) ja CMIX- funktiot ja käyttää eri alustusvektoria (IV512) ja hieman erilaista toimintojen järjestystä F-512:ssa. Fugue-512 palauttaa 64 tavun hash-arvon.

F-512-hajautusalgoritmin toteutus pseudokoodissa

Seuraava on F-512-hajautusalgoritmin toteutus pseudokoodissa:

Jos j = 0...19, aseta Sj = 0; Jos j = 0...15, aseta S(20+j) = IVj . Jos i = 1..m { TIX(Pi); Toistettu 4 kertaa: { ROR3;CMIX; SMIX; } } Toistuu 32 kertaa: { ROR3;CMIX; SMIX; } Toistettu 13 kertaa: { 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; Palautus: S1..4 S9..12 S18..21 S27..30

missä:

TIX ( I ) koostuu seuraavista vaiheista:

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

CMIX (Sarake MIX) koostuu seuraavista vaiheista:

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

Fugue-256:n lajikkeet

"Pseudosatunnainen" hash-funktio PR-Fugue-256

PR-Fugue-256 hyväksyy binääridatan 0 - 2 64 −1 bittiä sekä 32-tavuisen avaimen. Tätä avainta käytetään olennaisesti alustusvektorina kiinteän IV256:n sijaan, mikä on ainoa ero Fugue-256:sta.

"Pakattu" C-Fugue-256-toiminto

C-Fugue-256 on määritelty taaksepäin yhteensopivuutta varten sovelluksille, joiden on käytettävä Merkle-Damgard- pakkausta . Kehittäjät väittävät, että tämä Fuguen käyttö ei ole optimaalinen suorituskyvyn ja turvallisuuden kannalta, mutta se mahdollistaa Fuguen käytön sitä tarvitsevissa sovelluksissa.

HMAC-Fugue-256

Fugue-256 voi korvata SHA-256:n monissa toimintatiloissa, mukaan lukien HMAC , käyttämättä taaksepäin yhteensopivaa C-Fugue-256-ominaisuutta.

Esimerkiksi HMAC-Fugue-256 ottaa tiedot X ja avaimen K syötteenä ja laskee:

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

Suorituskyky

Fugue-algoritmin riippumattomat suorituskykytestit, jotka suoritettiin käyttämällä eBASH- vertailuarvoa , osoittivat seuraavat tulokset (nopeus ilmoitetaan jaksoina tavua kohden ( cpb )) [3] :

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

Fuuga-funktiolla on osittain rinnakkainen arkkitehtuuri, jonka avulla voit luoda tehokkaita toteutuksia algoritmista. Jotkut ohjeet ovat saatavilla monille tunnetuille arkkitehtuureille ( x86 , PowerPC , ARM ).

Mitä tulee RAM -vaatimuksiin, Fugue-hajautustoiminto tarvitsee paljon muistia tallentaakseen sisäisen tilan.

Fuuga 2.0

Fugue 2.0 [4] on laajennus alkuperäiselle Fugue-hajautusalgoritmille, jonka kirjoittajat ovat valmistaneet SHA-3-kilpailun toista kierrosta varten. Se on kaksi kertaa nopeampi 256-bittiselle hashille. Suunnittelijat ovat osoittaneet paremman suojan differentiaalisia kryptausanalyysihyökkäyksiä vastaan uudessa versiossa.

Muistiinpanot

↑ SHA-3 kierroksen 2 ehdokkaat .
↑ http://csrc.nist.gov/publications/nistir/ir7764/nistir-7764.pdf Arkistoitu 15. helmikuuta 2013 Wayback Machinen tilaraportissa SHA-3 Cryptographic Hash Algorithm Competition -kilpailun toisesta kierroksesta
↑ eBASH benchmarkin virallinen sivusto .
↑ Fugue 2.0 hash-funktion virallinen dokumentaatio .

Kirjallisuus

Hash Function Fuguen virallinen verkkosivusto . Haettu: 20. joulukuuta 2013.

SHA-3-kilpailu (2007-2012 ) . Haettu: 20. joulukuuta 2013.

Hash Function Fuguen viralliset asiakirjat . Haettu: 20. joulukuuta 2013.

Hash Function Fugue 2.0 :n viralliset asiakirjat . Haettu: 20. joulukuuta 2013.

eBASH: Salaa vertailuindeksin virallinen sivusto (englanniksi) (downlink) . Käyttöpäivä: 20. joulukuuta 2013. Arkistoitu alkuperäisestä 4. joulukuuta 2013.

SHA-3 toisen kierroksen ehdokkaat . Haettu: 20. joulukuuta 2013.

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga 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 Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA