SHA-3

KangarooTwelve
Allmän
Designers	Guido Bertoni, Joan Daemen , Michaël Peeters, Gilles Van Assche , Ronny Van Keer, Benoît Viguier
Först publicerad	10 augusti 2016 ; för 6 år sedan
Härrörande från	Keccak
Detalj
Digest storlekar	slumpmässig
Strukturera	svampkonstruktion och trädhasning med känguruhoppning
Omgångar	12
Fart	0,51 cpb på SkylakeX med AVX-512
Bästa offentliga kryptoanalys
	Samma som Keccaks

SHA-3 (Keccak)
Allmän
Designers	Guido Bertoni, Joan Daemen , Michaël Peeters och Gilles van Assche .
Först publicerad	2016 ; 7 år sedan
Serier	( SHA-0 ), SHA-1 , SHA-2 , SHA-3
Certifiering	FIPS PUB 202
Detalj
Digest storlekar	slumpmässig
Strukturera	svampkonstruktion
Fart	12,6 cpb på en typisk x86-64-baserad maskin för Keccak-f[1600] plus XORing 1024 bitar, vilket ungefär motsvarar SHA2-256.
Bästa offentliga kryptoanalys
	Preimage-attack på Keccak-512 reducerad till 8 omgångar, vilket kräver 2 511,5 tid och 2 508 minne. Nollsumme-särskiljare finns för hela 24-rundor Keccak-f[1600], även om de inte kan användas för att attackera själva hashfunktionen

Secure Hash Algoritmer
Secure Hash Algoritmer
Koncept
	hashfunktioner · SHA · DSA
Huvudstandarder
	SHA-0 · SHA-1 · SHA-2 · SHA-3

SHA-3 ( Secure Hash Algorithm 3 ) är den senaste medlemmen i Secure Hash Algorithm- familjen av standarder, släppt av NIST den 5 augusti 2015. Även om SHA-3 är en del av samma serie av standarder, skiljer sig internt från MD5 - liknande struktur för SHA-1 och SHA-2 .

SHA-3 är en delmängd av den bredare kryptografiska primitiva familjen Keccak ( / ˈ k ɛ tʃ æ k / eller / ˈ k ɛ tʃ ɑː k / ), designad av Guido Bertoni, Joan Daemen , Michaël Peeters och Gilles Van Assche , byggnad på RadioGatún . Keccaks författare har föreslagit ytterligare användningsområden för funktionen, som (ännu) inte standardiserats av NIST, inklusive ett strömchiffer , ett autentiserat krypteringssystem , ett "träd"-hashingschema för snabbare hash på vissa arkitekturer och AEAD -chiffer Keyak och Ketje.

Keccak är baserad på en ny metod som kallas svampkonstruktion . Svampkonstruktion är baserad på en bred slumpmässig funktion eller slumpmässig permutation , och tillåter inmatning ("absorbera" i svampterminologi) vilken mängd data som helst, och mata ut ("pressa") vilken mängd data som helst, samtidigt som den fungerar som en pseudoslumpmässig funktion med avseende på alla tidigare ingångar. Detta leder till stor flexibilitet.

NIST planerar för närvarande inte att dra tillbaka SHA-2 eller ta bort den från den reviderade Secure Hash Standard. ^{[ behöver uppdateras? ]} Syftet med SHA-3 är att det kan ersättas direkt med SHA-2 i nuvarande applikationer om det behövs, och att avsevärt förbättra robustheten hos NIST:s övergripande hashalgoritmverktyg.

För små meddelandestorlekar föreslår skaparna av Keccak-algoritmerna och SHA-3-funktionerna att använda den snabbare funktionen KangarooTwelve med justerade parametrar och ett nytt trädhashningsläge utan extra overhead.

Historia

Keccak-algoritmen är ett verk av Guido Bertoni, Joan Daemen (som också designade Rijndael -chifferet tillsammans med Vincent Rijmen ), Michaël Peeters och Gilles Van Assche . Den är baserad på tidigare hashfunktionsdesigner PANAMA och RadioGatún . PANAMA designades av Daemen och Craig Clapp 1998. RadioGatún, en efterträdare till PANAMA, designades av Daemen, Peeters och Van Assche och presenterades på NIST Hash Workshop 2006. Referensimplementeringskällkoden var dedikerad till allmän egendom . via CC0 dispens .

