AI-agenten die onder menselijk toezicht werken, hebben Google DeepMind in staat gesteld twee manieren te identificeren om de aanvalskosten van RSA 1024-bits cryptosystemen te verlagen. Dit werk, uitgevoerd met cryptografen van UC San Diego en Inria, geeft aan dat aanvallen op het verouderde RSA-1024 minder rekenkracht vereisen dan tot nu toe werd aangenomen.
RSA is een systeem voor asymmetrische encryptie, waarvan de sterkte berust op de moeilijkheid om een groot getal in priemfactoren te ontbinden. Pushmeet Kohli, vice-president van Google DeepMind en chief scientist van Google Cloud, wil de reikwijdte van deze resultaten echter relativeren: « In de praktijk hebben deze resultaten alleen betrekking op verouderde RSA 1024-bits systemen, en moderne encryptieprotocollen, die bijna universeel sleutels van 2048 bits of meer gebruiken, blijven veilig. »
Digitale handtekeningen en padding
De eerste ontdekking gaat over digitale handtekeningen en over padding, de vooraf vastgestelde gegevens die veel handtekeningsstandaarden aan een bericht toevoegen om het op een vaste blokgrootte te brengen. Dit mechanisme stond bekend als een complicerende factor voor vervalsing, maar de effectiviteit ervan tegen een aanvaller die kan kiezen wat er wordt ondertekend, was onduidelijk. DeepMind heeft vastgesteld dat alles afhangt van het deel van het ondertekende blok dat de aanvaller controleert. Zoals Pushmeet Kohli uitlegt: « Zodra ze ongeveer de helft van het blok of meer controleren, biedt de padding geen enkele bescherming meer. »
Volgens het wetenschappelijke artikel dat dit werk begeleidt, betreft dit het PKCS#1 v1.5-formaat, dat wordt gebruikt door de PKCS#11-handtekeninginterface van cryptografische apparaten zoals hardware security modules (HSM’s).
In een test uitgevoerd in een geïsoleerde omgeving, lieten de agenten een reeds gepubliceerde vervalsingsaanval uit een academische studie opnieuw lopen, op dezelfde 1024-bits sleutel. De benodigde processortijd werd met een factor 3,5 gereduceerd. De eerste vervalsing vereiste 391 processorjaren, tegenover 1.380 in de oorspronkelijke studie.
Twee AI-agenten ontwierpen, voerden uit en corrigeerden de vervalsingsberekening in minder dan vier dagen, met ongeveer 20 berichten van de menselijke onderzoeker, voornamelijk goedkeuringen. De sleutel werd niet gefactoriseerd, een operatie die de bron schat op 500.000 tot 1 miljoen processorjaren. Wanneer de aanvaller een kleiner deel van het blok controleert, bijvoorbeeld een hash van 32 bytes, is vervalsing moeilijker. DeepMind zegt desalniettemin een algoritme te hebben gevonden dat, volgens hun theoretische schattingen, ongeveer 1.600 keer beter is dan de vorige meest effectieve methode tegen 1024-bits sleutels.
Factorisatie van meerdere sleutels
De tweede ontdekking betreft de factorisatie van vele RSA-sleutels van dezelfde grootte. Een aanvaller kan dan de kosten van een enkele, grote initiële berekening spreiden over al deze sleutels. De agenten van DeepMind hebben een algoritme ontwikkeld dat, gemiddeld, de factorisatie van elke extra 1024-bits sleutel ongeveer 30 keer goedkoper maakt dan de beste vorige benadering. Deze theoretische schatting veronderstelt echter een initiële berekening die even kostbaar is als het factoriseren van één enkele sleutel, en de methode is niet geïmplementeerd.
De onderzoekers benadrukken dat de aanval op handtekeningen niet toestaat de privésleutel te achterhalen. Het vereist vooraf ongeveer 4 miljard handtekeningverzoeken en werkt niet tegen apparaten die berichten intern hashen. « Samen tonen deze resultaten aan dat we, in een nieuw tijdperk van door AI ondersteunde wiskunde en berekening, cryptografische moeilijkheid niet als een vaststaande aanname kunnen beschouwen », concludeert Pushmeet Kohli. Hij voegt toe: « Het gebruik van AI om onze eerdere aannames rigoureus te testen, zal ervoor zorgen dat moderne encryptie veilig blijft. »
