SHA-3

Извор: testwiki
Пређи на навигацију Пређи на претрагу

SHA-3 (Сигурни хеш алгоритам 3) је последњи стандард из породице Сигурних хеш алгоритама, као део шире фамилије алгоритама Кечак (Шаблон:Јез-eng).[1][2] који су креирали Јоан Дамен (Шаблон:Јез-nl), Гвидо Бертони (Шаблон:Јез-nl), Михаел Питерс (Шаблон:Јез-nl) и Жил Ван Аш (Шаблон:Јез-nl), а објавио NIST 2015. године. [3][4] Аутори Кечака су предложили и друге намене овог алгоритма, као што су проточна шифра, шифровање са аутентикацијом, хеш-стабло предвиђено за брзи рад на неким архитектурама, [5][6] и AEAD (аутентификована шифра са придруженим подацима) шифре Keyak и Ketje.[7][8] Иако се по имену наставља на стандарде SHA-1 и SHA-2, сличне алгоритму MD5, унутрашња организација алгоритма SHA3-3 битно је другачија.

Алгоритам у току рада имитира сунђер конструкцију [9] – упија (апсорбује) било коју количину података и избацује тражену количину података, понашајући се као псеудослучајна функција, која зависи од свих претходних улаза. Тиме се омогућава велика флексибилност.

NIST за сада не планира да укине SHA-2. Сврха SHA-3 је да може директно да замени SHA-2 у тренутним применама, када је то потребно, и повећа робустност NIST-овог скупа хеш алгоритама. [10] Аутори алгоритма Кечак предлажу употребу брже функције, KangarooTwelve, са прилагођеним параметрима и ново дрво хеширања, која је ефикасније за кратке поруке.

Историја

Неколико успешно пронађених колизија за хеш алгоритме MD5, SHA-0 и SHA-1 [11][12] током 2004-2005 навело је NIST да организује 2006. године такмичење за нови хеш стандард, SHA-3. С обзиром на то да није откривен успешан напад на SHA-2, SHA-3 је потребан само као алтернатива.

Алгоритам Кечак је 2. октобра 2012. године проглашен победником такмичења [1] на коме је учествовао 51 кандидат. Његови аутори су Гвидо Бертони, Јоан Дамен, Михаел Питерс и Жил Ван Аш. Базиран је на ранијим хеш функцијама, Panama и RadioGatun, који је представљен 2006. године. [13] Референтна реализација овог алгоритма је отворени код. [14] У току такмичења било је дозвољено такмичарима да "дотерују" своје алгоритме и тако отклоне проблеме откривене у међувремену.

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

  • број рунди је повећан са Шаблон:Nowrap на Шаблон:Nowrap, ради конзервативније гаранције
  • допуњавање поруке је, уместо сложене схеме, замењено једноставним низом бита 10*1
  • параметар r је повећан до границе безбедности, уместо ранијег заокруживања на најближи степен двојке

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

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

Illustration of the sponge construction
Сунђер конструкција за хеш функције. Pi су улази, Zi су излази.

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

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

  • Допунити улазну ниску N помоћу функције pad, тако да се добије допуњена ниска битова P чија је дужина дељива са r; нека је n количник дужине P и броја r
  • Поделити P на n блоковa дужине r P0, P1Pn-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 битова, алгоритам је отпоран на нападе проширењем дужине (Шаблон:Јез-eng), којима су подложни алгоритми SHA-1 и SHA-2.

У алгоритму стање S је низ од Шаблон:Nowrap речи дужине w (w = 64), b = 5x5xw = укупно 1600 битова. Алгоритам Кечак такође може да користи мање дужине - степене двојке, од w=1 до w=32, за тестирање криптоаналитичких напада и у неким практичним, лакшим апликацијама. [7][8]

За инстанце 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. [19]Шаблон:Rp У том случају, додаје се наредни блок који почиње и који се завршава јединицом, између којих се налазе r-2 нуле. На овај начин се постиже да порука чија је дужина дељива са r, а која се завршава низом бита који изгледа као низ за допуњавање, не даје исту хеш вредност као порука са одстрањеним делом која личи на допуњавање.

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

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

Трансформација блока f користи XOR, AND и NOT операције и дизајнирана је за лаку имплементацију и у софтверу и у хардверу. Дефинисана је за речи чија је дужина степен двојке, Шаблон:Math бита. Основна имплементација ради са 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
Корак Шаблон:Mvar (rho) – битска ротација
За свaко t такво да је Шаблон:Math ставити Шаблон:Math, где је (ij)=(3210)t(01)
Корак Шаблон:Mvar (pi) - пермутација 25 речи
Пермутовати 25 речи, тако да Шаблон:Math


