Egy makacs tévhit akadályozza a kvantumfelkészültség már így is kemény munkáját.
Miközben egyre nagyobb figyelem irányul arra az egzisztenciális fenyegetésre, amelyet a kvantum-számítástechnika jelent a titkosítás néhány legfontosabb és legszélesebb körben használt formájára, Filippo Valsorda kriptográfiai mérnök egy dolgot teljesen világossá akar tenni: a közhiedelemmel ellentétben, amely nem hajlandó meghalni, az AES 128 tökéletesen megfelel a posztkvantum világnak.
Az AES 128 az Advanced Encryption Standard, egy 2001-ben a NIST által hivatalosan elfogadott blokkrejtjelcsomag legszélesebb körben használt változata. Bár a specifikáció 192 és 256 bites kulcsméreteket tesz lehetővé, az AES 128-at széles körben az előnyben részesítettnek tartották, mivel ideális egyensúlyt teremt a használatához szükséges számítási erőforrások és az általa kínált biztonság között. Mivel 30 éves története során nem ismert sebezhetőségekről, a feltörésére csak a nyers erő támadás ismert. 2128 vagy 3,4 x 1038 lehetséges kulcskombinációval egy ilyen támadás körülbelül 9 milliárd évig tartana, 2026-ig a teljes bitcoin bányászati erőforrásokat felhasználva.
A lényeg a párhuzamosítás
Az elmúlt évtizedben valami érdekes történt ezzel a közbizalommal. Amatőr kriptográfusok és matematikusok elferdítették a Grover-algoritmusként ismert egyenletsorozatot, hogy kihirdessék az AES 128 halálát, miután létrejött egy kriptográfiailag releváns kvantumszámítógép (CRQC). Azt mondták, hogy egy CRQC a tényleges erősséget a felére csökkentené, mindössze 264-re , ami elég kicsi készlet ahhoz, hogy – ha igaz – ugyanazok a bitcoin-bányászati erőforrások kevesebb mint egy másodperc alatt nyers erővel végrehajtsák azt (az összehasonlítás pusztán illusztrációs célokat szolgál; egy CRQC szinte biztosan nem tudna úgy futni, mint a bitcoin ASIC-ek klaszterei, és ami még fontosabb, nem tudná párhuzamosítani a munkaterhelést, ahogy az amatőrök feltételezik).
Hétfőn Valsorda végre beleöntötte évek óta tartó, a széles körben elterjedt félreértés által táplált frusztrációját egy „A kvantumszámítógépek nem jelentenek veszélyt a 128 bites szimmetrikus kulcsokra” című blogbejegyzésbe.
„Általános tévhit, hogy a kvantumszámítógépek „felezik” a szimmetrikus kulcsok biztonságát, és 256 bites kulcsokra van szükségük a 128 bites biztonsághoz” – írta. „Ez nem pontos értelmezése a kvantumalgoritmusok által kínált gyorsulásnak, nem tükröződik semmilyen megfelelőségi előírásban, és azzal a kockázattal jár, hogy elterelődik az energia és a figyelem a ténylegesen szükséges posztkvantumális átmenetről.”
Ez az érvelés könnyebb része. A sokkal nehezebb része a matematika és a fizika, ami megmagyarázza. Legmagasabb szinten a lényeg az, hogy alapvető különbség van a nyers erővel történő keresés és a Grover algoritmusa közötti működés között. A klasszikus számítógépek több keresést is képesek egyszerre végrehajtani, ami lehetővé teszi a nagy feladatok kisebb darabokra bontását, hogy a teljes munka gyorsabban elvégezhető legyen. Grover algoritmusa ezzel szemben hosszú ideig tartó soros számítást igényel, ahol minden keresést egyesével kell elvégezni.
„A Grovert az teszi különlegessé, hogy párhuzamosításával egyre kisebb az előnye a nem kvantumos algoritmusokkal szemben” – mondta Valsorda egy interjúban. Majd így folytatta:
Képzeljük el kis számokkal, tegyük fel, hogy 256 lehetséges kombináció van egy zárhoz. Egy normál támadás 256 próbálkozást igényelne. Úgy döntesz, hogy ez túl hosszú, ezért három barátot választasz, és mindegyikük 64 próbálkozást végez. „Ez a klasszikus párhuzamosítás. Groverrel elméletileg √256)=16 próbálkozást tehetnél egymás után, de ha ez még mindig túl hosszú, és ismét három baráttól kérsz segítséget, mindegyiküknek √256/4)=8 próbálkozást kell tennie.”
Tehát összesen 8*4=32 próbálkozást végzel, ami több, mint a 16, amit egyedül csináltál volna! A segítségkérés a támadás párhuzamosításához összességében lelassította a támadást. Ami a klasszikus támadások esetében nem így van.
Természetesen a számok sokkal nagyobbak, de ha bármilyen ésszerű korlátozást alkalmazunk a támadóra vonatkozóan (például, hogy 10 év alatt be kell fejeznie egy menetet), a teljes munka sokkal több lesz, mint 264 .
A 2 64 sosem volt a helyes szám, mert az azt állítja, hogy az AES-t egyetlen műveletként lehet elvégezni egyetlen qubiten. Ez némileg ortogonális. E két megfigyelés kombinációja a tényleges költséget 2 104 -re konvertálja , ami jóval meghaladja a biztonsági küszöböt.
Sophie Schmieg, a Google vezető kriptográfiai mérnöke ezt így magyarázta:
Egy normál nyers erővel történő keresésnél, ha félúton megszakítom, nagyjából 50% az esélye, hogy már sikeres lesz. Tehát két számítógéppel is elvégezhetem a keresést, mindegyik a kulcsok több mint 50%-án, és fele annyi idő alatt végezhetek vele. De a Grover keresésénél, ha félúton megszakítom, a helyes válasz valószínűsége csak 25%. Tehát a keresési terület felén két számítógép helyett most négyre van szükségem.
Tehát ha megnézzük a magmásodperceket, a klasszikus algoritmusok annyiba kerülnek, amennyibe kerülnek, függetlenül attól, hogy hány számítógépet használunk párhuzamosan. Növelhetjük a magok számát, és az idő ennek megfelelő mértékben csökken. De a kvantumalgoritmusnál a magmásodpercek nem függetlenek a párhuzamosítási stratégiától. Több mag nem csökkenti az időt ugyanannyival, odáig, hogy ha a maximálisan párhuzamos példányra mennénk, ahol minden QC-nek csak egyetlen kulcsot kell ellenőriznie, akkor 2128 QC -re lenne szükségünk , és nem 264 -re , azaz nem vagyunk jobbak a klasszikusnál.
Valsorda bejegyzése matematikailag részletesebb magyarázatot nyújt, akárcsak ez a videó.
Valsorda számos forrást sorolt fel, amelyek alátámasztják azt az állítást, hogy az AES tökéletesen elfogadható a posztkvantum világban, beleértve a Nemzeti Szabványügyi és Technológiai Intézetet ( itt , itt és itt ), a Német Szövetségi Információbiztonsági Hivatalt ( itt ), valamint Samuel Jaques-t, a Waterlooi Egyetem Kombinatorikai és Optimalizálási Tanszékének adjunktusát ( itt ).
Az ajánlások alóli kivételt az NSA Kereskedelmi Nemzetbiztonsági Algoritmuscsomagjának 2. verziója részletezi, amely az AES 256 használatát írja elő. Valsorda elmondta, hogy a 256-os szintű biztonság követelményei már az előző algoritmuscsomagban is érvényben voltak, és nem kifejezetten a kvantumkészültségre vonatkoztak. „Amennyire meg tudom állapítani, a cél az, hogy elkerüljék a biztonsági szintek által bevezetett ugyanazt a fragmentációt, ha egyetlen túlméretezett primitívet választanak ki az összes beállításhoz.”
Továbbá elmondta, hogy a 256 bites AES bizonyos esetekben is indokolt, például az ütközések lehetőségének elkerülése érdekében, amikor két kulcs véletlenszerűen egyenlővé válik a születésnapi paradoxon miatt.
Tehát legközelebb, amikor azt hallja valakitől, hogy a kvantum-számítástechnika a felére csökkenti az AES biztonságát, kérjük, emlékeztesse rá, hogy ez egy babona, amely elvonja a mérnökök figyelmét a CRQC megjelenésére való világfelkészítés valódi és jelentős munkájáról. Ez egy elég magas rendű frissítés az aszimmetrikus algoritmusoknál, amelyekről ismert, hogy sebezhetőek a Shor algoritmusával szemben, amely polinomiális idő alatt, konkrétan köbös idő alatt feltöri őket , ami hatalmas előnyt jelent a mai klasszikus számítógépek által biztosított exponenciális időhöz képest.
„A szükséges és a szükségtelen változtatások összekeverése szükségtelen lemorzsolódást okoz, és elvonja az erőforrásokat a sürgős frissítésektől” – érvelt Valsorda. „Szerencsések vagyunk, hogy a szimmetrikus kriptográfiai (al)rendszereket érintetlenül hagyhatjuk; ezt az áldást kellene elfogadnunk, és a ténylegesen elvégzendő munkára kellene összpontosítanunk, amiből pedig bőven van.”
Tovább a cikkre: arstechnica.com (Dan Goodin)
