SHA-3

SHA-3 (Сигурни хеш алгоритам 3) је последњи стандард из породице Сигурних хеш алгоритама, као део шире фамилије алгоритама Кечак (енгл. Keccak). који су креирали Јоан Дамен (хол. Joan Daemen), Гвидо Бертони (хол. Guido Bertoni), Михаел Питерс (хол. Michaël Peeters) и Жил Ван Аш (хол. Gilles Van Assche), а објавио NIST 2015. године. Аутори Кечака су предложили и друге намене овог алгоритма, као што су проточна шифра, шифровање са аутентикацијом, хеш-стабло предвиђено за брзи рад на неким архитектурама, и 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. године. Референтна реализација овог алгоритма је отворени код. У току такмичења било је дозвољено такмичарима да "дотерују" своје алгоритме и тако отклоне проблеме откривене у међувремену.

Алгоритам Кечак имао је неколико промена:

• број рунди је повећан са 12+l на 12+2l, ради конзервативније гаранције
• допуњавање поруке је, уместо сложене схеме, замењено једноставним низом бита 10^*1
• параметар r је повећан до границе безбедности, уместо ранијег заокруживања на најближи степен двојке

Године 2014. NIST објављује нацрт FIPS 202 “Стандард SHA-3 : Хеш базиран на пермутацијама и функцијама са проширивим излазима” , који је годину дана касније, 5. августа 2015. године, одобрен и проглашен новим стандардом.

Конструкција

Сунђер конструкција за хеш функције. P_i су улази, Z_i су излази.

Хеш функције породице SHA-3 имају структуру која подсећа на сунђер , улазни подаци се најпре упијају у сунђер, а онда се излазни подаци истискују из њега. У фази упијања, блокови порука се XOR-ују са подскупом стања, а затим се трансформишу узајамно једнозначном функцијом f. У фази истискивања, излазни блокови се читају из истог подскупа стања, при чему се после сваког ишчитавања примењује функција f. Величина дела стања које се пише и чита назива се "брзина” (енгл. rate, ознака r), а величина дела стања које је остало непромењено при улазу/излазу назива се “капацитет” (енгл. capacity, ознака c). Капацитет одређује сигурност хеш алгоритма. Процена је да ниво сигурности алгоритма (логаритам за основу 2 броја покушаја приликом напада заснованог на рођенданском парадоксу) једнак половини капацитета.

Нека је $N$ улазна ниска, $pad$ функција за допуњавање, $f$ функција која трансформише блокове од $b$ бита, брзине $r$ и нека је дужина излаза $d$. Тада је капацитет $c=b-r$ и сунђер $Z={\text{sponge}}[f,pad,r](N,d)$, на излазу даје битску ниску $Z$ дужине $d$, и ради на следећи начин:

• Допунити улазну ниску N помоћу функције pad, тако да се добије допуњена ниска битова P чија је дужина дељива са r; нека је n количник дужине P и броја r
• Поделити P на n блоковa дужине r P₀, P₁…P_n-1
• Иницијализовати стање S ниском нула дужине b
• Упијање улаза у стање: за сваки блок P_i:
  • Допунити P_i са c нула на крају, тако да је нова дужина b
  • Извршити операцију XOR са P_i и S
  • Применити функцију пермутације на добијени резултат
• Иницијализовати Z празном ниском
• Фаза истискивања: све док је дужина Z мања од d (d је дужина вредности хеш функције):
  • додати првих r битова стања S на ниску Z
  • ако је дужина Z мања од d, применом функцијeе f формирати ново стање C
• скратити Z на d битова

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

У алгоритму стање S је низ од 5 × 5 речи дужине 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 операције и дизајнирана је за лаку имплементацију и у софтверу и у хардверу. Дефинисана је за речи чија је дужина степен двојке, w = 2^ℓ бита. Основна имплементација ради са 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) ставити a[i][ j][k] ← a[i][ j][k] ⊕ парност(a[0...4][ j−1][k]) ⊕ парност(a[0...4][ j+1][k−1])

Корак ρ (rho) – битска ротација

За свaко t такво да је 0 ≤ t < 24 ставити a[i][ j][k] ← a[i][ j][k−(t+1)(t+2)/2], где је ${\begin{pmatrix}i\\j\end{pmatrix}}={\begin{pmatrix}3&2\\1&0\end{pmatrix}}^{t}{\begin{pmatrix}0\\1\end{pmatrix}}$

Корак π (pi) - пермутација 25 речи

Пермутовати 25 речи, тако да a[j][2i+3j] ← a[ i][j]

Корак χ (chi)