2006 började NIST organisera NIST-hashfunktionstävlingen för att skapa en ny hashstandard, SHA-3. SHA-3 är inte tänkt att ersätta SHA-2 , eftersom ingen signifikant attack på SHA-2 har visats. På grund av de framgångsrika attackerna på MD5 , SHA-0 och SHA-1 uppfattade NIST ett behov av en alternativ, olik kryptografisk hash, som blev SHA-3.

Efter en uppställningsperiod skulle antagningen lämnas in i slutet av 2008. Keccak antogs som en av de 51 kandidaterna. I juli 2009 valdes 14 algoritmer ut till den andra omgången. Keccak gick vidare till den sista omgången i december 2010.

Under tävlingen fick deltagarna "tweaka" sina algoritmer för att lösa problem som upptäcktes. Ändringar som har gjorts i Keccak är:

Antalet omgångar ökades från 12 + ℓ till 12 + 2 ℓ för att vara mer konservativ när det gäller säkerhet.
Meddelandeutfyllningen ändrades från ett mer komplext schema till det enkla 10 ^* 1 mönstret som beskrivs nedan.
Kursen r höjdes till säkerhetsgränsen i stället för att avrundas nedåt till närmaste potens av 2.

Den 2 oktober 2012 utsågs Keccak till vinnare av tävlingen.

2014 publicerade NIST ett utkast till FIPS 202 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions". FIPS 202 godkändes den 5 augusti 2015.

Den 5 augusti 2015 meddelade NIST att SHA-3 hade blivit en hashstandard.

Försvagande kontrovers

I början av 2013 tillkännagav NIST att de skulle välja olika värden för "kapacitet", den övergripande hållfastheten mot hastighetsparametern, för SHA-3-standarden, jämfört med inlämningen. Förändringarna orsakade viss oro.

Hashfunktionstävlingen krävde hashfunktioner som var minst lika säkra som SHA-2-instanserna. Det betyder att en d -bitars utdata ska ha d /2-bitars resistans mot kollisionsattacker och d -bitars resistans mot preimage attacker , det maximala som kan uppnås för d bitar av utdata. Keccaks säkerhetsbevis tillåter en justerbar säkerhetsnivå baserat på en "kapacitet" c , vilket ger c /2-bitars motstånd mot både kollision och preimage attacker. För att uppfylla de ursprungliga tävlingsreglerna föreslog Keccaks författare c = 2 d . Den aviserade förändringen var att acceptera samma d /2-bitars säkerhet för alla former av attacker och standardisera c = d . Detta skulle ha påskyndat Keccak genom att tillåta ytterligare d bitar av indata att hashas varje iteration. Hash-funktionerna skulle dock inte ha varit drop-in-ersättningar med samma preimage-motstånd som SHA-2 längre; det skulle ha halverats, vilket gör det sårbart för framsteg inom kvantberäkningar, vilket effektivt skulle halvera det en gång till.

I september 2013 föreslog Daniel J. Bernstein på e-postlistan NIST hash-forum att stärka säkerheten till den 576-bitars kapacitet som ursprungligen föreslogs som standard Keccak, utöver och inte inkluderade i SHA-3-specifikationerna. Detta skulle ha tillhandahållit åtminstone en SHA3-224 och SHA3-256 med samma förbildsresistans som deras SHA-2-föregångare, men SHA3-384 och SHA3-512 skulle ha haft betydligt mindre förbildsresistans än deras SHA-2-föregångare. I slutet av september svarade Keccak-teamet med att säga att de hade föreslagit 128-bitars säkerhet genom att ställa in c = 256 som ett alternativ redan i deras SHA-3-förslag. Även om den minskade kapaciteten var motiverad enligt deras åsikt, i ljuset av det negativa svaret, föreslog de att kapaciteten skulle höjas till c = 512 bitar för alla instanser. Detta skulle vara lika mycket som alla tidigare standarder upp till 256-bitars säkerhetsnivå, samtidigt som det ger rimlig effektivitet, men inte 384-/512-bitars förbildsresistans som erbjuds av SHA2-384 och SHA2-512. Författarna konstaterade att "att göra anspråk på eller förlita sig på säkerhetsstyrkanivåer över 256 bitar är meningslöst".

I början av oktober 2013 kritiserade Bruce Schneier NIST:s beslut på grundval av dess möjliga skadliga effekter på acceptansen av algoritmen och sa:

Det är för mycket misstro i luften. NIST riskerar att publicera en algoritm som ingen kommer att lita på och ingen (förutom de tvingade) kommer att använda.

