RSA kraken: vijf fouten in plaats van vijfhonderd jaar rekenen

SEO-titel: RSA kraken: vijf fouten in de sleutel | Hackerscollectief.nl Meta-description: RSA kraken gaat bijna nooit over rekenkracht. Vijf aannames waar het misgaat, met de aanvallen, de wiskunde en de incidenten erbij. Slug: rsa-kraken-vijf-fouten

# RSA kraken: vijf fouten in plaats van vijfhonderd jaar rekenen

In het kort

RSA met 2048 bits kraak je niet met een snellere computer. De grootste modulus die ooit publiek is ontbonden had 829 bits, en dat kostte in 2020 een cluster en maanden rekenwerk. Rekenkracht is dus geen plan.

Toch gaat het in de praktijk steeds mis, en altijd om dezelfde reden: er zit een fout in de manier waarop de sleutel is gemaakt of gebruikt. RSA is een algoritme met vijf aannames, en elke aanname heeft zijn eigen aanval. Wie één aanname kan breken, heeft geen rekenkracht nodig. In dit artikel staan ze alle vijf, met de wiskunde erbij, de echte incidenten, en wat je er als bouwer of als tester mee doet.

Hoe RSA werkt, in vijf regels

Twee priemgetallen p en q, hun product n = p·q, een exponent e die meestal 65537 is, en een geheime d met e·d ≡ 1 (mod φ(n)). Versleutelen is c = m^e mod n, ontsleutelen is m = c^d mod n. De veiligheid hangt aan één paal: wie n kan ontbinden, kan d uitrekenen en dus alles lezen.

Alles wat hierna komt is een variatie op die ene zin. De aanval ontbindt n niet door te zoeken, maar door iets te misbruiken wat de maker van de sleutel of de implementatie heeft weggegeven. Soms is dat een fout in de sleutel, soms een fout in de communicatie.

Waarom brute force geen plan is

Het ontbinden van n is niet onmogelijk, het is alleen te duur. De beste bekende methode, de general number field sieve, is subexponentieel: hij groeit sneller dan polynomiaal en veel langzamer dan volledig zoeken, maar bij 2048 bits kom je uit op een hoeveelheid rekenwerk die geen enkele organisatie kan betalen. Daarom is de vuistregel dat 2048 bits vandaag voldoende is, en dat de klok pas echt gaat tikken als er een grootschalige quantumcomputer staat.

De vijf aanvallen hieronder hebben dat probleem niet. Ze hebben n soms helemaal niet nodig, of ze ontbinden hem met een berekening die seconden kost, omdat de sleutel niet is wat hij had moeten zijn.

De vijf aannames

Aanname 1: de padding verraadt niets

RSA zonder padding is deterministisch: dezelfde boodschap geeft altijd dezelfde ciphertext, en dat alleen al is een lek. Daarom wordt er padding gebruikt, en daar begint het probleem. Bij PKCS#1 v1.5 begint het bericht met een vaste structuur, en een server die bij ontsleutelen zegt “padding ongeldig” versus “padding geldig maar de rest klopt niet”, is een orakel. Je hoeft de sleutel niet te kennen; je hoeft alleen duizenden malen te vragen of een zelfgekozen ciphertext er goed uitkomt, en dan convergeert het antwoord naar de boodschap.

Bleichenbacher beschreef dit in 1998. In 2017 bleek het raster overal nog open te staan: onderzoekers vonden het in tientallen TLS-stacks en producten, onder de naam ROBOT. Bijna twintig jaar oud, nooit structureel gerepareerd, omdat de fout niet in het algoritme zit maar in de foutafhandeling.

De les is breder dan RSA. Elke keer dat een systeem anders reageert op een bijna-goede en een echt-foute invoer, lekt het één bit. Genoeg bits en je hebt de boodschap. Verdediging: OAEP in plaats van v1.5, constante tijd, en één generieke foutmelding voor alles wat misgaat.

Aanname 2: priemgetallen zijn onafhankelijk

Twee willekeurig gekozen priemgetallen zijn bijna nooit gelijk. Maar “bijna nooit” is geen garantie, en de zwakte zit in de randomgenerator, niet in de wiskunde. In 2008 bleek dat de OpenSSL in Debian twee jaar lang vrijwel geen entropie had gebruikt, waardoor sleutels voorspelbaar werden en opnieuw gegenereerd konden worden. Wie de lijst met mogelijke sleutels had, had de sleutels.

De tweede variant is subtieler en schaalbaar: verzamel heel veel publieke moduli en bereken de ggd van elk paar. Twee sleutels die één priemgetal delen, ontbinden allebei onmiddellijk, en dat kost geen rekenkracht maar een middag. Dat is in de praktijk gedaan met grote verzamelingen certificaten en met sleutels uit embedded apparaten, waar dezelfde generator met dezelfde seed aan het werk was. De aanval is niet gericht: je hoeft geen doelwit te kiezen, je hoeft alleen maar veel sleutels te hebben.

