CubeHash

CubeHash [1]  je parametrizovatelná rodina kryptografických hašovacích funkcí CubeHash r/b . CubeHash8/1 byl navržen Danielem Bernsteinem jako nový standard pro SHA-3 v hashovací soutěži National Institute of Standards and Technology (NIST) . Zpočátku NIST vyžadoval asi 200 cyklů na bajt [2] . Po určitých upřesněních od NIST autor změnil parametry na CubeHash16/32, který je asi 16krát rychlejší než CubeHash8/1 a snadno dohání SHA-256 a SHA-512 na různých platformách [3] [4] [5] [6] .

CubeHash se probojoval do druhého kola soutěže, ale mezi pět nejlepších finalistů se nedostal [7] [8] .

Popis algoritmu

Práce CubeHash r/bh je založena na třech parametrech: r , b a h .

Algoritmus má 5 hlavních kroků:

Inicializace. Na 128bajtový stav je nahlíženo jako na sekvenci 32 čtyřbajtových slov x 00000 , x 00001 , x 00010 ,…, x 11111 , z nichž každé je reprezentováno ve formě little-endian jako 32bitová celá čísla. První tři slova x 00000 , x 00001 , x 00010 jsou nastavena na h /8, b , r . Zbývající slova jsou nula. Poté se stav transformuje prostřednictvím 10 r stejných kol.

Plnicí. K příchozí zprávě se přidá 1 bit, poté se doplní minimálním možným počtem nulových bitů tak, aby počet bitů byl násobkem 8 b .

Padding nevyžaduje oddělení úložiště délky zprávy, bloku zpracování a zbytku. Implementace může uložit jediné číslo mezi 0 a 8b pro záznam počtu bitů dosud zpracovaných v aktuálním bloku.

Dokončení. 1 je přidán modulo dva k poslednímu stavu slova x 11111. Dále se stav transformuje držením 10 r stejných kol.

Každé kolo obsahuje 10 kroků:

Vlastnosti algoritmu

Algoritmus CubeHash nezahrnuje bloky čítačů, bloky používající náhodná čísla a podobné bloky. Bez těchto bloků je snazší najít stav, kde došlo ke kolizi , ale tento argument nefunguje, když je velikost stavu poměrně velká. Typický útok na CubeHash by zabral 2^400 pokusů najít 1024bitovou stavovou kolizi pro CubeHash. Také není potřeba narušovat jakoukoliv symetrii, která se používá v kolech .

Inicializační stav CubeHash není symetrický, pokud parametr b není příliš velký, pak útočník nemá dostatečný výpočetní výkon na výpočet symetrického stavu nebo dvojice stavů.

Hlavní operace používané v CubeHash jsou:

Tyto operace trvají na typických procesorech konstantní čas. Většina implementací zabrání únikům z různých softwarových vrstev. U většiny softwarových implementací využívajících AES je například možné uniknout klíče přes mezipaměť . Tato skutečnost donutila Intel přidat časovou konstantu související s AES.

Rychlost práce

Na soutěži SHA - 3 testoval NIST navržené funkce, jednou z nich byl CubeHash s parametry 16/32. Testování bylo provedeno na dvou procesorech Intel Core 2 Duo 6f6 (katana) a Intel Core 2 Duo E8400 1067a (cihla):

• 11,47 cyklů/bajt: CubeHash16/32, cihla, architektura AMD64.

• 12,60 cyklů/bajt: SHA-512, cihla, architektura AMD64.

• 12,60 cyklů/bajt: SHA-512, katana, architektura AMD64.

• 12,66 cyklů/bajt: CubeHash16/32, katana, architektura AMD64.

• 12,74 cyklů/bajt: CubeHash16/32, cihla, architektura x86.

• 14,07 cyklů/bajt: CubeHash16/32, katana, architektura x86.

• 15,43 cyklů/bajt: SHA-256, cihla, architektura x86.