За све тројке (i,j,k) такве да је 0≤i<5, 0≤j<5 и 0≤k<w ставити a[i][ j][k] ← a[i][ j][k] ⊕ (¬a[i][ j+1][k] & a[i][ j+2][k])

Овај корак је једина нелинеарна трансформација у оквиру алгоритма SHA-3.

Корак ι (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₈[R]

Вратити R[0]

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

• • За све тројке(i,j,k) такве да је 0≤i<5, 0≤j<5 и 0≤k<w ,нека је а′[i,j,k]= а[i,j,k]
  • Нека је RC=0^w
  • За j од 0 до l, нека је RC[2^j - 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 са допуњеним P_i. Довољно је операцију 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	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)

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

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

SHAKE128(М, 256) се може користити као хеш функција са дужином хеша од 256 битова и укупном мером сигурности 128 битова. Све инстанце додају неке битове поруци, чији крајњи десни део представља суфикс за раздвајање домене (енгл. domain separation suffix), да би се онемогућило конструисање порука које дају исти хеш за различите примене 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 се поставља на празну ниску
• S је персонализована ниска битова. Корисник користи ову ниску да дефинише варијанту функције. Када није потребна персонализација, S се поставља на празну ниску.
• К је кључ; ниска битова било које дужине, укључујући нулу.
• B је величина блока у бајтовима за паралелно хеширање. Може бити било који цели број такав да је 0 < B < 2²⁰⁴⁰.

Резултати каснијег развоја

Хеш стабло

Аутори SHA-3 функција и алгоритма Кечак су 2016. године предложили брже алтернативе (KangarooTwelve и MarsupilamiFourteen), које користе мањи број рунди (са 24 сведене су на 12 и 14 рунди) и које користе хеш стабло и тако омогућавају паралелно извршавање. Самим тим су брже од стандардних функција SHA-3 које користе Паралелни хеш (енгл. ParallelHash). Сврха паралелног хеша је да подржи ефикасно хеширање дугих ниски користећи предност паралелизма који је доступан у савременим процесорима. Иако не припадају 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.

Познат је резултат (Гроверов алгоритам) да квантни рачунари могу да одреде инверзну слику за време ${\sqrt {2^{d}}}=2^{d/2}$, док је за класичан напад грубом силом потребно време 2^d. Структурирани preimage напади доводе до second preimage напада, а тиме и до колизионог напада(енгл. collision attack). Ови рачунари могу да произведу и birthday напад (енгл. birthday attack) у ${\sqrt[{3}]{2^{d}}}=2^{d/3}$. Највећа снага може бити $c/2$, тако да су горње границе квантум сигурности SHA-3:

Инстанца	Снага безбедности у битовима
	Колизија (Brassard et al.)	Колизија (Bernstein)	Оригинал	Други оригинал
SHA3-224(M)	74⅔	112	112	112
SHA3-256(M)	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)	≥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)

Аутори нису доказали да је сунђераста структура коју користи SHA-3 отпорна на квантум нападе.

Примери SHA-3 варијанти

Наредне хеш вредности су са сајта NIST.gov:

SHA3-224("")

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

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

SHAKE128("The quick brown fox jumps over the lazy dog", 256)
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
SHAKE128("The quick brown fox jumps over the lazy dof", 256)
853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Поређење SHA функција

Поређење SHA функција

Алгоритам и варијанте		Беличина излаза (bits)	Величина унутрашњег стања	Величина блока	Број рунди	Операције	Отпорност на колзиони напад	Отпорност на напад са продужавањем поруке	Перформансе на Skylake (медијана)		Прво издање
									велике поруке	8 бајта
MD5 (as reference)		128	128 (4 × 32)	512	64	And, Xor, Rot, Add (mod 232), Or	≤18 (collisions found)	0	4.99	55.00	1992
SHA-0		160	160 (5 × 32)	512	80	And, Xor, Rot, Add (mod 232), Or	<34 (collisions found)	0	≈ SHA-1	≈ SHA-1	1993
SHA-1							<63 (collisions found)		3.47	52.00	1995
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	64	And, Xor, Rot, Add (mod 232), Or, Shr	112 128	32 0	7.62 7.63	84.50 85.25	2004 2001
	SHA-384 SHA-512	384 512	512 (8 × 64)	1024	80	And, Xor, Rot, Add (mod 264), Or, Shr	192 256	128 (≤ 384) 0	5.12 5.06	135.75 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	And, 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
	SHAKE128 SHAKE256	d (arbitrary) d (arbitrary)		1344 1088			min(d/2, 128) min(d/2, 256)	256 512	7.08 8.59	155.25 155.50