Aanname 3: p en q liggen ver uit elkaar

Fermat gaat ervan uit dat n te schrijven is als a² - b², en dus als (a-b)(a+b). Begin bij a als de wortel van n en tel op tot a² - n een kwadraat is. Als p en q dicht bij elkaar liggen, is die eerste a er bijna meteen.

from math import isqrt

def fermat(n, pogingen=100000):
    a = isqrt(n) + 1
    for _ in range(pogingen):
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1
    return None

Een rekenvoorbeeld met echte getallen. Neem twee priemgetallen van 41 bits, 1099511640127 en 1099512640151. Ze verschillen iets meer dan een miljoen, en Fermat heeft ze in één stap. Zet ze honderd bits uit elkaar en dezelfde code loopt zich dood, want het aantal stappen groeit met het kwadraat van het verschil. De methode is dus niet traag, hij is alleen van toepassing op een situatie die nooit had mogen ontstaan.

Op twee priemgetallen die honderd bits van elkaar verschillen, is dit kansloos. Op twee priemgetallen die vijf bits van elkaar verschillen, heb je je factoren voordat je koffie koud is. Daarom hoort bij sleutelgeneratie een expliciete controle, en daarom is “een priemgetal zoeken in de buurt van de wortel” een klassieke beginnersfout.

Aanname 4: de boodschap is groot genoeg

Met e = 3 en een boodschap die kleiner is dan de derde wortel van n, geldt m³ < n en is de modulus dus nooit in werking getreden. De ciphertext is dan letterlijk de derde macht van de boodschap, en de derdemachtswortel geeft hem terug. Geen ontbinding, geen wiskundig vernuft, alleen een wortel.

Håstad maakte daar in 1985 een aanval van die erger is: stuur dezelfde boodschap naar drie ontvangers met drie verschillende moduli en dezelfde e = 3, en de Chinese reststelling reconstrueert m³ over alle drie, waarna de wortel volgt. Coppersmith breidde dat uit naar het geval waarin een deel van de boodschap bekend is. Dit is de reden dat er padding is, en de reden dat e = 3 niet fout is maar wel vraagt om een implementatie die snapt waarom.

Aanname 5: de modulus is een willekeurig getal

Dit is de aanname die het minst besproken wordt en in de praktijk het vaakst over het hoofd gezien. Stel dat iemand de priemgetallen niet onafhankelijk kiest, maar via één gedeelde constante:

p = a·r + b        q = c·r + d

met r een groot priemgetal en a, b, c, d klein. Dan is n = p·q een kwadraatvorm in r:

n = ac·r² + (ad + bc)·r + bd

Wie n twee keer achter elkaar door r deelt, houdt drie getallen over: X, Y en Z. En dan geldt dat Y² - 4XZ gelijk is aan (ad - bc)², een volkomen kwadraat. De discriminant van een vierkantsvergelijking, zonder ooit te ontbinden.

from math import gcd, isqrt

def factoreer_gestructureerd(n, r):
    Z = n % r
    K = (n - Z) // r
    X = K // r
    Y = K % r
    disc = Y * Y - 4 * X * Z
    delta = isqrt(disc)
    if delta * delta != disc:
        return None                      # geen structuur, of verkeerde r
    U, V = (Y + delta) // 2, (Y - delta) // 2
    a_p = gcd(X, U)
    a_q, b_q = X // a_p, U // a_p
    b_p = V // a_q
    return a_p * r + b_p, a_q * r + b_q

Een voorbeeld met getallen die je kan narekenen. Neem r = 1000000000039, een priemgetal van veertig bits, en p = 7r + 12345, q = 11r + 987. Dan is n = 77000000148710000017867088, en de drie delingen geven X = 77, Y = 142704 en Z = 12184515. Kijk wat daar staat: X is precies a·c en Y is a·d + b·c, oftewel 7·987 + 12345·11. En Y² - 4XZ komt uit op 16611600996, wat 128886² is. Drie delingen en een wortel, en de factoren rollen eruit.

De ggd geeft a·ggd(c,d) en niet zonder meer a, dus de uitkomst moet je controleren: klopt p·q == n en zijn beide factoren priem? In de code hierboven is dat de laatste stap, en dat is precies de reden dat deze aanval niet stil kan mislukken. Verificatie in plaats van aanname.

De aanval werkt ook omgekeerd als les. Een modulus hoort geen zichtbare structuur te hebben. Wie zijn priemgetallen deelt via een gemeenschappelijke factor, en dat doen meer systemen dan je denkt, levert een sleutel af die met drie delingen en een wortel valt.

Wat de vijf gemeen hebben

