Fúga (hash függvény)

Fúga
Fejlesztők Shai Halevi , William E. Hall , Charanjit S. Jutla
Létrehozva 2009
közzétett 2009. október
Hash méret 224, 256, 384 vagy 512 bit
A körök száma négy
Típusú hash függvény

A fúga egy kivonatoló  algoritmus , amelyet Shai Halevi , William E. Hall és Charanjit S. Jutla fejlesztett ki az IBM - től a 2009 -es National Institute of Standards and Technology hash versenyre , ahol bejutott a második fordulóba [1] . Az algoritmus azonban nem jutott be a verseny harmadik fordulójába az elégtelen kriptográfiai elemzés és a kriptográfiai erősség bizonytalansága miatt. [2]

Az 1–264–1 bites bemeneti üzenetek esetében az algoritmus 224, 256, 384 vagy 512 bites hash értéket generál, amelyet üzenetkivonatnak is neveznek . A megfelelő kimeneti hosszokhoz tartozó függvények neve Fugue-224, Fugue-256, Fugue-384 és Fugue-512. A szerzők leírták a fúga algoritmus paraméterezett változatát is. A Fugue-256 gyengén védett változatát, amely kétszer olyan gyorsan fut, mint a standard változat, szintén paraméterezett változatban írják le.

A szerzők azt állítják, hogy a legtöbb létező támadási stratégia a hash függvényekre differenciális kriptográfiai elemzésen alapul . A Fugue-t úgy tervezték, hogy csökkentse az ilyen típusú támadásokkal szembeni sebezhetőséget. Biztosítékuk szerint az algoritmus hatékonysága versenyképes az SHA hash funkcióival szoftveres és alkalmazási szempontból, és akár 36,2 ciklus per bájt ( CPB ) teljesítményt is elérhet az Intel Xeon 5150 processzorok hatodik családján és akár 25 ciklusonként. bájtot ( CPB ) az Intel Core 2 T7700 processzoron. A 45 nm-es Intel Core 2 T9400 Fugue-256 chipen mindössze 16 ciklust ér el bájtonként ( CPB ) az SSE 4.1 utasításokat használva . A Westmere (32 nm) processzorokon, mint például az Intel Core i5, a Fugue-256 számítása 14 ciklus bájtonként ( CPB ) történik.

Algoritmus

Fő ötlet

A Fugue a Grindahl hash algoritmuson alapul , ezért az AES S-boxokat használja , de a 4x4-es permutációs mátrixot egy 16x16-os "Super-Mix" művelet váltja fel, nagymértékben javítva a lavinahatást . Ugyanakkor a "szuperpermutáció" ("Super-Mix") csak valamivel munkaigényesebb művelet, mint az AES permutációs stratégia .

Super-Mix

A Fugue-224, Fugue-256 állapoton működik, amelyet egy 4x30-as előjel nélküli bájtok mátrixa ábrázolhat, míg a Fugue-384 és Fugue-512 egy 4x36 bájtos mátrixon működik. Ebből az állapotból további adat-előkészítés nélkül is elvégezhetők a műveletek.

A "Super-Mix transzformációként" ismert algoritmus egy 4x4-es mátrix bemenetén alapul, és egy új 4x4-es mátrix visszaadásán alapul. A függvény bemenete egyszerűen az aktuális mátrix első négy oszlopa (4x30 vagy 4x36), és a kapott új mátrix helyettesíti a felhasznált bemeneti adatokat. Tehát a szuperpermutáció csak az állapotmátrix első 4 oszlopát érinti.

A "Super-Mix" funkció meghatározása a következő:

ahol:

;  egy 4x4-es bájtos mátrix (azaz egy S-blokk helyettesítés utáni mátrix);  az M transzponált mátrix.

A transzformáció egy 4x4-es mátrixot vesz fel, és a -edik sort egy bájttal balra tolja el, azaz.

A szuperpermutáció egy reverzibilis függvény.

Hash függvény F-256

Az F-256 funkció a Fugue-256 szíve. Az F-256 bemenetként egy 4 bájtos karakterláncot és egy 32 bájtos inicializációs vektort (IV256) vesz, és 32 bájt hashed értéket ad ki.

Az F-256 hash függvény harminc 4 bájtos oszlop állapotát tárolja, az inicializálási vektorból (IV256) kapott inicializálási állapotból kiindulva. A 4 m bájtos ( m ≥ 0) bemeneti adatfolyamot m négybájtos szóra osztjuk, és egy-egy szót adunk át az R kerek transzformációs függvénynek , amely megváltoztatja a belső állapotot. Minden körtranszformáció után a belső állapot a G transzformáció utolsó fordulójába kerül . Összesen 8 állapotoszlop kerül visszaadásra az F-256 függvény eredményeként.