Han tog senare tillbaka sitt tidigare uttalande och sa:

Jag talade fel när jag skrev att NIST gjorde "interna ändringar" i algoritmen. Det var slarvigt av mig. Keccak-permutationen förblir oförändrad. Vad NIST föreslog var att minska hashfunktionens kapacitet i prestandas namn. En av Keccaks trevliga egenskaper är att den är mycket avstämbar.

Paul Crowley, en kryptograf och senior utvecklare på ett oberoende mjukvaruutvecklingsföretag, uttryckte sitt stöd för beslutet och sa att Keccak ska vara avstämbar och att det inte finns någon anledning till olika säkerhetsnivåer inom en primitiv. Han tillade också:

Ja, det är lite synd för tävlingen att de krävde en viss säkerhetsnivå för deltagare, för att sedan ge ut en standard med en annan. Men det finns inget som kan göras för att fixa det nu, förutom att öppna tävlingen igen. Att kräva att de ska hålla fast vid sina misstag förbättrar inte saker för någon.

Det fanns en viss förvirring om att interna ändringar kan ha gjorts i Keccak, som klarades upp av det ursprungliga teamet, och angav att NIST:s förslag för SHA-3 är en delmängd av Keccak-familjen, för vilken man kan generera testvektorer med hjälp av deras referenskod lämnade in till tävlingen och att detta förslag var resultatet av en serie diskussioner mellan dem och NIST-hashteamet.

Som svar på kontroversen föreslog John Kelsey från NIST i november 2013 att man skulle gå tillbaka till det ursprungliga förslaget c = 2 d för alla SHA-2 drop-in-ersättningsinstanser. Återgången bekräftades i efterföljande utkast och i den slutliga versionen.

Design

Svampkonstruktionen för hashfunktioner. P _i är ingång, Z _i är hashad utgång. Den oanvända "kapaciteten" c bör vara två gånger det önskade motståndet mot kollision eller preimage attacker .

SHA-3 använder svampkonstruktionen , där data "absorberas" i svampen, sedan "pressas" resultatet ut. I den absorberande fasen XOReras meddelandeblock till en delmängd av tillståndet, som sedan transformeras som en helhet med hjälp av en permutationsfunktion $f$ . I "squeeze"-fasen läses utgångsblock från samma delmängd av tillståndet, alternerat med tillståndstransformationsfunktionen f {\ $f}$ . Storleken på den del av tillståndet som skrivs och läses kallas "hastighet" (betecknad $r$ ), och storleken på den del som är orörd av ingång/utgång kallas "kapacitet" (betecknad $c$ ). Kapaciteten avgör systemets säkerhet. Den maximala säkerhetsnivån är halva kapaciteten.

Givet en indatabitsträng $N$ , en utfyllnadsfunktion $pad$ , en permutationsfunktion $f$ som verkar på bitblock med bredd $b$ , en hastighet $r$ och en utgångslängd $d$ , vi har kapacitet $c=br$ och svampkonstruktionen ${\displaystyle Z={\text{svamp}}[f,pad,r](N,d)} ,$ ger en bitsträng $Z$ med längden $d$ , fungerar enligt följande :

fylla på ingången N med hjälp av pad-funktionen, vilket ger en utfylld bitsträng P med en längd som är delbar med $r$ (så att $n={\text{len}}( P)/r$ är ett heltal)
₀ bryt P i n på varandra följande r -bitar P , ..., P _{n −1}
initiera tillståndet S till en sträng med b nollbitar
absorbera ingången till tillståndet: för varje block P _i :
- förläng P _i i slutet med en sträng av c nollbitar, vilket ger en med längden b
- XOR det med S
- tillämpa blockpermutationen f på resultatet, vilket ger ett nytt tillstånd S
initiera Z för att vara den tomma strängen
medan längden på Z är mindre än d :
- lägg till de första r bitarna av S till Ö
- om Z fortfarande är mindre än d bitar lång, applicera f på S , vilket ger ett nytt tillstånd S
trunkera Z till d bitar

Det faktum att det interna tillståndet S innehåller c ytterligare informationsbitar utöver vad som matas ut till Z förhindrar de längdförlängningsattacker som SHA-2, SHA-1, MD5 och andra hash baserade på Merkle–Damgård-konstruktionen är känsliga för.

