Grostl

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. kesäkuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Grostl
Kehittäjät	Soren Stefan Thompson, Lars Knudsen , Martin Schlaffer, Christian Rechberger, Florian Mendel, Christian Matusevich, Praaven Gauravaram
Hash-koko	224, 256, 384, 512 (muuttuva, 8-512 bittiä)
Kierrosten lukumäärä	9 (suositus)
Tyyppi	hash-toiminto

Grøstl ( Groestl ) on iteratiivinen kryptografinen hash-funktio . Yksi viidestä finalistista NIST :n järjestämässä SHA-3-kilpailussa . Supistusfunktio Grøstl koostuu kahdesta kiinteästä 2n-bittisestä permutaatiosta P ja Q, joiden rakenne on lainattu AES -salauksesta . Erityisesti käytetään samaa S-laatikkoa . Hajautusfunktion tuloksen pituus voi olla 8 - 512 bittiä 8 bitin askeleella. Varianttia, joka palauttaa n bittiä, kutsutaan nimellä Grøstl-n.

Historia

Grøstl-algoritmin suunnitteli erityisesti SHA-3 kryptografisten toimintojen kilpailua varten ryhmä kryptografeja [1] Tanskan teknisestä yliopistosta . Funktio oli alun perin nimeltään Grøstl-0. Permutaatioiden välisiä rakenteellisia eroja lisättiin kuitenkin finaaliin pääsemiseksi. ShiftBytes-arvot permutaatiossa Q muutettiin. Myös P:n ja Q:n pyöreät vakiot muutettiin. Päivitetty hash-funktio sai nimen Grøstl. Kuitenkin osoittanut hyvän kryptografisen vahvuuden , se oli useissa indikaattoreissa huonompi kuin muut viimeisellä kierroksella osallistujat, eikä siitä voinut tulla voittajaa.

Nimen alkuperä

Gröstl on itävaltalainen ruokalaji . Resepti on hyvin lähellä ruokaa nimeltä "Hash" Yhdysvalloissa . Kirjain "ö" funktion nimessä on korvattu kirjaimella "ø" tanskalaisesta aakkosesta, jolla on sama ääntäminen.

Ominaisuudet

Grøstl on tavusuuntautunut SP-verkko . Rakenteeltaan se eroaa merkittävästi SHA-perheen algoritmeista. Monet hash-funktion komponentit on lainattu AES-salauksesta. Kuten AES, permutaatiot kehitetään käyttämällä Wide Trail -suunnittelustrategiaa , jonka pääperiaatteet ovat, että lohkosalauksessa on :

Epälineaariset substituutiot (eli hyvä S-laatikko)
Lineaariset muunnokset (varmistetaan S-laatikon hyvä diffuusio ja epälineaarisuus)
Keskeiset lisäykset (yleensä XOR :lla )

Funktion sisäisen tilan koko on paljon suurempi kuin lähtötietojen koko. Tämä on niin sanottu "leveäputkirakenne".

Algoritmi

Ensin viesti jaetaan lohkoihin , ,…, jokaiseen bitti kerrallaan . Jopa 256 bittiä palauttaville funktiovarianteille = 512. Suuria arvoja palauttaville muunnelmille = 1024. $M$ $t$ $m$ $yksi$ $m$ $2$ $m$ $t$ $l$ $l$ $l$

Seuraavaksi rakennetaan hajautusfunktio käyttämällä toistuvaa laskentamenetelmää. Jokainen lohko käsitellään peräkkäin pakkausfunktiolla kaavan , mukaisesti . $m$ $f$ $h$ $i$ $=$ $f$ $($ $m$ $i$ $h$ $i-1$ $)$

$h$ $=$ $($ $h$ $0$ , ,…, on niin kutsuttu ketjutussyöttö. $h$ $yksi$ $h$ $t$ $)$

Alkuarvo = . $h$ $0$ $iv$

Kun viimeinen lohko on käsitelty, -bitin arvo syötetään muunnosfunktiolle Ω , joka palauttaa viestin, jonka pituus on ≤ . $l$ $h$ $i$ $($ $h$ $i$ $)$ $n$ $2n$ $l$

Siten tiivistefunktion tulos Ω $H$ $($ $M$ $)$ $=$ $($ $h$ $t$ $)$

