SHA

Secure Hash Algorithm ehk SHA on krüptograafiliste räsifunktsioonide tootepere, mis töötati välja Ameerika Ühendriikide Riiklikus Standardite ja Tehnoloogia Instituudis (NIST) koostöös Riikliku julgeolekuagentuuriga.

SHA algoritmide tooteperre kuuluvad SHA-0, SHA-1, SHA-2 ja SHA-3.

SHA-0 ja SHA-1

SHA-0 algoritmi algne nimi oli SHA, kuid uuemate sarnase põhimõttega algoritmide lisandumisel võeti kasutusele nimi SHA-0. 1993. aastal avaldati algse algoritmi edasiarendus SHA-1. Uues algoritmis oli parandatud varem leitud turvaauk, kusjuures SHA-0 ja SHA-1 erinevad ainult ühe tehte võrra. Praeguseks on SHA-1 algoritm kuulutatud ebaturvaliseks ning NIST soovitab riigiorganisatsioonidel kasutada uuemaid SHA räsifunktsioone^[1].

Microsoft^[2], Google^[3] ja Mozilla^[4] lõpetasid 2017. aastast brauserites SHA-1 kasutavate SSL sertifikaatide toetamise.

SHA-1 on kasutusel Giti^[5] ja Mercuriali versioonihaldustarkvaras andmete terviklikkuse kontrollimise eesmärgil.

SHA-2

SHA-2 perekonda kuuluvad räsifunktsioonid SHA-256 ja SHA-512. SHA-256 kasutab 32-bitiseid sõnu ning SHA-512 64-bitiseid sõnu.

Rakendused

SHA-2 räsifunktsioon on kasutusel sellistes rakendustes ja protokollides nagu TLS, SSL, PGP, SSH, S/MIME ja IPsec.

SHA-256 funktsiooni kasutatakse Debian GNU ja Linuxi tarkvarapakkide autentimisel^[6] ja DKIM sõnumite allkirjastamise standardis. SHA-512 on kasutusel süsteemis, mis autendib arhiivitud videoid Rwanda genotsiidi tribunalist^[7]. Linuxi ja UNIXi arendajatel on kavas paroolide räsimiseks võtta kasutusele SHA-256 ja SHA-512^[8].

Bitcoin kasutab SHA-256 funktsiooni tehingute verifitseerimiseks ja toimingutõestuse arvutamisel.

SHA-2 räsifunktsiooni ühe iteratsiooni skeem

Teadaolevad rünnakud

Artikkel	Aasta	Ründemeetod	Rünnak	Variant	Tsükleid	Keerukus
New Collision Attacks Against Up To 24-step SHA-2^[9]	2008	Deterministlik	Kollisioon	SHA-256	24/64	2^28.5
New Collision Attacks Against Up To 24-step SHA-2^[9]	2008	Deterministlik	Kollisioon	SHA-512	24/80	2^32.5
Preimages for step-reduced SHA-2^[10]	2009	Keskelkohterünne	Originaalirünne	SHA-256	42/64	2^251.7
				SHA-256	43/64	2^254.9
				SHA-512	42/80	2^502.3
				SHA-512	46/80	2^511.5
Advanced meet-in-the-middle preimage attacks^[11]	2010	Keskelkohterünne	Originaalirünne	SHA-256	42/64	2^248.4
Advanced meet-in-the-middle preimage attacks^[11]	2010	Keskelkohterünne	Originaalirünne	SHA-512	42/80	2^494.6
Higher-Order Differential Attack on Reduced SHA-256^[12]	2011	Diferentsiaalne krüptoanalüüs	Pseudokollisioon	SHA-256	46/64	2¹⁷⁸
Higher-Order Differential Attack on Reduced SHA-256^[12]	2011	Diferentsiaalne krüptoanalüüs	Pseudokollisioon	SHA-256	33/64	2⁴⁶
Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family^[13]	2011	Keskelkohterünne	Originaalirünne	SHA-256	45/64	2^255.5
			Originaalirünne	SHA-512	50/80	2^511.5
			Pseudo-originaalirünne	SHA-256	52/64	2²⁵⁵
			Pseudo-originaalirünne	SHA-512	57/80	2⁵¹¹
Improving Local Collisions: New Attacks on Reduced SHA-256^[14]	2013	Diferentsiaalne krüptoanalüüs	Kollisioon	SHA-256	31/64	2^65.5
	2013	Diferentsiaalne krüptoanalüüs	Pseudokollisioon	SHA-256	38/64	2³⁷
Branching Heuristics in Differential Collision Search with Applications to SHA-512^[15]	2014	Heuristiline diferentsiaalne krüptoanalüüs	Pseudokollisioon	SHA-512	38/80	2^40.5
Analysis of SHA-512/224 and SHA-512/256^[16]	2016	Diferentsiaalne krüptoanalüüs	Kollisioon	SHA-256	28/64	praktiline
			Kollisioon	SHA-512	27/80	praktiline
			Pseudokollisioon	SHA-512	39/80	praktiline

SHA-3