I SHA-3 består tillståndet S av en 5 × 5 array av w -bitars ord (med w = 64), b = 5 × 5 × w = 5 × 5 × 64 = 1600 bitar totalt. Keccak är också definierad för mindre power-of-2 ordstorlekar w ner till 1 bit (totalt tillstånd på 25 bitar). Små tillståndsstorlekar kan användas för att testa kryptoanalytiska attacker, och mellanliggande tillståndsstorlekar (från w = 8 , 200 bitar, till w = 32 , 800 bitar) kan användas i praktiska, lätta applikationer.

För SHA3-224-, SHA3-256-, SHA3-384- och SHA3-512-instanser är r större än d , så det finns inget behov av ytterligare blockpermutationer i klämfasen; de ledande d- bitarna i tillståndet är den önskade hashen. SHAKE128 och SHAKE256 tillåter dock en godtycklig utdatalängd, vilket är användbart i applikationer som optimal asymmetrisk krypteringsutfyllnad .

Stoppning

För att säkerställa att meddelandet kan delas upp i r -bitars block krävs utfyllnad. SHA-3 använder mönstret 10 ^* 1 i sin utfyllnadsfunktion: en 1 bit, följt av noll eller fler 0 bitar (maximalt $r - 1$ ) och en sista 1 bit.

Maximalt $r - 1$ noll bitar inträffar när det sista meddelandeblocket är $r - 1$ bitar långt. Sedan läggs ytterligare ett block till efter den initiala 1-biten, innehållande $r - 1$ nollbitar före den sista 1-biten.

De två 1-bitarna kommer att läggas till även om längden på meddelandet redan är delbar med r . I detta fall läggs ytterligare ett block till meddelandet, innehållande en 1 bit, följt av ett block med $r - 2$ nollbitar och ytterligare 1 bit. Detta är nödvändigt för att ett meddelande med en längd som är delbar med r som slutar på något som ser ut som utfyllnad inte producerar samma hash som meddelandet med de bitarna borttagna.

Den initiala 1 biten krävs så att meddelanden som skiljer sig endast med några ytterligare 0 bitar i slutet inte producerar samma hash.

Placeringen av den sista 1 biten indikerar vilken hastighet r som användes (multi-rate padding), vilket krävs för att säkerhetsbeviset ska fungera för olika hashvarianter. Utan det skulle olika hashvarianter av samma kortmeddelande vara desamma fram till trunkering.

Blockpermutationen

Blocktransformationen f , som är Keccak-f[1600] för SHA-3, är en permutation som använder XOR , AND och NOT -operationer och är designad för enkel implementering i både mjukvara och hårdvara.

Den är definierad för vilken storlek som helst av två ord , $w = 2 ℓ$ bitar. Den huvudsakliga SHA-3-inlämningen använder 64-bitars ord, $ℓ = 6$ .

Tillståndet kan anses vara en $5 \times 5 \times w$ -matris av bitar. Låt $a [i][j][k]$ vara bit $(5 i + j) \times w + k$ av ingången, med hjälp av en liten-endian- bitnumreringskonvention och rad-major- indexering. Dvs $i$ väljer raden, $j$ kolumnen och $k$ biten.

Indexaritmetik utförs modulo 5 för de två första dimensionerna och modulo w för den tredje.

Den grundläggande blockpermutationsfunktionen består av $12 + 2 ℓ$ omgångar med fem steg:

$θ$ (theta): Beräkna pariteten för var och en av de $5 w$ (320, när $w = 64$ ) 5-bitars kolumner och exklusiva-eller det i två närliggande kolumner i ett regelbundet mönster. För att vara exakt, $a [i][j][k] \leftarrow a [i][j][k] \oplus paritet(a[0...4][j -1][k]) \oplus paritet(a[ 0...4][j +1][k -1])$
$ρ$ (rho): Rotera vart och ett av de 25 orden bitvis med ett annat triangulärt tal 0, 1, 3, 6, 10, 15, .... För att var exakt, a [0][0] roteras inte, och för alla $0 \leq t < 24$ , $a [i][j][k] \leftarrow a [i][j][k -(t +1)(t +2)/2]$ , där ${\begin{pmatrix}i\\j\end{pmatrix}}={\begin{pmatrix}3&2 \\1&0\end{pmatrix}}^{t}{\begin{pmatrix}0\\1\end{pmatrix}}$ .
$π$ (pi): Permutera de 25 orden i ett fast mönster. $a [3 i +2 j][i] \leftarrow a [i][j]$ .
$χ$ (chi): Kombinera bitvis längs rader med $x \leftarrow x \oplus (\neg y & z)$ . För att vara exakt, $a [i][j][k] \leftarrow a [i][j][k] \oplus (\neg a [i][j + 1][k] & a [i][j + 2] [k])$ . Detta är den enda icke-linjära operationen i SHA-3.
$ι$ (iota): Exklusiv - eller en rund konstant till ett ord av staten. För att vara exakt, i omgång $n$ , för $0 \leq m \leq ℓ$ , XOReds $a [0][0][2 m -1] med bit$ $m + 7 n$ av en LFSR - sekvens på 8 grader. Detta bryter symmetrin som bevaras av de andra stegen.

