Nepopiratelnost. To slovo lΘtß vzduchem snad na ka₧dΘ p°ednßÜce o elektronickΘm podepisovßnφ. NejΦast∞ji zde symbolizuje vφru u₧ivatel∙, ₧e nikdo nem∙₧e pozd∞ji jednoduÜe tvrdit, ₧e jφm podepsan² dokument ve skuteΦnosti nikdy nepodepsal a podepsat ani necht∞l. Opravdu nem∙₧e? O jednΘ, sice teoretickΘ, leΦ pro praxi nikterak slibn∞ vyhlφ₧ejφcφ mo₧nosti bude pojednßno v nßsledujφcφm Φlßnku.
Na ·vod si nejprve uve∩me volnou, ale dostateΦn∞ nßzornou definici pojmu nepopiratelnost: O systΘmu °ekneme, ₧e poskytuje slu₧bu nepopiratelnosti, pokud pro nezßvislou t°etφ stranu existuje zp∙sob, jak se jednoznaΦn∞ (se zanedbatelnou pravd∞podobnostφ omylu) p°esv∞dΦit o tom, ₧e danß akce v systΘmu nastala, respektive nenastala. Pod pojmem akce si m∙₧eme p°edstavit nap°φklad prßv∞ podepsßnφ dokumentu Φi autentizaci subjektu do systΘmu.
Z kryptologickΘho hlediska chßpeme nepopiratelnost jako jednu ze zßkladnφch slu₧eb (vedle ostatnφch, jako jsou d∙v∞rnost, integrita a autentizace), kterΘ se sna₧φme vhodnou konstrukcφ kryptografick²ch mechanism∙ zajistit. Situace je p°itom ve v∞tÜin∞ ohled∙ podobnß zmφn∞n²m ostatnφm slu₧bßm. Vezm∞me si nap°φklad starou znßmou slu₧bu zajiÜt∞nφ d∙v∞rnosti. Vφme, ₧e zßkladem vÜeho je kvalitnφ Üifrovacφ algoritmus, ale ₧e ten sßm o sob∞ je pouze podmφnkou nutnou (a nikoliv postaΦujφcφ). Vφme, ₧e je t°eba jeÜt∞ vybudovat kvalitnφ klφΦovΘ hospodß°stvφ, p°iΦem₧ zvlßÜtnφ pozornost musφ b²t v∞novßna zp∙sobu ulo₧enφ klφΦovΘho materißlu, a tak dßle. V p°φpad∞ nepopiratelnosti je situace v zßsad∞ obdobnß. Nejprve musφme mφt kryptografickΘ schΘma schopnΘ tuto slu₧bu zajistit a potΘ je nutnΘ v∞novat pozornost nßvaznosti na ostatnφ procesy informaΦnφho systΘmu tak, aby t°etφ strana (soud) byla v p°φpad∞ n∞jakΘho sporu schopna nezßvisle rozhodnout ve smyslu v²Üe zavedenΘ definice.
V nßsledujφcφm textu se budeme v∞novat problematice (ne)popiratelnosti digitßlnφch podpis∙, i kdy₧ zde p°edstavenß technika ·toku je aplikovatelnß i v ostatnφch p°φpadech, kdy je danΘ podpisovΘ schΘma vyu₧ito k zajiÜt∞nφ mφrn∞ odliÜnΘ slu₧by - nap°φklad prßv∞ k autentizaci u₧ivatel∙.
Rovn∞₧ poznamenejme, ₧e ·tok, kter² bude dßle popsßn, se zam∞°uje na prolomenφ nepopiratelnosti p°φmo u zßkladnφch podpisov²ch schΘmat, tedy nikoliv ve vyÜÜφch vrstvßch systΘmu. Pro lepÜφ porozum∞nφ technikßm popφrßnφ podpisu je vhodnΘ si uvΘst, jak²m zp∙sobem se vlastn∞ proti u₧ivateli z°φkajφcφmu se svΘho podpisu vede d∙kaz na kryptologickΘ ·rovni. Budeme zde p°itom p°edpoklßdat znalosti na ·rovni Φlßnk∙ [7]. Vφme, ₧e u schΘmat digitßlnφho podpisu se mimo jinΘ opφrßme o zßkladnφ vlastnost, kterß °φkß, ₧e: Pro libovolnou zprßvu je v²poΦetn∞ nemo₧nΘ p°i pouhΘ znalosti ve°ejnΘho klφΦe a parametr∙ nalΘzt jejφ platn² podpis (obecn∞ji viz [7]). Platφ-li tato hypotΘza a p°edpoklad, ₧e pouze dan² u₧ivatel znß sv∙j privßtnφ klφΦ a jakΘkoliv jeho pou₧itφ musφ b²t tφmto u₧ivatelem v∞dom∞ schvßleno (toto je nutno explicitn∞ zajistit organizaΦn∞-technick²mi prost°edky), potom ka₧d² platn² podpis usv∞dΦuje danΘho u₧ivatele z toho, ₧e dan² dokument opravdu podepsal. Nynφ se v₧ijme do situace, kdy bude u₧ivatel chtφt sv∙j podpis pop°φt. Aby tak uΦinil, musφ zpochybnit platnost n∞kterΘho z tvrzenφ (Φi spφÜe z p°edpoklad∙), kterΘ jsou v d∙kaznφm procesu pou₧ity. Na v²b∞r mß zejmΘna napadenφ:
a) jednoznaΦnosti obsahu zprßvy (viz [7]);
b) platnosti zßkladnφ vlastnosti;
c) v²hradnφ kontroly nad privßtnφm klφΦem.
Cφlem p°itom v₧dy je p°inΘst zmφn∞nΘ d∙v∞ryhodnΘ t°etφ stran∞ alternativnφ vysv∞tlenφ toho, proΦ jen se pod dan²m dokumentem nachßzφ platn² podpis, kdy₧ jej nßÜ u₧ivatel ve skuteΦnosti vlastn∞ v∙bec nepodepsal. Je velmi d∙le₧itΘ si zde uv∞domit, ₧e veÜkerΘ "dokazovßnφ" je zde zalo₧eno na tom, ₧e u₧ivatel takovΘ alternativnφ vysv∞tlenφ, kterΘ by vypadalo alespo≥ trochu v∞rohodn∞, p°edlo₧it nedokß₧e. Jakmile by takovΘ vysv∞tlenφ p°inesl, musφ se jφm t°etφ strana zaΦφt vß₧n∞ zab²vat, a pokud zase ona nep°ijde s rozumn²m d∙vodem, proΦ je to celΘ nesmysl, ·toΦnφk vyhrßl. Alespo≥ tedy ve sv∞t∞ teoretickΘ kryptologie.
Praxe m∙₧e b²t nakonec jinß a na zßklad∞ fenomΘnu zvanΘho zdrav² lidsk² rozum p°ece jen ·toΦnφka zarazit. NicmΘn∞ nemusφ to tak b²t v₧dy, a proto bychom nad chybami v teorii rozhodn∞ nem∞li zavφrat oΦi. Prßv∞ proto se kryptologovΘ sna₧φ ze vÜech sil, vym²Ülφ a kombinujφ, aby si vΦas sami povÜimli by¥ jen trochu rozumn∞ vypadajφcφ cesty vedoucφ k uvedenΘmu alternativnφmu vysv∞tlenφ. Kdy₧ uvß₧φme, ₧e ve sv∞tle ryze matematickΘho pojetφ je °ada souΦasn²ch kryptografick²ch mechanism∙ pon∞kud na vod∞ (toto tΘma by s p°ehledem vydalo na samostatnou knihu), nenφ to rozhodn∞ lehkß a u₧ v∙bec ne rutinnφ prßce, kterß by Üla n∞jak metodicky podchytit (v tom je ovÜem takΘ jejφ kouzlo).
Pojem k-kolize
Vφme, ₧e slovo kolize ve spojenφ s digitßlnφm podpisem rozhodn∞ nev∞Ütφ nic dobrΘho. V∞tÜinou se zde mluvφ o kolizi pou₧itΘ haÜovacφ funkce (h), co₧ znamenß, ₧e ·toΦnφk disponuje dv∞ma r∙zn²mi zprßvami (m1,2) se stejn²m haÜov²m k≤dem (Φili h(m1) = h(m2)). Vzhledem k tomu, ₧e na ·rovni b∞₧n²ch podpisov²ch schΘmat se haÜovΘ k≤dy pova₧ujφ za dostateΦn∞ v∞rnΘ reprezentanty podepisovan²ch zprßv, je ·tok na nepopiratelnost doslova nabφledni. U₧ivatel se bude p°i popφrßnφ svΘho podpisu sna₧it stranu provßd∞jφcφ d∙kaz p°esv∞dΦit o tom, ₧e mφsto m1 ve skuteΦnosti podepsal m2 Φi obrßcen∞. V drtivΘ v∞tÜin∞ p°φpad∙ tak dosßhne alespo≥ podstatnΘho prodlou₧enφ celΘho sporu. KryptologovΘ o tomto problΘmu samoz°ejm∞ v∞dφ a usilovn∞ pracujφ na tom, aby pou₧φvanΘ haÜovacφ funkce hledßnφ kolizφ neumo₧≥ovaly.
ProblΘmem, na kter² bylo poprvΘ poukßzßno v pracφch [6, 5], vÜak je, ₧e zprßvy nejsou tφm jedin²m, co m∙₧e v danΘm schΘmatu kolidovat! Kolidovat mohou toti₧ takΘ ve°ejnΘ klφΦe. O tom, jak takovß situace vypadß, hovo°φ nßsledujφcφ definice: Dvojici r∙zn²ch ve°ejn²ch klφΦ∙ (PubA,B) nazveme klφΦovou kolizφ (dßle k-kolizφ, tΘ₧ k-kolizφ prvnφho druhu), pokud existuje zprßva m a jejφ podpis S tak, ₧e S je platn² podpis zprßvy m vzhledem k ob∞ma ve°ejn²m klφΦ∙m PubA i PubB.
Stejn∞ jako je v p°φpad∞ haÜovacφch funkcφ ne₧ßdoucφ, aby byl ·toΦnφk schopen nalΘzt kolizi podepisovan²ch zprßv, je zde ne₧ßdoucφ to, aby byl schopen zkonstruovat k-kolizi. V opaΦnΘm p°φpad∞ toti₧ m∙₧e k t°etφ nezßvislΘ stran∞ p°ijφt snadno s alternativnφm vysv∞tlenφm, kde bude tvrdit, ₧e dan² podpis by sice mohl b²t jeho, ale ₧e ve skuteΦnosti jeho nenφ! Jako d∙kaz pak p°edlo₧φ druh² z kolidujφcφch ve°ejn²ch klφΦ∙ a osobu s nφm spojenou, kterß naopak bude tvrdit, ₧e danou zprßvu skuteΦn∞ podepsala.
Jist∞ si umφme p°edstavit praktickou situaci, kdy by nßm pomohlo, pokud bychom mohli pozd∞ji sv∙j podpis "hodit" na n∞koho jinΘho (n∞kdy to m∙₧e b²t i vzßjemn∞ v²hodnΘ). Celß situace je ilustrovßna na obrßzku 1. Pro lepÜφ nßzornost zde mφsto samostatn²ch ve°ejn²ch klφΦ∙ a parametr∙ schΘmatu vystupujφ jejich autentizovanΘ nosiΦe - certifikßty. S ohledem na dalÜφ zam∞°enφ tohoto p°φsp∞vku zde takΘ uvßdφme podpis implicitn∞ ve tvaru dvojice hodnot (r, s).
JeÜt∞ horÜφch p°ekvapenφ se m∙₧eme doΦkat v p°φpad∞, kdy je znßm nekooperativnφ postup vedoucφ ke zvlßdnutelnΘmu hledßnφ k-kolizφ. To znamenß, ₧e ·toΦnφk je schopen nalΘzt kolidujφcφ ve°ejn² klφΦ (nejlΘpe vΦetn∞ privßtnφho), ani₧ by od majitele prvnφho klφΦe pot°eboval jakΘkoliv informace, kterΘ nejsou ve°ejn∞ k dispozici. V takovΘm p°φpad∞ se m∙₧e ·toΦnφk namφsto popφrßnφ svΘho podpisu naopak aktivn∞ hlßsit k podpisu cizφmu.
Na prvnφ pohled to nevypadß jako vß₧n² nedostatek, nebo¥ je-li dokument ve°ejn², m∙₧e jej kdokoliv a kdykoliv bez obav podepsat. UrΦit∞ bychom vÜak naÜli °adu p°φpad∙, kdy nenφ mo₧nΘ, aby dokument podepsal kdokoliv a kdykoliv, a pak lze logicky usuzovat na to, ₧e ·toΦnφk zφskß nekooperativnφm v²poΦtem k-kolize jistou nezanedbatelnou v²hodu. Jako p°φklad si m∙₧eme uvΘst situaci, kdy je podepsan² dokument opat°en n∞jak²m razφtkem (Φasov²m, notß°sk²m podpisem apod.). Toto razφtko ji₧ nelze pozd∞ji "podlΘzt", tak₧e p°idßnφ novΘho Φi nßhrada starΘho podpisu nejsou jednoduÜe mo₧nΘ. Pokud vÜak p∙vodnφ razφtko nepokr²vß takΘ detailnφ informace o ve°ejnΘm klφΦi, kter² se mß k ov∞°enφ podpisu pou₧φt (co₧ se bohu₧el v praxi stßvß), m∙₧e ·toΦnφk takto orazφtkovan² podpis sm∞le vydßvat za sv∙j. Tato situace je ilustrovßna v levΘ Φßsti obrßzku 1.
V²poΦet k-kolizφ u (EC)DSA
Existenci a zp∙soby hledßnφ k-kolizφ m∙₧eme studovat u ka₧dΘho schΘmatu digitßlnφho podpisu, pochopiteln∞ ovÜem s r∙zn²m v²sledkem. Zatφm byla tato problematika otev°ena v souvislosti se schΘmaty RSA ([6]) a (EC)DSA ([6, 5]). V obou p°φpadech existujφ v²poΦetn∞ trivißln∞ sch∙dnΘ postupy pro nekooperativnφ hledßnφ k-kolizφ pro prakticky libovolnΘ hodnoty vstupnφ zprßvy, jejφho podpisu a ve°ejnΘho klφΦe (vΦetn∞ ve°ejn²ch parametr∙). NejjednoduÜÜφ je pak situace jednoznaΦn∞ v p°φpad∞ (EC)DSA, kdy je navφc velmi obtφ₧n∞ prokazatelnΘ, kter² z dvojice kolidujφcφch ve°ejn²ch klφΦ∙ byl vytvo°en ·toΦnφkem. To v²razn∞ zt∞₧uje potencißlnφ spory o autorstvφ podpisu v p°φpad∞, ₧e se k n∞mu aktivn∞ hlßsφ oba majitelΘ kolidujφcφch klφΦ∙ (viz nφ₧e). Dßle se proto budeme v∞novat prßv∞ schΘmatu (EC)DSA ([2, 3, 4]).
Z d∙vodu rozsahu Φlßnku musφme ud∞lat jeÜt∞ jeden zjednoduÜujφcφ krok. Vlastnφ popis ·toku provedeme pouze na DSA s tφm, ₧e hned zde zkonstatujeme, ₧e uveden² postup je trivißln∞ rozÜi°iteln² i na (EC)DSA, co₧ bylo ukßzßno v [6]. Sama jednoduchost tohoto p°echodu je zde pozoruhodnß a plyne z toho, ₧e ·tok vyu₧φvß velmi obecn²ch algebraick²ch vlastnostφ DSA, kterΘ jsou s ECDSA spoleΦnΘ.
Hlavnφ partie schΘmatu DSA jsou p°ipomenuty na obrßzku 2, vlastnφ postup v²poΦtu kolidujφcφ instance je uveden na obrßzku 3. Podrobn∞jÜφ rozbor tohoto algoritmu je podßn v [6, 5], zde se zam∞°φme pouze na jeho hlavnφ body. P°ipome≥me, ₧e cφlem v²poΦtu je pro znßmou hodnotu podpisu (r, s) zprßvy m a ve°ejn² klφΦ yA s parametry (pA, qA, gA) najφt ve°ejn² klφΦ yB s parametry (pB, qB, gB) tak, aby (yA, yB) vytvß°ely na podpisu (r, s) zprßvy m k-kolizi. V prvnφm kroku algoritmu zaΦφnßme tφm, ₧e poklßdßme pB = pA a qB = qA. Tento krok je zcela v souladu s definicφ DSA [2], kde se p°edpoklßdß, ₧e vφce u₧ivatel∙ m∙₧e sdφlet spoleΦnΘ ve°ejnΘ parametry. Pokud se pou₧ijφ mechanismy pro sv∞dectvφ o sprßvnΘm vygenerovßnφ t∞chto hodnot ([2]), tak je k tomu dokonce i dobr² d∙vod. V p°φpad∞ ECDSA tento krok odpovφdß tomu, ₧e ·toΦnφk pou₧ije stejnou eliptickou k°ivku nad stejn²m t∞lesem jako majitel instance A. Takov² postup je zcela b∞₧n² a na prvnφ pohled rovn∞₧ nebudφ ₧ßdnΘ podez°enφ (zvlßÜt∞ kdy₧ A pou₧il n∞kterou ze standardizovan²ch k°ivek [2]).
V krocφch (ii) a₧ (v) je nalezen generßtor gB spolu s hodnotou doΦasnΘho klφΦe zprßvy kB pro podpis od u₧ivatele B. Zde je patrn∞ hlavnφ moment celΘho postupu, kdy dφky (velmi obecn²m) algebraick²m vlastnostem DSA umφme najφt hodnoty gB, kB tak, aby platilo r = (gBkB mod pB) mod qB, ani₧ bychom byli nuceni °eÜit slo₧it² problΘm diskrΘtnφho logaritmu. V jistΘm, zcela nepravd∞podobnΘm p°φpad∞ se m∙₧e stßt, ₧e jsme p°φmo naÜli kB = kA. Potom jednoduÜe podle rovnice pro sA (viz obrßzek 2, krok (iii)) najdeme p°φmo privßtnφ klφΦ xA u₧ivatele A. Zde si nelze odpustit jist² komentß° - toti₧ stojφ za poznamenßnφ, ₧e pokud ·toky tohoto typu z n∞jakΘho d∙vodu b∞hem v²poΦtu vyboΦφ z "normßlnφch" kolejφ, potom v∞tÜinou ku prosp∞chu ·toΦnφka, kter² tak zφskß nakonec vφc, ne₧ p∙vodn∞ cht∞l!
Dßle algoritmus pokraΦuje nalezenφm hodnot privßtnφho a ve°ejnΘho klφΦe u₧ivatele B. V poznßmkßch je pak uveden vztah mezi t∞mito hodnotami a klφΦi na stran∞ u₧ivatele A. Z t∞chto poznßmek je vid∞t, ₧e ve velmi specißlnφm p°φpad∞ se m∙₧e stßt, ₧e v²sledkem algoritmu bude yB = yA. Takovß situace vÜak nastßvß se zanedbatelnou pravd∞podobnostφ, a proto ji zde nebudeme uva₧ovat.
Za zmφnku dßle stojφ hodnota b, kterß ob∞ instance v podstat∞ odd∞luje a kterß je zßvislß na nßhodn²ch Φφslech kA a z, p°iΦem₧ ka₧dΘ z nich je voleno jin²m u₧ivatelem. K tomu, aby jeden z nich dokßzal ob∞ instance propojit, musφ znßt ob∞ tyto hodnoty (nebo b²t schopen rozbφt DSA zcela, co₧ nep°edpoklßdßme). Odtud plyne, ₧e oba majitelΘ kolidujφcφch instancφ vystupujφ p°ed t°etφ d∙v∞ryhodnou stranou ve zcela symetrick²ch pozicφch a na zßklad∞ pouhΘ matematiky stojφcφ za DSA nelze rozhodnout, kter² z nich vlastnφ "pad∞lanou" instanci. Ob∞ instance lze samoz°ejm∞ bez problΘm∙ (a¥ u₧ s funkΦnostφ Φi s bezpeΦnostφ) pou₧φvat k "normßlnφmu" podepisovßnφ. Vφce o vlastnostech vypoΦten²ch instancφ viz [6, 5].
Samoz°ejm∞ i zde p°ichßzφ zßchrana v podob∞ mechanism∙ vyÜÜφ ·rovn∞. Nap°φklad druh² u₧ivatel bude mφt problΘm zφskat d∙v∞ryhodn² certifikßt datujφcφ vznik jeho instance zp∞t do minulosti, tak₧e pomocφ zdravΘho lidskΘho rozumu snad nakonec bude rozhodnuto sprßvn∞. Na druhΘ stran∞ je to jasnΘ selhßnφ DSA, kterΘ by do vyÜÜφch vrstev rozhodn∞ nem∞lo pouÜt∞t takovΘ "Üpeky".
Protiopat°enφ a k-kolize druhΘho druhu
Za hlavnφ opat°enφ proti uvedenΘmu ·toku lze pova₧ovat rozÜφ°enφ kontrol korektnφho vygenerovßnφ parametr∙ p, q ([2]) i na generßtor g. Tφm by ·toΦnφk ztratil mo₧nost libovolnΘ volby tohoto parametru, na Φem₧ je cel² jeho postup zalo₧en. Zßkladnφ princip zmφn∞n²ch kontrol spoΦφvß v tom, ₧e sledovanΘ parametry jsou vytvß°eny jednosm∞rn²mi funkcemi (fp, fq), p°iΦem₧ systΘm krom∞ (p, q) uchovßvß takΘ SEEDp a SEEDq, kde p = fp(SEEDp), q = fq(SEEDq). Tento vztah lze kdykoliv ov∞°it a dφky jednosm∞rnosti pou₧it²ch funkcφ nelze testovacφ hodnoty SEEDp a SEEDq pad∞lat (v souΦasnΘ definici [2] se pou₧φvß jedna spoleΦnß hodnota SEED). Analogick² mechanismus existuje i pro ECDSA.
Je celkem s podivem, ₧e tato technika nebyla rozÜφ°ena i na generßtor g (toto u₧ v minulosti zp∙sobovalo problΘmy - viz [8], kde je diskutovßna problematika "klasick²ch" kolizφ zprßv). Tento krok by proto nynφ m∞l logicky nßsledovat. Nelze ovÜem dop°edu °φci, zda a kdy se k n∞mu americkß autorita NIST odhodlß (o ·toku byla informovßna), tak₧e zatφm nezb²vß ne₧ obdobn² mechanismus v citliv²ch systΘmech zavΘst po svΘm. Prakticky by pak vyhodnocenφ sprßvnosti podpisu probφhalo podle obrßzku 4. Poznamenejme, ₧e operßtor AND na konci postupu v podstat∞ existuje u₧ dnes a vstupujφ sem podmφnky, jako je platnost certifikßtu apod.
V jist²ch p°φpadech m∙₧e pomoci jeÜt∞ jeden druh protiopat°enφ a tφm je p°idßnφ detailnφch informacφ o ve°ejnΘm klφΦi (nejlΘpe celΘho certifikßtu) do podepisovan²ch dat. Podle osobnφch zkuÜenostφ s nßvrhß°i informaΦnφch systΘm∙ mohu konstatovat, ₧e tento postup vypadß z jejich pohledu elegantn∞ a jednoduÜe. D∙razn∞ zde ovÜem podot²kßm, ₧e to rozhodn∞ nenφ univerzßlnφ opat°enφ a ₧e m∙₧e stejn∞ elegantn∞ a jednoduÜe selhat. Abychom vid∞li proΦ, musφme nejprve zavΘst k-kolize druhΘho druhu: Dvojici r∙zn²ch ve°ejn²ch klφΦ∙ (PubA,B) nazveme k-kolizφ druhΘho druhu, pokud existujφ dv∞ zprßvy m1,2 a jeden podpis S tak, ₧e S je platn² podpis zprßvy m1 vzhledem ke klφΦi PubA a zßrove≥ S je platn² podpis zprßvy m2 vzhledem ke klφΦi PubB. Na rozdφl od k-kolize prvnφho druhu nestanovujeme u druhΘho druhu to, ₧e se podpis musφ vztahovat ke stejnΘ hodnot∞ zprßvy. Takovß kolize je u₧iteΦnß prßv∞ v p°φpad∞ ·toΦenφ na zmφn∞nΘ elegantnφ a jednoduchΘ protiopat°enφ.
Celß situace je naznaΦena na obrßzku 5. Vidφme, ₧e pro u₧ivatele A a B se liÜφ konkrΘtnφ hodnota zprßvy, kterou nakonec oba podepisujφ. Tato odliÜnost je zp∙sobena prßv∞ p°idßnφm informacφ o ve°ejnΘm klφΦi. Pokud je vÜak tato informace p°idßna tak, ₧e ji lze kdykoliv vym∞nit (tj. nenφ pevn∞ svßzßna s vlastnφ zprßvou n∞jakou formou razφtka - pozor, i zde se mohou uplatnit k-kolize), m∙₧e ·toΦnφk se schopnostφ hledat k-kolize druhΘho druhu pro libovolnΘ dvojice zprßv snadno zvφt∞zit.
Nynφ ji₧ zb²vß jen ukßzat, ₧e u (EC)DSA lze snadno nekooperativn∞ hledat i k-kolize druhΘho druhu, a to pro prakticky libovolnou dvojici m1,2. Pou₧ijeme k tomu p°φmo algoritmus z obrßzku 3, kde v kroku (ii) pou₧ijeme jako m zprßvu m1 a v kroku (vi) jako m dosadφme m2. Poznßmky na konci algoritmu pak budou pochopiteln∞ vypadat pon∞kud jinak. S ohledem na rozsah Φlßnku vÜak jejich odvozenφ musφme ponechat na "domßcφ cviΦenφ".
Zßv∞r
Problematika klφΦov²ch kolizφ v podpisov²ch schΘmatech p°edstavuje hrozbu pro systΘmy spolΘhajφcφ se na nepopiratelnost elektronic-kΘho podepisovßnφ zalo₧enΘho na bßzi schΘmat digitßlnφho podpisu. V p°φsp∞vku jsme si v hrub²ch rysech p°edstavili tento zcela p∙vodnφ zp∙sob ·toku na podpisovß schΘmata, p°iΦem₧ jako konkrΘtnφ p°φklad bylo p°edvedeno napadenφ schΘmatu (EC)DSA, je₧ spolu s RSA (u kterΘho lze takΘ najφt tento druh ·toku - viz [6]) pat°φ celosv∞tov∞ k nejrozÜφ°en∞jÜφm.
S ohledem na praktickΘ systΘmy je hrozba plynoucφ z rozebφranΘho ·toku zatφm spφÜe teoretickß. Tento stav vÜak nenφ ani tak zp∙soben "zßzraΦnou" odolnostφ praktick²ch systΘm∙, jako skuteΦnostφ, ₧e dosud neexistuje mnoho takov²ch aplikacφ, ve kter²ch by se zisk z prolomenφ nepopiratelnosti vyrovnal vynalo₧enΘmu ·silφ. V okam₧iku, kdy takovΘ systΘmy vzniknou, stane se uvedenß hrozba mnohem reßln∞jÜφ. Proto je jist∞ vhodnΘ vyu₧φt tento "oddechov²" Φas k implementaci p°φsluÜn²ch protiopat°enφ.
TomᚠRosa, autor@chip.cz
Literatura: [1] Archiv Φesk²ch Φlßnk∙ o kryptologii, www.decros.cz/bezpecnost/_kryptografie.html. [2] FIPS PUB 186-2: Digital Signature Standard (DSS), National Institute of Standards and Technology, January 27, 2000, http://csrc.nist.gov/publications/fips/fips1862/fips186-2.pdf, update: October 5, 2001. [3] Klφma, V.: EliptickΘ k°ivky a Üifrovßnφ (1 - 2), CHIP, zß°φ °φjen 2002, dostupnΘ v [1]. [4] Klφma, V.: PoΦφtaΦovß bezpeΦnost (DSS): Podpis bez pera i papφru, Chip, kv∞ten 1999, dostupnΘ v [1]. [5] Rosa, T.: On Key-collisions in (EC)DSA, CRYPTO 2002 Rump Session, Santa Barbara, USA, August 2002, http://eprint.iacr.org/2002/129/. [6] Rosa, T.: O klφΦov²ch kolizφch v podpisov²ch schΘmatech, Sbornφk p°ednßÜek seminß°e VelikonoΦnφ kryptologie, str. 14 - 26, Brno, 2002, dostupnΘ v [1]. [7] Rosa, T.: Podpis pro pokroΦilΘ (1 - 2), Chip, listopad prosinec 2000, dostupnΘ v [1]. [8] Vaudenay, S.: Hidden Collisions on DSS, in Proc. of CRYPTO '96, pp. 83-88, Springer-Verlag, 1996.
Obr. 2. P°ehled schΘmatu DSA
Instance DSA je tvo°ena:
Ve°ejn²mi parametry (p, q, g), kde:
p, q jsou prvoΦφsla, q|(p-1), 21023 < p < 21024, 2159 < q < 2160,
g je generßtor cyklickΘ podgrupy grupy Zp* °ßdu q.
Privßtnφm klφΦem x, 0 < x < q.
Ve°ejn²m klφΦem y, y = gx mod p.
V²poΦet podpisu zprßvy m:
i) Zvolme nßhodn² klφΦ zprßvy k, 0 < k < q.
ii) VypoΦt∞me r = (gk mod p) mod q.
iii) VypoΦt∞me s = (h(m) + xr)*k-1 mod q, kde kk-1 ╛ 1 (mod q) a h je haÜovacφ funkce - ve standardu DSS h =def SHA-1.
iv) Podpisem budi₧ dvojice (r, s).
Ov∞°enφ podpisu (r, s) zprßvy m:
i) VypoΦt∞me w: ws ╛ 1 (mod q).
ii) VypoΦt∞me v = (gwh(m)ywr mod p) mod q.
iii) Podpis je platn² iff v = r.
Obr. 3. Postup v²poΦtu k-kolize pro DSA
Vstup: Podpis (r, s) zprßvy m, ve°ejn² klφΦ yA a parametry (pA, qA, gA), haÜovacφ funkce h pou₧itß p°i podpisu m.
Postup:
i) Polo₧me pB = pA = p, qB = qA = q.
ii) VypoΦt∞me a = gAwh(m)yAwr mod p, kde w*s ╛ 1 (mod q).
iii) Zvolme nßhodnΘ Φφslo kB, 0 < kB < q.
iv) VypoΦt∞me z: zkB ╛ 1 (mod q).
v) VypoΦt∞me gB = az mod q.
vi) VypoΦt∞me privßtnφ klφΦ xB = t(kBs - h(m)) mod q, kde rt ╛ 1 (mod q).