Alkuarvo

Funktion Grøstl-n alkuarvolle annetaan -bittinen esitys luvusta n. Taulukko näyttää alkuarvot eri hajautusfunktioille. $iv$ $n$ $l$

$n$	$iv$ $n$
224	00…00 00 e0
256	00…00 01 00
384	00…00 01 80
512	00…00 02 00

pad-toiminto

Jos haluat käsitellä mielivaltaisen pituisia viestejä, käytä toimintoa . Se muuntaa mielivaltaisen pituisen viestin viestiksi, jonka pituus on kerrannainen . Tätä varten viestiin lisätään ensin bitti, jonka arvo on 1. Sitten lisätään nolla bittiä, missä . Ja lopuksi 64-bittinen esitys numerosta lisätään . Sama numero määrittää lohkojen määrän, joihin viesti jaetaan. $x*=tyyny(x)$ $x$ $N$ $l$ $w$ $w=(-N-65)mod$ $l$ $(N+w+65)/l$

Supistumisfunktio

Pakkausfunktio tai pakkausfunktio koostuu kaksibittisistä permutaatioista ja ja määritellään nimellä . $l$ $P$ $K$ $f(h,m)=P(h\oplus m)\oplus Q(m)\oplus h$

Lähtömuunnos

Lähtömuunnosfunktio määritellään muodossa Ω , jossa on funktio, joka palauttaa tuloarvon viimeiset bitit . $(x) = katkaisu$ $n$ $(P(x)\plus x)$ $trunc$ $n$ $(x)$ $n$ $x$

P:n ja Q:n permutaatiot

Grøstl-pakkaustoiminto voi toimia lyhyiden (512 bittiä) ja pitkien viestien (1024 bittiä) kanssa. Vastaavasti on olemassa 4 permutaatiota , ja , . $P$ $512$ $K$ $512$ $P$ $1024$ $K$ $1024$

Jokainen permutaatio suoritetaan kierroksina, joista jokaisessa suoritetaan 4 kierrosta muunnoksia: $R$

AddRoundConstant
Subtavut
ShiftBytes (tai ShiftBytesWide pitkille tiivistelmille)
MixBytes

Nämä muunnokset ohjaavat tilaa, jota edustaa matriisi A, joka sisältää 1 tavun tietoa kussakin solussa. Lyhytsanomien tiivistelmien käsittelyä varten matriisin koko on 8x8, pitkien tiivistelmien koko on 8x16.

Ensin matriisi A täytetään tavujonolla. Esimerkiksi sekvenssille 00 01 02 … 3f matriisi A näyttää tältä.

${\begin{bmatrix}00&08&10&18&20&28&30&38\\01&09&11&19&21&29&31&39\\02&0a&12&1a&22&2a&32&3a\\03&0b&13&1b&23&2b&33&3b\\04&0c&14&1c&24&2c&34&3c\\05&0d&15&1d&25&2d&35&3d\\06&0e&16&1e&26&2e&36&3e\\07&0f&17&1f&27&2f&37&3f\end{bmatrix}}$

8 x 16 matriisi täytetään samalla tavalla.

Seuraavaksi suoritetaan pyöreät muunnokset matriisille A.

AddRoundConstant

Tämä muunnos suorittaa XOR-operaation tilamatriisin ja kierroskohtaisen vakion välillä: A←A , jossa on kierroskohtainen vakio. Nämä vakiot ovat erilaisia jokaiselle P:n ja Q:n permutaatiolle: $\oplus C[i]$ $C[i]$

$P$ 512 $:C[i]={\begin{bmatrix}00\oplus i&10\oplus i&20\oplus i&30\oplus i&40\oplus i&50\oplus i&60\oplus i&70\oplus i\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\ \00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\end{bmatrix}}$

$P$ 1024 $:C[i]={\begin{bmatrix}00\oplus i&10\oplus i&20\oplus i&30\oplus i&40\oplus i&50\oplus i&60\oplus i&70\oplus i&\cdots &f0\oplus i&\cdots &f0\oplus i&10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\end{bmatrix}}$

$K$ 512 $:C[i]={\begin{bmatrix}ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff\oplus i&ef\oplus i&df\oplus i&cf\oplus i&bf\oplus i&af\ oplus i&9f\oplus i&8f\oplus i\end{bmatrix}}$