Fart

Hastigheten för SHA-3-hashning av långa meddelanden domineras av beräkningen av f = Keccak-f[1600] och XORing S med den utökade Pi , en operation på b = 1600 bitar _. Men eftersom de sista c bitarna i den utökade Pi är 0 ändå, och XOR med 0 är en NOP, är det tillräckligt att utföra XOR-operationer endast för _r bitar ( r = 1600 − 2 × 224 = 1152 bitar för SHA3-224 , 1088 bitar för SHA3-256, 832 bitar för SHA3-384 och 576 bitar för SHA3-512). Ju lägre r är (och, omvänt, ju högre c = b − r = 1600 − r ), desto mindre effektiv men säkrare blir hashningen eftersom färre bitar av meddelandet kan XOReras till tillståndet (en snabb operation) före varje tillämpning av det beräkningsmässigt dyra f . Författarna rapporterar följande hastigheter för programvaruimplementationer av Keccak-f[1600] plus XORing 1024 bitar, vilket ungefär motsvarar SHA3-256:

57,4 cpb på IA-32, Intel Pentium 3
41 cpb på IA-32+MMX, Intel Pentium 3
20 cpb på IA-32+SSE, Intel Core 2 Duo eller AMD Athlon 64
12,6 cpb på en typisk x86-64-baserad maskin
6–7 cpb på IA-64

För exakt SHA3-256 på x86-64 mäter Bernstein 11,7–12,25 cpb beroende på CPU. SHA-3 har kritiserats för att vara långsam på instruktionsuppsättningsarkitekturer (CPU) som inte har instruktioner speciellt avsedda för att beräkna Keccak-funktioner snabbare – SHA2-512 är mer än dubbelt så snabb som SHA3-512, och SHA-1 är mer än tre gånger så snabbt på en Intel Skylake-processor klockad till 3,2 GHz. Författarna har reagerat på denna kritik genom att föreslå att använda SHAKE128 och SHAKE256 istället för SHA3-256 och SHA3-512, på bekostnad av att halvera förbildsmotståndet (men samtidigt behålla kollisionsmotståndet). Med detta är prestanda i nivå med SHA2-256 och SHA2-512.

Men i hårdvaruimplementeringar är SHA-3 märkbart snabbare än alla andra finalister, och även snabbare än SHA-2 och SHA-1.

Från och med 2018 inkluderar ARMs ARMv8- och IBMs s390x-arkitekturer speciella instruktioner som gör det möjligt för Keccak-algoritmer att exekvera snabbare.

Instanser

NIST-standarden definierar följande instanser, för meddelande M och utgångslängd d :

Exempel	Utdatastorlek d _	Rate r = blockstorlek	Kapacitet c	Definition	Säkerhetsstyrkor i bitar
Exempel	Utdatastorlek d _	Rate r = blockstorlek	Kapacitet c	Definition	Kollision	Förbild	2:a förbilden
SHA3-224( M )	224	1152	448	Keccak[448]( M \|\| 01, 224)	112	224	224
SHA3-256( M )	256	1088	512	Keccak[512]( M \|\| 01, 256)	128	256	256
SHA3-384( M )	384	832	768	Keccak[768]( M \|\| 01, 384)	192	384	384
SHA3-512( M )	512	576	1024	Keccak[1024]( M \|\| 01, 512)	256	512	512
SHAKE128( M , d )	d	1344	256	Keccak[256]( M \|\| 1111, d )	min( d /2 128)	≥min( d ,128)	min( d ,128)
SHAKE256( M , d )	d	1088	512	Keccak[512]( M \|\| 1111, d )	min( d /2 256)	≥min( d ,256)	min( d ,256)

Med följande definitioner

Keccak[ c ]( N , d ) = svamp[Keccak-f[1600], pad10 ^* 1, r ]( N , d )
Keccak-f[1600] = Keccak-p[1600, 24]
c är kapaciteten
r är hastigheten = 1600 − c
N är inmatningsbitsträngen