• 15,53 cyklů/bajt: SHA-256, cihla, architektura amd64.

• 15,56 cyklů/bajt: SHA-256, katana, architektura AMD64.

• 17,76 cyklů/bajt: SHA-512, cihla, architektura x86.

• 20,00 cyklů/bajt: SHA-512, katana, architektura x86.

• 22,76 cyklů/bajt: SHA-256, katana, architektura x86.

CubeHash není v rychlosti horší než jeho soupeři.

Příklady hashů

Tento příklad používá CubeHash 8/1-512.

Inicializační vektor je stejný pro všechny hashe 8/1-512 a vypadá takto:

6998f35dfb0930c760948910e626160f36077cf3b58b0d0c57cf193d3341e7b8\ a334805b2089f9ef31ffc4142aef3850fe121839e940a4527d5293a27045ca12\ 9358096e81bf70349a90a44a93c33edb14c3e9844a87dbd0bc451df25212b3ac\ 6aabe51c5df0f63bddbb8ae8fad3cf0fd52582fbad2e2446094025a521a23d5c

Hašování ASCII zprávy „Ahoj“ (hex: 0x48, 0x65, 0x6c, 0x6c, 0x6f) používá 6 bloků. Prvních 5 bloků pochází (protože v tomto případě je každé písmeno jeden bajt) ze zprávy a jeden další blok k vyplnění.

Hodnota 512bitového hashe je:

7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\ 8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b

Malá změna ve zprávě (například změna jednoho bitu) vede k výrazné změně hashe (tzv. lavinový efekt ).

Vezměme si například zprávu „ahoj“, která se od „Ahoj“ liší jen o jeden bit. Hash této zprávy je:

01ee7f4eb0e0ebfdb8bf77460f64993faf13afce01b55b0d3d2a63690d25010f\ 7127109455a7c143ef12254183e762b15575e0fcc49c79a0471a970ba8a66638

Změnit nastavení

CubeHash r/bh přijímá mnoho různých parametrů používaných k určení hashe. To poskytuje flexibilitu algoritmu ve vztahu ke koncovému uživateli, který sám určuje nejlepší parametry pro použití. Níže jsou uvedeny některé příklady hashů různých zpráv pomocí různých parametrů algoritmu. Všechny zprávy jsou psány v ASCII. Tři parametry používané při generování hash jsou ve formátu r/bh .

Zpráva: "" (prázdný řetězec, řetězec nulové délky) CubeHash 16/32-512: 4a1d00bbcfcb5a9562fb981e7f7db3350fe2658639d948b9d57452c22328bb32\ f468b072208450bad5ee178271408be0b16e5633ac8a1e3cf9864cfbfc8e043a CubeHash 8/1-512: 90bc3f2948f7374065a811f1e47a208a53b1a2f3be1c0072759ed49c9c6c7f28\ f26eb30d5b0658c563077d599da23f97df0c2c0ac6cce734ffe87b2e76ff7294 CubeHash 1/1-512: 3f917707df9acd9b94244681b3812880e267d204f1fdf795d398799b584fa8f1\ f4a0b2dbd52fd1c4b6c5e020dc7a96192397dd1bce9b6d16484049f85bb71f2f CubeHash 16/32-256: 44c6de3ac6c73c391bf0906cb7482600ec06b216c7c54a2a8688a6a42676577d CubeHash 8/1-256: 38d1e8a22d7baac6fd5262d83de89cacf784a02caa866335299987722aeabc59 CubeHash 1/1-256: 80f72e07d04ddadb44a78823e0af2ea9f72ef3bf366fd773aa1fa33fc030e5cb Zpráva: "Dobrý den" CubeHash 16/32-512: dcc0503aae279a3c8c95fa1181d37c418783204e2e3048a081392fd61bace883\ a1f7c4c96b16b4060c42104f1ce45a622f1a9abaeb994beb107fed53a78f588c CubeHash 8/1-512: 7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\ 8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b CubeHash 1/1-512: 13cf99c1a71e40b135f5535bee02e151eb4897e4de410b9cb6d7179c677074eb\ 6ef1ae9a9e685ef2d2807509541f484d39559525179d53838eda95eb3f6a401d CubeHash 16/32-256: e712139e3b892f2f5fe52d0f30d78a0cb16b51b217da0e4acb103dd0856f2db0 CubeHash 8/1-256: 692638db57760867326f851bd2376533f37b640bd47a0ddc607a9456b692f70f CubeHash 1/1-256: f63041a946aa98bd47f3175e6009dcb2ccf597b2718617ba46d56f27ffe35d49