$K$ 1024 $:C[i]={\begin{bmatrix}ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\ cdots &ff\\ff\oplus i&ef\oplus i&df\oplus i&cf\oplus i&bf\oplus i&af\oplus i&9f\oplus i&8f\oplus i&\cdots &0f\oplus i\end{bmatrix}}$

missä on pyöreä luku, jota edustaa 8-bittinen arvo. $i$

Alatavut

Tämä muunnos korvaa tilamatriisin jokaisen tavun S-laatikosta otetulla arvolla. Grøstl-hajautusfunktio käyttää samaa S-laatikkoa kuin AES-salaus. Siksi muunnos näyttää tältä: ← , missä on matriisin A elementti. Ja S-laatikko näyttää tältä: $a$ $i, j$ $S(a$ $i, j$ $)$ $a$ $i, j$

	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	kolmekymmentä	01	67	2b	esim	d7	ab	76
kymmenen	noin	82	c9	7d	fa	59	47	f0	ilmoitus	d4	a2	af	9c	a4	72	c0
kaksikymmentä	b7	fd	93	26	36	3f	f7	cc	34	a5	e5	f1	71	d8	31	viisitoista
kolmekymmentä	04	c7	23	c3	kahdeksantoista	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
viisikymmentä	53	d1	00	toim	kaksikymmentä	fc	b1	5b	6a	cb	olla	39	4a	4c	58	vrt
60	d0	ef	aa	fb	43	4d	33	85	45	f9	02	7f	viisikymmentä	3c	9f	a8
70	51	a3	40	8f	92	9d	38	f5	eKr	b6	da	21	kymmenen	ff	f3	d2
80	CD	0c	13	ec	5f	97	44	17	c4	a7	7e	3d	64	5d	19	73
90	60	81	4f	DC	22	2a	90	88	46	ee	b8	neljätoista	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	1f	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	yksitoista	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

Muunnos etsii elementit ensimmäisestä sarakkeesta ja elementti ensimmäisestä rivistä. ( on looginen "tai"). Lähtö on elementti, joka sijaitsee niiden leikkauskohdassa. $S(a$ $i, j$ $)$ $a$ $i, j$ $\bigwedge f0$ $a$ $i, j$ $\bigwedge 0f$ $\iso kiila$

ShiftBytes(ShiftBytesWide)

Olkoon α=[α 1 , α 2 ,…, α 7 ] joukko kokonaislukuja 1:stä 7:ään. ShiftBytes-muunnos kiertää kaikki tilamatriisin A rivin i tavut α i -paikalla vasemmalle. Permutaatioille P ja Q nämä numerojoukot ovat erilaisia:

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

Vastaavasti ShiftBytesWide-funktiolle:

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

MixBytes

Tällä muunnolla matriisin A kukin sarake kerrotaan vakiomatriisilla B äärellisessä kentässä . Matriisi B määritellään seuraavasti $\mathbb {F}$ $256$
$B={\begin{bmatrix}02&02&03&04&05&03&05&07\\07&02&02&03&04&05&03&05\\05&07&02&02&03&04&05&03\\03&05&07&02&02&03&04&05\\05&03&05&07&02&02&03&04\\04&05&03&05&07&02&02&03\\03&04&05&03&05&07&02&02\\02&03&04&05&03&05&07&02\end{bmatrix}}$

MixBytes-muunnos voidaan merkitä seuraavasti: A←B A. $\ajat$

Turvallisuus

Hajautusfunktion luotettavuus riippuu suoraan kierrosten lukumäärästä. Kryptusanalyysin tuloksena oli mahdollista tuottaa vain 3 ensimmäistä kierrosta. Taulukossa on joitain tuloksia SHA-3-hajautusfunktiokilpailun viimeisen kierroksen aikana tehdystä kryptausanalyysistä:

Hyökkäyksen kohde	Hyökkäystyyppi	Lähtöbittien lukumäärä	kierrosten määrä	Toimien lukumäärä
hash-toiminto	törmäysten löytäminen	224, 256	3	264 _
hash-toiminto	törmäysten löytäminen	512	3	2192 _
Pakkaustoiminto	osittaisten törmäysten löytäminen	256	6	2 120
Pakkaustoiminto	osittaisten törmäysten löytäminen	384	6	2 180
Pakkaustoiminto	osittaisten törmäysten löytäminen	512	6	2 180
permutaatio	erilainen ominaisuus	256	9	2368 _
permutaatio	erilainen ominaisuus	512	kahdeksan	2280 _
permutaatio	erilainen ominaisuus	512	9	2328 _
permutaatio	erilainen ominaisuus	512	kymmenen	2392 _
lähdön muunnos	Prototyypin löytäminen	256	6	2251 _
lähdön muunnos	Prototyypin löytäminen	256	5	2206 _
lähdön muunnos	Prototyypin löytäminen	512	kahdeksan	2495 _
hash-toiminto	pseudoesikuvan löytäminen	256	5	2245 _
hash-toiminto	pseudoesikuvan löytäminen	512	kahdeksan	2507 _

Suorituskyky

Grøstlin ohjelmistototeutus on suunniteltu pääosin 64-bittiselle prosessorille, mutta myös 32-bittisille prosessoreille on mahdollista työskennellä. NIST-kilpailun finaalissa suoritetuissa testeissä hash-funktion suorituskyky oli heikoin verrattuna muihin kilpailun osallistujiin. Kuitenkin, kun algoritmi suoritettiin mikro-ohjaimella, sen toimintanopeus osoittautui paljon suuremmaksi kuin kilpailijoiden. Taulukossa on esitetty toiminnon eri versioiden ohjelmistototeutusten nopeus.

prosessori	Ominaisuusvariantti	Nopeus (sykli/tavu)
Intel Core i7 M620	Grøstl-224/256	12.45
Intel Core i7 M620	Grøstl-384/512	17.85

Seuraava taulukko näyttää 8-bittisen toteutuksen ATmega 163 -mikro-ohjaimessa.

hash-toiminto	prosessori	Muisti	Nopeus (sykli/tavu)
Grøstl-256	ATmega163	994	469
Grøstl-256	ATmega163	226	531
Grøstl-256	ATmega163	164	760

Grøstl hash esimerkkejä

Eri hash-muunnelmien arvot tyhjästä merkkijonosta.

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

Pieni muutos viestissä johtaa todennäköisesti suureen muutokseen hash-arvossa lumivyöryvaikutuksen vuoksi , kuten seuraavassa esimerkissä näkyy:

Grøstl-256 ("Nopea ruskea kettu hyppää laiskan koiran yli") 0x 8c7ad62eb26a21297bc39c2d7293b4bd4d3399fa8afab29e970471739e28b301 Grøstl-256("Nopea ruskea kettu hyppää laiskan koiran yli.") 0x f48290b1bcacee406a0429b993adb8fb3d065f4b09cbcdb464a631d4a0080aaf Grøstl-512 ("Nopea ruskea kettu hyppää laiskan koiran yli") 0x badc1f70ccd69e0cf3760c3f93884289da84ec13c70b3d12a53a7a8a4a513f99715d46288f55e1dbf926e6d084a1dbf926e6d084a0538e4cf92cc1 ruskea14cfc94cf1 0x 518a55cc274fc887d8dcbd0bb24000395f6d3be62445d84cc9e85d419161a968268e490f7537e475e57d8c009b0957e57d8c009b0957caa2c5c009b0957caa2c5

Muistiinpanot

↑ Hash-funktio Grøstl - SHA-3 ehdokas . Haettu 13. joulukuuta 2013. Arkistoitu alkuperäisestä 11. lokakuuta 2013. (määrätön)

Linkit

Differentiaalivikaanalyysi Grøstlissä IEEE Xploressa (englanniksi);
Parannetut törmäyshyökkäykset redusoidun kierroksen Grøstl-hash-funktioon ResearchGatessa ( englanniksi);
Grøstl Hash -funktion välinpitämättömyydestä Springer Science+Business Mediassa (englanniksi)
Grøstlin verkkosivusto
Grostl-spesifikaatio
NIST-sivusto. Kilpailu SHA-3-algoritmista
SHA-3-algoritmin lopullisen kilpailun tulos
Laaja polun suunnittelustrategia

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