Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Kryptologie a kombinatorika na slovech L’ubom´ıra Balkov´ a Semin´ aˇr souˇ casn´ e matematiky
6. bˇrezna 2013
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Program
1
Haˇsovac´ı funkce Ditherovan´e haˇsovac´ı funkce Naˇc jsou haˇsovac´ı funkce dobr´e? Nov´y haˇsovac´ı standard - SHA-3
2
Gener´atory n´ahodn´ych ˇc´ısel Aperiodick´y gener´ ator n´ ahodn´ych ˇc´ısel
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Program
1
Haˇsovac´ı funkce Ditherovan´e haˇsovac´ı funkce Naˇc jsou haˇsovac´ı funkce dobr´e? Nov´y haˇsovac´ı standard - SHA-3
2
Gener´atory n´ahodn´ych ˇc´ısel Aperiodick´y gener´ ator n´ ahodn´ych ˇc´ısel
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Jednocestnost a bezkoliznost
Definice (jednocestn´e funkce) f : X → Y nazveme jednocestn´ a (one-way), pokud 1
pro kaˇzd´e x ∈ X je snadn´e spoˇc´ıst y = f (x),
2
pro n´ahodnˇe vybran´e y ∈ f (X ) je v´ypoˇcetnˇe nemoˇzn´e naj´ıt jeho vzor, tj. x ∈ X tak, ˇze y = f (x).
Definice (bezkolizn´ı funkce) f : X → Y nazveme bezkolizn´ı (collision-free), pokud je v´ypoˇcetnˇe nemoˇzn´e naj´ıt x, x ′ ∈ X , x 6= x ′ tak, ˇze f (x) = f (x ′ ).
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Definice kryptografick´e haˇsovac´ı funkce
Definice (kryptografick´ a haˇsovac´ı funkce) Necht’ N, n ∈ N a n << N a f : {0, 1}N → {0, 1}n nazveme haˇsovac´ı (hash function), pokud je jednocestn´ a a bezkolizn´ı. f (M) naz´yv´ame hash (otisk, haˇsov´y k´od) zpr´ avy M. Pozn. Obvykle N = 264 − 1, N = 2128 − 1 a n stovky bit˚ u (pro MD5/SHA-1/SHA256/SHA512 je to 128/160/256/512 bit˚ u).
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Odolnost proti nalezen´ı vzoru
Chov´a-li se haˇsovac´ı funkce f : {0, 1}N → {0, 1}n jako n´ahodn´e or´akulum, pak sloˇzitost nalezen´ı vzoru (i druh´eho vzoru) k dan´emu y = f (M) je ∼ 2n . Pokud lze vzor hledat jednoduˇseji, hovoˇr´ıme o prolomen´ı haˇsovac´ı funkce.
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Odolnost proti nalezen´ı kolize
Chov´a-li se haˇsovac´ı funkce f : {0, 1}N → {0, 1}n jako n´ahodn´e or´akulum, pak sloˇzitost nalezen´ı kolize (dvou libovoln´ych zpr´av se stejnou haˇs´ı) je ∼ 2n/2 . Pokud lze kolize hledat jednoduˇseji, hovoˇr´ıme o prolomen´ı haˇsovac´ı funkce. Poˇcet koliz´ı: v pr˚ umˇeru 2N−n zpr´ av m´ a stejnou haˇs.
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Narozeninov´y paradox mnoˇzina o m prvc´ıch, vyb´ır´ ame k prvk˚ u po 1 s vracen´ım pravdˇepodobnost, ˇze ve v´ybˇeru nˇekter´y prvek aspoˇ n 2kr´ at: P(m, k) = 1 −
m(m − 1) . . . (m − k + 1) mk
pro k = O(m1/2 ) a m jdouc´ı do nekoneˇcna −k 2 . P(m, k) = 1 − e 2m . . pro k = (2m · ln 2)1/2 = m1/2 je P(m, k) = 50% Pozn. P(365, 23) = 0, 507 a P(365, 30) = 0, 706 ⇒ ve skupinˇe 23 lid´ı najdeme s pravdˇepodobnost´ı 50% dvojici slav´ıc´ı narozeniny ve stejn´y den, ve skupinˇe 30 lid´ı s pravdˇepodobnost´ı 70%. Obvykl´e vn´ım´an´ı: hled´an´ı jednˇech konkr´etn´ıch narozenin, proto paradox. L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Damgard-Merklova konstrukce - Crypto 1989 iterativn´ı haˇsovac´ı funkce s vyuˇ zit´ım tzv. kompresn´ı funkce
zpr´ava dlouh´a aˇz napˇr. 264 − 1 bit˚ u ⇒ haˇsov´ an´ı po bloc´ıch (M rozdˇelena na 512-bitov´e bloky m1 , m2 , . . . , mk , kde mk pˇr´ıpadnˇe kratˇs´ı) Damgard-Merklovo zes´ılen´ı - doplnˇen´ı M na d´elku p × 512: M doplnˇena bitem 1, pot´e bity 0 (m˚ uˇze jich b´yt 0 - 447) na d´elku p × 512 − 64 a nakonec bin´ arn´ım z´ apisem d´elky M kompresn´ı funkce: 2 vstupy (aktu´ aln´ı blok zpr´avy mi a kontext hi −1 ) a 1 v´ystup (kontext hi ), tedy zpracov´ av´a ˇsirˇs´ı vstup na uˇzˇs´ı v´ystup algoritmus: h0 = IV , hi = f (hi −1 , mi ) v´ystup haˇsovac´ı funkce je hk nebo jeho ˇc´ ast dok´az´ano, ˇze bezkoliznost kompresn´ı funkce ⇒ bezkoliznost haˇsovac´ı funkce (proto staˇcilo naj´ıt kvalitn´ı kompresn´ı funkce) L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
´ Utok na opakuj´ıc´ı se kontexty
pokud hi −1 = hi = f (hi −1 , mi ), pak haˇse m1 . . . mi −1 mi mi +1 . . . mk a m1 . . . mi −1 miℓ mi +1 . . . mk stejn´e, coˇz vede k nalezen´ı 2. vzoru se sloˇzitost´ı t · 2n/2+1 + 2n−t+1 pro zpr´avy s d´elkou 2t bl´ızkou 2n/2 napˇr. pro SHA-1 lze ke zpr´ avˇe o d´elce 260 naj´ıt 2. vzor se 106 sloˇzitost´ı 2 na rozd´ıl od teoretick´e sloˇzitosti 2160 J. Kelsey, B. Schneier, Second preimages on n-bit hash functions for much less than 2n work
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Ditherov´an´ı zpracov´an´ı obrazu: simulace barev, kter´e nem´ ame, n´ahodn´ym m´ıch´an´ım pixel˚ u podobn´ych barev; c´ılem odstranˇen´ı neˇz´adouc´ıch lini´ı
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Ditherov´an´ı haˇsovac´ıch funkc´ı hi = f (hi −1 , mi , di ) 1
ditherov´an´ı ˇc´ıtaˇcem: di := i (probl´em libovoln´ych d´elek zpr´av ⇒ di nad nekoneˇcnou abecedou)
2
ditherov´an´ı n´ahodnou posloupnost´ı: di := ri (nechr´an´ı proti opakov´an´ı blok˚ u)
3
ditherov´an´ı stˇr´ıd´an´ım 0 a 1 (nechr´ an´ı proti opakov´an´ı blok˚ u)
4
ditherov´ an´ı pomoc´ı square-free a abelian square-free nekoneˇ cn´ ych slov R. Rivest, Abelian square-free dithering for iterated hash functions
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Square-free slova square-free slovo neobsahuje ww Pˇr´ıklad abracadabra OK, banana NE neexistuj´ı square-free nekoneˇcn´ a slova nad {0, 1} existuj´ı square-free nekoneˇcn´ a slova nad {0, 1, 2} Pˇr´ıklad Thue-Morseovo slovo t = 0110100110010110 . . . je cube-free (i overlap-free) odvozen´ e slovo v = 2102012 . . . je square-free ˇ DOKAZTE! L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Abelian square-free slova abelian square-free slovo neobsahuje ww ′ , kde w ′ permutace w Pˇr´ıklad abelianalien NE, obsahuje alien a elian Pˇr´ıklad abcacdcbcdcadcdbdaba cabadbabcbdbcbacbcdc magick´e slovo S = d´elky 85 acbabdabacadcbcdcacd bcbacbcdcacdcbdcdadbdcbca oznaˇcme σ cyklick´y posun σ(abcacd ) = bcdbda, pak Ker¨ anenovo abelian square-free slovo je pevn´y bod morfismu a → S, b → σ(S), c → σ 2 (S), d → σ 3 (S) L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Ot´azky
1
Jsou abelian square-free slova v ditherov´ an´ı v nˇeˇcem lepˇs´ı neˇz square-free slova?
2
Najdˇete vhodn´e ditheraˇcn´ı posloupnosti (nesm´ı m´ıt n´ızkou komplexitu).
3
Zkoumejte odolnost ditherovan´ych haˇsovac´ıch funkc´ı v˚ uˇci zn´am´ym u ´tok˚ um.
4
Studujte jin´e zp˚ usoby ditherov´ an´ı.
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Kryptografick´e vyuˇzit´ı haˇsovac´ıch funkc´ı
jednoznaˇcn´a identifikace dat (zejm´ena pro digit´aln´ı podpisy) kontrola integrity (kontrola shody velk´ych soubor˚ u dat) ukl´ad´an´ı a kontrola pˇrihlaˇsovac´ıch hesel prokazov´an´ı autorstv´ı prokazov´an´ı znalosti autentizace p˚ uvodu dat nepadˇelateln´a kontrola integrity pseudon´ahodn´e gener´ atory
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Digit´aln´ı otisk dat (digital fingerprint) nebo v´ytah zpr´avy (message digest)
z velk´ych dat vytv´ aˇr´ı haˇsovac´ı funkce jejich identifik´ator (d´ıky bezkoliznosti nejsme schopni nal´ezt jinou zpr´ avu se stejnou haˇs´ı) v ˇradˇe zem´ı stoj´ı digit´ aln´ı otisky na u ´rovni otisk˚ u prst˚ u pro identifikaci lid´ı, proto pˇri digit´ aln´ım podpisu zpr´avy staˇc´ı podepsat jej´ı haˇs
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Ukl´ad´an´ı pˇrihlaˇsovac´ıch hesel
m´ısto hesel se ukl´ adaj´ı jejich haˇse pˇrihlaˇsov´an´ı do syst´emu = v´ypoˇcet haˇse a jeho porovn´an´ı s uloˇzenou hodnotou haˇse neodhaluj´ı hesla, z nichˇz jsou vypoˇcteny
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Kl´ıˇcovan´y haˇsov´y autentizaˇcn´ı k´od HMAC
haˇsov´an´ım zpracov´ av´ a nejen zpr´ avu M, ale i tajn´y kl´ıˇc K pouˇzit´ı: nepadˇelateln´e zabezpeˇcen´ı zpr´av (´ utoˇcn´ık nem˚ uˇze data mˇenit bez zmˇeny HMACu a ten bez tajn´eho kl´ıˇce nevypoˇcte spr´avnˇe) pr˚ ukaz znalosti pˇri autentizaci entit (dotazovatel odeˇsle challenge, od prokazovatele obdrˇz´ı HMAC(challenge, K), ´utoˇcn´ık z odpovˇedi nez´ısk´a kl´ıˇc K)
znaˇcen´ı HMAC-SHA-1(M,K)
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Pseudon´ahodn´e gener´atory chov´an´ı jako n´ahodn´ a or´ akula, zmˇena 1 bitu na vstupu ⇒ zmˇena kaˇzd´eho v´ystupn´ıho bitu s pravdˇepodobnost´ı 50% PKCS#1 v.2.1(RSA Cryptography Standard) definuje MGF1 (Mask Generation Function)
h(seed||0x00000001), h(seed||0x00000002), h(seed||0x00000003), . . . kde 0x hexadecim´ aln´ı vyj´ adˇren´ı dan´eho ˇc´ısla standard pro podpisov´e sch´ema DSA definuje n´ahodn´y gener´ator x0 := K , xj+1 := h((K + 1 + xj ) mod 2m ), kde K je poˇc´ateˇcn´ı vstup (kl´ıˇc) a m d´elka bloku haˇsovac´ı funkce h L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Prolomen´ı haˇsovac´ıch funkc´ı
“masov´a” kryptografie na nedokazateln´ych (nedok´azan´ych) principech prolomen´ı je pˇrirozen´ a vˇec 2004 - prolomena MD5 (2006 Kl´ıma - generov´an´ı koliz´ı na notebooku bˇehem 1 minuty) 2010 - konec platnosti SHA-1 souˇcasn´y platn´y standard SHA-2 je 3kr´ at pomalejˇs´ı
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Soutˇeˇz o SHA-3 listopad 2007 - NIST (americk´y u ´ˇrad pro standardizaci) soutˇeˇz o nov´y haˇsovac´ı standard SHA-3 poˇzadavky: rychlost (SHA-1 7,5 cyklu procesoru/byte, SHA-2 20 cykl˚ u procesoru/byte), n´aroky na pamˇet’ (stovky byt˚ u) 64 algoritm˚ u od 191 kryptolog˚ u (univerzity a elektronick´e giganty, ale i nejvˇetˇs´ı svˇetov´ı v´yrobci z oblasti ˇcip˚ u) napˇr. firmy: Microsoft, Sony, RSA, Intel, IBM, MIT, PGP, Hitachi, zn´am´a jm´ena: Rivest, Schneier ˇ si spojeni s 2 kandid´aty: EDON-R (Aleˇs Dr´apal, Vlastimil Ceˇ Kl´ıma, vlastn´ık a vyn´alezce Danilo Gligoroski), BMW (vlastn´ık-vyn´alezce Gligoroski-Kl´ıma)
ˇcervenec 2009 - vybr´ ano 14 kandid´ at˚ u: BLAKE, BMW, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, Skein prosinec 2011 - vybr´ ano 5 finalist˚ u: BLAKE, Grøstl, JH, Keccak, Skein L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
14 kandid´at˚ u
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
BMW = Blue Midnight Wish
vznikla spoluprac´ı Vlastimila Kl´ımy na vylepˇsen´ı Turbo-SHA Danila Gligorosk´eho a Sveina Knapskoga po roce pr´ace (konec 2008) odesl´ ana do soutˇeˇze NISTu pracovn´ı n´azev nejprve Blue Wish, pak ale autoˇri zjistili, ˇze jde o registrovanou znaˇcku, kdyˇz se po x-t´e o p˚ ulnoci bl´ıˇzili ke koneˇcn´e variantˇe algoritmu, napadlo je Blue Midnight Wish
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Nov´e n´apady poˇzadavek: vˇetˇs´ı bezpeˇcnost i rychlost ⇒ nutnost nov´ych n´apad˚ u soustavy rovnic tvoˇren´e polynomy o mnoha nezn´am´ych (booleovsk´e promˇenn´e) nedovedeme ˇreˇsit v polynomi´aln´ım ˇcase ALE! spoˇc´ıst hodnotu n´ ahodn´eho polynomu 32. stupnˇe s promˇenn´ymi a0 , a1 , . . . , a31 a b0 , b1 , . . . , b31 , napˇr. a0 ∗ a1 ∗ · · · ∗ a31 ⊕ a0 ∗ b0 ∗ b1 ∗ b2 ∗ a12 ⊕ · · · ⊕ je n´aroˇcn´e na pamˇet’ i ˇcas (∼ poˇctu ∗ a ⊕) existuje operace, kterou modern´ı procesory zvl´adaj´ı v 1 taktu (nejrychleji, jak je to moˇzn´e), a pˇresto poskytuje 32 polynom˚ u vysok´ych ˇr´ad˚ u najednou! L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Operace ADD jedn´a se o operaci ADD ( mod 232 )! oznaˇcme a31 . . . a1 a0 bin´ arn´ı z´ apis a a b31 . . . b1 b0 bin´arn´ı z´apis b, s31 . . . s1 s0 bin´ arn´ı z´ apis s = a + b mod 232 a c31 . . . c2 c1 bity pˇrenosu (carry), pak s = (a31 ⊕ b31 ⊕ c31 , . . . , a1 ⊕ b1 ⊕ c1 , a0 ⊕ b0 ) c1 = a0 ∗ b0 c2 = a1 ∗ b1 ⊕ a1 ∗ c1 ⊕ b1 ∗ c1 c3 = a2 ∗ b2 ⊕ a2 ∗ c2 ⊕ b2 ∗ c2 ... c31 = a30 ∗ b30 ⊕ a30 ∗ c30 ⊕ b30 ∗ c30 L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Kandid´ati na SHA-3
dosad´ıme jednotliv´e v´yrazy pro bity pˇrenosu do vyˇsˇs´ıch bit˚ u: c1 = a0 ∗ b0
1 term ˇr´ adu 2
c2 = a1 ∗b1 ⊕a1 ∗a0 ∗b0 ⊕b1 ∗a0 ∗b0
1 term ˇr´ adu 2 a 2 termy ˇr´adu 3
jedinou operac´ı a + b tak vznikne 32 polynom˚ u, kter´e dohromady obsahuj´ı pˇres 2 miliardy term˚ u ˇr´ adu 2 – 32
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Termy v souˇctu 32-bitov´ych ˇc´ısel
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Vlastnosti BMW
pouˇz´ıv´a jen operace ADD a XOR, operace bitov´ych posun˚ u a cyklick´ych bitov´ych posun˚ u podobnˇe vypadaj´ı vˇsichni nejrychlejˇs´ı kandid´ ati (poˇzadavek na rychlost vedl logicky k vyuˇzit´ı operace ADD)
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Spoleˇcn´e prvky SHA-2 a BMW
iterativn´ı princip a kompresn´ı funkce padding = doplnˇen´ı haˇsovan´e zpr´ avy na potˇrebn´y poˇcet bit˚ u, zarovn´an´ı na nejbliˇzˇs´ı n´ asobek 512 nebo 1024 bit˚ u (podle toho, zda jde o BMW256/BMW512, resp. SHA256/SHA512)
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Haˇsov´an´ı 1
pˇredzpracov´an´ı doplˇn zpr´avu M jednoznaˇcnˇe definovan´ym zp˚ usobem o d´elku zpr´avy v bitech a doplnˇek rozdˇel zpr´avu na celistv´y n´asobek N m-bitov´ych blok˚ u M1 , M2 , . . . , MN nastav poˇc´ateˇcn´ı hodnotu pr˚ ubˇeˇzn´e haˇse H0 := IV
2
v´ypoˇcet haˇse for i = 1 to N Hi := f (Mi , Hi −1 )
3
z´avˇer H(M) := definovan´ych n bit˚ u z hodnoty HN
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Mouchy SHA-2 podle NISTu
moˇznost nalezen´ı multikoliz´ı rychlejˇs´ı neˇz u n´ ahodn´eho or´akula u n´ahodn´eho or´akula sloˇzitost nalezen´ı r = 2k multikoliz´ı 2n(r −1)/r operac´ı, u SHA-2 pouze k2n/2 (Joux)
moˇznost nalezen´ı kolize stejn´ a jako u n´ ahodn´eho or´akula (2n/2 podle narozeninov´eho paradoxu) n´achylnost na u ´tok prodlouˇzen´ım zpr´ avy
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Dvojn´asobn´a pumpa
vyuˇzita ˇc´ast´ı kandid´ at˚ u na SHA-3 navrˇzena k ˇreˇsen´ı v´yˇse uveden´ych much Lucksem jde o zdvojn´asoben´ı ˇs´ıˇrky pr˚ ubˇeˇzn´e haˇse a v´ysledn´a haˇs je pak polovina pr˚ ubˇeˇzn´e haˇse k nalezen´ı koliz´ı Jouxov´ym u ´tokem je tˇreba k2n operac´ı v´ypoˇcet ale pak trv´ a cca. 4kr´ at d´ele
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Pumpa BMW
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Ditherovan´ e haˇsovac´ı funkce Naˇ c jsou haˇsovac´ı funkce dobr´ e? Nov´ y haˇsovac´ı standard - SHA-3
Zd˚ uvodnˇen´ı NISTu
Security: We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us ’nervous’, even though we knew of no clear attack against the full algorithm. 31.12.2012 - vyhl´ aˇsen´ı v´ıtˇeze Keccak
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Program
1
Haˇsovac´ı funkce Ditherovan´e haˇsovac´ı funkce Naˇc jsou haˇsovac´ı funkce dobr´e? Nov´y haˇsovac´ı standard - SHA-3
2
Gener´atory n´ahodn´ych ˇc´ısel Aperiodick´y gener´ ator n´ ahodn´ych ˇc´ısel
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Gener´atory n´ahodn´ych ˇc´ısel
rozliˇsujeme dva druhy gener´ ator˚ u: 1
gener´ator prav´ych n´ahodn´ych ˇc´ısel (RNG)
2
gener´ator pseudon´ahodn´ych ˇc´ısel (PRNG)
zaloˇzen na n´ ahodnosti fyzik´ aln´ıch jev˚ u algoritmus vytv´ aˇrej´ıc´ı posloupnosti ˇc´ısel chovaj´ıc´ı se zd´ anlivˇe n´ ahodnˇe
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Line´arn´ı kongruenˇcn´ı gener´ator (LCG) definov´an rekurentn´ım vztahem xn+1 = (axn + c) mod m 0<m 0≤a<m 0≤c<m 0 ≤ x0 < m
modulo multiplik´ ator posunut´ı seed
nev´yhody LCG: periodiˇcnost mˇr´ıˇzkov´a struktura
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Mr´ıˇzkov´a struktura LCG
Obr´azek: RANDU: a = 65539, m = 231 , c = 0
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
APRNG d´any dva LCG X = (xn )n≥0 a Y = (yn )n≥0 a nekoneˇcn´e aperiodick´e slovo u = u1 u2 u3 . . . nad {0, 1} pak APRNG Z = (zn )n≥0 zaloˇzen´y na slovˇe u z´ısk´ame pomoc´ı algoritmu: 1 2
3
postupnˇe ˇcteme p´ısmena slova u ˇcteme-li ve slovˇe u po i-t´e nulu, potom na konec posloupnosti Z pˇrid´ame i-t´y ˇclen posloupnosti X ˇcteme-li ve slovˇe u po i-t´e jedniˇcku, potom na konec posloupnosti Z pˇrid´ame i-t´y ˇclen posloupnosti Y
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Aperiodick´y gener´ator n´ahodn´ych ˇc´ısel
APRNG jsou aperiodick´e APRNG zaloˇzen´e na podtˇr´ıdˇe cut and project“ slov nemaj´ı ” mˇr´ıˇzkovou strukturu L.-S. Guimond, Jan Patera, Jiˇr´ı Patera, Statistical properties and implementation of aperiodic pseudorandom number generators
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Slova s dobˇre rozm´ıstˇen´ymi v´yskyty
APRNG zaloˇzen´e na slovech splˇ nuj´ıc´ıch vlastnost DRV nemaj´ı mˇr´ıˇzkovou strukturu nekoneˇcn´e aperiodick´e slovo u nad {0, 1} m´ a vlastnost DRV pr´avˇe tehdy, kdyˇz pro libovoln´e m ∈ N a pro libovoln´y faktor w splˇ nuje slovo u n´ asleduj´ıc´ı podm´ınku: oznaˇc´ıme i1 , i2 , . . . v´yskyty w v u, pak (|u1 u2 . . . uij |0 , |u1 u2 . . . uij |1 ) mod m j ∈ N = Z2m
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Sturmovsk´a slova
nekoneˇcn´e slovo u nazveme sturmovsk´e, pokud jeho faktorov´a komplexita splˇ nuje Cu (n) = n + 1 pro kaˇzd´e n ∈ N ˇ aperiodick´a (DOKAZTE!) maj´ı vlastnost DRV sturmovsk´a slova jsou ˇsiˇrˇs´ı tˇr´ıdou neˇz cut and project“ slova ” uvaˇzovan´a v ˇcl´anku
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Fibonacciho slovo
sturmovsk´e generov´an´ı pomoc´ı substituce ϕ : 0 7→ 01, 1 7→ 0 f je pevn´y bod substituce ϕ f = 010010100100101001010010010100100101001010 . . .
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Thue-Morseovo slovo
nen´ı sturmovsk´e generov´an´ı pomoc´ı substituce ϕ : 0 7→ 01, 1 7→ 10 t je pevn´y bod substituce ϕ t = 011010011001011010010110011010011001011 . . .
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Thue-Morseovo slovo kombinace stejn´ych LCG pomoc´ı Thue-Morseova slova zachov´av´a mˇr´ıˇzkovou strukturu Thue-Morseovo slovo tedy nem´ a vlastnost DRV
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Ot´azky
Co se dˇeje, kombinujeme-li podle v´ıcep´ısmenn´ych nekoneˇcn´ych slov, tedy kombinujeme-li v´ıce gener´ator˚ u? Existuje i v takov´em pˇr´ıpadˇe podobn´ a kombinatorick´a podm´ınka jako je vlastnost DRV v pˇr´ıpadˇe bin´arn´ıch slov? Zlepˇsuj´ı se kombinac´ı v´ıce gener´ ator˚ u statistick´e vlastnosti vznikl´eho APRNG? Existuje souvislost mezi dalˇs´ımi kombinatorick´ymi vlastnostmi nekoneˇcn´ych slov (komplexita, palindromy, frekvence, n´avratov´a slova apod.) a statistick´ymi vlastnostmi APRNG?
L’. Balkov´ a
SSM
Haˇsovac´ı funkce Gener´ atory n´ ahodn´ ych ˇ c´ısel
Aperiodick´ y gener´ ator n´ ahodn´ ych ˇ c´ısel
Dˇ ekuji za pozornost
L’. Balkov´ a
SSM