Zabezpečení

Síla tohoto algoritmu se zvyšuje jak se snižováním b na 1, tak i s rostoucím r .
Proto je CubeHash 8/1-512 stabilnější (bezpečnější) než CubeHash 1/1-512 a CubeHash 1/1-512 je stabilnější než CubeHash 1/2-512. Nejslabší možná verze tohoto algoritmu je CubeHash 1/128- h . Bezpečnost je však závislá na čase. U bezpečnější možnosti bude výpočet hodnoty hash trvat déle.

Možné útoky

Útoky využívající strukturu hashovací funkce jsou obvykle nejúspěšnější ze všech možných typů útoků. Takové útoky mohou najít kolize, předobrazy a druhé předobrazy. Charakteristickým rysem takových útoků je však to, že jsou téměř vždy navrženy pro konkrétní hashovací funkci, protože takové útoky využívají specifickou implementaci výpočtu stavu [9] .

Jednoblokový útok

Protože kolo výpočtu v CubeHash je reverzibilní, lze počáteční stav vypočítat provedením inverzních operací na konečném stavu. Jednoblokový útok je založen na této okolnosti.

Podívejme se na algoritmus tohoto útoku.

Daný hash H nějaké zprávy, b bajtů druhého předobrazu zprávy se vypočítá pomocí CubeHashr/bh .

  1. Nastavíme prvních h/8 bajtů konečného stavu pomocí hashe H a zbývajících 128-h/8 bajtů pomocí zkušební hodnoty T dostaneme stav 6. Způsob výběru zkušební hodnoty bude popsán později.
  2. Aplikováním 10r zpětných kol na stav 6 získáme stav 5. Zpětná zaokrouhlení funkce lze získat provedením kroků algoritmu v opačném pořadí, tj. nahrazením kruhových posunů doleva kruhovými posuny doprava a nahrazení sčítání odečítáním modulo 2 32 .
  3. Použijte operaci výlučnosti nebo na 1 a poslední slovo stavu 5, čímž získáte stav 4
  4. Po provedení r obrácených kol se stavem 4 dostaneme stav 3.
  5. Aplikujeme operaci výhradní nebo operaci na zprávu 0x80 a první stavový bajt 4, výsledkem je stav 3.
  6. Po provedení r obrácených kol se stavem 2 dostaneme stav 1.
  7. Pokud posledních 128 b bajtů stavu 1 neodpovídá 128 b bajtů inicializačního vektoru (stav 0), byla zpráva sondy vybrána neúspěšně.
  8. Jinak je testovací zpráva úspěšně vybrána. Druhý předobraz je vypočítán pomocí exkluzivních nebo přes prvních b bajtů stavu 1 a prvních b bajtů stavu inicializačního vektoru.

Opakováním výše uvedeného postupu s různými hodnotami T se nakonec vygeneruje druhý předobraz. Způsob výběru hodnoty T není kritický. Lze například použít posloupnost po sobě jdoucích čísel.

