Prulom v kryptografii

[Vlada Macek]

Projekt md5crk skoncil. Pred nekolika dny byla ctyrmi Cinany nalezena
kolize hashovaciho algoritmu MD5 ve dvou proudech o velikosti 1024 bitu.
Bez prispeni projektu md5crk svoji zatim nezverejnenou metodou tuto
kolizi zjistili vypoctem v radu hodin!!! V intervalech jeste kratsich
nasledovaly dalsi kolize z teto "rodinky".

Cinani prolomili zaroven algoritmy MD4, HAVAL-128 a RIPEMD, viz
http://eprint.iacr.org/2004/199.pdf.

Jak vidite, soubory si jsou velice podobne:

$ od -tx1z -w16 -Ax file0
000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c  >.1......i=.....\<
000010 2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89  >/....F~. na .X>....<
000020 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a  >U.4.........%qAZ<
000030 08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b  >.Q%..........7<[<
000040 96 0b 1d d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d5  >.....A{.....ZeU.<
000050 35 73 9a c7 f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f  >5s......0).f....<
000060 75 27 7f 79 30 d5 5c eb 22 e8 ad ba 79 cc 15 5c  >u'.y0.\."...y..\<
000070 ed 74 cb dd 5f c5 d3 6d b1 9b 0a d8 35 cc a7 e3  >.t.._..m....5...<

$ od -tx1z -w16 -Ax file1
000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c  >.1......i=.....\<
000010 2f ca b5 07 12 46 7e ab 40 04 58 3e b8 fb 7f 89  >/....F~. na .X>....<
000020 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a  >U.4.........%.AZ<
000030 08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b  >.Q%........r.7<[<
000040 96 0b 1d d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d5  >.....A{.....ZeU.<
000050 35 73 9a 47 f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f  >5s.G....0).f....<
000060 75 27 7f 79 30 d5 5c eb 22 e8 ad ba 79 4c 15 5c  >u'.y0.\."...yL.\<
000070 ed 74 cb dd 5f c5 d3 6d b1 9b 0a 58 35 cc a7 e3  >.t.._..m...X5...<

MD5: a4c0d35c95a63a805915367dcfe6b751

Vice viz zprava na http://www.md5crk.com (asi casem zmizi) a clanky a
diskuze k tematu na http://www.freedom-to-tinker.com. Velice zajimave,
nezdrzi vas to dlouho!

Nedavno byly nalezeny kolize v plnem algoritmu SHA-0, coz je o neco
starsi bratricek dnes siroce pouzivaneho SHA-1. Oba byly navrzene asi
pred deseti lety jistou agenturou NSA (zkratka od No Such Agency).

Zaroven byla nalezena kolize v redukovane verzi algoritmu SHA-1. Muzeme
se tedy za nejaky cas nadit i kolizi plnych. Ve zminenych diskuzich jsou
odpovedi na otazky, proc nekonci svet, ale zaroven kde je hrozba.
Vysledkem bude, ze rozumni navrhari zacnou rychle opoustet MD5 (pokud to
jeste neudelali!) a
pomalu SHA-1. Budou hledany dalsi alternativy pro siroke nasazeni, ktere
po SHA-1 prevezmou statut Secure Hash Algorithm. To, ze MD5 neni
"bezpecny", se vi uz dlouho.

Vysledkem je to, ze na kryptografii jakozto na jediny zpusob ochrany se
neda nikdy spolehat. Je treba venovat velkou pozornost i konvencnim
zpusobum ochrany dat (edukace uzivatelu, prava k shadow souborum, atd.).
Pilire individualni bezpecnostni politiky musi byt ruznorode.

Jiz byla aktualizovana hesla SHA-1 a MD5 na Wikipedia.org... taky
doporucuju.

Vlada Macek

------------- další část ---------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 252 bytes
Desc: OpenPGP digital signature
URL: <http://www.linux.cz/pipermail/linux/attachments/20040823/adc5e2aa/attachment.sig>