Корак Шаблон:Mvar (chi)
За све тројке (i,j,k) такве да је 0≤i<5, 0≤j<5 и 0≤k<w ставити Шаблон:Math
Овај корак је једина нелинеарна трансформација у оквиру алгоритма 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 = Trunc8[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=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

Брзина

На брзину израчунавања хеш вредности дугачких порука највише утиче време за израчунавање функције f и операције XOR стања S са допуњеним Pi. Довољно је операцију XOR извршити са првих r битова, јер су последњих c битова нуле. Мање r, a самим тим, веће c, даје мању ефикасност, али већу сигурност хеширања јер ће мање битова порукe бити XOR-овано са стањем пре сваке примене рачунски сложене функције f. Софтверска реализација SHA3-512 је око два пута спорија од реализације SHA2-512 [20] . С друге стране, хардверске реализације 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 битова. Све инстанце додају неке битове поруци, чији крајњи десни део представља суфикс за раздвајање домене (Шаблон:Јез-eng), да би се онемогућило конструисање порука које дају исти хеш за различите примене 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 < 22040.

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

Хеш стабло

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

Познат је резултат (Гроверов алгоритам) да квантни рачунари могу да одреде инверзну слику за време 2d=2d/2, док је за класичан напад грубом силом потребно време 2d. Структурирани preimage напади доводе до second preimage напада, а тиме и до колизионог напада(Шаблон:Јез-eng). Ови рачунари могу да произведу и birthday напад (Шаблон:Јез-eng) у 2d3=2d/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:[22]

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 функција Шаблон:Navbar
Алгоритам и варијанте Беличина излаза
(bits)
Величина унутрашњег стања Величина блока Број рунди Операције Отпорност на колзиони напад Отпорност на напад са продужавањем поруке Перформансе на Skylake (медијана) Прво издање
велике поруке 8 бајта
MD5 (as reference) 128 128
Шаблон:Nowrap
512 64 And, Xor, Rot, Шаблон:Nowrap Or Шаблон:Bad Шаблон:Bad 4.99 55.00 1992
Шаблон:Nowrap 160 160
Шаблон:Nowrap
512 80 And, Xor, Rot, Шаблон:Nowrap Or Шаблон:Bad rowspan="2" Шаблон:Bad ≈ SHA-1 ≈ SHA-1 1993
Шаблон:Nowrap Шаблон:Bad 3.47 52.00 1995
Шаблон:Nowrap SHA-224
SHA-256
224
256
256
Шаблон:Nowrap
512 64 And, Xor, Rot, Шаблон:Nowrap Or, Shr Шаблон:Good Шаблон:Bad 7.62
7.63
84.50
85.25
2004
2001
SHA-384
SHA-512
384
512
512
Шаблон:Nowrap
1024 80 And, Xor, Rot, Шаблон:Nowrap Or, Shr Шаблон:Good Шаблон:Bad 5.12
5.06
135.75
135.50
2001
Шаблон:Nowrap
Шаблон:Nowrap
224
256
Шаблон:Good Шаблон:Good Шаблон:Nowrap Шаблон:Nowrap 2012
Шаблон:Nowrap SHA3-224
SHA3-256
SHA3-384
SHA3-512
224
256
384
512
1600
Шаблон:Nowrap
1152
1088
832
576
Шаблон:Nowrap[23] And, Xor, Rot, Not Шаблон:Good Шаблон:Good 8.12
8.59
11.06
15.88
154.25
155.50
164.00
164.00
2015
SHAKE128
SHAKE256
Шаблон:Nowrap
Шаблон:Nowrap
1344
1088
Шаблон:Good Шаблон:Good 7.08
8.59
155.25
155.50

Референце

Шаблон:Reflist

Шаблон:Нормативна контрола

  1. 1,0 1,1 Шаблон:Cite web
  2. Шаблон:Cite web
  3. Шаблон:Cite web
  4. Шаблон:Cite journal
  5. Шаблон:Cite web
  6. Шаблон:Cite web 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).
  7. 7,0 7,1 Шаблон:Cite web
  8. 8,0 8,1 Шаблон:Cite web
  9. 9,0 9,1 Шаблон:Cite web
  10. Шаблон:Cite web
  11. Шаблон:Cite web
  12. Шаблон:Cite web
  13. Шаблон:Cite web
  14. 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: -{R|http://keccak.noekeon.org/Implementation}-Шаблон:Dead link 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. -{R|https://creativecommons.org/publicdomain/zero/1.0/}-"
  15. Шаблон:Cite web
  16. Шаблон:Cite web
  17. Шаблон:Cite web
  18. Шаблон:Cite web
  19. 19,0 19,1 Шаблон:Cite web
  20. Шаблон:Cite web
  21. SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash Шаблон:PD-notice
  22. Шаблон:Cite web
  23. Шаблон:Cite web