Az F-256 inicializálási vektora:

Kerek transzformáció R

Az R körkörös transzformáció 30 S állapotú oszlopot és egy 4 bájtos I szót vesz be bemenetként, és egy 30 oszlopból álló új állapotot ad vissza. Az R transzformáció a következő lépésekből áll:

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

ahol:

A TIX ( I ) jelentése "kicsinyítés XOR-hoz", "törlés" (Csonkítás), "beszúrás" (Beszúrás), "kizárólagos vagy" ( XOR ), a következő lépésekből áll:

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

A ROR3  csak egy állapoteltolás 3 oszloppal jobbra,

A CMIX oszlopkeverés  (Column MIX), a következő lépésekből áll:

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

A SuperMix (vagy SMIX ) egy "szuperpermutáció" ("Super-Mix")

G átalakulásának utolsó fordulója

A G transzformáció utolsó köre 30 S állapotú oszlopot vesz fel bemenetként , és 30 oszlopból álló végső állapotot ad vissza. Így néz ki:

Ismételje meg 5-ször { ROR3;CMIX; SMIX ROR3;CMIX; SMIX } 13-szor ismétlődik { S4 += S0; S15 += S0;ROR15; SMIX; S4 += S0; S16 += S0;ROR14; SMIX; } S4 += S0; S15 += S0; Az F-256 hash algoritmus megvalósítása pszeudokódban

Az alábbiakban az F-256 hash algoritmus pszeudokódban való megvalósítása látható, minden jelölés a fenti:

ha j = 0...21, akkor Sj = 0; j = 0..7 esetén állítsa be S(22+j) = IVj . mert i = 1..m { TIX(Pi); 2-szer ismétlődik { ROR3;CMIX; SMIX; } } 10-szer ismétlődik { ROR3;CMIX; SMIX; } 13-szor ismétlődik { S4 += S0; S15 += S0;ROR15; SMIX; S4 += S0; S16 += S0;ROR14; SMIX; } S4 += S0; S15 += S0; Visszaküldés: S1 S2 S3 S4 S15 S16 S17 S18.

Az utolsó G kör után a következő oszlopok jelennek meg: S 1 S 2 S 3 S 4 S 15 S 16 S 17 S 18 , vagyis ha a végső állapot így néz ki:

,

akkor a kimenet első 16 bájtja a következő lesz: 04 05 06 07 08 09 ... 12 13

Fúga-224

A Fugue-224 algoritmus gyakorlatilag nem különbözik a Fugue-256-tól. Az F-224 függvény eredménye S 1…4 S 15…17 bájtok a Fugue-256-ban S 1 …4 S 15 … 18 helyett , és az inicializálási vektor (IV224) is eltérő:

Fúga-384

A Fuga-384 és a Fuga-256 közötti különbségek

A Fugue-384 algoritmus gyakorlatilag nem különbözik a Fugue-256-tól. Ez az algoritmus felülírja a TIX ( I ) és CMIX függvényeket , más inicializálási vektort (IV384) és kissé eltérő műveleti sorrendet használ az F-384-ben, és 48 bájtos hash értéket ad vissza.

Az F-384 hash algoritmus megvalósítása pszeudokódban

Az alábbiakban az F-384 hash algoritmus pszeudokódban való megvalósítása látható:

j = 0...23 esetén állítsa be Sj = 0 értékét; Ha j = 0...11, állítsa be az S(24+j) = IVj értéket. Mert i = 1..m { TIX(Pi); 3-szor ismételve: { ROR3;CMIX; SMIX; } } 18-szor ismételve: { ROR3;CMIX; SMIX; } 13-szor ismételve: { S4+ = S0; S12+ = S0; S24+ = S0; ROR12; SMIX; S4+ = S0; S13+ = S0; S24+ = S0; ROR12; SMIX; S4+ = S0; S13+ = S0; S25+ = S0; ROR11; SMIX; } S4+ = S0; S12+ = S0; S24+ = S0; Visszatér: S1..4 S12..15 S24..27.

ahol:

A TIX ( I ) jelentése "kicsinyítés XOR-hoz", "törlés" (Csonkítás), "beszúrás" (Beszúrás), "kizárólagos vagy" ( XOR ), a következő lépésekből áll:

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

A CMIX oszlopkeverés  (Column MIX), a következő lépésekből áll:

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

Fúga-512

A Fugue-512 és a Fugue-256 különbségei

