Wie ein 512-Bit-DKIM-Schlüssel für weniger als 8 US-Dollar Cloud-Kosten geknackt wurde

 (dmarcchecker.app)
3 Punkte von GN⁺ 2025-01-09 | 1 Kommentare | Auf WhatsApp teilen
  • Bei einer Untersuchung der Top-1-Million-Websites wurden mehr als 1.700 DKIM-Public-Keys mit weniger als 1.024 Bit gefunden; das Experiment prüfte, ob der 512-Bit-RSA-DKIM-Schlüssel von redfin.com tatsächlich ausnutzbar ist
  • Durch Decodieren des p-Tags im DKIM-Record wurden der RSA-Modulus n und der öffentliche Exponent e=65537 gewonnen; anschließend wurde der Modulus mit CADO-NFS faktorisiert
  • Auf einem Hetzner-Server mit 8 dedizierten vCPUs und 32 GB RAM wurde n in rund 86 Stunden in die beiden Primzahlen p und q zerlegt; auf dieser Basis wurde der RSA-Private-Key rekonstruiert
  • Mit dem rekonstruierten Private Key signierte E-Mails vom Absender security@redfin.com wurden von Gmail und Outlook abgelehnt, aber Yahoo Mail, Mailfence und Tuta lieferten dkim=pass zurück
  • Bei der DMARC-Policy p=reject; pct=100 von redfin.com führt ein bestandener DKIM-Check auch zu einem bestandenen DMARC-Check; Mailanbieter sollten daher RSA-DKIM-Signaturen mit weniger als 1.024 Bit ablehnen

Das Problem verbleibender 512-Bit-DKIM-Schlüssel

  • Bei einer Untersuchung von SPF-, DKIM- und DMARC-Records der Top-1-Million-Websites wurden mehr als 1.700 öffentliche DKIM-Schlüssel mit einer Länge von weniger als 1.024 Bit gefunden
  • RSA-Schlüssel mit weniger als 1.024 Bit gelten als unsicher; für DKIM wird ihre Nutzung seit RFC 8301 aus dem Jahr 2018 nicht mehr empfohlen
  • Ziel des Experiments war der bei key1._domainkey.redfin.com gefundene 512-Bit-RSA-Public-Key
  • Ziel war zu prüfen, ob sich allein aus dem Public Key der Private Key wiederherstellen lässt, um E-Mails so zu signieren, als kämen sie vom ursprünglichen Domain-Absender
  • Zusätzlich wurde geprüft, ob große E-Mail-Anbieter wie Gmail, Outlook.com und Yahoo Mail DKIM-Signaturen mit kurzen Schlüsseln akzeptieren

RSA-Komponenten aus dem DKIM-Public-Key extrahieren

  • Das p-Tag eines DKIM-Records enthält den Public Key, zunächst im ASN.1-DER-Format codiert und anschließend erneut Base64-codiert
  • Mit Crypto.PublicKey.RSA.import_key in Python wurde der Public Key eingelesen und die RSA-Komponenten wurden extrahiert
    • Modulus n: 10709580243955269690347257968368575486652256021267387585731784527165077094358215924099792804326677548390607229176966588251215467367272433485332943072098119
    • Öffentlicher Exponent e: 65537

Faktorisierung des Modulus mit CADO-NFS

  • Um den RSA-Private-Key zu erzeugen, muss der Modulus n in das Produkt zweier Primzahlen p und q zerlegt werden
  • Für die Faktorisierung wurde CADO-NFS verwendet
    • CADO-NFS ist eine Implementierung des Number-Field-Sieve(NFS)-Algorithmus zur Faktorisierung großer Ganzzahlen
  • Damit der lokale Rechner nicht mehrere Tage blockiert war, wurde ein Hetzner-Cloud-Server gemietet
    • Die Server-Spezifikation: 8 dedizierte vCPUs, AMD EPYC 7003-Serie, 32 GB RAM
    • Als OS lief Ubuntu
    • Um genügend Speicher für den Job bereitzustellen, wurden 32 GB Swap hinzugefügt
  • Die Faktorisierung wurde ausgeführt, indem der Modulus n an cado-nfs.py übergeben wurde
  • Der gesamte Job dauerte auf dem 8-vCPU-Server rund 86 Stunden, und n wurde in die folgenden beiden Primzahlen zerlegt
    • p = 97850895333751392558280999318309697780438485965134147739065017624372104720767
    • q = 109447953515671602102748820944693252789237215829169932130613751100276125683257
  • Mit einem leistungsfähigeren Server oder verteilter Ausführung auf mehreren Systemen lässt sich die Zeit verkürzen; CADO-NFS vereinfacht verteilte Jobs