SHA-3-instanser är drop-in-ersättningar för SHA-2, avsedda att ha identiska säkerhetsegenskaper.

SHAKE kommer att generera så många bitar från sin svamp som begärts, kallade XOFs (Extendable Output Functions). Till exempel kan SHAKE128(M, 256) användas som en hashfunktion med en bitström på 256 tecken med 128-bitars säkerhetsstyrka. Godtyckligt stora längder kan användas som pseudo-slumptalsgeneratorer. Alternativt kan SHAKE256(M, 128) användas som en hashfunktion med en 128-bitars längd och 128-bitars resistans.

Alla instanser lägger till några bitar till meddelandet, varav den längst till höger representerar domänseparationssuffixet. Syftet med detta är att säkerställa att det inte är möjligt att konstruera meddelanden som producerar samma hash-utdata för olika tillämpningar av Keccak-hashfunktionen. Följande domänseparationssuffix finns:

Ändelse	Menande
...0	reserverad för framtida bruk
01	SHA-3
...11	RawSHAKE
1111	SKAKA

Ytterligare instanser

I december 2016 publicerade NIST ett nytt dokument, NIST SP.800-185, som beskriver ytterligare SHA-3-härledda funktioner:

Exempel	Beskrivning
cSHAKE128( X , L , N , S )	En version av SHAKE som stöder explicit domänseparation via anpassningsparametrar.
cSHAKE256( X , L , N , S )
KMAC128( K , X , L , S )	En nyckelad hash-funktion baserad på Keccak. Kan även användas utan nyckel som vanlig hashfunktion.
KMAC256( K , X , L , S )
KMACXOF128( K , X , L , S )
KMACXOF256( K , X , L , S )
TupleHash128( X , L , S )	En funktion för att hasha tuplar av strängar. Utdata från denna funktion beror på både innehållet och sekvensen av inmatningssträngar.
TupleHash256( X , L , S )
TupleHashXOF128( X , L , S )
TupleHashXOF256( X , L , S )
ParallelHash128( X , B , L , S )	En funktion utformad för att utnyttja parallellism i moderna processorer för snabbare hash. Till skillnad från KangarooTwelve, använder inte reducerad rund Keccak.
ParallelHash256( X , B , L , S )
ParallelHashXOF128( X , B , L , S )
ParallelHashXOF256( X , B , L , S )

• X är den huvudsakliga indatabitsträngen. Den kan ha vilken längd som helst, inklusive noll.

• L är ett heltal som representerar den begärda utdatalängden i bitar.

• N är en funktionsnamnbitsträng som används av NIST för att definiera funktioner baserade på cSHAKE. När ingen annan funktion än cSHAKE önskas sätts N till den tomma strängen.

• S är en anpassningsbitsträng. Användaren väljer denna sträng för att definiera en variant av funktionen. När ingen anpassning önskas sätts S till den tomma strängen.

• K är en nyckelbitsträng av valfri längd, inklusive noll.

• B är blockstorleken i byte för parallell hashing. Det kan vara vilket heltal som helst så att 0 < B < 2 ²⁰⁴⁰ .

Senare utveckling

KangarooTwelve

Under 2016 introducerade samma team som gjorde SHA-3-funktionerna och Keccak-algoritmen snabbare reducerade rundor (reducerade till 12 och 14 omgångar, från de 24 i SHA-3) alternativ som kan utnyttja tillgängligheten av parallell exekvering på grund av att använda träd hashing : KangarooTwelve och MarsupilamiFourteen.

Dessa funktioner skiljer sig från ParallelHash, den FIPS-standardiserade Keccak-baserade parallelliserbara hashfunktionen, med avseende på parallelliteten, genom att de är snabbare än ParallelHash för små meddelandestorlekar.

Det minskade antalet rundor motiveras av den enorma kryptoanalytiska insatsen fokuserad på Keccak som inte gav några praktiska attacker på något i närheten av Keccak med tolv rundor. Dessa högre hastighetsalgoritmer är inte en del av SHA-3 (eftersom de är en senare utveckling), och är därför inte FIPS-kompatibla; men eftersom de använder samma Keccak-permutation är de säkra så länge det inte finns några attacker på SHA-3 reducerade till 12 omgångar.

