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

Příklady kolizních dokumentů

Elektronický podpis zakládá své fungování na tom, že není možné (v únosně krátkém čase) najít vzájemně kolizní dokumenty. Tedy takové dokumenty, které jsou sice jiné, ale mají stejný otisk (tzv. hash). Tím pádem budou mít i stejný elektronický podpis a nebude možné poznat, který z nich je "ten pravý".

Náročnost hledání kolizních dokumentů záleží ještě na tom, zda jde o kolizi prvního řádu (kdy hledáme dva dokumenty, které mají stejný otisk), nebo druhého řádu (kdy k zadanému dokumentu hledáme jiný dokument, se stejným otiskem). V prvním případě je totiž situace jednodušší a hledání kolizních dokumentů přeci jen snazší.

Obecně pak náročnost (složitost) hledání kolizních dokumentů závisí hlavně na "síle" hašovací funkce, která je použita. Dříve používaná funkce MD5 je dnes již zcela nepoužitelná, protože nalezení kolizních dokumentů (1 řádu) je pro tuto hašovací funkci záležitostí několika vteřin. Novější SHA-1 je na tom podstatně lépe, ale od roku 2010 se také již nedoporučuje používat. Místo ní se dnes běžně používá hašovací ffunkce SHA-2, v některé ze svých variant.

Jako příklad toho, že kolizní dokumenty reálně existují, zde najdete dva soubory. Obsahují PDF-ka, záměrně stylizovaná do formy dlužního úpisu: jeden z nich říká, že "starší" dluží "mladšímu", zatímco druhý dokument říká přesný opak (že "mladší" dluží "staršímu").


dlužní úpis 1 | dlužní úpis 2

Obě tato PDF-ka jsou vložena do obálky (v podobě samorozbalovacího archivu s příponou .exe, konkrétně package1.exe a package2.exe) - a tyto dvě obálky mají stejný otisk (hash), vytvořený pomocí hašovací funkce MD5 (tj. v rozsahu 128 bitů). Jeho hodnota je:

MD5:
16C87FCCEEC61DB8A5D852A8624B8F75

Z pohledu hašovací funkce MD5 jsou tedy tyto obálky (obsahující protichůdné dlužní úpisy) vzájemně kolizními dokumenty (nalezenými jako klize 1. řádu). To znamená, že pokud je jeden z nich podepsán - a to takovým elektronickým podpisem, který pro otisk podepisovaného dokumentu používá právě funkci MD5 - pak tento podpis bude "sedět" i na druhý dokument a nebude již možné rozlišit, který dokument byl původně podepsán.

Při použití "vyšších" hašovacích funkcí už ale oba dokumenty (obálky) nebudou vzájemně kolizní. Jejich otisky již budou odlišné:

SHA1:
92C9D76D293197BC577D0C78EA0D27000A5B1D58
B92DBDB10A04E2B237E81A7702FC129B92263498

SHA256:
8DAEBD87933562EE9717A9C5AE59A3B4AB6C8A5E1FB1D4D5CFAD5BCA62098950
ED58627AE5B1667F39A94D03121C944DCE34C7D8AFF63A70B9AEEF55ED059ECF

Elektronické podpisy, které by vyžívaly otisky na bázi MD5, se dnes již prakticky nepoužívají. Dokonce by se neměly používat ani podpisy s otisky na bázi SHA-1 (ale již jen s SHA2). Nicméně je pouze otázkou času, kdy výpočetní schopnosti našich počítačů vzrostou natolik, aby se v dostatečně krátkém čase stihly najít vzájemně kolizní dokumenty i podle SHA1, či dokonce SHA2. Mezitím, a to s dostatečným předstihem, ale budou muset přejít elektronické podpisy (i vydávané certifikáty atd.) na ještě "vyšší" hašovací funkce, pro které bude hledání kolizních dokumentů opět podstatně náročnější (a nad možnosti aktuálně dostupných počítačů).
Pro zjišťování hodnot otisků (hashů) lze použít například freewarové programy LockIT/ELPI 2, HashTab, MD Pack apod.


© 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
3120
4A69
7269
2050
6574
6572
6B61