Rekonstruktion des RSA-Private-Keys

  • Nachdem p, q und e vorlagen, wurde mit Python und PyCryptodome ein RSA-Private-Key konstruiert
  • Für die Berechnung wurden die folgenden Werte und Schritte verwendet
    • n = p * q
    • phi = (p-1) * (q-1)
    • d = inverse(e, phi)
    • RSA.construct((n, e, d, p, q))
  • Das Ergebnis war ein RSA-Private-Key im PEM-Format, der in die OpenDKIM-Konfiguration integriert und zum Signieren von Testmails verwendet wurde

Ergebnisse der DKIM-Prüfung nach Mailanbieter

  • Der rekonstruierte Private Key wurde in OpenDKIM eingebunden, und Testmails mit der FROM-Adresse security@redfin.com wurden an mehrere E-Mail-Hosting-Dienste gesendet
  • Die meisten Anbieter stuften den 512-Bit-Schlüssel als unsicher ein und lehnten die DKIM-Signatur ab, doch drei Anbieter lieferten dkim=pass zurück
  • Die Ergebnisse nach Anbieter waren wie folgt
    • Gmail: FAIL
    • Outlook: FAIL
    • Yahoo Mail: PASS
    • Zoho: FAIL
    • Fastmail: FAIL
    • Proton Mail: FAIL
    • Mailfence: PASS
    • Tuta: PASS
    • GMX: FAIL
    • OnMail: FAIL
  • redfin.com verfügt über einen gültigen DMARC-Record der Form v=DMARC1;p=reject;pct=100;...
  • Ein bestandener DKIM-Check für redfin.com führte zu einem bestandenen DMARC-Check und erfüllte auch die Anforderungen von BIMI

Kosten und operative Maßnahmen

  • Vor 30 Jahren war das Brechen eines 512-Bit-RSA-Public-Keys eine Aufgabe auf Supercomputer-Niveau; heute ist es auf einem Cloud-Server für unter 8 US-Dollar möglich
  • Mit einem leistungsstarken Heimcomputer mit 16 oder mehr Kernen könnte es sogar schneller und günstiger gehen
  • Es gibt keinen Grund, 512-Bit- oder 768-Bit-DKIM-Schlüssel beizubehalten; E-Mail-Anbieter sollten DKIM-Signaturen, die mit RSA-Schlüsseln unter 1.024 Bit erzeugt wurden, automatisch ablehnen
  • Yahoo, Mailfence und Tuta wurden über die Ergebnisse des Experiments und die Empfehlungen informiert
  • Domaininhaber sollten ihre DNS-Einstellungen auf veraltete DKIM-Records prüfen
    • Das p-Tag eines DKIM-Records lässt sich einfach prüfen, indem man die Anzahl der Base64-Zeichen zählt
    • Ein 1.024-Bit-RSA-Public-Key hat in Base64 mindestens 216 Zeichen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-01-09