SHA-3 loodi Riikliku Standardite ja Tehnoloogia Instituudi poolt peetud avaliku konkursi käigus. Konkursi komisjoni poolt väljavalituks osutunud räsialgoritmi Keccak loojateks on Guido Bertoni, Joan Daemen, Michaël Peeters ja Gilles Van Assche^[17]. SHA-3 loomise eesmärk ei olnud SHA-2 väljavahetamine, vaid sellele alternatiivi pakkumine juhul kui SHA-2 algoritmis avastatakse turvaauke.

SHA-3 perekonda kuuluvad laiendatava väljundiga räsifunktsioonid (ingl extendable-output function, XOF) SHAKE128 ja SHAKE256, mille väljundi suurus on vabalt muudetav. SHAKE-funktsioonid on esimesed Riikliku Standardite ja Tehnoloogia Instituudi poolt standardiseeritud XOF funktsioonid^[18].

SHA funktsioonide võrdlus

SHA funktsioonide võrdlus
vaata
redigeeri
Algoritmi variant		Väljundi suurus (bittides)	Sisemise oleku suurus (bittides)	Ploki suurus (bittides)	Maksimaalne sisendi suurus (bittides)	Tsüklite arv	Tehted	Turvalisus (bittides)	Arvutuskiirus [1] (MiB/s)
MD5 (võrdluseks)		128	128 (4 × 32)	512	Piiramatu^[19]	64	And, Xor, Rot, Add (mod 2³²), Or	<64 (on leitud kollisioone)	335
SHA-0		160	160 (5 × 32)	512	2⁶⁴ − 1	80	And, Xor, Rot, Add (mod 2³²), Or	<80 (on leitud kollisioone)	-
SHA-1		160	160 (5 × 32)	512	2⁶⁴ − 1	80	And, Xor, Rot, Add (mod 2³²), Or	<80 (teoreetiline rünnak^[20])	192
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	2⁶⁴ − 1	64	And, Xor, Rot, Add (mod 2³²), Or, Shr	112 128	139
SHA-2	SHA-384 SHA-512 SHA-512/224 SHA-512/256	384 512 224 256	512 (8 × 64)	1024	2¹²⁸ − 1	80	And, Xor, Rot, Add (mod 2⁶⁴), Or, Shr	192 256 112 128	154
SHA-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	Piiramatu^[21]	24^[22]	And, Xor, Rot, Not	112 128 192 256	-
SHA-3	SHAKE128 SHAKE256	d (arbitraarne) d (arbitraarne)	1600 (5 × 5 × 64)	1344 1088	Piiramatu^[21]	24^[22]	And, Xor, Rot, Not	min(d/2, 128) min(d/2, 256)	-

Viited

↑ http://csrc.nist.gov/groups/ST/hash/policy.html
↑ "Arhiivikoopia". Originaali arhiivikoopia seisuga 5. oktoober 2016. Vaadatud 5. oktoobril 2017.{{netiviide}}: CS1 hooldus: arhiivikoopia kasutusel pealkirjana (link)
↑ https://groups.google.com/a/chromium.org/d/msg/blink-dev/2-R4XziFc7A/i_JipRRJoDQJ
↑ https://blog.mozilla.org/security/2014/09/23/phasing-out-certificates-with-sha-1-based-signature-algorithms/
↑ https://www.youtube.com/watch?v=4XpnKHJAok8
↑ https://web.archive.org/web/20111107215111/http://google.com/codesearch/p?hl=en
↑ http://www.nytimes.com/2009/01/27/science/27arch.html
↑ http://people.redhat.com/drepper/sha-crypt.html
↑ Somitra Kumar Sanadhya & Palash Sarkar (2008). "New Collision Attacks Against Up To 24-step SHA-2" (PDF). IACR Cryptology ePrint Archive. 2008:270.
↑ Kazumaro Aoki; Jian Guo; Krystian Matusiewicz; Yu Sasaki & Lei Wang (2009). "Preimages for step-reduced SHA-2". Advances in Cryptology - ASIACRYPT 2009. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 5912: 578–597. DOI:10.1007/978-3-642-10366-7_34. ISBN 978-3-642-10366-7. ISSN 0302-9743.
↑ Jian Guo; San Ling; Christian Rechberger & Huaxiong Wang (2010). "Advanced meet-in-the-middle preimage attacks: First results on full Tiger, and improved results on MD4 and SHA-2" (PDF). Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 6477: 56–75. DOI:10.1007/978-3-642-17373-8_4. ISBN 978-3-642-17373-8. ISSN 0302-9743.
↑ Mario Lamberger & Florian Mendel (2011). "Higher-Order Differential Attack on Reduced SHA-256" (PDF). IACR Cryptology ePrint Archive. 2011:37.
↑ Dmitry Khovratovich, Christian Rechberger & Alexandra Savelieva (2011). "Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family" (PDF). IACR Cryptology ePrint Archive. 2011:286.
↑ Florian Mendel; Tomislav Nad; Martin Schläffer (2013). "Improving Local Collisions: New Attacks on Reduced SHA-256". Advances in Cryptology – EUROCRYPT 2013. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 7881: 262–278. DOI:10.1007/978-3-642-38348-9_16. ISBN 978-3-642-38348-9. ISSN 0302-9743.
↑ Maria Eichlseder and Florian Mendel and Martin Schläffer (2014). "Branching Heuristics in Differential Collision Search with Applications to SHA-512" (PDF). IACR Cryptology ePrint Archive. 2014:302.
↑ Christoph Dobraunig; Maria Eichlseder & Florian Mendel (2016). "Analysis of SHA-512/224 and SHA-512/256" (PDF). {{cite journal}}: viitemall journal nõuab parameetrit |journal= (juhend)
↑ http://csrc.nist.gov/groups/ST/hash/sha-3/
↑ http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
↑ "The MD5 Message-Digest Algorithm". Vaadatud 18.04.2016.
↑ "The SHAppening: freestart collisions for SHA-1". Vaadatud 5.11.2015.
↑ "The Sponge Functions Corner". Vaadatud 27.01.2016.
↑ "The Keccak sponge function family". Vaadatud 27.01.2016.

