Изворни код странице SHA-3

'''SHA-3''' ('''Сигурни хеш алгоритам 3''') је последњи стандард из породице Сигурних хеш алгоритама, као део шире фамилије алгоритама Кечак ({{јез-eng|Keccak}}).<ref name="nist" /><ref name="drdobbs">{{cite web|url=http://www.drdobbs.com/security/keccak-the-new-sha-3-encryption-standard/240154037|title=Keccak: The New SHA-3 Encryption Standard|last=Cruz|first=José R.C.|date=7. 5. 2013|website=Dr. Dobbs|url-status=live}}</ref>  који су креирали Јоан Дамен ({{јез-nl|Joan Daemen}}), Гвидо Бертони ({{јез-nl|Guido Bertoni}}), Михаел Питерс ({{јез-nl|Michaël Peeters}}) и Жил Ван Аш ({{јез-nl|Gilles Van Assche}}), а објавио NIST 2015. године. <ref name="nist.gov">{{cite web|url=https://www.nist.gov/itl/csd/201508_sha3.cfm|title=NIST Releases SHA-3 Cryptographic Hash Standard|last=Hernandez|first=Paul|date=5. 8. 2015|publisher=[[NIST]]|url-status=live}}</ref><ref>{{cite journal|last=Dworkin|first=Morris J.|date=4. 8. 2015|title=SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions|url=https://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061|journal=Federal Inf. Process. STDS. (NIST FIPS) – 202}}</ref> Аутори Кечака су предложили и друге намене овог алгоритма, као што су проточна шифра, [[аутентификовано шифровање|шифровање са аутентикацијом]], хеш-стабло предвиђено за брзи рад на неким архитектурама, <ref>{{cite web|title=The Keccak sponge function family: Specifications summary |url=http://keccak.noekeon.org/specs_summary.html |accessdate=11. 5. 2011|author1=Guido Bertoni |author2=Joan Daemen |author3=Michaël Peeters |author4=Gilles Van Assche}}</ref><ref>{{Cite web|url=https://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf|title=Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition|date=новембар 2012|doi=10.6028/NIST.IR.7896|url-status=live|access-date=29. 2. 2020}} Sections 5.1.2.1 (mentioning "tree mode"), 6.2 ("other features", mentioning authenticated encryption), and 7 (saying "extras" may be standardized in the future).</ref> и AEAD (аутентификована шифра са придруженим подацима) шифре Keyak и Ketje.<ref name="ketje">{{Cite web|url=https://competitions.cr.yp.to/round1/ketjev1.pdf|title=CAESAR submission: Ketje v1|last=Bertoni|first=Guido|last2=Daemen|first2=Joan|date=13. 3. 2014|url-status=live|access-date=29. 2. 2020|last3=Peeters|first3=Michaël|last4=Van Assche|first4=Gilles|last5=Van Keer|first5=Ronny}}</ref><ref name="keyak">{{Cite web|url=https://competitions.cr.yp.to/round1/keyakv1.pdf|title=CAESAR submission: Keyak v1|last=Bertoni|first=Guido|last2=Daemen|first2=Joan|date=13. 3. 2014|url-status=live|access-date=29. 2. 2020|last3=Peeters|first3=Michaël|last4=Van Assche|first4=Gilles|last5=Van Keer|first5=Ronny}}</ref>
Иако се по имену наставља на стандарде SHA-1 и SHA-2, сличне алгоритму MD5, унутрашња организација алгоритма SHA3-3 битно је другачија.

[[Алгоритам]] у току рада имитира [[сунђер конструкција|сунђер конструкцију]] <ref name="sponge"/> – упија (апсорбује) било коју количину података и избацује тражену количину података, понашајући се као псеудослучајна функција, која зависи од свих претходних улаза. Тиме се омогућава велика флексибилност.

[[NIST]] за сада не планира да укине [[SHA-2]]. Сврха  SHA-3 је да може директно да замени SHA-2 у тренутним применама, када је то потребно, и повећа робустност  NIST-овог скупа хеш алгоритама. <ref name="FRnotice">{{cite web |title=Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family [U.S. Federal Register Vol. 72 No. 212)] |url=http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf |date=2. 11. 2007 |url-status=dead |archive-url=https://web.archive.org/web/20110331175556/http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf |archive-date=31. 03. 2011 |access-date=18. 7. 2017 |df=mdy-all }}</ref> Аутори алгоритма Кечак предлажу употребу брже функције, KangarooTwelve, са прилагођеним параметрима  и ново дрво хеширања, која је ефикасније за кратке поруке.

==Историја==
Неколико успешно пронађених колизија за хеш алгоритме [[MD5]], [[SHA-0]] и [[SHA-1]] <ref>{{cite web|url=https://shattered.io/static/shattered.pdf|title=The first collision for full SHA-1|last1=Stevens|first1=Marc|last2=Bursztein|first2=Elie|url-status=live|accessdate=23. 2. 2017|last3=Karpman|first3=Pierre|last4=Albertini|first4=Ange|last5=Markov|first5=Yarik}}</ref><ref>{{cite web|last1=Leurent|first1=Gaëtan|last2=Peyrin|first2=Thomas|title= SHA-1 is a Shambles|url=https://sha-mbles.github.io/|accessdate=8. 1. 2020}}</ref> током 2004-2005 навело је [[NIST]] да организује 2006. године такмичење за нови хеш стандард, SHA-3. С обзиром на то да није откривен успешан напад на [[SHA-2]], SHA-3 је потребан само као алтернатива.  

Алгоритам Кечак је 2. октобра 2012. године проглашен победником такмичења <ref name="nist">{{cite web|url=https://www.nist.gov/itl/csd/sha-100212.cfm|title=NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition|date=2. 10. 2012|publisher=[[NIST]]|accessdate=2. 10. 2012}}</ref> на коме је учествовао 51 кандидат. 
Његови аутори су Гвидо Бертони, Јоан Дамен, Михаел Питерс и  Жил Ван Аш. Базиран је на ранијим хеш функцијама, Panama и RadioGatun, који је представљен 2006. године. <ref>{{cite web|url=http://keccak.noekeon.org/TheRoadFromPanamaToKeccak.pdf|title=The road from Panama to Keccak via RadioGatún|last=Bertoni|first=Guido|last2=Daemen|first2=Joan|url-status=live|access-date=29. 2. 2020|last3=Peeters|first3=Michaël|last4=Van Assche|first4=Gilles}}</ref> Референтна реализација овог алгоритма је [[Отворен код|отворени код]]. <ref>[https://keccak.team/obsolete/KeccakReferenceAndOptimized-3.2.zip KeccakReferenceAndOptimized-3.2.zip] mainReference.c ''"The Keccak sponge function, designed by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. For more information, feedback or questions, please refer to our website: http://keccak.noekeon.org/Implementation{{dead link|date=април 2018 |bot=InternetArchiveBot |fix-attempted=yes }} by the designers, hereby denoted as "the implementer". To the extent possible under law, the implementer has waived all copyright and related or neighboring rights to the source code in this file. https://creativecommons.org/publicdomain/zero/1.0/"''</ref>
У току такмичења било је дозвољено такмичарима да "дотерују" своје алгоритме и тако отклоне проблеме откривене у међувремену.

Алгоритам Кечак имао је неколико промена: <ref>{{Cite web|url=https://keccak.team/2009/version_2.0.html|title=Keccak parameter changes for round 2|date=22. 9. 2009|website=Keccak Team|url-status=live|archive-url=https://web.archive.org/web/20171113003333/https://keccak.team/2009/version_2.0.html|archive-date=13. 11. 2017|access-date=29. 2. 2020}}</ref><ref>{{cite web|url=http://keccak.noekeon.org/version_3.0.html|title=Simplifying Keccak's padding rule for round 3|date=17. 1. 2011|website=Keccak Team|url-status=live|access-date=29. 2. 2020}}</ref>
* број рунди је повећан са {{nowrap|12+l}} на {{nowrap|12+2l}}, ради конзервативније гаранције
* допуњавање поруке је, уместо сложене схеме, замењено једноставним низом бита 10<sup>*</sup>1
* параметар r је повећан до границе безбедности, уместо ранијег заокруживања на најближи степен двојке

Године 2014. [[NIST]] објављује нацрт FIPS 202 “Стандард SHA-3 : Хеш базиран на пермутацијама  и функцијама са проширивим излазима” <ref>{{cite web | url=http://csrc.nist.gov/groups/ST/hash/sha-3/sha-3_standardization.html | title=SHA-3 standardization | publisher=NIST | accessdate=16. 4. 2015}}</ref>, који је годину дана касније, 5. августа 2015. године, одобрен и проглашен новим стандардом.<ref>{{cite web|url=https://federalregister.gov/a/2015-19181|title=Federal Information Processing Standards: Permutation-Based Hash and Extendable-Output Functions, etc.|author=National Institute of Standards and Technology|date=5. 8. 2015|url-status=live|accessdate=5. 8. 2015}}</ref>

==Конструкција==
[[Image:SpongeConstruction.svg|thumb|upright=1.35|right|alt=Illustration of the sponge construction |Сунђер конструкција за хеш функције. ''P<sub>i</sub>'' су улази, ''Z<sub>i</sub>'' су излази.]]
Хеш функције породице SHA-3  имају структуру која подсећа на сунђер <ref name="sponge">{{cite web |url=http://sponge.noekeon.org/ |title=Sponge Functions |publisher=Ecrypt Hash Workshop 2007 |authors=Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche}}</ref>, улазни подаци се најпре упијају у сунђер, а онда се излазни подаци истискују из њега.  У фази упијања, блокови порука се XOR-ују са подскупом стања, а затим  се трансформишу узајамно једнозначном функцијом f. У фази истискивања, излазни блокови се читају из истог подскупа стања, при чему се после сваког ишчитавања примењује функција f. Величина дела стања које се пише и чита  назива се  "брзина” ({{јез-eng|rate}}, ознака r), а величина дела стања које је остало непромењено при улазу/излазу назива се “капацитет”  ({{јез-eng|capacity}}, ознака c). Капацитет  одређује сигурност хеш алгоритма. Процена је да ниво сигурности алгоритма ([[логаритам]] за основу 2 броја покушаја приликом напада заснованог на рођенданском парадоксу) једнак половини капацитета.

Нека је  <math>N</math> улазна ниска, <math>pad</math> функција за допуњавање, <math>f</math> функција која трансформише блокове од <math>b</math> бита, брзине <math>r</math> и нека је дужина излаза <math>d</math>. Тада је капацитет <math>c = b - r</math> и сунђер <math>Z = \text{sponge}[f,pad,r](N,d)</math>, на излазу даје битску ниску <math>Z</math> дужине <math>d</math>, и ради на следећи начин: <ref name="fips202">{{Cite web|url=https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf|title=SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions|last=[[NIST]]|date=август 2015|doi=10.6028/NIST.FIPS.202|url-status=live|access-date=29. 2. 2020}}</ref>

* Допунити улазну ниску ''N'' помоћу функције pad, тако да се добије допуњена ниска битова ''P'' чија је  дужина дељива са  r; нека је ''n'' количник дужине ''P'' и броја ''r''
* Поделити P  на n блоковa дужине r ''P''<sub>0</sub>, ''P''<sub>1</sub>…''P''<sub>''n''-1</sub>
*  Иницијализовати стање S ниском нула дужине b
* Упијање улаза у стање: за сваки блок ''P''<sub>''i''</sub>:
**Допунити ''P''<sub>''i''</sub> са c нула на крају, тако да је нова дужина b
** Извршити операцију [[XOR]] са ''P''<sub>''i''</sub> и S
** Применити функцију пермутације на добијени резултат
* Иницијализовати Z празном ниском
* Фаза истискивања: све док је дужина Z мања од d (d је дужина вредности хеш функције):
** додати првих r битова стања S на ниску Z
** ако је дужина  Z мања од d, применом функцијeе f формирати ново стање C 
* скратити Z на d битова

Због чињенице да стање S садржи  додатних c битова, алгоритам је отпоран на нападе проширењем дужине ({{јез-eng|length extension attack}}), којима су подложни алгоритми [[SHA-1]] и [[SHA-2]].

У алгоритму стање S је низ од  {{nowrap|5 × 5}}  речи дужине ''w (w = 64), b = 5x5xw ='' укупно 1600  битова. Алгоритам Кечак такође може да користи мање дужине - степене двојке, од ''w=1'' до ''w=32'', за тестирање криптоаналитичких напада и у неким практичним, лакшим апликацијама. <ref name="ketje"/><ref name="keyak"/>

За инстанце SHA-3-224, SHA-3-256, SHA-3-384 и SHA-3-512, r је веће од d, тако да нису потребне додатне примене функције f у фази истискивања, водећих d битова су жељени хеш, док је код SHAKE-128 и SHAKE-256 дозвољена произвољна излазна дужина.

==Допуњавање==

Допуњавање је неопходно да би се обезбедило да дужина поруке буде дељива са r.

Aлгоритам SHA-3 допуњава поруку низом бита: јединица, па 0 или више нула (највише r-1 нула), па јединица.
Максимални низ од r-1 нула се додаје ако је последњи блок поруке дуг r-1.

Два јединице се додају и у случају када је дужина поруке већ дељива са r. <ref name="fips202"/>{{rp|5.1}} У том  случају, додаје се наредни блок који почиње и који се завршава јединицом, између којих се налазе  r-2 нуле. На овај начин се постиже да порука чија је дужина дељива са r, а која се завршава низом бита који изгледа као низ за допуњавање, не даје исту хеш вредност као порука са одстрањеним делом која личи  на допуњавање.

Прва додата јединица је неопходна да би се разликовале хеш вредности порука које се разликују само по броју  нула на својим крајевима. Позиција последње јединице указује на то која је брзина r искоришћена. 

==Трансформација блока - функција f==

Трансформација блока f користи [[XOR]], [[AND]] и [[NOT]] операције и дизајнирана је за лаку имплементацију и у софтверу и у хардверу.  Дефинисана је за речи чија је дужина степен двојке, {{math|1=''w'' = 2<sup>''ℓ''</sup>}} бита. Основна имплементација ради са 64-битне речи, где је ''l=6''.

Стање S се може представити као тродимензионална матрица битова величине  ''5x5xw''. 

Тада је елемент матрице ''а[i][j][k]'' бит улаза са редним бројем ''(5i + j) * w + k''. При томе су i, j, k редом индекси врсте, односно колоне, односно бита. Са индексима се рачуна по модулу 5 за прва два индекса, односно по модулу w за трећи индекс.

Основна блок пермутација састоји се од ''12 + 2l'' рунди, од којих се свака састоји од наредних пет корака, у којима се нова матрица а′ добија од старе матрице а:

;Koрак {{mvar|θ}} (theta)
:Нека је парност неког скупа бита једнака вредности XOR-a тих бита.
:За све тројке (i, j, k) ставити {{math|''a''[''i'']['' j''][''k''] ← ''a''[''i'']['' j''][''k''] ⊕ парност(a[0...4]['' j''−1][''k'']) ⊕ парност(a[0...4]['' j''+1][''k''−1])}}

;Корак {{mvar|ρ}} (rho) – битска ротација
:За свaко t такво да је {{math|0 ≤ ''t'' < 24}} ставити {{math|''a''[''i'']['' j''][''k''] ← ''a''[''i'']['' j''][''k''−(''t''+1)(''t''+2)/2]}}, где је  <math>\begin{pmatrix} i \\ j \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 0 \end{pmatrix}^t \begin{pmatrix} 0 \\ 1 \end{pmatrix}</math>

;Корак {{mvar|π}} (pi) - пермутација 25 речи
:Пермутовати 25 речи, тако да {{math|''a''[''j''][2''i''+3''j''] ← ''a''['' i''][''j'']}}


;Корак {{mvar|χ}} (chi)
:За све тројке (i,j,k) такве да је  0≤i<5, 0≤j<5 и 0≤k<w ставити {{math|''a''[''i'']['' j''][''k''] ← ''a''[''i'']['' j''][''k''] ⊕ (¬''a''[''i'']['' j''+''1''][''k''] &amp; ''a''[''i'']['' j''+''2''][''k''])}}
:Овај корак је једина нелинеарна трансформација у оквиру алгоритма SHA-3.   

;Корак {{mvar|ι}} (iota)
:У овом кораку се користи константни низ rc[0...255] који се добија из померачког регистра са линеарном спрегом дужине 8 на следећи начин:

:Ако је  t mod 255 = 0, врати  1.
:Нека је  R = 10000000.
:За  i од 1 до t mod 255, нека је : 
:R = 0 || R;
:R[0] = R[0] ⊕ R[8]; 
:R[4] = R[4] ⊕ R[8];
:R[5] = R[5] ⊕ R[8];
:R[6] = R[6] ⊕ R[8]; 
:R = ''Trunc<sub>8</sub>[R]''
:Вратити R[0]

'''Алгоритам {{mvar|ι}} (A, n)'''
Елементи низа rc користе се на различите начине за модификацију матрице а у зависности од редног броја рунде n 

** За све тројке(i,j,k) такве да је  0≤i<5, 0≤j<5 и 0≤k<w ,нека је а′[i,j,k]= а[i,j,k]
** Нека је  RC=0<sup>''w''</sup>
** За j од 0 до l, нека је  RC[2<sup>''j''</sup> - 1]=rc(j+7n)
** За све k тако да је  0≤k<w  нека је  a′[0, 0,k]=a′[0, 0,k] ⊕ RC[z].

'''Трансформација f у алгоритму SHA-3'''

Улаз: стање S дужине b, број рунди  n
Излаз: ниска  S′ дужине b

* претворити S u низ a
* за n од ''12+2l – ''n'' до ''12+2l – 1'', нека ''a=Rnd(a, n)'', где је ''Rnd(a, n) = {{mvar|ι}}({{mvar|χ}}({{mvar|π}}({{mvar|ρ}}({{mvar|θ}}(a)))), n)''.
* Претворити  a y ниску S′ дужине  b
* Вратити S′

==Брзина==
На брзину израчунавања хеш вредности дугачких порука највише утиче време за израчунавање функције f и операције XOR стања S са допуњеним  ''P''<sub>''i''</sub>. Довољно је операцију XOR извршити са првих ''r'' битова, јер су последњих c битова нуле. Мање ''r'', a самим тим,  веће ''c'', даје мању ефикасност, али већу сигурност хеширања јер ће мање битова порукe бити XOR-овано са стањем пре сваке примене рачунски сложене функције f.
Софтверска реализација SHA3-512 је око два пута спорија од реализације SHA2-512 <ref name="slow">{{cite web|url=http://keccak.noekeon.org/is_sha3_slow.html|title=Keccak Team|website=keccak.noekeon.org}}</ref> . 
С друге стране, хардверске реализације SHA-3 знатно су брже од реализације свих других финалиста конкурса.

==Инстанце==
Oригинални алгоритам Кечак има много опционих параметара, како би се осигурао оптималан однос снаге и брзине криптографије за специфичну примену алгоритма на одређеној платформи. Опционе вредности су: величина блока података, величина стања алгоритма, број рунди у функцији f() и друге.

У стандардy су уведене „Прошириве излазне функције“ (XOF, Extendable Output Functions) SHAKE128 и SHAKE256, за које се порука допуњује „суфиксом“ од 2 или 4 бита, у зависности од врсте функције.

{| class="wikitable"
! rowspan="2" | Инстанца
! rowspan="2" | Дужина излаза ''d''
! rowspan="2" | Брзина ''r''
! rowspan="2" | Капацитет  ''c''
! rowspan="2" | Дефиниција
! colspan="3" | Сигурност у битовима
|-
! Koлизија!! Одређивање поруке на основу хеша!! Одређивање поруке са истим хешом као дата порука
|-
| SHA3-224(''M'') || 224 ||1152||448|| Keccak[448](''M'' &#124;&#124; 01, 224) || 112 || 224 || 224
|-
| SHA3-256(''M'') || 256 ||1088||512|| Keccak[512](''M'' &#124;&#124; 01, 256) || 128 || 256 || 256
|-
| SHA3-384(''M'') || 384 ||832||768|| Keccak[768](''M'' &#124;&#124; 01, 384) || 192 || 384 || 384
|-
| SHA3-512(''M'') || 512 ||576||1024|| Keccak[1024](''M'' &#124;&#124; 01, 512) || 256 || 512 || 512
|-
| SHAKE128(''M'', ''d'') || ''d'' || 1344||256||Keccak[256](''M'' &#124;&#124; 1111, ''d'') || min(''d''/2,128)||&ge;min(''d'',128)||min(''d'',128)
|-
| SHAKE256(''M'', ''d'') || ''d'' ||1088||512|| Keccak[512](''M'' &#124;&#124; 1111, ''d'') || min(''d''/2,256)||&ge;min(''d'',256)||min(''d'',256)
|}

У табели су коришћене следеће ознаке:

* Keccak[''c''](''N'', ''d'') = sponge[Keccak-f[1600], pad10<sup>*</sup>1, ''r''](''N'', ''d'')
* Keccak-f[1600] = Keccak-p[1600, 24]
* c је капацитет
* r је ''брзина = 1600 − c''

SHAKE128(М, 256) се може користити као хеш функција са дужином хеша од 256 битова и укупном мером сигурности 128 битова. Све инстанце додају неке битове поруци, чији крајњи десни део представља суфикс за раздвајање домене ({{јез-eng|domain separation suffix}}), да би се онемогућило конструисање порука које дају исти хеш за различите примене Keчак хеш функције. 

За сада су дефинисани следећи суфикси:
Суфикс ...0 је резервисан за будуће примене, 01 је SHA-3, a …11 je RawSHAKE.

==Додатне инстанце==
У децембру 2016. NIST је објавио нови документ NIST SP.800-185, који описује додатне  SHA-3 изведене функције:

{| class="wikitable"
! Инстанца !! Опис
|-
| cSHAKE128(''X'', ''L'', ''N'', ''S'') ||rowspan="2" |Верзија SHAKE која подржава експлицитно одвајање домена помоћу параметара
|-
| cSHAKE256(''X'', ''L'', ''N'', ''S'')
|-
| KMAC128(''K'', ''X'', ''L'', ''S'') ||rowspan="4" |Хеш функција са кључем заснована на алгоритму Кечак
|-
| KMAC256(''K'', ''X'', ''L'', ''S'')
|-
| KMACXOF128(''K'', ''X'', ''L'', ''S'')
|-
| KMACXOF256(''K'', ''X'', ''L'', ''S'')
|-
| TupleHash128(''X'', ''L'', ''S'') ||rowspan="4" |Функција за хеширање [[торки]], чији излаз зависи од садржаја и редоследа улазних ниски
|-
| TupleHash256(''X'', ''L'', ''S'')
|-
| TupleHashXOF128(''X'', ''L'', ''S'')
|-
| TupleHashXOF256(''X'', ''L'', ''S'')
|-
| ParallelHash128(''X'', ''B'', ''L'', ''S'') ||rowspan="4" |Функција дизајнирана за искоришћавање паралелизма у циљу бржег хеширања
|-
| ParallelHash256(''X'', ''B'', ''L'', ''S'')
|-
| ParallelHashXOF128(''X'', ''B'', ''L'', ''S'')
|-
| ParallelHashXOF256(''X'', ''B'', ''L'', ''S'')
|}

* X је улазна ниска битова. Може бити било које дужине, укључујући дужину нула
* L је цели број који представља тражену излазну дужину у битовима.
* N је име функцијe као ниска битова, које NIST  користи за дефинисање функција заснованих на cSHAKE. Када није потребна ниједна друга функција осим cSHAKE, N се поставља на празну ниску
* S је персонализована ниска битова. Корисник користи ову ниску да дефинише  варијанту функције. Када није потребна персонализација, S се поставља на празну ниску.
* К је кључ; ниска битова било које дужине, укључујући нулу.
* B је величина блока у бајтовима за паралелно хеширање. Може бити било који цели број такав да је  0 < B < 2<sup>2040</sup>.

==Резултати каснијег развоја==
===Хеш стабло===
Аутори  SHA-3 функција и алгоритма Кечак су 2016. године предложили брже алтернативе (KangarooTwelve и MarsupilamiFourteen), које користе мањи број рунди (са 24 сведене су на 12 и 14 рунди) и које користе хеш стабло и тако омогућавају паралелно извршавање. Самим тим су брже од стандардних функција  SHA-3 које користе Паралелни хеш ({{јез-eng|ParallelHash}}). Сврха паралелног хеша је да подржи ефикасно хеширање дугих ниски користећи предност паралелизма који је доступан у савременим процесорима. <ref>[http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash] {{PD-notice}}</ref> Иако не припадају [[ FIPS]] стандарду, јер су развијене касније, они су једнако безбедни као функције  SHA-3 јер користе исте Keчак пермутације, а не зна се за напад на Keчак са 12 рунди.

KangarooTwelve је верзија Keчакa са 12 рунди, за коју се тврди да обезбеђује сигурност од 128 бита, а да за извршавање користи само 0,55 циклуса по бајту.
MarsupilamiFourteen, мала варијација KangarooTwelve, користи 14 рунди и обезбеђује, како се тврди, сигурност од 256 бита. 256-битна безбедност у пракси ништа не значи у односу на 128-битну сигурност ако се разматра напад грубом силом помоћу класичног рачунара. 

Током 2016. године, Keчак тим je  објавио другачију конструкцију која се зове Farfalle конструкција, и Kravatte, пример  Farfalle која користи Keчак-p пермутацију, као и два алгоритма за шифровање са аутентикацијом, Kravatte-SANE and Kravatte-SANSE.

Познат је резултат (Гроверов алгоритам) да квантни рачунари могу да одреде инверзну слику за време  <math>\sqrt{2^d} = 2^{d/2}</math>, док је за класичан напад грубом силом потребно време 2<sup>''d''</sup>. Структурирани preimage напади доводе до second preimage напада, а тиме и до колизионог напада({{јез-eng|collision attack}}). Ови рачунари могу да произведу и birthday напад ({{јез-eng|birthday attack}}) у <math>\sqrt[3]{2^d} = 2^{d/3}</math>. Највећа снага може бити <math>c/2</math>, тако да су горње границе квантум сигурности SHA-3:
{| class="wikitable"
|-
! rowspan="2" | Инстанца
! colspan="4" | Снага безбедности у битовима
|-
! Колизија<br/>(Brassard et al.) !! Колизија<br/>(Bernstein) !! Оригинал!!  Други оригинал
|-
| SHA3-224(''M'') || style="background: yellow;" | 74⅔ || 112 || 112 || 112
|-
| SHA3-256(''M'') || style="background: yellow;" | 85⅓ || 128 || 128 || 128
|-
| SHA3-384(''M'') || 128 || 192 || 192 || 192
|-
| SHA3-512(''M'') || 170⅔ || 256 || 256 || 256
|-
| SHAKE128(''M'', ''d'') 
| min(''d''/3,128)
| min(''d''/2,128)
| &ge;min(''d''/2,128)
| min(''d''/2,128)
|-
| SHAKE256(''M'', ''d'') || min(''d''/3,256)||min(''d''/2,256)||&ge;min(''d''/2,256)||min(''d''/2,256)
|}

Аутори нису доказали да је сунђераста структура коју користи SHA-3 отпорна на квантум нападе.
==Примери SHA-3 варијанти==
Наредне хеш вредности су са сајта NIST.gov:<ref>{{cite web|title=NIST.gov – Computer Security Division – Computer Security Resource Center|url=http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing|date=29. 12. 2016}}</ref>

<span style="color: green;">SHA3-224("")</span>
 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
 <span style="color: green;">SHA3-256("")</span>
 a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
 <span style="color: green;">SHA3-384("")</span>
 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
 <span style="color: green;">SHA3-512("")</span>
 a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
 <span style="color: green;">SHAKE128("", 256)</span>
 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
 <span style="color: green;">SHAKE256("", 512)</span>
 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

Промена једног бита узрокује промену сваког бита на излазу са вероватноћом ''50\% '', демонстрирајући тзв. лавински ефекат

 <span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy dog", 256)</span>
 f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
 <span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy do<span style="color: red;">f</span>", 256)</span>
 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c


==Поређење SHA функција==
{| class="wikitable" style="margin-top: 0px; width:100%"
|+ Поређење SHA функција {{Navbar|Поређење SHA функција|plain=1|style=float:right}}
|- style="vertical-align:bottom;"
! colspan="2" rowspan="2" | Алгоритам и варијанте 
! rowspan="2" |  Беличина излаза<br/>(bits)
! rowspan="2" |  Величина унутрашњег стања
! rowspan="2" | Величина блока
! rowspan="2" | Број рунди
! rowspan="2" | Операције
! rowspan="2" | Отпорност на колзиони напад
! rowspan="2" | Отпорност на напад са продужавањем поруке
! colspan="2" | Перформансе на Skylake (медијана)
! rowspan="2" |  Прво издање
|- style="vertical-align:bottom;"
! велике поруке!!  8 бајта
|- style="text-align:center;vertical-align:top;"
| colspan="2" | '''[[MD5]]''' (as reference) || 128 || 128<br>{{nowrap|(4 × 32)}} || 512  || 64 || And, Xor, Rot, {{nowrap|Add (mod&nbsp;2<sup>32</sup>),}} Or || {{Bad|≤18<br/>(collisions found)<ref>{{Cite techreport|first1=Xie|last1=Tao|first2=Fanbao|last2=Liu|first3=Dengguo|last3=Feng|year=2013|title=Fast Collision Attack on MD5|work=Cryptology ePrint Archive|publisher=[[International Association for Cryptologic Research|IACR]]|url=https://eprint.iacr.org/2013/170.pdf}}</ref>}} || {{Bad|0}}|| 4.99 || 55.00 || 1992
|- style="text-align:center;vertical-align:top;"
| colspan="2" | '''{{nowrap|[[SHA-0]]}}''' || rowspan="2" | 160 || rowspan="2" | 160<br>{{nowrap|(5 × 32)}} || rowspan="2" | 512  || rowspan="2" | 80 || rowspan="2" | And, Xor, Rot, {{nowrap|Add (mod&nbsp;2<sup>32</sup>),}} Or || {{Bad|&lt;34<br/>(collisions found)}}  || rowspan="2"  {{Bad|0}} || ≈ SHA-1 || ≈ SHA-1 || 1993
|- style="text-align:center;vertical-align:top;"
| colspan="2" | '''{{nowrap|[[SHA-1]]}}''' || {{Bad|&lt;63<br/>(collisions found)<ref>{{Cite techreport|last1=Stevens|first1=Marc|author-link1=Marc Stevens (cryptology)|last2=Bursztein|first2=Elie|author-link2=Elie Bursztein|last3=Karpman|first3=Pierre|last4=Albertini|first4=Ange|last5=Markov|first5=Yarik|title=The first collision for full SHA-1|publisher=[[Google|Google Research]]|url=https://shattered.io/static/shattered.pdf|lay-url=https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html|lay-source=Google Security Blog|lay-date=23. 2. 2017|accessdate=21. 5. 2020|archiveurl=https://web.archive.org/web/20180515222208/http://shattered.io/static/shattered.pdf|archivedate=15. 5. 2018|url-status=dead}}</ref>}} || 3.47 || 52.00 || 1995
|- style="text-align:center;vertical-align:top;"
| rowspan="3" | '''{{nowrap|[[SHA-2]]}}''' || ''SHA-224''<br/>''SHA-256'' || 224<br/>256 || 256<br/>{{nowrap|(8 × 32)}} || 512 || 64 || And, Xor, Rot, {{nowrap|Add (mod&nbsp;2<sup>32</sup>),}} Or, Shr || {{Good|112 <br/> 128}} || {{Bad|32<br/>0}}|| 7.62<br/>7.63 || 84.50<br/>85.25 || 2004<br/>2001
|- style="text-align:center;vertical-align:top;"
| ''SHA-384''<br/>''SHA-512'' ||  384<br/>512 || rowspan="2" | 512<br/>{{nowrap|(8 × 64)}} || rowspan="2" | 1024 || rowspan="2" | 80  || rowspan="2" | And, Xor, Rot, {{nowrap|Add (mod&nbsp;2<sup>64</sup>),}} Or, Shr || {{Good|192<br/>256}} || {{Bad|{{nowrap|128 (&le; 384)}}<br/>0}} || 5.12<br/>5.06 ||  135.75<br/>135.50 ||  2001
|- style="text-align:center;vertical-align:top;"
| ''{{nowrap|SHA-512/224}}''<br/>''{{nowrap|SHA-512/256}}'' || 224<br/>256 || {{Good|112<br/>128}} || {{Good|288<br/>256}} || {{nowrap|≈ SHA-384}} || {{nowrap|≈ SHA-384}} || 2012
|- style="text-align:center;vertical-align:top;"
| rowspan="2" | '''{{nowrap|[[SHA-3]]}}''' || ''SHA3-224''<br/>''SHA3-256''<br/>''SHA3-384''<br/>''SHA3-512'' || 224<br/>256<br/>384<br/>512 || rowspan="2" | 1600<br>{{nowrap|(5 × 5 × 64)}} || 1152<br/>1088<br/>832<br/>576 || rowspan="2" | {{nowrap|24}}<ref>{{cite web|url=http://keccak.noekeon.org/specs_summary.html |title=The Keccak sponge function family |date= |accessdate=27. 1. 2016}}</ref> || rowspan="2" | And, Xor, Rot, Not  || {{Good|112<br/>128<br/>192<br/>256}} ||{{Good|448<br/>512<br/>768<br/>1024}}|| 8.12<br/>8.59<br/>11.06<br/>15.88 ||154.25<br/>155.50<br/>164.00<br/>164.00 || rowspan="2" | 2015
|- style="text-align:center;vertical-align:top;"
| ''SHAKE128''<br/>''SHAKE256'' || {{nowrap|''d'' (arbitrary)}}<br/>{{nowrap|''d'' (arbitrary)}} || 1344<br/>1088 || {{Good|min(''d''/2, 128)<br/>{{nowrap|min(''d''/2, 256)}}}} || {{Good|{{nowrap|256<br/>512}}}} || 7.08<br/>8.59 || 155.25<br/>155.50
|}
==Референце==
{{Reflist}}

{{нормативна контрола}}

[[Категорија:Алгоритми]]