Za předpokladu, že se CubeHash (dopředu nebo dozadu) chová jako náhodné mapování pro libovolnou zkušební hodnotu T, pak pravděpodobnost, že posledních 128-b bytů stavu 1 se bude rovnat odpovídajícím bytům inicializačního vektoru, je 2 −8( 128-b) . Počet zpráv sondy před úspěchem je tedy 2 8(128-b) . Pokud 2 8(128-b) < 2 h , pak útok jediným blokem najde druhý předobraz za méně pokusů než hrubá síla. Jinými slovy, útok jedním blokem je účinnější než hrubá síla pro následující hodnoty h = 224 a b > 100 , pro h = 256 a b > 96 , pro h=384 a b> 80 , pro h=512 ab > 64 .

Předpokládaný počet pokusů potřebných k úspěchu však nezávisí na počtu kol r. Čas potřebný k provedení útoku se zvyšuje lineárně s r, a ne jako exponenciální funkce. Pro b = 128 bude jakákoliv hodnota T okamžitě druhým předobrazem.

Zvažte algoritmus pro zlepšení útoku na nalezení prvního předobrazu.

  1. Na základě hodnot ( h , b , r ) vypočítáme inicializační vektor (stav 0).
  2. Pro h bity a 1024-h proveďte 10r reverzní kola a XOR, abyste získali stav f .
  3. Najděte dvě n blokové sekvence, které mapují stav 0 a stav f do dvou stavů, které mají stejných posledních 1024-h bitů.

Existuje 2 nb možných vstupních n bloků a jeden z nich bude kolidovat. Počet pokusů potřebných k nalezení kolize se odhaduje jako

2 * (521 / b - 4) * 2 512 - 4b = 2 * 522 - 4b - logb

Navíc bereme v úvahu, že každé kolo vyžaduje 2 11 bitové operace, poté se vzorec změní na 2 533-4b-logb+logr bitové operace. Zrychlení tohoto útoku lze dosáhnout tím, že kolizi budeme hledat nejen po výpočtu n-tého bloku, ale i v každém jiném stavu, kterého jsme dosáhli (využijeme i mezistavy). Tím se zbavíme faktoru (512/b-4) . Potom bude počet pokusů potřebných k nalezení kolize odhadnut na 2513-4b bitové operace. Uvažujme CubeHash-512 s parametry h, b, r rovnými 512, 1, 8 v tomto pořadí. U vylepšeného algoritmu je počet pokusů potřebných k nalezení kolize 2 523 ve srovnání se standardním algoritmem útoku s 2 532 pokusy o nalezení kolize . Je-li r = 8 , vylepšený algoritmus potřebuje b>3 , aby počet pokusů byl menší než 2512 , normální algoritmus musí splňovat b>5 .

Symmetry attack

Jak bylo uvedeno výše, algoritmus CubeHash je velmi symetrický a nepoužívá žádné konstanty. Proto existuje mnoho tříd symetrie s ohledem na permutace. Nejúčinnějším útokem je použití třídy symetrie, pro kterou může rozšíření o zprávu generovat symetrické zprávy. Můžeme například použít třídu symetrie nazvanou C2. Pro tuto třídu se stav nazývá symetrický, jestliže x ijkl0 =x ijkl1 pro libovolné i, j, k, l.

Když je parametr b 32, tj. CubeHash je normální, vkládání zprávy poskytuje kontrolu nad x 00klm pro jakékoli k, l, m.

Proto, aby bylo dosaženo symetrického stavu, stačí dosáhnout stavu splňujícího následující 384bitovou rovnici

x 01kl0 = x 01kl1

x 10kl0 = x 10kl1

x 11kl0 = x 11kl1

pro jakékoli k, l.

A pak lze použít vkládání zpráv k dosažení plně symetrického stavu. Předpokládaná složitost je 2 384 .

To může být použito pro preimage útok. Algoritmus lze napsat následovně

  1. Najděte zprávu A, která je symetrická s inicializačním vektorem
  2. Najděte zprávu D, která je nepřímo symetrická s danou.
  3. Vygenerujte 2 192 symetrických zpráv B j . Poté vypočítejte stav získaný po provedení operace nebo na A a Bj
  4. Vygenerujte 2 192 symetrických zpráv С j . Poté vypočítejte stav vyplývající z provedení operace nebo z provedení Cj a D.
  5. S vysokou pravděpodobností existuje dvojice hodnot, které vyhovují

