SHA-3 (Сигурни хеш алгоритам 3) је последњи стандард из породице Сигурних хеш алгоритама, као део шире фамилије алгоритама Кечак (). који су креирали Јоан Дамен (), Гвидо Бертони (), Михаел Питерс () и Жил Ван Аш (), а објавио NIST 2015. године. Аутори Кечака су предложили и друге намене овог алгоритма, као што су проточна шифра, шифровање са аутентикацијом, хеш-стабло предвиђено за брзи рад на неким архитектурама, 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). и AEAD (аутентификована шифра са придруженим подацима) шифре Keyak и Ketje. Иако се по имену наставља на стандарде SHA-1 и SHA-2, сличне алгоритму MD5, унутрашња организација алгоритма SHA3-3 битно је другачија.
Алгоритам у току рада имитира сунђер конструкцију – упија (апсорбује) било коју количину података и избацује тражену количину података, понашајући се као псеудослучајна функција, која зависи од свих претходних улаза. Тиме се омогућава велика флексибилност.
NIST за сада не планира да укине SHA-2. Сврха SHA-3 је да може директно да замени SHA-2 у тренутним применама, када је то потребно, и повећа робустност NIST-овог скупа хеш алгоритама. Аутори алгоритма Кечак предлажу употребу брже функције, KangarooTwelve, са прилагођеним параметрима и ново дрво хеширања, која је ефикасније за кратке поруке.
Историја Неколико успешно пронађених колизија за хеш алгоритме MD5, SHA-0 и SHA-1 током 2004-2005 навело је NIST да организује 2006. године такмичење за нови хеш стандард, SHA-3. С обзиром на то да није откривен успешан напад на SHA-2, SHA-3 је потребан само као алтернатива.
Алгоритам Кечак је 2. октобра 2012. године проглашен победником такмичења на коме је учествовао 51 кандидат. Његови аутори су Гвидо Бертони, Јоан Дамен, Михаел Питерс и Жил Ван Аш. Базиран је на ранијим хеш функцијама, Panama и RadioGatun, који је представљен 2006. године. Референтна реализација овог алгоритма је отворени код. 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 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/" У току такмичења било је дозвољено такмичарима да "дотерују" своје алгоритме и тако отклоне проблеме откривене у међувремену.
Алгоритам Кечак имао је неколико промена: број рунди је повећан са на , ради конзервативније гаранције допуњавање поруке је, уместо сложене схеме, замењено једноставним низом бита 10*1 параметар r је повећан до границе безбедности, уместо ранијег заокруживања на најближи степен двојке
Године 2014. NIST објављује нацрт FIPS 202 “Стандард SHA-3 : Хеш базиран на пермутацијама и функцијама са проширивим излазима” , који је годину дана касније, 5. августа 2015. године, одобрен и проглашен новим стандардом.
Конструкција
Хеш функције породице SHA-3 имају структуру која подсећа на сунђер , улазни подаци се најпре упијају у сунђер, а онда се излазни подаци истискују из њега. У фази упијања, блокови порука се XOR-ују са подскупом стања, а затим се трансформишу узајамно једнозначном функцијом f. У фази истискивања, излазни блокови се читају из истог подскупа стања, при чему се после сваког ишчитавања примењује функција f. Величина дела стања које се пише и чита назива се "брзина” (, ознака r), а величина дела стања које је остало непромењено при улазу/излазу назива се “капацитет” (, ознака c). Капацитет одређује сигурност хеш алгоритма. Процена је да ниво сигурности алгоритма (логаритам за основу 2 броја покушаја приликом напада заснованог на рођенданском парадоксу) једнак половини капацитета.
Нека је улазна ниска, функција за допуњавање, функција која трансформише блокове од бита, брзине и нека је дужина излаза . Тада је капацитет и сунђер , на излазу даје битску ниску дужине , и ради на следећи начин:
Допунити улазну ниску N помоћу функције pad, тако да се добије допуњена ниска битова P чија је дужина дељива са r; нека је n количник дужине P и броја r Поделити P на n блоковa дужине r P0, P1…Pn-1 Иницијализовати стање S ниском нула дужине b Упијање улаза у стање: за сваки блок Pi: Допунити Pi са c нула на крају, тако да је нова дужина b Извршити операцију XOR са Pi и S Применити функцију пермутације на добијени резултат Иницијализовати Z празном ниском Фаза истискивања: све док је дужина Z мања од d (d је дужина вредности хеш функције): додати првих r битова стања S на ниску Z ако је дужина Z мања од d, применом функцијeе f формирати ново стање C скратити Z на d битова
Због чињенице да стање S садржи додатних c битова, алгоритам је отпоран на нападе проширењем дужине (), којима су подложни алгоритми SHA-1 и SHA-2.
У алгоритму стање S је низ од речи дужине w (w = 64), b = 5x5xw = укупно 1600 битова. Алгоритам Кечак такође може да користи мање дужине - степене двојке, од w=1 до w=32, за тестирање криптоаналитичких напада и у неким практичним, лакшим апликацијама.
За инстанце 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. У том случају, додаје се наредни блок који почиње и који се завршава јединицом, између којих се налазе r-2 нуле. На овај начин се постиже да порука чија је дужина дељива са r, а која се завршава низом бита који изгледа као низ за допуњавање, не даје исту хеш вредност као порука са одстрањеним делом која личи на допуњавање.
Прва додата јединица је неопходна да би се разликовале хеш вредности порука које се разликују само по броју нула на својим крајевима. Позиција последње јединице указује на то која је брзина r искоришћена.
Трансформација блока - функција f
Трансформација блока f користи XOR, AND и NOT операције и дизајнирана је за лаку имплементацију и у софтверу и у хардверу. Дефинисана је за речи чија је дужина степен двојке, бита. Основна имплементација ради са 64-битне речи, где је l=6.
Стање S се може представити као тродимензионална матрица битова величине 5x5xw.
Тада је елемент матрице а[i][j][k] бит улаза са редним бројем (5i + j) * w + k. При томе су i, j, k редом индекси врсте, односно колоне, односно бита. Са индексима се рачуна по модулу 5 за прва два индекса, односно по модулу w за трећи индекс.
Основна блок пермутација састоји се од 12 + 2l рунди, од којих се свака састоји од наредних пет корака, у којима се нова матрица а′ добија од старе матрице а:
Koрак (theta) Нека је парност неког скупа бита једнака вредности XOR-a тих бита. За све тројке (i, j, k) ставити
Корак (rho) – битска ротација За свaко t такво да је ставити , где је
Корак (pi) - пермутација 25 речи Пермутовати 25 речи, тако да
Корак (chi) За све тројке (i,j,k) такве да је 0≤i<5, 0≤j<5 и 0≤k<w ставити Овај корак је једина нелинеарна трансформација у оквиру алгоритма SHA-3.
Корак (iota) У овом кораку се користи константни низ rc[0...255] који се добија из померачког регистра са линеарном спрегом дужине 8 на следећи начин:
Ако је t mod 255 = 0, врати 1. Нека је R = 10000000. За i од 1 до t mod 255, нека је : R = 0 || R; R = R ⊕ R; R = R ⊕ R; R = R ⊕ R; R = R ⊕ R; R = Trunc8[R] Вратити R
Алгоритам (A, n) Елементи низа rc користе се на различите начине за модификацију матрице а у зависности од редног броја рунде n
За све тројке(i,j,k) такве да је 0≤i<5, 0≤j<5 и 0≤k<w ,нека је а′[i,j,k]= а[i,j,k] Нека је RC=0w За j од 0 до l, нека је RC[2j - 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) = (((((a)))), n). Претворити a y ниску S′ дужине b Вратити S′
Брзина На брзину израчунавања хеш вредности дугачких порука највише утиче време за израчунавање функције f и операције XOR стања S са допуњеним Pi. Довољно је операцију XOR извршити са првих r битова, јер су последњих c битова нуле. Мање r, a самим тим, веће c, даје мању ефикасност, али већу сигурност хеширања јер ће мање битова порукe бити XOR-овано са стањем пре сваке примене рачунски сложене функције f. Софтверска реализација SHA3-512 је око два пута спорија од реализације SHA2-512 . С друге стране, хардверске реализације SHA-3 знатно су брже од реализације свих других финалиста конкурса.
Инстанце Oригинални алгоритам Кечак има много опционих параметара, како би се осигурао оптималан однос снаге и брзине криптографије за специфичну примену алгоритма на одређеној платформи. Опционе вредности су: величина блока података, величина стања алгоритма, број рунди у функцији f() и друге.
У стандардy су уведене „Прошириве излазне функције“ (XOF, Extendable Output Functions) SHAKE128 и SHAKE256, за које се порука допуњује „суфиксом“ од 2 или 4 бита, у зависности од врсте функције.
Инстанца Дужина излаза d Брзина r Капацитет c Дефиниција Сигурност у битовима Koлизија Одређивање поруке на основу хеша Одређивање поруке са истим хешом као дата порука SHA3-224(M) 224 1152448 Keccak(M || 01, 224) 112 224 224 SHA3-256(M) 256 1088512 Keccak(M || 01, 256) 128 256 256 SHA3-384(M) 384 832768 Keccak(M || 01, 384) 192 384 384 SHA3-512(M) 512 5761024 Keccak(M || 01, 512) 256 512 512 SHAKE128(M, d) d 1344256Keccak(M || 1111, d) min(d/2,128)≥min(d,128)min(d,128) SHAKE256(M, d) d 1088512 Keccak(M || 1111, d) min(d/2,256)≥min(d,256)min(d,256)
У табели су коришћене следеће ознаке:
Keccak[c](N, d) = sponge[Keccak-f, pad10*1, r](N, d) Keccak-f = Keccak-p[1600, 24] c је капацитет r је брзина = 1600 − cSHAKE128(М, 256) се може користити као хеш функција са дужином хеша од 256 битова и укупном мером сигурности 128 битова. Све инстанце додају неке битове поруци, чији крајњи десни део представља суфикс за раздвајање домене (), да би се онемогућило конструисање порука које дају исти хеш за различите примене Keчак хеш функције.
За сада су дефинисани следећи суфикси: Суфикс ...0 је резервисан за будуће примене, 01 је SHA-3, a …11 je RawSHAKE.
Додатне инстанце У децембру 2016. NIST је објавио нови документ NIST SP.800-185, који описује додатне SHA-3 изведене функције:
Инстанца Опис cSHAKE128(X, L, N, S) Верзија SHAKE која подржава експлицитно одвајање домена помоћу параметара cSHAKE256(X, L, N, S) KMAC128(K, X, L, S) Хеш функција са кључем заснована на алгоритму Кечак KMAC256(K, X, L, S) KMACXOF128(K, X, L, S) KMACXOF256(K, X, L, S) TupleHash128(X, L, S) Функција за хеширање торки, чији излаз зависи од садржаја и редоследа улазних ниски TupleHash256(X, L, S) TupleHashXOF128(X, L, S) TupleHashXOF256(X, L, S) ParallelHash128(X, B, L, S) Функција дизајнирана за искоришћавање паралелизма у циљу бржег хеширања ParallelHash256(X, B, L, S) ParallelHashXOF128(X, B, L, S) ParallelHashXOF256(X, B, L, S)
X је улазна ниска битова. Може бити било које дужине, укључујући дужину нула L је цели број који представља тражену излазну дужину у битовима. N је име функцијe као ниска битова, које NIST користи за дефинисање функција заснованих на cSHAKE. Када није потребна ниједна друга функција осим cSHAKE, N се поставља на празну ниску