Grostl

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. června 2015; kontroly vyžadují 10 úprav .
Grostl
Vývojáři Soren Stefan Thompson, Lars Knudsen , Martin Schlaffer, Christian Rechberger, Florian Mendel, Christian Matusevich, Praaven Gauravaram
Velikost hash 224, 256, 384, 512 (proměnná, 8–512 bitů)
Počet kol 9 (doporučeno)
Typ hashovací funkce

Grøstl ( Groestl ) je iterativní kryptografická hašovací funkce . Jeden z pěti finalistů soutěže SHA-3 pořádané společností NIST . Kontrakce funkce Grøstl se skládá ze dvou pevných 2n-bitových permutací P a Q, jejichž struktura je vypůjčena ze šifry AES . Zejména se používá stejný S-box . Výsledek hashovací funkce může mít délku 8 až 512 bitů s krokem 8 bitů. Varianta, která vrací n bitů, se nazývá Grøstl-n.

Historie

Algoritmus Grøstl byl speciálně navržen pro soutěž kryptografických funkcí SHA-3 týmem kryptografů [1] z Dánské technické univerzity . Funkce se původně jmenovala Grøstl-0. Strukturální rozdíly mezi obměnami se však zvýšily, aby se kvalifikovaly do finále. Byly změněny hodnoty ShiftBytes v permutaci Q. Změnily se i zaokrouhlovací konstanty v P a Q. Aktualizovaná hashovací funkce se jmenovala Grøstl. Poté, co prokázal dobrou kryptografickou sílu , byl v řadě ukazatelů horší než ostatní účastníci finálového kola a nemohl se stát vítězem.

Původ jména

Gröstl  je rakouský pokrm . Recept je velmi blízký pokrmu zvanému „Hash“ v USA . Písmeno „ö“ v názvu funkce bylo nahrazeno písmenem „ø“ z dánské abecedy, které má stejnou výslovnost.

Funkce

Grøstl je byte-orientovaná SP síť . Svou strukturou se výrazně liší od algoritmů rodiny SHA. Mnoho komponent hashovací funkce je vypůjčeno ze šifry AES. Stejně jako AES jsou permutace vyvíjeny pomocí strategie návrhu Wide Trail , jejímž hlavním principem je, že bloková šifra má :

Velikost vnitřního stavu funkce je mnohem větší než velikost výstupních dat. Jedná se o tzv. „wide-pipe construction“.

Algoritmus

Nejprve je zpráva rozdělena do bloků , ,…, každý bit po bitu. Pro varianty funkcí vracející až 256 bitů = 512. Pro varianty vracející velké hodnoty = 1024.

Dále je vytvořena hašovací funkce pomocí metody opakovaného výpočtu. Každý blok je zpracován postupně kompresní funkcí podle vzorce , .

, ,…,  je tzv. řetězený vstup.

Počáteční hodnota = .

Po zpracování posledního bloku je hodnota -bit vložena do transformační funkce Ω , která vrací zprávu o délce , tedy ≤ .

Tedy výsledek hašovací funkce Ω

Počáteční hodnota

Počáteční hodnotě funkce Grøstl-n je přiřazena -bitová reprezentace čísla n. Tabulka ukazuje počáteční hodnoty pro různé hashovací funkce.

224 00…00 00 e0
256 00…00 01 00
384 00…00 01 80
512 00…00 02 00

funkce podložky

Pro práci se zprávami libovolné délky použijte funkci . Převede zprávu libovolné délky na zprávu s délkou, která je násobkem . K tomu se do zprávy nejprve přidá bit s hodnotou 1. Poté se přidají nulové bity, kde . A nakonec je přidána 64bitová reprezentace čísla . Stejné číslo určuje počet bloků, do kterých bude zpráva rozdělena.

Funkce kontrakce

Kompresní funkce nebo kompresní funkce se skládá z dvoubitových permutací a je definována jako .

