5 év alatt feltörték a 64 bites titkosítást

˝Some things are better left unread˝, azaz ˝Egyes dolgokat jobb ismeretlenül hagyni˝ – ez volt az a kódolt üzenet, amelyet 5 éve keresett a Distributed.net, elosztott számítási rendszert (distributed computing) üzemeltető szervezet.

Az üzenetet az RC5-64 titkosítási algoritmussal kódolta az algoritmust kifejlesztő RSA Labs Security biztonságtechnikai vállalat, és 10.000 dollárt ajánlott fel a visszafejtésért.

Az RC5 titkosítás fajtájából adódóan a szervezet a nyers erő (brute force) módszerét alkalmazta, ami nem kevesebb, mint 18.446.744.073.709.551.615 lehetséges kulcs – a 64 biten binárisan ábrázolható számtartomány egyesével való – végigpróbálgatását jelenti.

Az erőfeszítés végülis a munka ötödik évében, 2002-ben jutott a siker küszöbére: az újonnan csatlakozott számítógépek, illetve a technikai fejlődés által folyamatosan növekvő összesített számítási teljesítmény alapján január 11-én az addig 67%-ot felgöngyölítő 1541 nappal szemben a maradék 33%-hoz már csak 339 napot előrejelezve a megfejtés még ebben az évben várható lett.

Aztán szeptember 25-én robbant a bomba: ˝We´re done!˝, ˝RC5-64 has been solved!˝ – vagyis ˝Megcsináltuk!˝, ˝Az RC5-64 fel lett törve!˝. A titkosítást feloldó 0x63DE7DC154F4D039 kulcsot egy Windows 2000-et futtató tokiói (Japán) Pentium 3 450-es gép (amely gazdájának a neve titok marad) találta meg.

˝Egy késő üzenet, egy megkésett levél˝

Üröm az örömben, hogy a kérdéses kulcsot tartalmazó csomagot a japán gép már július 14-én visszaküldte valamelyik kulcsszervernek – a fő kulcsszerver hibája miatt azonban erről egészen augusztus 12-ig (amikor az RSA Labs megerősítette a megoldás megtalálását) senki sem tudott, miközben a bejelentést tovább késleltette a helyes kulcsot megtaláló gép gazdájának nehéz elérhetősége.

A világ számára így csak szeptember 26-án vált nyilvánvalóvá, hogy öt év kemény munkájával feltörték a 64 bites – az óceán túloldalán törvényben meghatározott maximális bithosszúságú, vagyis az ott engedélyezett ˝legbiztonságosabb˝ – titkosítást.

Hajrá magyarok!

A legnagyobb magyar csapatként a Team Hungary STB+ 413 regisztrált és 822 valaha aktív tagjával mind a korábbi 56 bites, mind a jelenlegi 64 bites RC5 titkosítás feltörése során végig aktívan az utóbb 12.565 csapatból álló rangsor 18. helyén végzett.

A csapat egyébként augusztus végén lett 5 éves, és összetartására jellemző, hogy még egységes csapatpóló is készült.

5 év számokban

A feladat teljesítése összesen 12.565 csapatba szerveződött 331.252 önkéntes internetes felhasználó 1757 napos közreműködésével volt lehetséges, amelynek során összesen 15.268.315.356.922.380.288 kulcsot – a lehetséges 18.446.744.073.709.551.615 kulcsból álló tartomány (keyspace) 82,77%-át – kellett átvizsgálni a megfejtést jelentő kulcs megtalálásáig.

A munka 5 éve során a Distributed.net összesített sávszélessége 270.147.024.000 kulcs/s-mal érte el csúcspontját, amikor is egyetlen nap alatt a keyspace 0,12%-át sikerült felgöngyölíteni – ez mintegy 46 ezer különálló 2 GHz-es AMD Athlon XP-t tartalmazó számítógép összesített teljesítményével mérhető össze. Állandó ilyen sebességgel az 1757 nap helyett legkésőbb mintegy 790 nap alatt sikerült volna feltörni az RC5-64 titkosítást.

Megyünk tovább – irány a 72 bit?

A Distributed.net már tett célzást arra, hogy a jövőben némi hálózat- és kliensprogram-fejlesztést követően hozzáfog a 72 bites titkosítás feltöréséhez is.

A 64-nél ˝mindössze˝ 8 bittel hosszabb kulcsú 72 bites kódnak a megfejtése a mai számítási csúcsteljesítménnyel mintegy 554 évbe telik, azonban ha a résztvevő önkéntes internetes felhasználók által csatlakoztatott számítógépek száma nem is nő jelentős mértékben tovább, viszont Moore törvénye hosszú távon érvényes marad (továbbá ilyen késő éjjel én sem rontottam el a számítást), akkor az RC5-72 megfejtésére akár már 10-12 év múlva sor kerülhet.

Megjegyzés:

Természetesen az RSA RC5-64 titkosítási kód: 4 éve zajló törés – soha nem lesz megfejtés… című, április 1-ei hírünk valamennyi mondata hazugság volt – áprilisi tréfa, teljes mértékben a szerző fantáziájának szülötte. Így ezúton kérünk elnézést (!) azoktól, akiket a hír megtévesztett, illetve külön azoktól is, akik különböző fórumokon igyekeztek beszélgetőpartnereiknek elmagyarázni és bebizonyítani a hír mondanivalóját…