[Ojr9l-1] ttp://csrc.nist.gov/groups/ST/hash/policy.html

[sC4pT-2] "Arhiivikoopia". Originaali arhiivikoopia seisuga 5. oktoober 2016. Vaadatud 5. oktoobril 2017.{{netiviide}}: CS1 hooldus: arhiivikoopia kasutusel pealkirjana (link)

[4a6q7-3] ttps://groups.google.com/a/chromium.org/d/msg/blink-dev/2-R4XziFc7A/i_JipRRJoDQJ

[3YeTU-4] ttps://blog.mozilla.org/security/2014/09/23/phasing-out-certificates-with-sha-1-based-signature-algorithms/

[BVEek-5] ttps://www.youtube.com/watch?v=4XpnKHJAok8

[6UD4j-6] ttps://web.archive.org/web/20111107215111/http://google.com/codesearch/p?hl=en

[Y5JNu-7] ttp://www.nytimes.com/2009/01/27/science/27arch.html

[WLacf-8] ttp://people.redhat.com/drepper/sha-crypt.html

[collision-sanadhya-9] Somitra Kumar Sanadhya & Palash Sarkar (2008). "New Collision Attacks Against Up To 24-step SHA-2" (PDF). IACR Cryptology ePrint Archive. 2008:270.

[preimage-merged-10] Kazumaro Aoki; Jian Guo; Krystian Matusiewicz; Yu Sasaki & Lei Wang (2009). "Preimages for step-reduced SHA-2". Advances in Cryptology - ASIACRYPT 2009. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 5912: 578–597. DOI:10.1007/978-3-642-10366-7_34. ISBN 978-3-642-10366-7. ISSN 0302-9743.

[preimage-gou-11] Jian Guo; San Ling; Christian Rechberger & Huaxiong Wang (2010). "Advanced meet-in-the-middle preimage attacks: First results on full Tiger, and improved results on MD4 and SHA-2" (PDF). Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 6477: 56–75. DOI:10.1007/978-3-642-17373-8_4. ISBN 978-3-642-17373-8. ISSN 0302-9743.

[collision-lamberger-12] Mario Lamberger & Florian Mendel (2011). "Higher-Order Differential Attack on Reduced SHA-256" (PDF). IACR Cryptology ePrint Archive. 2011:37.

[preimage-khov-13] Dmitry Khovratovich, Christian Rechberger & Alexandra Savelieva (2011). "Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family" (PDF). IACR Cryptology ePrint Archive. 2011:286.

[collision-mendel-14] Florian Mendel; Tomislav Nad; Martin Schläffer (2013). "Improving Local Collisions: New Attacks on Reduced SHA-256". Advances in Cryptology – EUROCRYPT 2013. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 7881: 262–278. DOI:10.1007/978-3-642-38348-9_16. ISBN 978-3-642-38348-9. ISSN 0302-9743.

[collision-eichlseder-15] Maria Eichlseder and Florian Mendel and Martin Schläffer (2014). "Branching Heuristics in Differential Collision Search with Applications to SHA-512" (PDF). IACR Cryptology ePrint Archive. 2014:302.

[y1xSE-16] Christoph Dobraunig; Maria Eichlseder & Florian Mendel (2016). "Analysis of SHA-512/224 and SHA-512/256" (PDF). {{cite journal}}: viitemall journal nõuab parameetrit |journal= (juhend)

[zixjs-17] ttp://csrc.nist.gov/groups/ST/hash/sha-3/

[ONj46-18] ttp://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

[VeEGz-19] "The MD5 Message-Digest Algorithm". Vaadatud 18.04.2016.

[7WIHr-20] "The SHAppening: freestart collisions for SHA-1". Vaadatud 5.11.2015.

[CgKgi-21] "The Sponge Functions Corner". Vaadatud 27.01.2016.

[eztTP-22] "The Keccak sponge function family". Vaadatud 27.01.2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]