Szerző: Pfeiffer Szilárd

2023. január 16. 09:35

Már ma is törhető az RSA titkosítás?

Kínai kutatók egy közelmúltban megjelent publikációban azt állítják, hogy létezik olyan algoritmus, ami a kvantumszámítógépek mai szintje mellett is lehetővé teszi az internetes titkosítás egyik sarokkövének számító RSA algoritmus törését. Vannak ugyanakkor kétségek a publikáció megbízhatósága kapcsán, amik, ha igazolódnak is, a kvantumszámítógépek okozta biztonsági fenyegetés akkor is velünk marad.

A 24 kínai kutató által tavaly karácsonykor megjelentetett publikáció alapvető állítása, hogy sikerült találniuk olyan algoritmust, amely lehetővé teszi a 2048 bites RSA kulcsok törését még a ma elérhető, relatíve kis teljesítményű kvantumszámítógépek számára is. Abban nincs igazán újdonság, hogy a kvantumszámítógépek úgy általában kockázatot jelentenek az olyan, a biztonságos internetes kommunikációt szavatoló, kriptográfiai eljárások megbízhatóságára nézvést, mint az RSA nyílt kulcsú titkosító, vagy a Diffie-Hellman kulcscsere algoritmus. Ezen eljárások ugyanis olyan matematikai problémán alapulnak, melyek a hagyományos számítógépekkel a gyakorlatban megoldhatatlanok, viszont kellően nagy kapacitású kvantumszámítógépek esetén akár néhány óra alatt is megoldhatóak. A kellően nagy ez esetben 20 millió kvantumbit, a kvantumszámítógépek esetén a bit megfelelője. Ezzel a 20 milliós értékkel csupán annyi a probléma, hogy az IBM tavaly novemberben bejelentett – egyszersmind a legnagyobb ma ismert – kvantumszámítógépe ebből a 20 millió kvantumbitből mindösszesen 433-at képes felmutatni. Nem túlzás tehát azt állítani, hogy a kínai kutatók egy Grand Canyon méretű szakadék áthidalására tettek kísérletet. De sikerült?

Nyakunkon a kriptográfiai armageddon?


Erre a kérdésre csak elméletben születhetett válasz a kínai kutatók részéről és nem is nagyon született más, mivel az általuk vázolt technikák eredményeként létrejött megoldás egy 372 kvantumbites számítógépet igényel, ami hiába létezik az IBM falai között, a kínai kutatóknak ez a gép nem állt rendelkezésükre. Rendelkezésükre állt viszont több kisebb kapacitású gép – 3, 5, illetve 10 kvantumbitesek – melyek mindegyikével sikerült egy 48 bites (15 számjegy) számot faktorizálniuk.

ibm_quantum

Ha a "dobozos" megoldás kevés: tesztinfrastruktúra házon belül (x)

A thyssenkrupp kormányrendszereinek tesztelését is saját fejlesztésű infrastruktúrán végzi.

Ha a "dobozos" megoldás kevés: tesztinfrastruktúra házon belül (x) A thyssenkrupp kormányrendszereinek tesztelését is saját fejlesztésű infrastruktúrán végzi.

Ez elsőre talán nem tűnik különösebb áttörésnek, ha azonban hozzátesszük, hogy ez az eddigi legnagyobb szám, amit sikerült általános algoritmussal faktorizálni, már más a helyzet. Arról nem is beszélve, hogy sikerült egy elméletet a gyakorlatba is átültetni, kérdés, hogy sikerülhetett az említett szakadékot áthidalni. Ahogy az Bruce Schneier – az IT-biztonság egyik ikonikus alakja – és Roger Grimes – számos kriptográfiai témájú könyv szerzője – levelezéséből kiderül, a kínai kutatók egy olyan publikációból indultak ki, ami szintén azt állította, hogy sikerülhet igen nagy számokat prím tényezőkre bontani, méghozzá hagyományos számítógépeken. Ezt a publikációt azonban a szerzője visszavonni kényszerült, mivel a publikáció ellenőrzése során, az algoritmusban egy hibát tártak fel. A kínai kutatók pont arra jöttek rá, hogy az a probléma, ami miatt a publikációt vissza kellett vonni, akár kis kapacitású kvantumszámítógépekkel is áthidalható. Azt gondolhatnánk, hogy  nyakunkon a kriptográfiai armageddon.

Nem eszik olyan forrón!