KangarooTwelve är en version av Keccak med reducerad runda (från 24 till 12 omgångar) med högre prestanda och som påstår sig ha 128 bitars säkerhet samtidigt som den har prestanda så hög som 0,55 cykler per byte på en Skylake CPU. Denna algoritm är ett IETF RFC- utkast.

MarsupilamiFourteen, en liten variation på KangarooTwelve, använder 14 omgångar av Keccak-permutationen och hävdar 256 bitar av säkerhet. Observera att 256-bitars säkerhet inte är mer användbar i praktiken än 128-bitars säkerhet, men kan krävas av vissa standarder. 128 bitar är redan tillräckligt för att besegra brute-force-attacker på nuvarande hårdvara, så att ha 256-bitars säkerhet ger inget praktiskt värde, såvida inte användaren är orolig för betydande framsteg i hastigheten hos klassiska datorer . För motstånd mot kvantdatorer , se nedan.

KangarooTwelve och MarsupilamiFourteen är Extendable-Output-funktioner, liknande SHAKE, därför genererar de närbesläktade utdata för ett vanligt meddelande med olika utdatalängd (den längre utmatningen är en förlängning av den kortare utmatningen). Sådana egenskaper visas inte av hashfunktioner som SHA-3 eller ParallelHash (förutom XOF-varianter).

Farfalle-konstruktionen

Under 2016 släppte Keccak-teamet en annan konstruktion som heter Farfalle-konstruktion, och Kravatte, en instans av Farfalle som använder Keccak-p-permutationen, samt två autentiserade krypteringsalgoritmer Kravatte-SANE och Kravatte-SANSE

Sakura träd hashing

RawSHAKE är grunden för Sakura-kodningen för trädhashing, som inte har standardiserats ännu. Sakura använder suffixet 1111 för enstaka noder, motsvarande SHAKE, och andra genererade suffix beroende på trädets form.

Säkerhet mot kvantattacker

Det finns ett allmänt resultat ( Grovers algoritm ) att kvantdatorer kan utföra en strukturerad förbildsattack i ${\sqrt {2^{d}}}=2^{d/2}$ , medan en klassisk brute-force attack behöver 2 ^d . En strukturerad förbildsattack innebär en andra förbildsattack och därmed en kollisionsattack . En kvantdator kan också utföra en födelsedagsattack och därmed bryta kollisionsmotståndet, i ${\sqrt[{3}]{2^{d}}}=2^{d/3 }$ (även om det är omtvistat). Notera att den maximala styrkan kan vara $c/2$ , detta ger följande övre gränser för kvantsäkerheten för SHA-3:

Exempel	Säkerhetsstyrkor i bitar
Exempel	Kollision (Brassard et al.)	Kollision (Bernstein)	Förbild	2:a förbilden
SHA3-224( M )	74 2 ⁄ 3	112	112	112
SHA3-256( M )	85 1⁄3 _ _	128	128	128
SHA3-384( M )	128	192	192	192
SHA3-512( M )	170 2⁄3 _ _	256	256	256
SHAKE128( M , d )	min( d /3 128)	min( d /2 128)	≥min( d /2 128)	min( d /2 128)
SHAKE256( M , d )	min( d /3 256)	min( d /2 256)	≥min( d /2 256)	min( d /2 256)

Det har visat sig att Merkle–Damgård-konstruktionen , som den används av SHA-2, kollapsar och som följd är kvantkollisionsbeständig, men för svampkonstruktionen som används av SHA-3 ger författarna bevis endast för det fall då blockfunktionen f är inte effektivt inverterbar; Keccak-f[1600] är dock effektivt inverterbar, så deras bevis gäller inte.

Exempel på SHA-3-varianter

Följande hash-värden är från NIST.gov:

 SHA3-224("")  6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7  SHA3-256("")  a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a  SHA3-384("")  0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004  SHA3-512("")  a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26  SHAKE128("", 256)  7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26  SHAKE256("", 512)  46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

Att ändra en enskild bit gör att varje bit i utgången ändras med 50 % sannolikhet, vilket visar en lavineffekt :

 SHAKE128("Den kvicka bruna räven hoppar över den lata hunden", 256)  "  f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e  SHAKE128("Den snabba bruna räven hoppar över den bruna 128("Den kvicka 2 do 5) ", den kvicka 2 do 5  )  38be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Jämförelse av SHA-funktioner

I tabellen nedan betyder internt tillstånd antalet bitar som överförs till nästa block.

