Bajecny svet elektronickeho podpisu | online podpora stejnojmenne knihy z Edice CZ.NIC

2.5.1         Máme se bát kolizí?

Používání hašování a hašovacích funkcí na jedné straně řeší problém s podepisováním libovolně velkých dokumentů, na druhé straně ale vytváří jiný nepříjemný problém. Jeho podstata vyplývá již ze samotného principu hašování, kdy se „z něčeho většího“ stává „něco menšího“: budou existovat takové dokumenty, které sice budou navzájem odlišné, ale jejich „zmenšeniny“ (otisky, hash-e) budou stejné.

Jenže: když se při podpisu z takto různých dokumentů nejprve udělají jejich otisky (které vyjdou stejné), a tyto otisky se následně podepíší, vznikne z toho stejný elektronický podpis (ve smyslu: se stejnou hodnotou, chápeme-li jej jako číslo).

Jinými slovy: budeme mít dva různé dokumenty, ale jeden elektronický podpis.  A už nebudeme schopni rozlišit, zda tento podpis „patří“ jednomu či druhému dokumentu. Správně totiž „patří“ oběma.

Došlo by tedy k něčemu, co bychom mohli označit jako kolizi (dvou dokumentů s jediným otiskem) – a podle toho se také takovéto dokumenty označují jako kolizní dokumenty[21].

Pro obrázek ve větší kvalitě klikněte na odkaz pod číslem obrázku v legendě

Představa kolizních dokumentů

Obrázek 2 - 10: Představa kolizních dokumentů

Samozřejmě je to nežádoucí situace, které bychom se měli vyhnout. Protože když by nám někdo předložil nějaký elektronicky podepsaný dokument, jak bychom se ujistili, že je to skutečně ten původně podepsaný a nikoli nějaký jiný (a to kolizní) dokument? Ze samotného ověření elektronického podpisu bychom to nepoznali, protože to by změnu dokumentu (skrze porušení jeho integrity) neodhalilo.

Existenci kolizních dokumentů ale nemůžeme v principu zabránit. Jak jsme si již uvedli, vyplývá už ze samotné podstaty hašování, kdy „něco většího“ zmenšujeme na „něco menšího“[22].

Musíme se tedy smířit s tím, že kolizní dokumenty existují[23]. Jak ale potom může vůbec fungovat elektronický podpis a jak mu můžeme důvěřovat, když z principu nelze vyloučit existenci kolizních dokumentů?

Odpověď na tuto velmi zajímavou otázku je sama o sobě nesmírně důležitá a má velmi závažné důsledky, zejména pokud jde o dlouhodobou platnost elektronických podpisů. Jak ale tato odpověď zní?

Zní tak, že samotná existence kolizních dokumentů nám ještě vadit nemusí – pokud je zajištěno, že nikdo nebude reálně schopen nalézt (vypočítat) jakýkoli kolizní dokument v takovém čase, který by mu umožňoval nějaké reálné zneužití.

Pro obrázek ve větší kvalitě klikněte na odkaz pod číslem obrázku v legendě

Představa nemožnosti výpočtu kolizního dokumentu

Obrázek 2 - 11: Představa nemožnosti výpočtu kolizního dokumentu

Jinými slovy: jde o to, aby hledání kolizních dokumentů (tj. jejich výpočet) bylo tak ztíženo, aby nešlo dělat příliš rychle. Aby příslušný výpočet byl tak složitý (výpočetně náročný), že zabere neúnosně dlouhou dobu a nejde ho zkrátit ani jakkoli „obejít“. A ona „dlouhá doba“ by neměla být kratší, než jsou nějaké stovky či lépe miliony let – aby se skutečně nikomu nevyplatilo čekat na výsledek.

K nemožnosti hledat kolizní dokumenty „nějak rychleji“ patří i správná konstrukce hašovacích funkcí. Ty samozřejmě nemohou fungovat na nějakém „naivním“ principu, tak aby je šlo obelstít a tím zrychlit hledání kolizí. Nebo dokonce nějak „obrátit“, tak aby se z otisku dal odvodit původní dokument.

Správně navržená hašovací funkce musí například „reagovat“ na jakoukoli změnu výchozího dokumentu: i kdyby se na něm změnil jen jeden jediný bit, musí být nový otisk odlišný od původního otisku. Ostatně, jinak by se nedala zajistit integrita dokumentu, kterou požadujeme od elektronického podpisu: pokud by při změně dokumentu zůstával jeho otisk beze změny, porušení integrity by se nedalo zjistit.


[21] V praxi bychom ještě měli rozlišovat mezi kolizemi prvního a druhého řádu. Kolizí prvního řádu se rozumí nalezení (jakýchkoli) dvou dokumentů, které mají stejný otisk (hash). To by mělo být jednodušší než kolize druhého řádu, při které ke známému dokumentu hledáme druhý (odlišný) dokument se stejným otiskem.

[22] Přesnější zdůvodnění je takové, že neexistuje prosté (injektivní) zobrazení z větší do menší množiny

[23] Ba co více: ke každému konkrétnímu dokumentu již z principu existuje nekonečně mnoho kolizních dokumentů



© Jiří Peterka, 2011, profil na Google+
Valid HTML 4.01 Transitional Ověřit CSS!
3A2E
5665
6E6F
7661
6E69
2E3A
0D0A
5475
746F
206B
6E69
6875
2076
656E
756A
6920
7376
6520
7A65
6E65
2049
7265
6E65
2C20
7379
6E6F
7669
204A
6972
696D
7520
6120
6463
6572
6920
4576
652E
0D0A
5620
5072
617A
652C
204C
5032
3031
3020
4A69
7269
2050
6574
6572
6B61