Ezen a ponton azonban bicsaklik egy kisebbet a történet, mivel a skálázás közel sem triviális. A kínai kutatók eljárásának alapját ugyanis Claus Schnorr faktorizálási algoritmusa képezi, ami kisebb értékkel – amivel maguk a kutatók tesztelték is – jól működik, nagyobb értékekkel azonban már nem. A kínai kutatók állítása épp az, hogy ezen a limitáción sikerült túllépniük, habár ennek részleteiről nem ejtenek szót, és kellő kapacitású kvantumszámítógép hiányában ezt a gyakorlatban bizonyítaniuk sem sikerült.

A legszélesebb körben használt kriptográfiai eljárások gyakorlati feltörhetetlenségét garantáló matematikai probléma a számok prím tényezőkre bontása. A feladat néhány számjegyből álló számoknál egészen triviális (15 = 3 *5), de több száz, esetleg néhány ezer számjegy esetén a szükséges számításigény olyan nagyra nő, hogy még a legnagyobb kapacitású gépek használata mellett is nagyságrendileg annyit időt igényelne, mint az univerzum teljes élettartama. Az Egysült Államok Nemzeti Szabványügyi és Technológiai Intézetének (NIST) ajánlása szerint a legkisebb biztonságosnak tekinthető RSA kulcs mérete 2048 bit. Ez ~600 számjegyet jelent, de számos helyen használnak ennél nagyobb, 3072 vagy 4096 bites kulcsokat is, ahol tízes számrendszerben kifejezve a számjegyek száma már jócskán meghaladja az ezret, vagyis ezek a kulcsok hagyományos módszerekkel a gyakorlatban törhetetlenek. Ugyanakkor Peter Shor már 1994-ben előállt egy algoritmussal, amely – egy akkor még csak elméletben létező kvantumszámítógépen – képes lenne a prím tényezőkre bontást a korábbiakhoz képest jóval nagyobb hatékonysággal elvégezni, ami azt jelentené, hogy megszűnik a titkosítási eljárásaink jelentékeny részének ellenálló képessége a törésekkel szemben, beleértve egyebek mellett a böngészés biztonságát adót HTTPS-t, vagy a távmunka egyik alapját képező VPN protokollokat.

Vagyis vagy arról van szó, hogy a kínai kutatók algoritmusa nem skálázódik, ahogy a Schnorr-féle algoritmus sem, vagy komoly bajban vagyunk, mivel Schneier véleménye szerint ez olyan algoritmusok feltörését is lehetővé teszi, amiket eddig ellenállónak gondoltunk a kvantumszámítógépekkel szemben. Akkor tehát marad a kétségek között vergődés mindaddig, amíg valaki ki nem próbálja az algoritmust egy elégségesen nagy kapacitású kvantumszámítógépen? Részben. Vannak olyan jelek ugyanis, amik kétkedésre adnak okot az egész történettel szemben. Az egyik ilyen, hogy a kínai kutatóknak sem sikerült bezsebelni a RSA Factoring Challenge által kínált 200.000 dolláros díjat, ami annak jár, aki sikeresen fel tud feltörni egy 2048 bites RSA kulcsot. Persze lehet mondani, hogy nincs meg a szükséges hardverük hozzá, de egy levelet azért bizonnyal megért volna az IBM felé, hogy – még ha megosztva is, de – megkaphassák az összeget. Egy másik, bár kissé alusisakos, érvelés, hogy a kínai állam miért nem tartotta meg magának a felfedezést és kezdte önteni a pénzt egy megfelelő kvantumszámítógép fejlesztésébe, ami nyilván igencsak súlyos összeg, de igen komoly haszonnal is kecsegtet. Ugyanakkor tudományos oldalról is erős a szkepszis. Scott Aaronson, aki korábban az MIT, jelenleg a Texasi Egyetem kutatójaként több, mint 15 éve, kifejezetten a kvantumszámítógépekkel, illetve komplexitáselmélettel, vagyis a téma szempontjából talán két legfontosabb tudományterülettel foglalkozik, meglehetősen lesújtóan nyilatkozott a blogján a kínai eredményekről.

Háromszavas összegzése a publikációban foglaltakról:

No. Just no.