Geen van deze aanvallen is een aanval op RSA als algoritme. Ze zijn aanvallen op een implementatie die iets weggeeft: een foutmelding die te veel zegt, een generator die te weinig entropie had, een priemgetal dat te dicht bij het andere lag, een exponent die te klein was voor de boodschap, of een modulus met structuur.

Dat maakt de verdediging ook concreet, en saai. Gebruik een beproefde bibliotheek in plaats van zelf iets te bouwen. Gebruik OAEP. Zorg voor echte entropie. Controleer na het genereren dat |p - q| groot genoeg is en dat n geen deler deelt met andere sleutels. Zeg nooit tegen een client welk deel van de ontsleuteling misging. En test met bekende vectoren, want de fouten hierboven zijn allemaal ooit door iemand ingecheckt die dacht dat het goed ging.

Zo toets je een sleutel of implementatie

Voor een pentest of een code review zijn dit de vragen die je in één middag beantwoordt:

• Hoe is de entropie geregeld, en is die bron aantoonbaar? Een embedded apparaat dat bij de eerste boot zijn sleutel maakt, is een rode vlag.
• Ligt |p - q| ruim boven de drempel die je hanteert, en is dat gecontroleerd of alleen gehoopt?
• Deelt deze modulus een factor met andere sleutels in je omgeving? Een batch-ggd over je hele certificaatvoorraad kost weinig en levert soms verrassingen.
• Welke padding wordt gebruikt, en wat zegt de server bij een fout? Test het met een bewust kapotte ciphertext en kijk of het antwoord verschilt.
• Is e klein, en wordt er dan gepad? Zonder padding is e = 3 een open deur.
• Heeft de modulus een algebraïsche vorm, bijvoorbeeld omdat er een gemeenschappelijke constante in de priemgeneratie zit?

Wat dit betekent voor CTF en leren

De reden dat deze aanvallen in challenges terugkomen is dat ze iets leren wat geen tutorial je geeft: kijken naar wat er gegeven is. Een modulus die netjes 2048 bits is maar waarvan de priemgetallen via een gemeenschappelijke factor zijn gemaakt, ziet er in eerste instantie hetzelfde uit als een goede sleutel. Het verschil zit in de structuur, en die moet je leren zien.

Voor wie verder wil in de wiskunde achter dit soort opgaven: ons stuk over groepsorde berekenen met Schreier-Sims gaat over dezelfde houding, namelijk niet zoeken maar de structuur gebruiken. En in CTF & Labs staat waar je zulke opgaven tegenkomt en hoe je ze aanpakt.

Veelgestelde vragen

Is RSA nu wel of niet gebroken?

Nee. RSA met een correct gegenereerde sleutel van 2048 bits en OAEP is niet praktisch te breken met klassieke computers. Wat gebroken is, zijn specifieke implementaties en specifieke sleutels. Dat onderscheid is precies het onderwerp van dit artikel.

Moet ik van RSA afstappen?

Voor nieuwe systemen is de richting eerder elliptische curve of post-quantum, niet omdat RSA vandaag te breken is, maar omdat de sleutels groot zijn en de migratie naar quantumveilige cryptografie jaren kost. Voor bestaande systemen is de eerste winst bijna altijd padding, entropie en foutafhandeling, niet het algoritme.

Waarom staat Coppersmith er niet als zesde aanname?

Omdat het een techniek is en geen aanname. Coppersmith laat zien hoe je kleine wortels van een vergelijking modulo n vindt, en die techniek wordt gebruikt bij kleine exponenten, bij gedeeltelijk bekende boodschappen en bij lekken in de bovenste bits van een priemgetal. Het is het gereedschap achter meerdere van de vijf.

Kan ik deze aanvallen zelf oefenen?

Ja, en dat is de beste manier om ze te begrijpen. Gebruik eigen sleutels of challenge-omgevingen waarin je expliciet toestemming hebt, en nooit andermans systemen. De code in dit artikel is bedoeld voor getallen die je zelf hebt gemaakt.

Hoe weet ik of mijn certificaat een zwakke sleutel heeft?

Begin met de bron: laat je sleutels genereren door een beproefde bibliotheek met een goede entropiebron, en documenteer dat. Daarna kan je toetsen: deel je modulus een factor met anderen, is |p - q| groot, en gebruikt je stack OAEP. Voor veel organisaties is dat laatste het enige dat in de praktijk ooit fout gaat.

Verder lezen

De oorspronkelijke artikelen zijn ouder dan de meeste mensen die ze nu tegenkomen, en ze zijn nog steeds de beste uitleg. Bleichenbacher uit 1998 over het padding-orakel, Håstad uit 1985 over de broadcast-aanval, en het ROBOT-onderzoek uit 2017 dat liet zien dat het eerste probleem nooit echt was opgelost. Wie de wiskunde achter de laatste aanname wil, kan terecht bij de literatuur over ontbinden met gedeeltelijk bekende factoren, waar Coppersmith de basis legde.