Jämförelse av SHA-funktioner
Algoritm och variant		Utdatastorlek (bitar)	Intern tillståndsstorlek (bitar)	Blockstorlek (bitar)	Omgångar	Operationer	Säkerhet mot kollisionsattacker (bitar)	Säkerhet mot längdförlängningsattacker (bitar)	Prestanda på Skylake (median cpb )		Först publicerad
Algoritm och variant		Utdatastorlek (bitar)	Intern tillståndsstorlek (bitar)	Blockstorlek (bitar)	Omgångar	Operationer	Säkerhet mot kollisionsattacker (bitar)	Säkerhet mot längdförlängningsattacker (bitar)	Långa meddelanden	8 byte	Först publicerad
MD5 (som referens)		128	128 (4 × 32)	512	64	Och, Xor, Eller, Rot, Lägg till (mod 2 ³² )	≤ 18 (krockar hittade)	0	4,99	55,00	1992
SHA-0		160	160 (5 × 32)	512	80	Och, Xor, Eller, Rot, Lägg till (mod 2 ³² )	< 34 (kollisioner hittades)	0	≈ SHA-1	≈ SHA-1	1993
SHA-1		160	160 (5 × 32)	512	80	Och, Xor, Eller, Rot, Lägg till (mod 2 ³² )	< 63 (kollisioner hittades)	0	3,47	52,00	1995
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	64	Och, Xor, Or, Rot, Shr, Add (mod 2 ³² )	112 128	32 0	7,62 7,63	84,50 85,25	2004 2001
	SHA-384	384	512 (8 × 64)	1024	80	Och, Xor, Or, Rot, Shr, Add (mod 2 ⁶⁴ )	192	128 (≤ 384)	5.12	135,75	2001
	SHA-512	512					256	0	5.06	135,50	2001
	SHA-512/224 SHA-512/256	224 256					112 128	288 256	≈ SHA-384	≈ SHA-384	2012
SHA-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	24	Och, Xor, Rot, Not	112 128 192 256	448 512 768 1024	8,12 8,59 11,06 15,88	154,25 155,50 164,00 164,00	2015
SHA-3	SHAKE128 SHAKE256	d (godtyckligt) d (godtyckligt)	1600 (5 × 5 × 64)	1344 1088	24	Och, Xor, Rot, Not	min( d /2, 128) min( d /2, 256)	256 512	7,08 8,59	155,25 155,50	2015

Optimerad implementering med AVX-512VL (dvs från OpenSSL , körs på Skylake-X- processorer) av SHA3-256 uppnår cirka 6,4 cykler per byte för stora meddelanden och cirka 7,8 cykler per byte när du använder AVX2 på Skylake -processorer. Prestanda på andra x86-, Power- och ARM-processorer beroende på instruktioner som används, och den exakta CPU-modellen varierar från cirka 8 till 15 cykler per byte, med vissa äldre x86-processorer upp till 25–40 cykler per byte.

Genomföranden

Nedan är en lista över kryptografibibliotek som stöder SHA-3:

Hårdvaruacceleration

Apple A13 ARMv8 sexkärniga SoC CPU-kärnor har stöd för att accelerera SHA-3 (och SHA-512) med hjälp av specialiserade instruktioner (EOR3, RAX1, XAR, BCAX) från ARMv8.2-SHA kryptotilläggsset.

Vissa programbibliotek använder vektoriseringsfaciliteter för CPU: er för att påskynda användningen av SHA-3. Till exempel kan Crypto++ använda SSE2 på x86 för att accelerera SHA3, och OpenSSL kan också använda MMX , AVX-512 eller AVX-512VL på många x86-system. Även POWER8- processorer implementerar 2x64-bitars vektorrotation, definierad i PowerISA 2.07, vilket på något sätt kan accelerera SHA-3-implementeringar. De flesta implementeringar för ARM använder inte Neon- vektorinstruktioner eftersom skalär kod är snabbare. ARM-implementeringar kan dock accelereras med SVE- och SVE2-vektorinstruktioner; dessa finns till exempel i Fujitsu A64FX CPU.

IBM z/Architecture stöder SHA-3 sedan 2017 som en del av Message-Security-Assist Extension 6. Processorerna stöder en komplett implementering av hela SHA-3 och SHAKE-algoritmerna via KIMD- och KLMD-instruktionerna med hjälp av en byggd hårdvaruassistansmotor in i varje kärna.

Användning i protokoll

Ethereum § Ether

Se även

Ethash – en annan Keccak-baserad hash

externa länkar