Határozott hangvétel mellett kritizálja a publikációt, mondván, az pont a kritikus kérdésekről nem ejt szót. Meglátása szerint csodára lenne szükség ahhoz, hogy a kínaiak által vázolt megközelítés bármilyen előnyt jelentsen ahhoz képest, mint ha valaki a Schnorr algoritmus futtatásával a saját laptopján próbálkozna. Ezután a tanulmányt az általa az elmúlt 25 évben olvasott hasonló témájú publikációk közül a legfélrevezetőbbnek aposztrofálta, mely véleményével nincs is egyedül. Meg kell jegyezni, hogy a publikációs felület (arχiv), ahol a kínai tanulmány megjelent, nem végez szakmai bírálatot, vagyis a publikálás puszta ténye önmagában nem jelent túl sokat és egy olyan népszerű terület, mint a kvantumszámítógépek és a kriptográfia kitettetek a hatásvadászatnak. Ki gondolná, hogy a tudományos publikációk világa sem mentes a clickbaitnek.

Akkor most megúsztuk vagy sem?


A konkrét esetben talán igen, egyébként sajnos közel sem. Még hogy ha le is számítjuk azokat a vadhajtásokat, amik egy népszerű és komoly elismeréssel kecsegtető tudományterület esetén szükségképpen számolni kell, akkor is ott van a rideg valóság.

Minden ma rögzített titkosított adat, ami olyan kriptográfiai eljárást alkalmaz, ami nem áll ellen a kvantumszámítógépek okozta kihívásoknak, a nem túl távoli jövőben kompromittálhatóvá válhat.

Tehát már ma szükség lenne arra, hogy olyan eljárásokat alkalmazzunk (post-quantum kriptográfiai), melyek ellenállnak a kvantumszámítógépek okozta kihívásoknak, ahhoz, hogy az említett “harvest now decrypt later” technika okozta károkat – ha eliminálni nem is –, de legalább enyhíteni lehessen. Az informatikai iparág biztonsághoz való jelenlegi viszonya mellett – mely témáról a Balasys egy kerekasztal-beszélgetés keretében is foglalkozott – nem mindig könnyű optimistának lenni. Egy-egy nagyobb publicitást kapott kriptográfiai probléma kapcsán, mint amilyen a Heartbleed volt 2014-ben, viszonylag gyorsan reagált a piac, bár itt is hetekben lehetett mérni, mire akárcsak a leglátogatottabb százezer oldalról kikopott a hiba. Más esetekben, melyek nem kaptak akkora nyilvánosságot, ez évekbe is telhet a Qualys statisztikái alapján. Nem számíthatunk tehát arra, hogy a post-quantum eljárások bevezetése ennél sokkal gyorsabban tudna megtörténni.

pichai_quantum
sundar pichai, az alphabet elnök-vezérigazgatója egy kísérleti kvantumszámítógéppel

Hasonlóan a globális felmelegedéshez, a jelenben kellene kezelni egy olyan problémát, ami a kritikussá válás jövőbeni pillanatában már nem kezelhető. A hasonlóság már csak azért is szembeszökő, mert a tudomány emberei már évtizedek óta ijesztegetnek a kvantumszámítógépek rémével, de ez egy ideig csupán teóriának tűnt, mostanra azonban valósággá vált. Az IBM az év végére ezer, a Google az évtized végére egymillió kvantumbites számítógépet ígér, ahol az utóbbi semmi jóval nem kecsegtet, hiszen az már csak adattárolási kapacitás kérdése, hogy mennyi adathoz lehet hozzáférni miután például az RSA törése ez által realitássá válik.

Kellően nagy kapacitású gépei elsőként vélhetőleg a ma is sokat kárhoztatott technológia óriásoknak, illetve a nagyobb államoknak lesznek. Utóbbiak már jelen állás szerint is próbálnak jogi úton kiskapukat építtetni a kriptográfiai rendszerekbe, annak súlyos kockázatai mellett is, de egy ilyen technikai áttörés mellett erre nem is feltétlenül lesz szükségük. Ez azonban nehezen belátható következményekkel járhat mind a privát szférára, mind pedig az egyre inkább a kibertérbe áthelyeződő konfliktusok kimeneteleire.

A szerző, Pfeiffer Szilárd a Balasysnál dolgozik, mint Security Engineer. Hálózatbiztonsági termékek fejlesztése során szerezett 15+ év tapasztalatot C/C++, Python nyelveken. A szabad szoftverek, a hálózati- és adatbiztonság elkötelezettjeként konferenciák, tréningek állandó előadója.

a címlapról