Tento Φlßnek je prvnφ z °ady nepravideln²ch p°φsp∞vk∙, kterΘ majφ za cφl navßzat na p°edchozφ dvoudφln² ·vod do problematiky schΘmat digitßlnφch podpis∙ tφm, ₧e se budou sna₧it teoretick²m, avÜak zßrove≥ v₧dy p°φstupn²m zp∙sobem rozebrat n∞kter² z vybran²ch problΘm∙ v tΘto oblasti, kter² bude v danou dobu aktußlnφ.
Pro tento ·vodnφ dφl byly vybrßny dva (°ekn∞me zah°φvacφ) problΘmy z oblasti schΘmat digitßlnφch podpis∙, kter²mi je jednak sprßvnß terminologie v nßzvoslovφ pro pou₧itΘ transformace, jednak poukßzßnφ na zajφmavou snahu autority NIST spoΦφvajφcφ v zavedenφ nov²ch haÜovacφch funkcφ SHA-256, -384 a -512.
èifrovat, Φi deÜifrovat?
ZaΦn∞me prvnφm problΘmem, na kter² se zam∞°φme vzhledem k siln∞ zako°en∞nΘmu mylnΘmu nßzoru, kter² spojuje podepisovacφ transformaci s operacφ Üifrovßnφ. Nejvφce se s touto problematikou setkßvßme u systΘmu RSA, na kter² lze pohlφ₧et jako na podpisovΘ schΘma vzniklΘ p°evodem asymetrickΘ Üifry na schΘma digitßlnφho podpisu. S ohledem na tento fakt m∙₧e b²t za jist²ch okolnostφ p°φpustnΘ (nebo dokonce vhodnΘ) pou₧φvat mφsto nßzv∙ podepisovacφ a ov∞°ovacφ transformace nßzvy operacφ "p∙vodnφch" û tj. deÜifrovßnφ a Üifrovßnφ. V takovΘm p°φpad∞ je vÜak t°eba d∙sledn∞ dodr₧ovat vzßjemnΘ p°i°azenφ t∞chto operacφ (tj. nezam∞≥ovat Üifrovßnφ s deÜifrovßnφm).
Tolik na ·vod a nynφ se vra¥me k Φlßnku [SDP1], konkrΘtn∞ k mφstu, kde jsme se zab²vali p°evodem asymetrick²ch Üifrovacφch schΘmat (AèS) na schΘmata digitßlnφho podpisu (SDP). Zde jsme rozbor tΘto problematiky ukonΦili tφm, ₧e jsme si °ekli, ₧e deÜifrovacφ transformaci AèS budeme pou₧φvat jako podepisovacφ transformaci SDP a Üifrovacφ transformaci AèS jako ov∞°ovacφ transformaci SDP. Otßzku, zdali p°i operaci podepisovßnφ provßdφme operaci Üifrovßnφ nebo deÜifrovßnφ, jsme tak pova₧ovali za vy°φzenou. PraktickΘ zkuÜenosti vÜak ukazujφ, ₧e touha tvrdit, ₧e p°i podepisovßnφ se Üifruje, je v lidech natolik zako°en∞na, ₧e je patrn∞ vhodnΘ v∞novat tΘto otßzce pon∞kud vφce prostoru. Z praktickΘho hlediska mo₧nß jde o "pouhou" formalitu, avÜak p°i matematickΘm modelovßnφ kryptografie (kterΘ pot°ebujeme nap°φklad pro formßlnφ d∙kazy bezpeΦnosti) je t°eba mφt v t∞chto zßkladnφch otßzkßch zcela jasno.
Nejprve p°ipome≥me, ₧e obecn² model AèS se soust°e∩uje zejmΘna na Üifrovacφ a deÜifrovacφ transformace, kterΘ chßpe jako zobrazenφ mezi mno₧inami otev°en²ch a Üifrov²ch text∙. KlφΦe pou₧itΘ pro jednotlivß zobrazenφ zde p°itom tyto transformace "pouze" parametrizujφ (zcela obecn² model uva₧uje klφΦe jako indexy do mno₧iny vÜech mo₧n²ch Üifrovacφch/deÜifrovacφch transformacφ). To, ₧e u RSA vypadajφ zßkladnφ definice obou transformacφ stejn∞, co₧ nßs nutφ k jejich rozliÜovßnφ podle pou₧itΘho klφΦe, nenφ d∙vodem k tomu, abychom na tomto obecnΘm modelu n∞co m∞nili.
Dßle si uv∞domme, ₧e v po₧adavcφch na AèS se podle obecnΘho modelu hovo°φ pouze o slo₧itosti (nemo₧nosti) deÜifrovat nßhodn∞ vybran² Üifrov² text s pouhou znalostφ Üifrovacφ transformace, kterou byl tento vytvo°en. O slo₧itosti opaΦnΘho problΘmu, tedy o tom, jak by bylo obtφ₧nΘ najφt pro nßhodn∞ zvolenou otev°enou zprßvu jφ odpovφdajφcφ Üifrov² text s pouhou znalostφ deÜifrovacφ transformace, se v tomto modelu nikde nemluvφ!
Z uvedenΘho tak dostßvßme, ₧e pokud chceme najφt u AèS ekvivalent k podepisovacφ transformaci u SDP, potom se musφme soust°edit v²hradn∞ na pou₧itφ deÜifrovacφ transformace. Pouze tak toti₧ m∙₧eme dokßzat platnost zßkladnφ vlastnosti SDP (viz [SDP1]). Pova₧ujeme-li podepisovanß data (z pohledu podepisovacφ transformace) za Üifrov² text c a jejich podpis za odpovφdajφcφ hodnotu otev°enΘho textu m, potom m∙₧eme tvrdit, ₧e tento podpis nebude mo₧nΘ (pro danou hodnotu dat) nalΘzt s pouhou znalostφ ov∞°ovacφ transformace. Pomocφ tΘto transformace, kterou ztoto₧nφme s operacφ Üifrovßnφ, nicmΘn∞ m∙₧eme jednoznaΦn∞ prokßzat, ₧e dan² podpis je platn² (na ·rovni SDP) podle toho, zda platφ c = Ee(m) (p°esn∞jÜφ zp∙sob u₧itφ tΘto transformace viz [SDP1]).
Z uvedenΘho rozboru vypl²vß, ₧e pokud u₧ chceme v p°φpad∞ schΘmat digitßlnφho podpisu vznikl²ch p°evodem asymetrick²ch Üifrovacφch schΘmat pou₧φvat p∙vodnφ terminologii, potom musφme vnit°n∞ p°ijmout fakt, ₧e p°i podpisu dat je vlastn∞ deÜifrujeme.
Opravdu to nejde
SystΘm RSA mß bohu₧el tu (ne)v²hodu, ₧e Üifrovacφ i deÜifrovacφ transformace p°edstavujφ v zßkladnφ definici stejn² vzorec. To by na prvnφ pohled mo₧nß mohlo n∞koho svßd∞t k tomu, ud∞lat alespo≥ u RSA v²jimku a naz²vat podepisovacφ transformaci Üifrovßnφm. To, ₧e toto ani v tomto p°φpad∞ nenφ mo₧nΘ, ukß₧eme s vyu₧itφm alternativnφho zp∙sobu definice deÜifrovacφ transformace, kterou uvßdφ nap°φklad norma PKCS#1. Na obrßzku 1 a 2 jsou uvedeny Üifrovacφ a deÜifrovacφ transformace systΘmu RSA, kterΘ vyhovujφ zmφn∞nΘ norm∞.
Vidφme, ₧e v tomto p°φpad∞ je ji₧ zp∙sob v²poΦtu obou transformacφ r∙zn² a vyu₧φvß rovn∞₧ r∙znΘho formßtu ulo₧enφ klφΦe. AΦkoliv hlavnφm cφlem tΘto ·pravy bylo dφky aplikaci ╚φnskΘ v∞ty o zbytku v²razn∞ urychlit deÜifrovßnφ, poslou₧φ nßm jejφ sekundßrnφ vlastnosti v²hodn∞ k tomu, abychom ukßzali, ₧e transformaci uvedenou na obrßzku 2 nelze oznaΦit jako Üifrovßnφ.
Vlastnφ d∙kaz je velmi jednoduch². Pokud by toti₧ tato transformace (oznaΦme ji pro konkrΘtnφ hodnotu klφΦe jako F) byla Üifrovßnφm, potom by muselo platit, ₧e pro nßhodn∞ zvolen² Üifrov² text c je s pouhou znalostφ F v²poΦetn∞ nemo₧nΘ nalΘzt odpovφdajφcφ otev°en² text m (c = F(m)). Vzhledem ke zp∙sobu definice F vÜak toto neplatφ. Vytvo°φme-li z tΘto transformace novou funkci (nazv∞me ji G) tak, ₧e mφsto hodnot dQ a dP pou₧ijeme hodnoty eQ a eP takovΘ, ₧e eQ*dQ ( 1 (mod (q-1)) a eP*dP ( 1 (mod (p-1)), potom snadno nalezneme hledanΘ m jako m = G(c). Pro vÜechna m ( Zn toti₧ platφ, ₧e G(F(m)) = m. Ani vlastnφ v²poΦet hodnoty funkce G ani jejφ odvozenφ ze znalosti funkce F p°itom zcela jist∞ nejsou v²poΦetn∞ nemo₧nΘ. Odtud jasn∞ vidφme, ₧e funkci F ani p°i nejlepÜφ v∙li nem∙₧eme nazvat Üifrovßnφm.
Funkce SHA-xxx
Patrn∞ mßme jeÜt∞ vÜichni v ₧ivΘ pam∞ti datum 2. °φjna roku 2000, kterΘ vstoupφ do d∞jin kryptografie jako den, kdy byl zvolen nov² nßstupce ji₧ dosti ztrouchniv∞lΘho systΘmu DES. Mßme zde na mysli blokovou symetrickou Üifru Rijndael, kterß byla autoritou NIST (National Institute of Standards and Technology) zvolena nov²m Üifrovacφm standardem zvan²m AES û Advanced Encryption Standard. Vφce informacφ je mo₧nΘ nalΘzt p°φmo na webovΘ strßnce [AES]. Jako Φesk² zdroj pak mohu doporuΦit Φlßnky na strßnce [CRYPTO].
Standard AES jako takov² nßle₧φ k technikßm vyu₧φvan²m zejmΘna k zajiÜt∞nφ slu₧by d∙v∞rnosti p°enßÜen²ch dat, tak₧e na oblast schΘmat digitßlnφho podpisu nemß p°φm² dopad. Vzhledem k tomu, ₧e dnes se ji₧ b∞₧n∞ setkßme s informaΦnφmi systΘmy vyu₧φvajφcφmi kryptografii souΦasn∞ pro n∞kolik ·Φel∙ (zejmΘna pro slu₧by d∙v∞rnost, autentizace subjektu a autentizace p∙vodu dat), p°iΦem₧ pro ka₧d² z t∞chto je po₧adovßna zhruba stejnß ·rove≥ bezpeΦnosti, je jist∞ vhodnΘ zavΘst souΦasn∞ s AES jeÜt∞ dalÜφ kryptografickΘ techniky umo₧≥ujφcφ tΘto ·rovn∞ dosßhnout. S ohledem na tuto filozofii se autorita NIST rozhodla osv∞₧it takΘ dosud vydanΘ standardy haÜovacφch funkcφ. Tento krok ji₧ zaΦφnß b²t pro oblast schΘmat digitßlnφch podpis∙ zajφmav².
Zatφm jedinou haÜovacφ funkcφ, kterß je posv∞cena autoritou NIST, je funkce SHA-1 definovanß dokumentem FIPS PUB 180-1 (jejφ p°edch∙dkyni SHA-0 neuvßdφme). Jak vφme, jednß se o haÜovacφ funkci s dΘlkou v²stupnφho bloku 160 bit∙, o nφ₧ se vÜeobecn∞ p°edpoklßdß, ₧e je jednosm∞rnß (OWHF) a bezkoliznφ (CRHF û oba termφny viz [SDP2]). Z kryptografickΘho hlediska se jednß o celkem oblφbenou a tudφ₧ Üiroce pou₧φvanou haÜovacφ funkci. Nabφzφ se proto otßzka, proΦ zavßd∞t funkce novΘ. Odpov∞∩ se ukr²vß ve slo₧itosti ·toku hrubou silou na schΘmata digitßlnφho podpisu, kterß by m∞la b²t zhruba stejnß, jako je slo₧itost ·toku hrubou silou na algoritmus AES.
Pro lepÜφ srozumitelnost si naznaΦenΘ srovnßnφ rozebereme podrobn∞ji. P°edpoklßdejme, ₧e navrhujeme informaΦnφ systΘm, kter² bude poskytovat slu₧by d∙v∞rnost a autentizace p∙vodu dat (chcete-li zaruΦen² elektronick² podpis). Pro zajiÜt∞nφ d∙v∞rnosti bude p°itom pou₧it algoritmus AES v blokovΘm re₧imu CBC. Zde budou podporovßny vÜechny definovanΘ dΘlky klφΦe tohoto algoritmu: 128b, 192b a 256b.
Zßkladnφ odhad bezpeΦnosti takovΘ slu₧by m∙₧eme s ohledem na pou₧itφ ·toku hrubou silou urΦit jako poΦet operacφ Üifrovßnφ (nebo deÜifrovßnφ) nutn²ch k nalezenφ p°φsluÜnΘho Üifrovacφho klφΦe e tak, ₧e pro znßmou hodnotu otev°enΘho (OT) a ÜifrovΘho textu (èT) budeme postupn∞ zkouÜet vÜechny mo₧nΘ klφΦe, dokud nebude platit èT = Ee(OT) (pro p°ehlednost pou₧φvßme tuto jednoduchou symboliku). Je reßlnΘ p°edpoklßdat, ₧e vzhledem k jistΘ redundanci zprßv v ka₧dΘm informaΦnφm systΘmu bude ·toΦnφk schopen pot°ebnΘ pßry (OT, èT) k provedenφ tohoto ·toku nalΘzt.
Slo₧itost zmφn∞nΘho ·toku, kter² vede p°i nßhodnΘ volb∞ klφΦe s cca 50% pravd∞podobnostφ k jeho nalezenφ, m∙₧eme odhadnout na 2k-1 zmφn∞n²ch operacφ, kde k je dΘlka klφΦe. Vidφme, ₧e i pro nejni₧Üφ dΘlku klφΦe 128 bit∙ dostßvßme zatφm technologicky nep°ekonatelnou slo₧itost.
Podφvejme se, jak jsme na tom u druhΘ ze slu₧eb û u zaruΦenΘho elektronickΘho podpisu. P°edpoklßdejme, ₧e pro vytvo°enφ tΘto slu₧by je pou₧ito schΘma digitßlnφho podpisu s dodatkem. DΘlka klφΦe pou₧itΘho asymetrickΘho algoritmu je p°itom volena tak, aby slo₧itost zßkladnφho znßmΘho ·toku (v p°φpad∞ RSA se jednß o faktorizaci, u DSA jde o ·lohu diskrΘtnφho logaritmu) odpovφdala slo₧itosti zßkladnφho ·toku na AES, kterß byla odvozena v²Üe. Z p°edchozφch pojednßnφ ovÜem vφme, ₧e bezpeΦnost v²slednΘho schΘmatu digitßlnφho podpisu nezßle₧φ jen na kvalit∞ pou₧itΘho asymetrickΘho systΘmu. Ukßzali jsme si, ₧e zde velmi zßle₧φ tΘ₧ na kvalitßch pou₧itΘ haÜovacφ funkce.
Obdobn∞ jako v p°φpad∞ symetrick²ch blokov²ch Üifer m∙₧eme i pro ka₧dou bezkoliznφ (CRHF) haÜovacφ funkci nalΘzt zßkladnφ druh ·toku vedoucφho k nalezenφ kolize, kter² je v₧dy (jako hledßnφ klφΦe hrubou silou) teoreticky mo₧n². V Φlßnku [SDP2] jsme si ukßzali, ₧e nalezenφ kolize u pou₧itΘ haÜovacφ funkce vede (alespo≥ teoreticky) k prolomenφ danΘho schΘmatu digitßlnφho podpisu. Proto je rezistence v∙Φi zßkladnφmu ·toku hledßnφ kolize pro danou haÜovacφ funkci vhodn²m parametrem, podle kterΘho m∙₧eme srovnat zßkladnφ ·rove≥ bezpeΦnosti poskytovanΘ touto funkcφ a algoritmem AES.
Zmφn∞n² zßkladnφ zp∙sob pro hledßnφ kolizφ u haÜovacφch funkcφ vychßzφ ze zajφmavΘ pravd∞podobnostnφ ·vahy, kterß se oznaΦuje jako narozeninov² paradox. Proto se ·toky tohoto typu v originßle Φasto oznaΦujφ jako birthday-attack. Podrobn∞jÜφ rozbor a odvozenφ narozeninovΘho paradoxu nalezne Φtenß° v [MOV96]. My se zde omezφme pouze na p°ipomenutφ st∞₧ejnφho tvrzenφ: M∞jme nßhodnou diskrΘtnφ veliΦinu X, kterß nab²vß koneΦn∞ mnoha (m) hodnot s rovnom∞rn²m rozd∞lenφm. Potom se v posloupnosti hodnot tΘto prom∞nnΘ (x1, x2, x3, ..., xk) o dΘlce k = (m*2ln(2)) 1/2, zhruba s padesßtiprocentnφ pravd∞podobnostφ vyskytnou dv∞ hodnoty stejnΘ. (Narozeninov² paradox zφskßme, pokud si uv∞domφme, ₧e ve skupin∞ o pouh²ch 23 lidech budou se zhruba 50% pravd∞podobnostφ dva lidΘ se stejn²m datem û m∞sφc a den û narozenφ.)
P°ipome≥me si jeÜt∞, ₧e pro nßhodnΘ veliΦiny, jejich₧ poΦet mo₧n²ch hodnot odpovφdß mocnin∞ dvou (m = 2n), existuje pro dΘlku popsanΘ posloupnosti odhad ve tvaru k = 2n/2+0.5. Pomocφ tohoto odhadu m∙₧eme nynφ jednoduÜe urΦit slo₧itost zßkladnφho ·toku na libovolnou haÜovacφ funkci o dΘlce v²stupnφho bloku n bit∙, kter² spoΦφvß v postupnΘm zjiÜ¥ovßnφ v²sledk∙ pro nßhodn∞ volenΘ vstupnφ zprßvy, a to tak dlouho, dokud v tΘto posloupnosti nenajdeme dv∞ hodnoty stejnΘ. Pro tyto hodnoty (xi a xj) potom platφ, ₧e h(zprßvai) = h(zprßvaj) a dvojice (zprßvai, zprßvaj) je hledan² kolidujφcφ pßr vstupnφch zprßv.
Slo₧itost takto pojatΘho ·toku vyjßd°enß pro funkci SHA-1 vychßzφ na zhruba 280,5 zpracovan²ch zprßv. Vidφme, ₧e to je (zanedbejme nynφ pam∞¥ovΘ nßroky) v²razn∞ mΘn∞ ne₧ poΦet operacφ nutn²ch pro ·tok na AES hrubou silou. Z tohoto pohledu tak m∙₧eme vyvodit, ₧e slu₧ba zaruΦenΘho elektronickΘho podpisu v naÜem hypotetickΘm informaΦnφm systΘmu poskytuje v²razn∞ ni₧Üφ ·rove≥ zßkladnφ bezpeΦnosti ne₧li p°edchozφ slu₧ba d∙v∞rnosti.
Abychom tento schodek vyrovnali, je t°eba zavΘst novΘ haÜovacφ funkce s v∞tÜφmi dΘlkami v²stupnφch blok∙, kterΘ by (podle narozeninovΘho paradoxu) m∞ly odpovφdat dvojnßsobk∙m standardnφch dΘlek klφΦ∙ pro AES. Prßv∞ tφmto sm∞rem se autorita NIST vydala, kdy₧ celkem nedßvno uve°ejnila nßvrhy haÜovacφch funkcφ nazvan²ch jako SHA-256, SHA-384 a SHA-512 (jejich definice viz [SHA-xxx]). ╚φslo za pomlΦkou p°itom zcela z°ejm∞ udßvß prßv∞ dΘlku v²stupnφho bloku. P°edpoklßdß se, ₧e tyto funkce budou vydßny jako oficißlnφ standard zhruba v dob∞, kdy bude vydßn standard AES (asi druhΘ Φtvrtletφ roku 2001).
Rozbor vlastnφch funkcφ SHA-xxx ji₧ p°esahuje rßmec tohoto Φlßnku, tak₧e se jφm zde zab²vat nebudeme. Pro nßs bylo d∙le₧itΘ zejmΘna poukßzat na nutnost udr₧enφ odpovφdajφcφ ·rovn∞ bezpeΦnosti p°es vÜechny pou₧itΘ mechanismy a uvΘst konkrΘtnφ zp∙sob, kter² tohoto stavu umo₧≥uje dosßhnout. Tabulka na obrßzku 3 shrnuje doporuΦovan² zp∙sob kombinace funkcφ SHA-xxx pro schΘma digitßlnφho podpisu s algoritmem AES o p°φsluÜnΘ dΘlce klφΦe.
Zßv∞rem tΘto Φßsti jeÜt∞ t°i poznßmky: Za prvΘ je t°eba poznamenat, ₧e pojem "odpovφdajφcφ ·rove≥ bezpeΦnosti" je sice zajφmav²m zaklφnadlem, avÜak teoretick² aparßt umo₧≥ujφcφ p°esn² popis tohoto fenomΘnu zatφm chybφ (a asi jeÜt∞ dlouho chyb∞t bude). DoporuΦenφ plynoucφ z popsan²ch ·vah je tak t°eba chßpat jako nejlepÜφ mo₧nΘ odhady, jejich₧ dodr₧enφm rozhodn∞ nelze nic pokazit. Druhß poznßmka se pak t²kß toho, ₧e NIST nenφ rozhodn∞ jedinou institucφ, kterß nabφzφ "delÜφ" haÜovacφ funkce. Z ostatnφch zmi≥me nap°φklad RIPEMD-320. Na SHA-xxx je vÜak zajφmavΘ to, ₧e pochßzejφ od stejnΘ autority jako AES, co₧ mß jist∞ urΦitou vßhu.
KoneΦn∞ t°etφ poznßmka °φkß, ₧e nevyrovnanß zßkladnφ bezpeΦnost u jednotliv²ch slu₧eb IS jeÜt∞ ne°φkß, ₧e je n∞kterß z t∞chto slu₧eb p°φmo napadnutelnß. ╪φkß pouze tolik, ₧e mezi bezpeΦnostφ jednotliv²ch slu₧eb existujφ urΦitΘ disproporce, kterΘ mohou b²t z urΦitΘho pohledu na Ükodu.
Zßv∞r
V tomto p°φsp∞vku jsme si ukßzali, ₧e podepisovacφ transformace u podpisov²ch schΘmat vznikl²ch p°evodem schΘmat Üifrovacφch musφ odpovφdat zßsadn∞ operaci deÜifrovßnφ. Proto je t°eba uvßd∞t, ₧e p°i podpisu se data deÜifrujφ, nikoliv zaÜifrujφ.
Dßle jsme upozornili na navrhovanΘ standardy nov²ch haÜovacφch funkcφ. Zde jsme uvedli, ₧e primßrnφm ·Φelem t∞chto funkcφ, jejich₧ finßlnφ uvoln∞nφ je plßnovßno spolu s uvoln∞nφm algoritmu AES, nenφ poskytnout prost°edek pro odvozovßnφ klφΦe pro algoritmus AES (i kdy₧ se samoz°ejm∞ v²born∞ hodφ i k tomuto ·Φelu), ale umo₧nit vyrovnßnφ zßkladnφ ·rovn∞ bezpeΦnosti u jednotliv²ch slu₧eb informaΦnφho systΘmu.
TomᚠRosa
mailto:tomas.rosa@decros.cz
literatura
[MOV96] Menezes, A. J., van Oorschot, P. C., Vanstone, S. A.: Handbook of Applied Cryptography, CRC Press 1996
[SDP1] Rosa, T.: Podpis pro pokroΦilΘ (1), CHIP 11/00, str. 174 û 178, dostupnΘ v [CRYPTO]
[SDP2] Rosa, T.: Podpis pro pokroΦilΘ (2), CHIP 12/00, str. 172 û 176, dostupnΘ v [CRYPTO]
P°ehled doporuΦen²ch kombinacφ funkcφ SHA-xxx s AES (Rijndael).
Kombinace Rijndael-yyy a SHA-xxxSlo₧itost luÜt∞nφ hrubou silouSlo₧itost hledßnφ kolizφRijndael-128 a SHA-25621272128.5Rijndael-192 a SHA-38421912192.5Rijndael-256 a SHA-51222552256.5