Transformace výstupu

Výstupní transformační funkce je definována jako Ω , kde  je funkce, která vrací poslední bity vstupní hodnoty .

Permutace P a Q

Kompresní funkce Grøstl umí pracovat s krátkými zprávami (512 bitů) a dlouhými zprávami (1024 bitů). V souladu s tím existují 4 permutace , a , .

Každá permutace se provádí v kolech, v každém z nich se provádějí 4 kolové transformace:

Tyto transformace řídí stav, který je reprezentován maticí A obsahující 1 bajt informace v každé buňce. Pro práci s krátkými výtahy zpráv má matice velikost 8X8, pro dlouhé výtahy - 8X16.

Nejprve je matice A vyplněna posloupností bajtů. Například pro posloupnost 00 01 02 … 3f matice A vypadá takto.

Matice 8 X 16 je vyplněna stejným způsobem.

Dále se na matici A provedou kulaté transformace.

AddRoundConstant

Tato transformace provádí operaci XOR mezi stavovou maticí a konstantou specifickou pro kolo: A←A , kde  je konstanta specifická pro kolo. Tyto konstanty jsou různé pro každou permutaci P a Q:

512

1024

512

1024

kde je zaokrouhlené číslo reprezentované 8bitovou hodnotou.

Subbytes

Tato transformace nahradí každý bajt stavové matice hodnotou převzatou z S-boxu. Hashovací funkce Grøstl používá stejný S-box jako šifra AES. Transformace tedy vypadá takto: ← , kde  je prvek matice A. A S-box vypadá takto:


00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
00 63 7c 77 7b f2 6b 6f c5 třicet 01 67 2b např d7 ab 76
deset ca 82 c9 7d fa 59 47 f0 inzerát d4 a2 af 9c a4 72 c0
dvacet b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 patnáct
třicet 04 c7 23 c3 osmnáct 96 05 9a 07 12 80 e2 eb 27 b2 75
40 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
padesáti 53 d1 00 vyd dvacet fc b1 5b 6a cb být 39 4a 4c 58 srov
60 d0 ef aa fb 43 4d 33 85 45 f9 02 7f padesáti 3c 9f a8
70 51 a3 40 8f 92 9d 38 f5 před naším letopočtem b6 da 21 deset ff f3 d2
80 CD 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5 d 19 73
90 60 81 4f DC 22 2a 90 88 46 ee b8 čtrnáct de 5e 0b db
a0 e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b0 e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c0 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 lf 4b bd 8b 8a
d0 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e0 e1 f8 98 jedenáct 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f0 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16


Transformace hledá prvky v prvním sloupci a prvek v prvním řádku.(  je logické "nebo"). Výstupem je prvek umístěný v jejich průsečíku.


ShiftBytes(ShiftBytesWide)

Nechť α=[α 1 , α 2 ,…, α 7 ] je množina celých čísel od 1 do 7. Transformace ShiftBytes otočí všechny bajty v řádku i stavové matice A o α i pozic doleva. Pro permutace P a Q jsou tyto sady čísel různé:

  • P 512 : α=[0,1,2,3,4,5,6,7]
  • Q 512 : α=[1,3,5,7,0,2,4,6]

V souladu s tím pro funkci ShiftBytesWide:

  • P 1024 : α=[0,1,2,3,4,5,6,11]
  • Q 1024 : α=[1,3,5,11,0,2,4,6]


MixBytes

Při této transformaci je každý sloupec matice A vynásoben konstantní maticí B v konečném poli . Matice B je definována jako

Transformaci MixBytes lze označit jako: A←B A.

Zabezpečení

Spolehlivost hashovací funkce přímo závisí na počtu kol. V důsledku kryptoanalýzy bylo možné vyrobit pouze první 3 náboje. Tabulka ukazuje některé výsledky kryptoanalýzy provedené během posledního kola soutěže o hashovací funkce SHA-3:

Cíl útoku Typ útoku Počet výstupních bitů počet kol Počet operací
hashovací funkce hledání kolizí 224, 256 3 264 _
hashovací funkce hledání kolizí 512 3 2192 _
Kompresní funkce nalezení dílčích kolizí 256 6 2 120
Kompresní funkce nalezení dílčích kolizí 384 6 2 180
Kompresní funkce nalezení dílčích kolizí 512 6 2 180
permutace diferenciální vlastnost 256 9 2368 _
permutace diferenciální vlastnost 512 osm 2280 _
permutace diferenciální vlastnost 512 9 2328 _
permutace diferenciální vlastnost 512 deset 2392 _
výstupní transformace Hledání prototypu 256 6 2251 _
výstupní transformace Hledání prototypu 256 5 2206 _
výstupní transformace Hledání prototypu 512 osm 2495 _
hashovací funkce nalezení pseudopředobrazu 256 5 2245 _
hashovací funkce nalezení pseudopředobrazu 512 osm 2507 _

Výkon

Softwarová implementace Grøstl je určena především pro 64bitový procesor, ale je možné pracovat i na 32bitových procesorech. Během testů provedených ve finále soutěže NIST byl výkon hashovací funkce nejnižší ve srovnání s ostatními účastníky soutěže. Při provádění algoritmu na mikrokontroléru se však rychlost jeho provozu ukázala být mnohem vyšší než u konkurentů. Tabulka ukazuje rychlost softwarových implementací různých verzí funkce.

procesor Varianta funkce Rychlost (cyklus/bajt)
Intel Core i7 M620 Grøstl-224/256 12:45
Intel Core i7 M620 Grøstl-384/512 17,85


Následující tabulka ukazuje 8bitovou implementaci na mikrokontroléru ATmega 163.

hashovací funkce procesor Paměť Rychlost (cyklus/bajt)
Grøstl-256 ATmega163 994 469
Grøstl-256 ATmega163 226 531
Grøstl-256 ATmega163 164 760

Příklady hash Grøstl

Hodnoty různých variant hash z prázdného řetězce.

Grøstl-224("") 0x f2e180fb5947be964cd584e22e496242c6a329c577fc4ce8c36d34c3 Grøstl-256("") 0x 1a52d11d550039be16107f9c58db9ebcc417f16f736adb2502567119f0083467 Grøstl-384("") 0x ac353c1095ace21439251007862d6c62f829ddbe6de4f78e68d310a9205a736d8b11d99bffe448f57a1cfa2934f044a5 Grøstl 0x 6d3ad29d279110eef3adbd66de2a0345a77baede1557f5d099fce0c03d6dc2ba8e6d4a6633dfbd66053c20faa87d1a11f439a8080

Malá změna ve zprávě pravděpodobně povede k velké změně hodnoty hash v důsledku lavinového efektu , jak ukazuje následující příklad:

Grøstl-256 („Rychlá hnědá liška skáče přes líného psa“) 0x 8c7ad62eb26a21297bc39c2d7293b4bd4d3399fa8afab29e970471739e28b301 Grøstl-256("Rychlá hnědá liška skáče přes líného psa.") 0x f48290b1bcacee406a0429b993adb8fb3d065f4b09cbcdb464a631d4a0080aaf Grøstl-512 („Rychlá hnědá liška skáče přes líného psa“) 0x badc1f70ccd69e0cf3760c3f93884289da84ec13c70b3d12a53a7a8a4a513f99715d46288f55e1dbf926e6d084a0538e714eeb912921714eebf 0x 518a55cc274fc887d8dcbd0bb24000395f6d3be62445d84cc9e85d419161a968268e490f7537e475e57d8c009b08852009b08852bce20

Poznámky

  1. ↑ Hashovací funkce Grøstl - kandidát SHA-3 . Získáno 13. prosince 2013. Archivováno z originálu 11. října 2013.

Odkazy

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