Kommentare auf Hacker News

  • Schon vor 14 Jahren war es möglich, 512-Bit-DKIM-RSA-Schlüssel zu knacken: https://blog.jgc.org/2010/06/facebooks-dkim-rsa-key-should-b...

    • Eine Zeit lang wurde die Verwendung schwacher DKIM-Schlüssel inoffiziell fast als Feature angesehen
      Die Logik war, dass bei kurzen Schlüsseln DKIM-Signaturen nicht lange als Beweis bestehen bleiben, sodass sich später schwerer nachweisen lässt, welche E-Mail echt war, und so plausible Abstreitbarkeit gewahrt bleibt
      Das heißt natürlich nicht, dass die meisten Unternehmen deshalb kurze Schlüssel verwendet haben, sondern nur, dass es eine gewisse Stimmung gab, nach der kurze Schlüssel nicht ausschließlich schlecht seien
      DKIM-Abstreitbarkeit ist für mich persönlich schon lange ein Thema [1]; solche kurzen Schlüssel sind ganz klar keine Lösung, aber ich sehe darin ein Ergebnis des wirren Denkens rund um DKIM und einer Community-Stimmung, die die Implikationen von E-Mail-Signatursystemen generell nicht akzeptieren wollte
      [1] https://blog.cryptographyengineering.com/2020/11/16/ok-googl...
    • Das erinnert mich an die Geschichte von jemandem, der einen DKIM-Schlüssel geknackt hat, weil er dachte, es sei eine Google-Bewerbungsaufgabe
      https://www.wired.com/2012/10/dkim-vulnerability-widespread/
    • 1999 zeigte die Faktorisierung von RSA-155 mit einigen hundert Computern, dass 512-Bit-Schlüssel praktisch knackbar sind, und inzwischen hieß es, das gehe mit normaler Hardware in wenigen Wochen
      Damit wäre es in ungefähr 14 Jahren von einigen Wochen auf 8 Stunden gesunken
    • Zur Einordnung: Der Verfasser des Elternkommentars ist der CloudFlare CTO
    • Dieser Blog wurde auch in den Kommentaren zu http://www.wired.com/threatlevel/2012/10/dkim-vulnerability-... erwähnt

  • Wenn man es zum Spaß ausprobieren will, kann man einen 4096-Bit-DKIM-Schlüssel erzeugen
    Online-DKIM/SPF-Prüfer sagen anhand des DNS, dass alles in Ordnung ist, aber Testmails schlagen fehl
    Man bekommt dann großartige Erklärungen wie STATUS: Fail, DKIM: Pass, SPF: Pass
    Im DKIM-Eintrag sind Schlüssel größer als 2048 Bit erlaubt und gültig, aber Validatoren mussten Schlüssel über 2048 Bit nicht zwingend verarbeiten können
    Dabei habe ich mir einige Haare ausgerauft

    • Ergänzend dazu: Um den Prüfungsfehler zu sehen, muss man eine strikte DMARC-Richtlinie setzen
      Interessanterweise sagen die Seiten, dass alle drei Punkte korrekt und gültig seien, behandeln die Mail aber trotzdem als fehlgeschlagen
      Vermutlich, weil DNS-Record-Prüfung und E-Mail-Verifikation von unterschiedlicher Software erledigt werden
    • Das aktuelle RFC, RFC8301, enthält dazu Anforderungen
      Validatoren müssen Signaturen mit Schlüsseln von 512 Bit bis 2048 Bit prüfen können und dürfen auch größere Schlüssel prüfen
      Ich habe vor einem Jahr meine Masterarbeit zu diesem Thema geschrieben, und damals unterstützten die großen Mailanbieter alle 4096 Bit, einige sogar bis 16384 Bit

  • Ich frage mich, warum man bei Verschlüsselung allgemein nicht einfach die Schlüsselgrößen deutlich anhebt
    Das wäre zwar keine endgültige Lösung, scheint aber zumindest Zeit zu kaufen
    Die Rechenleistung steigt schnell, und von Quantencomputern ist ständig die Rede, trotzdem wirkt es, als würde niemand etwas tun
    Klar kosten größere Schlüssel mehr Rechenleistung, aber unsere Rechenressourcen sind ja ebenfalls gewachsen; man sollte sie nicht nur für Angriffe nutzen, sondern auch für die Verteidigung
    Sogar die simple Sache, clientseitig TLS 1.3 statt TLS 1.2 zu erzwingen, führt noch zu vielen kaputten Dingen, auch bei der HN-Seite

    • Ein alter, aber weiterhin relevanter Text: https://www.schneier.com/blog/archives/2009/09/the_doghouse_...
      Diese Zahlen hängen nicht vom Stand der Gerätetechnik ab, sondern von den Maximalwerten, die die Thermodynamik erlaubt
      Unterm Strich ist es physikalisch unmöglich, AES-256 oder RSA-4096 per Brute Force zu brechen
    • Das passiert bereits
      1024-Bit-Schlüssel werden seit über 10 Jahren systemübergreifend ausgemustert
      Abgesehen von einer zurückgebliebenen Ausnahme ist das der Fall, und das Einzige, was 2048-Bit-Schlüssel bedroht, sind Quantencomputer; die bedrohen allerdings RSA insgesamt
      Fortschritt verläuft nicht linear, daher bedeutet ein geschwächtes 1024 nicht automatisch, dass 2048 mechanisch als Nächstes fällt, und selbst 1024 ist für praktische Angriffe heute nicht einfach
    • RSA-2048 ist noch nicht gebrochen, und danach kann man sich in den meisten Bereichen, in denen RSA genutzt wird, bereits auf das verbreitete RSA-4096 stützen
      DKIM ist eine der Ausnahmen
      Im DKIM-Bereich wartet man darauf, dass Ed25519 breit angenommen wird; dann würden sich einige Unannehmlichkeiten erledigen
    • Um die Nutzung zu erzwingen, muss man am Ende etwas kaputtmachen
      Meist wird dieser Schmerz nicht von den Dienstbetreibern getragen, sondern direkt an die Nutzer weitergereicht, in der Hoffnung, dass diese laut genug protestieren, damit die Betreiber reagieren
      Allerdings wechseln Nutzer dann auch leicht zur Konkurrenz, die verhindert, dass kleine Dinge wie Sicherheit den Umsatz blockieren
    • Als ich vor 8 Jahren in der E-Mail-Branche gearbeitet habe, war 512-Bit-DKIM schon extrem selten
      Im Grunde fragt man damit: „Warum macht ihr nicht das, was wir längst schon tun?“

  • Mit CADO-NFS geht das überraschend leicht
    Ich habe vor ein paar Wochen beruflich einen 512-Bit-RSA-DKIM-Schlüssel auf meinem Desktop-PC faktorisiert, und es hat nur 28 Stunden gedauert
    Konkret war es ein AMD Zen 5 9900X
    Leider sind 1024-Bit-Schlüssel für Hobbyaufwand noch zu schwer, aber für ein akademisches Projekt in der Größenordnung der Faktorisierung eines 768-Bit-Schlüssels im Jahr 2010 könnte es möglich sein: https://eprint.iacr.org/2010/006.pdf

  • Gestern erhielt ich von der Bank of America eine E-Mail zu einem Problem bei der Kontoeinrichtung.
    Ich hatte tatsächlich ein neues Konto erstellt, und die E-Mail kannte diese Tatsache sowie den Firmennamen usw.
    Es gab keinen Link, nur den Hinweis, die geschäftliche BofA-Nummer anzurufen; ich überprüfte die Nummer auf der BofA-Website, sie stimmte überein, also rief ich an.
    Aber niemand konnte mir sagen, warum ich die E-Mail erhalten hatte oder welches Problem es mit dem Konto gab, und die Mitarbeiterin konnte nicht einmal einen Versanddatensatz dieser E-Mail finden.
    Ich bin mir zu 100 % sicher, dass diese E-Mail von der Bank of America kam.
    Es gab keine Phishing-Merkmale, keinen Link und keine bösartige Telefonnummer.
    SPF, DKIM und DMARC bestanden alle in Googles ARC-Authentication-Results, und auch der DKIM-Schlüssel war 2048 Bit lang.
    Als ich die Bank of America bat, das zu untersuchen, antwortete man nur, es sei „wohl eine Phishing-Nachricht“ gewesen, und schickte mir einen Link mit Hinweisen zum Schutz vor Phishing.
    Wahrscheinlich war es einfach ein Fehler, bei dem ein System während der Kontoerstellung zu früh einen Konsistenzcheck ausführte und dadurch die E-Mail erzeugte.
    Aber weil sie es als „Phishing“ bezeichneten, habe ich dem CTO ein FedEx mit allen Unterlagen geschickt.
    Es gibt zwei Möglichkeiten: Entweder ist der DKIM-Schlüssel kompromittiert und es müsste sofort eine öffentliche Warnung geben, oder inkompetente Mitarbeiter und IT-Systeme haben mich im Kreis geschickt und mir eine Stunde verschwendet.
    In beiden Fällen will ich eine vollständige Untersuchung und Lösung.

  • Manche DNS-Anbieter sind miserabel und erlauben nur die Einrichtung von 1024-Bit-Schlüsseln.
    wordpress.com ist zum Beispiel so ein Fall.

    • 1024 Bit sind um mehrere Größenordnungen schwerer zu brechen als 512 Bit.
      Zur Einordnung: Die zuletzt gebrochene RSA-Zahl war RSA-250, also 829 Bit, und dafür brauchte man 2020 2700 Core-Jahre [1].
      RSA-155, also 512 Bit, wurde dagegen schon 1999 faktorisiert.
      Das ist also noch kein gefährlicher Zustand.
      [1]: https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.h...
    • NIST will bis 2035 sogar 2048-Bit-RSA verbieten,
      weil es kein ausreichendes Sicherheitsniveau mehr bietet.
    • RSA-1024 ist gegenüber RSA-512 grob gesehen etwa 8 Millionen Mal besser, sodass allein die Rechenkosten zum Brechen wohl bei rund 64 Millionen Dollar lägen.
      Das hält zwar nicht die NSA auf, aber wenn man bedenkt, dass DKIM nur eine von mehreren Schutzschichten ist, scheint es auszureichen, um Spammer aufzuhalten.
    • DKIM-Records sind einfach DNS-TXT-Records.
      Ich frage mich, ob es eine Größenbeschränkung für TXT-Records gibt oder ob sie versuchen, TXT-Records, die wie DKIM aussehen, unnötig zu parsen, dabei scheitern und das Hinzufügen dann verweigern.

  • Für eine gute Demonstration ist es sehr wertvolle Sicherheitsforschung, 512-Bit-Schlüssel zu brechen, auch wenn das bereits getan wurde.
    Es ist auch legitim, öffentlich zu sagen: „Hier ist eine Liste von Orten, die immer noch 512 Bit verwenden und migrieren sollten.“
    Aber tatsächlich einen realen, produktiv eingesetzten Schlüssel zu brechen, fühlt sich für mich persönlich ethisch wie eine Grenzüberschreitung an und macht mir Unbehagen.
    Ich bin kein Anwalt, aber es könnte auch strafbar sein, und es wirkt etwas unnötig.

    • Das betroffene Unternehmen wurde über die Schwachstelle informiert, sie wurde behoben, und danach wurde der Artikel veröffentlicht.
      Im Original kann man nach now no longer available suchen.
      Normalerweise weist man bei Online-Systemen auf eine Schwachstelle hin, indem man sie in gutem Glauben reproduziert, die Forschung dokumentiert und dann um Prüfung bittet.
      Ob es darum geht, ein kryptografisches System zu brechen, auf einer gesperrten Spielkonsole beliebigen Code auszuführen, zu beweisen, dass man Daten von Wahlmaschinen manipulieren kann, oder zu zeigen, dass sich Q&A-Kommentare in Google Meet bearbeiten lassen — der Ablauf ist derselbe.
      Wenn man nur sagt, dass etwas verwundbar ist, kann man ignoriert werden; wenn man sagt, dass es verwundbar ist, und es beweist, wird Ignorieren deutlich schwieriger.
      Wenn man dann noch eine branchenübliche Offenlegungsfrist setzt und etwa 60 Tage lang versucht, Kontakt aufzunehmen, bevor man die Schwachstelle veröffentlicht, bleibt praktisch kein Raum mehr, das zu ignorieren.
    • Einen Schlüssel zu brechen ist kein Verbrechen.
      Das ist einfach Mathematik.
      Illegal wird es, wenn man sich auf diese Mathematik stützt, um Betrug zu begehen oder E-Mails zu versenden, die in einer bestimmten Jurisdiktion gegen Gesetze verstoßen.
      Entscheidend sind nicht die Mathematik, sondern Handlung und Absicht.
      Jemanden darauf hinzuweisen, dass er etwas Dummes tut, ist ebenfalls nicht illegal — auch wenn diese Person Ihnen das Leben schwer machen könnte.
    • Das Gleiche lässt sich über einen großen Teil der Sicherheitsforschung sagen.
      Etwa im Sinn von: „Es ist okay zu zeigen, dass ein Bug ausnutzbar ist, aber Proof-of-Concept-Code zu schreiben, geht zu weit.“
      Das Problem ist, dass die meisten Sicherheitsforscher nicht ernst genommen werden, wenn sie nicht zeigen, dass es tatsächlich funktioniert.
    • Von etwa 1700 Domains, die Schlüssel kürzer als 1024 Bit verwenden, wurde tatsächlich nur eine namentlich genannt.
      Stattdessen wurden drei von zehn großen E-Mail-Anbietern, die das DKIM-RFC nicht korrekt einhalten — Yahoo, Tuta, Mailfence — nach vorheriger Benachrichtigung offengelegt.
    • Wenn nur öffentliche Informationen verwendet wurden und man mit dem Ergebnis nichts gemacht hat, dann ist das Brechen eines in der realen Welt genutzten Schlüssels an sich wahrscheinlich kein Verbrechen.

  • Das ist der Grund, warum ich das DNS-Management mit Hover aufgegeben habe.
    TXT-Records mit mehr als 255 Zeichen werden dort nicht unterstützt, und ich konnte keinen Fall finden, in dem aufgeteilte Records bei Hover funktioniert hätten.
    Am Ende bin ich bei Digital Ocean gelandet.
    Wenn sich dieses Problem noch weitere 10 Jahre hinzieht, hoffe ich, dass Elliptische-Kurven-Kryptografie bis dahin Standard wird.

  • Bei der Stelle „die meisten Anbieter identifizierten 512-Bit-Schlüssel korrekt als unsicher und lehnten die DKIM-Signatur ab, aber drei große Anbieter — Yahoo Mail, Mailfence, Tuta — meldeten dkim=pass“ frage ich mich, ob Google die DKIM-Signatur wirklich wegen ihrer Unsicherheit scheitern ließ oder ob sie wegen eines SPF-Fehlschlags scheiterte.

    • Die DKIM-Validierung scheiterte gemäß RFC 8301 mit dem Ergebnis dkim=policy (weak key).
      Genau wie in der Anforderung: „Ein Prüfer darf Signaturen, die RSA-Schlüssel unter 1024 Bit verwenden, nicht als gültige Signaturen betrachten.“

  • Ob 512 Bit viel oder wenig sind, hängt davon ab, ob es sich um symmetrische Kryptografie oder asymmetrische Kryptografie handelt
    Man kann grob sagen, dass asymmetrische Kryptografie immer 8-mal schwächer ist als symmetrische
    DKIM ist asymmetrisch, daher entsprechen 512-Bit-DKIM gemessen an symmetrischen Hashes 64 Bit und liegen damit auf einem Niveau, das schon seit Langem gebrochen ist
    Selbst 160-Bit-SHA-1 gilt bereits als gebrochen
    Für DKIM mit einer Stärke ähnlich zu 512-Bit-SHA-3 wären mindestens 4096 Bit nötig, und selbst das umfasst noch nicht die Abwehrmaßnahmen gegen Replay-Angriffe bei SHA-3

    • DKIM ist kein Verschlüsselungsalgorithmus
      Es ist ein Standard zum Einfügen und Prüfen von Signaturen in E-Mail-Headern
      Leider unterstützt DKIM nur rsa-sha1- und rsa-sha256-Signaturen: https://datatracker.ietf.org/doc/html/rfc6376/#section-3.3
      Es wäre gut, wenn DKIM überarbeitet würde und Ed25519 oder ähnliche Signaturen erlauben würde
    • RSA-Verschlüsselung ist 10-mal schwächer als Elliptische-Kurven-Kryptografie
      Zum Beispiel entspricht 224-Bit-ECC ungefähr 2048-Bit-RSA
      Beides sind asymmetrische Verfahren
      Umgekehrt hat asymmetrische Elliptische-Kurven-Kryptografie eine ähnliche Stärke wie die symmetrische Verschlüsselung AES
      Natürlich ist sie gegenüber Quantencomputern verwundbar