b 01kl0 =c 01kl0

b 10kl0 =c 10kl0

b 11kl0 = c 11kl0

pak ze symetrie vyplývají následující rovnosti

b 01kl1 =c 01kl1

b 10kl1 =c 10kl1

b 11kl1 =c 11kl1

které platí pro jakékoli k, l.

Potom použijeme blok X k porovnání prvních 256 bitů. Tím vznikne předobraz – provedeme operaci nebo na A, B i 0 , X, C i 0 , D.

Složitost kroků 1 a 2 je 2384 a složitost kroků 3 a 4 je 2192 . Lze jej implementovat bez velkých nákladů na paměť. Tento útok má stejnou složitost jako útok založený na síle, když B je mocninou dvou, ale stává se účinnějším, když b není mocninou dvou.

Časově nejnáročnější částí útoku založeného na symetrii je výpočet potřebný k výpočtu stavu symetrie. Ukazuje se však, že tento problém lze snadno vyřešit pomocí Groverova algoritmu na kvantovém počítači. Nalezení stavu, který splňuje výše popsanou rovnici, je ve skutečnosti ekvivalentní nalezení nulového předobrazu pro hashovací funkci, která bude iterovat přes cykly funkce CubeHash a jejíž výstup bude reprezentován

x 01000 x 01001

x 01010 x 01011

x 01100 x 01101

x 01110 x 01111

x 10 000 x 10 001

x 10010 x 10011

x 10100 x 10101

x 10110 x 10111

x 11000 x 11001

x 11010 x 11011

x 11100 x 11101

x 11110 x 11111

Pro 384bitovou funkci má Groverův algoritmus složitost 2 192 operací. Pak by útok symetrie vyžadoval 2 192 operací, za předpokladu, že jsou dostupné kvantové počítače.

Poznámky

  1. ↑ Daniel J. Bernstein. Specifikace CubeHash . Získáno 25. ledna 2013. Archivováno z originálu 14. srpna 2011.
  2. ↑ Daniel J. Bernstein. Odhady účinnosti CubeHash . Datum přístupu: 26. ledna 2013. Archivováno z originálu 14. srpna 2011.
  3. ↑ Daniel J. Bernstein. Vyladění parametru CubeHash: 16krát rychlejší . Získáno 25. ledna 2013. Archivováno z originálu 14. srpna 2011.
  4. ↑ Alan Kaminsky, Benjamin Bloom Jednoblokové útoky a statistické testy na CubeHash . Získáno 30. listopadu 2014. Archivováno z originálu 5. prosince 2014.
  5. ↑ Jean-Philippe Aumasson, Eric Brier, Willi Meier, Marıa Naya-Plasencia, Thomas Peyrin Inside the Hypercube Archivováno 4. prosince 2014.
  6. ↑ Gaëtan Leurent Quantum Preimage a kolizní útoky na CubeHash . Získáno 30. listopadu 2014. Archivováno z originálu 4. března 2016.
  7. ↑ Zpráva o stavu druhého kola soutěže o kryptografický hash algoritmus SHA-3 Archivována 14. března 2011 na Wayback Machine (PDF). Staženo 2. března 2011
  8. ↑ Komplexní srovnání výkonu hardwaru čtrnácti kandidátů SHA-3 kola 2 s 512bitovými výstupy (odkaz není k dispozici) . Staženo 11. 5. 2018. Archivováno z originálu 11. 5. 2018. 
  9. ↑ Kryptoanalýza CubeHash . Staženo 11. 5. 2018. Archivováno z originálu 11. 5. 2018.

Literatura

Odkazy

 Hashovací funkce
obecný účel
Kryptografický
Funkce generování klíčů
Kontrolní číslo ( srovnání )
Hashe