A Fugue-512 algoritmus a Fugue-384-hez hasonlóan gyakorlatilag nem különbözik a Fugue-256-tól. Ez az algoritmus újradefiniálja a TIX ( I ) és CMIX függvényeket is, és más inicializálási vektort (IV512) és kissé eltérő műveleti sorrendet használ az F-512-ben. A Fugue-512 64 bájtos hash értéket ad vissza.

Az F-512 hash algoritmus megvalósítása pszeudokódban

Az alábbiakban az F-512 hash algoritmus pszeudokódban való megvalósítása látható:

Ha j = 0...19, állítsa be Sj = 0 értékét; Ha j = 0...15, állítsa be az S(20+j) = IVj értéket. Mert i = 1..m { TIX(Pi); 4-szer ismételve: { ROR3;CMIX; SMIX; } } 32-szer ismétlődik: { ROR3;CMIX; SMIX; } 13-szor ismételve: { S4+ = S0; S9+=SO; S18+ = S0; S27+ = S0; ROR9; SMIX; S4+ = S0; S10+ = S0; S18+ = S0; S27+ = S0; ROR9; SMIX; S4+ = S0; S10+ = S0; S19+ = S0; S27+ = S0; ROR9; SMIX; S4+ = S0; S10+ = S0; S19+ = S0; S28+ = S0; ROR8; SMIX; } S4+ = S0; S9+ = S0; S18+ = S0; S27+ = S0; Visszaküldés: S1..4 S9..12 S18..21 S27..30

ahol:

A TIX ( I ) a következő lépésekből áll:

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

A CMIX (MIX oszlop) a következő lépésekből áll:

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

A fúga-256 fajtái

"Álvéletlen" hash függvény PR-Fugue-256

A PR-Fugue-256 0 és 2 64 -1 bit közötti bináris adatokat fogad be bemenetként, valamint egy 32 bájtos kulcsot. Ezt a kulcsot alapvetően inicializálási vektorként használják a rögzített IV256 helyett, ami az egyetlen különbség a Fugue-256-tól.

"Tömörített" C-Fugue-256 funkció

A C-Fugue-256 visszamenőleges kompatibilitásra szolgál azoknál az alkalmazásoknál, amelyeknek Merkle-Damgard tömörítést kell használniuk . A fejlesztők azt állítják, hogy a Fugue használata nem optimális teljesítmény és biztonság szempontjából, de lehetővé teszi a Fugue használatát olyan alkalmazásokban, ahol szükség van rá.

HMAC-Fugue-256

A Fugue-256 számos üzemmódban helyettesítheti az SHA-256-ot, beleértve a HMAC -t is , anélkül, hogy a visszafelé kompatibilis C-Fugue-256 funkciót használná.

Például a HMAC-Fugue-256 bemenetként veszi az X adatot és a K kulcsot , és kiszámítja:

Teljesítmény

A Fugue algoritmus független teljesítménytesztjei, amelyeket az eBASH benchmark segítségével végeztek , a következő eredményeket mutatták (a sebességet ciklusok bájtonként ( cpb ) adják meg) [3] :

processzor Core i5 2. mag (45 nm) 2. mag (65 nm)
Fúga 2.0 12,81 cbp 15,31 cbp 15,35 cbp
fúga-256 16,75 cbp 18,42 cbp 21,41 cbp
fúga-512 46,20 cbp 56,91 cbp 56,82 cbp

A fúga függvény részben párhuzamos architektúrával rendelkezik, amely lehetővé teszi az algoritmus hatékony implementációinak létrehozását. Néhány utasítás elérhető számos jól ismert architektúrán ( x86 , PowerPC , ARM ).

Ami a RAM -igényt illeti, a Fugue hash funkciónak sok memóriára van szüksége a belső állapot tárolására.

Fúga 2.0

A Fugue 2.0 [4]  az eredeti Fugue hash algoritmus kiterjesztése, amelyet a szerzők az SHA-3 verseny második fordulójára készítettek , és amely kétszer olyan gyors, mint egy 256 bites hash. A tervezők az új verzióban a differenciális kriptográfiai támadások elleni jobb védelmet bizonyították .

Jegyzetek

  1. ↑ SHA-3 2. forduló jelöltjei .
  2. ↑ http://csrc.nist.gov/publications/nistir/ir7764/nistir-7764.pdf Archiválva : 2013. február 15. a Wayback Machine Status Report az SHA-3 Cryptographic Hash Algorithm Competition második fordulójáról
  3. ↑ Az eBASH benchmark hivatalos webhelye .
  4. ↑ Fugue 2.0 hash függvény hivatalos dokumentációja .

Irodalom

 Hash függvények
Általános rendeltetésű
Kriptográfia
Kulcsgenerálási funkciók
Csekkszám ( összehasonlítás )
Hashes