BND CRYPTO CHALLENGE 2021: RSA Key Generation

Der Bundesnachrichtendienst sucht Hacker. Dabei hat sich der Auslandsnachrichtendienst der Bundesrepublik Deutschland mit der Glitch Karnickel Kampagne an die deutsche Hacker-Szene gewandt und versucht, sie mit ein paar Challenges für die Arbeit als Cyber-Spion zu begeistern. Da die Aktion für dieses Jahr wohl seit Anfang September beendet ist, halte ich es durchaus für vertretbar, meine Lösungen in Form eines Video-Writeups mit meiner Community zu teilen, denn jetzt verschaffe ich durch die Veröffentlichung meiner Lösung niemandem mehr einen unfairen Vorteil. Gleichzeitig hast du aber die Möglichkeit zu lernen, wie man an solche Aufgaben herangeht und wie du bereits aus meinem Video zum Hackenlernen weißt, sind CTFs eine gute Möglichkeit, sich Wissen in diesem Bereich anzueignen.

Aber genug der langen Vorrede. Im diesem ersten Teil bearbeiten wir die Challenge aus dem Bereich der Kryptologie. Warum? Nun, zum einen, weil sie vom Schwierigkeitsgrad her wohl die Einsteigeraufgabe zum Warmwerden ist und zum anderen, weil ich auf meinem Kanal bereits zahlreiche Videos zur Kryptologie erstellt habe, mit denen du dich auf diese Challenge vorbereiten kannst. Zudem schließt die Lösung dieser Aufgabe eine der noch offenen Lücken an Angriffsvektoren auf den RSA-Algorithmus.

Konspirative Account-Erstellung

Aber alles der Reihe nach. Zuerst müssen wir uns einen Account erstellen, um auf die Challenges zugreifen zu können. Und natürlich wollen wir dabei unerkannt bleiben. Denn wer hat schon Lust, einem Nachrichtendienst freiwillig Daten zu liefern? Deshalb erstellen wir uns ganz konspirativ über Tor eine Trash Mail Adresse, die nach 10 Minuten erlischt und uns aber Zugang zum Portal gewährt.

Im ersten Schritt rufen wir also die Webseite bnd.hacking-lab.com auf und werden nach etwas Wartezeit mit einer Anmeldemaske begrüßt.

Da wir noch keinen Account haben, erstellen wir uns einen durch einen Klick auf Register.

Das Registrierungsformular füllen wir mit ein paar Fantasiedaten. Unser Name ist jetzt einfach mal Schnee. Eduard Schnee. Als E-Mail-Adresse verwenden wir eine bereits erwähnte 10 Minuten lang gültige Trash Mail. Dazu gehen wir auf DuckDuckGo, suchen "10 minute mail", wählen einen Anbieter aus, kopieren uns die E-Mail-Adresse und können uns einen Username ausdenken. Inspiriert von meinem Video, warum Hacker die Zahl 0x41414141 lieben, wählen wir ganz einfallsreich 0x41414141. Zum Schluss vergeben wir noch ein sicheres Passwort, wiederholen das und klicken auf den Button Register.

Jetzt lesen wir uns natürlich ganz sorgfältig die Terms and Conditions durch (im Ernst, lies sie dir in einer ruhigen Minute mal durch) und klicken auf Accept, wenn wir das schon bei den Cookies nicht getan haben.

Im Account angekommen sehen wir erstmal, dass wir nichts sehen. Es laufen aktuell keine Events und es sind offenbar auch keine geplant. Wir können durch einen Klick das Feld "RUNNING, UPCOMING" oben rechts auswählen, dass wir vergangene Events anzeigen wollen ...

... und bekommen dann auch das bereits angesprochene Recruiting CTF aus diesem Jahr angezeigt, das am 30.08.2021 abgelaufen ist.

Leider können wir damit nichts machen. Das Event ist vorbei und somit auch die Teilnahmemöglichkeit. Zum Glück habe ich mir in der Zeit als die Challenges aktiv waren, einen Account erstellen und kann somit die Aufgaben hier mit dir teilen.

Nach der Anmeldung kann ich aus drei verschiedenen Challenge-Kategorien wählen, nämlich Cryptography, Web Security und Reverse Engineering & Exploitation.

Wir wählen die Kategorie Cryptography und dort die RSA Key generation Challenge aus. Wie man bereits sehen kann, wurde diese offenbar während der laufenden Challenge aktualisiert.

Die RSA Key Generation Challenge

Jetzt sind wir in der Challenge und sehen direkt ein paar Codezeilen und lange Zahlen, aber keine Sorge: Wir gehen die Aufgabe Schritt-für-Schritt durch. Wir halten aber schon einmal fest: Um beim Bundesnachrichtendienst als Hacker anfangen zu können, muss man obviously English speaken können. Ich übersetze dir die Aufgabe an dieser Stelle einfach mal.

Introduction

During a recent code review one of our engineers has found something weird in the RSA key generation. You have the task to find out whether this has any impact on the safety.

Während eines kürzlichen Code reviews hat einer unserer Ingenieure etwas Merkwürdiges bei der Schlüsselgenerierung für den RSA gefunden. Deine Aufgabe ist es herauszufinden, ob das irgendeinen Einfluss auf die Sicherheit hat.

Update on 2021-03-07

This challenge has been updated as following: The value for x from the code listing as well as the values of N and c given in the goal section have been re-generated. It is highly recommended to solve it using the new values, although the plaintext message is the same.

Huge thanks to everyone who told us that something was off with our values and sorry for the much harder than anticipated challenge.

Offenbar wurden die Zahlen in der Challenge aktualisiert, was uns aber nicht interessiert, weshalb wir diesen Hinweis gekonnt ignorieren.

Als nächstes werden wir mit ein bisschen Code konfrontiert. Der erste Code-Schnipsel scheint ein Python-Skript mit Utility-Funktionen zu sein.

### Excert from utils.py (used to encode / decode the message)
def encode(msg):
    """
    Convert a message to a number.
    
    Example:
    >>> hex(encode(b'ABCD'))
    '0x41424344'
    """
    return int.from_bytes(msg, byteorder='big')

def decode(msg):
    """
    Convert a number back to a message.
    
    Example:
    >>> decode(0x41424344)
    b'ABCD'
    """
    return int(msg).to_bytes(length=len(hex(msg))//2-1, byteorder='big')

Mit der Funktion encode kann man wohl einen Text im Binärformat in eine Hexadezimalzahl umwandeln. Umgekehrt erlaubt uns die Funktion decode, das wir eine Hexadezimalzahl in einen Text umwandeln können. Mit diesen beiden Funktionen werden wir wohl später unsere geknackten Codes in eine lesbare Flagge umwandeln können. Dazu kommen wir dann geeigneter Stelle noch einmal zu sprechen.

Der zweite Code-Schnipsel soll wohl eine Verschlüsselung mit dem RSA-Algorithmus ermöglichen. Da gehen wir später aber noch näher drauf ein.

### Excert from RSA.py
x = 0xbb31781a2436fd6833597b61f91b94fba8cc5be702c7084de28625d96823102daf48dd84244fe41d180452a900388d1666ff59981f0912c6640977684c20bcfdcbf365dfcb68c0c5a9fd02576134a0e94ab9e20bbacffb4df5c9c27ae7f5022f6609aefeb9f5249387925ad13ce80a13

def rsa_keygen():
    def a(x, y):
        z = 1
        while True:
            if is_prime(x*z + y):
                return x*z + y
            z += 1

    p = a(x, random_prime(2^128, None, 2^127))
    q = a(x, random_prime(2^128, None, 2^127))
    
    N = p * q
    e = 65537
    
    d = inverse_mod(e, (p-1) * (q-1))
    
    return e, d, N

def rsa_crypt(m, k, n):
    return lift(Mod(m, n) ^ k)

Goal

The engineer sent you a test message. Can you decrypt it?

Der Ingenieur hat uns eine Testnachricht geschickt, die wir entschlüsseln sollen. Am liebsten wäre es ihm vermutlich, wenn wir es nicht können, da das wiederum für eine unsichere Implementierung sprechen würde.

e = 65537
N = 6217468290706613301603616005528100131798149079252059573007495519788267044819121069395602245916998799930775648250683389442966714804739613450381148533419461928485596870928541962694971680190134542148996706927335882462229500089986851509475109505459048676123650490359710027902270147490153424656466031170743546488513755685818385587367321466024945007514143310365200975587058348169982977145650693955667384644381937407101389719894018805206516292068437770414857823797915459660636056085645464594641983523102970037856987032167809541108080330794363602778053
c = 2403958089131679913280388000590444805870336793994842072765238389702465658316012937918168208480675977995643226078413644628259138097045221263367315251880579357261568983261767728244111191268740525499918021532930079880132241418326592156659066605343402785460641431875333212535673641255300099993314785755934870975128143213605376650490207877022044023372044186152484758267679564160572404559310873497815049934655680334251964614447413366867181827019553147813581000873134348328652679149309707292737376026040119503186190733157879722025259970612661722013152

Notes

The code above is designed to run in Sage

Als kleine Randnotiz wird uns noch mitgeteilt, dass der Code wohl dazu ausgelegt ist, in Sage zu laufen. Was das ist, klären wir noch im Laufe der Challenge.

Wie funktioniert das RSA-Verfahren?

Wir kümmern uns jetzt erstmal darum nachzuvollziehen, was man überhaupt unter dem Dreh- und Angelpunkt dieser Challenge, nämlich dem RSA-Algorithmus, versteht.

Dazu schauen wir Benny und Ayumi dabei zu, wie sie sich gegenseitig mit dem RSA Verfahren verschlüsselte Nachrichten schicken wollen. Zunächst einmal musst du wissen, dass das RSA Verfahren zu den asymmetrischen Verschlüsselungsverfahren zählt. Das Grundprinzip kann man sehr schön an der Ende-zu-Ende-Verschlüsselung verdeutlichen, zu der ich bereits ein Video erstellt habe.

Jeder Kommunikationsteilnehmer besitzt dabei einen öffentlichen und einen privaten Schlüssel. Diese bilden zusammen ein sog. Schlüsselpaar. Der öffentliche Schlüssel steht in einem Schlüsselverzeichnis, auf das alle Teilnehmer Zugriff haben. Möchte Benny eine Nachricht an Ayumi schicken, dann verschlüsselt er sie mit ihrem öffentlichen Schlüssel. Aufgrund der mathematischen Verbundenheit der beiden Schlüssel, kann Ayumi (und nur Ayumi) die mit ihrem öffentlichen Schlüssel verschlüsselte Nachricht auch wieder entschlüsseln. Wie das geht, schauen wir uns jetzt mal im Detail an.

Schlüsselgenerierung

Zunächst einmal muss das Schlüsselpaar, bestehend aus dem öffentlichen und privaten Schlüssel berechnet werden.

Dafür wählt man zwei sehr große Primzahlen $p$ und $q$. Sie können auch gleich sein, was aber nicht zu empfehlen ist, weil man dann zum Faktorisieren nur die Quadratwurzel ziehen muss. Je größer die beiden Primzahlen sind, desto besser. Wir reden hier nicht von zwei- oder dreistelligen, sondern dreihundertstelligen Primzahlen (und mehr). Warum müssen die Primzahlen so groß sein?
Nun, im nächsten Schritt wird das Produkt $N=p\cdot q$ berechnet. Es soll einem Angreifer nicht möglich sein, dieses Produkt in seine beiden Primzahlen aufzuteilen. Darauf fußt im Übrigen auch die Sicherheit des gesamten RSA-Verfahrens.
Für das in Schritt 3 berechnete $N$ wird $\varphi(N)$ durch $(p-1)\cdot (q-1)$ berechnet. $\varphi(N)$ gibt die Anzahl der zu $N$ teilerfremden Zahlen an. Jetzt siehst du auch, weshalb wir zwei Primzahlen wählen. Damit kann $\varphi(N)$ leicht berechnet werden. Und genau dieses Wissen um die Primzahlen ist später auch Teil unseres Geheimnisses.
Näheres zu den mathematischen Zusammenhängen im RSA-Verfahren findest du in meinem Video zu den Grundlagen des RSA-Algorithmus

Jetzt wählt man eine Zahl $e$, die zwischen $1$ und $\varphi(N)$ liegen muss und die teilerfremd zu $\varphi(N)$ ist, d.h. $$ggT(e,\varphi(N))=1$$ Warum muss diese Eigenschaft vorliegen? Nun, dann ist $e$ in $\mathbb{Z}/N\mathbb{Z}$ invertierbar, d.h. es existiert eine Zahl $d$, für die $$e\cdot d\equiv 1\mod \varphi(N)$$ ist.
Dieses $d$ muss im nächsten Schritt berechnet werden. Das funktioniert mit dem erweiterten euklidischen Algorithmus.

Die beiden Schlüssel setzen sich wie folgt zusammen:

Öffentlicher Schlüssel: $(e,N)$
Privater Schlüssel: $(p,q,d)$

Diese Struktur der Schlüsselgenerierung findet sich auch in der keygen-Funktion des BND wieder.

Zuerst werden zwei zufällige Primzahlen generiert.

p = a(x, random_prime(2^128, None, 2^127))
q = a(x, random_prime(2^128, None, 2^127))

Die Art und Weise wie sie generiert werden ist übrigens das, was wir später attackieren werden. Danach wird das Produkt

N = p * q

berechnet. Dann wird das $e$ für den öffentlichen Schlüssel festgelegt

e = 65537

Das ist übrigens ein häufig verwendeter Wert beim RSA-Verfahren. Zum Schluss muss noch der letzte Teil des privaten Schlüssels, nämlich das $d$ berechnet werden. Hierzu kommt die hauseigene Funktion inverse_mod zum Einsatz, die das multiplikative Inverse der Zahl $e$ modulo $\varphi(N)$ berechnet. Auch hier gilt wieder $$\varphi(N)=(p-1)\cdot (q-1)$$ weil $p$ und $q$ Primzahlen sind.

d = inverse_mod(e, (p-1) * (q-1))

Zur Zusammensetzung der Schlüssel werden alle relevanten Bestandteile zurückgegeben.

return e, d, N

Verschlüsseln

Zum Verschlüsseln einer Nachricht $m$ mit dem öffentlichen Schlüssel $(e,N)$ des Kommunikationspartners wird $$m^e\mod N$$ berechnet.

Entschlüsseln

Zum Entschlüsseln von $c$ wird $$c^d\mod N$$ berechnet. Das funktioniert, weil $$c^d=\left(m^e\right)^d=m^{c\cdot d}=m^{1+r\cdot \varphi(N)}=m^1\cdot m^{r\cdot \varphi(N)}=m\cdot 1=m$$ ist. Was das alles zu bedeuten hat, erfährst du in meinem bereits angesprochenen Video zu den mathematischen Grundlagen des RSA-Algorithmus.

Ok, nachdem wir uns jetzt ganz grob ein Bild von der Funktionsweise des RSA-Algorithmus gemacht haben, geht es nun an die Installation der Tools, die wir für die Lösung benötigen.

SageMath

SageMath ist eine freie Software zur Lösung von mathematischen Problemen. Sie ist für Linux, macOS und Windows vefügbar. SageMath wurde in seiner ersten Version 2005 von einem Mathematiker an der University of Washington veröffentlicht. SAGE, wie man es heute auch noch kennt, steht dabei für Software for Algebra and Geometry Experimentation.

Was ist das Tolle an SageMath? Nun, es vereint viele Stärken von hochspezialisierten Computeralgebrasystemen und numerischen Bibliotheken. Es stehen zahlreiche Schnittstellen zu diversen bekannten Computeralgebrasystemen wie Mathematica und Maple zur Verfügung. Aber auch zu Python gibt es Schnittstellen, was für die Lösung dieser Challenge nicht ganz unerheblich sein wird.

[Dieser Abschnitt wurde zum Großteil von Wikipedia übernommen]

Zuvor musst du dir SageMath aber noch installieren. Dazu gehst du einfach auf die Seite des Herstellers und lädst dir die aktuellste Version von SageMath für dein System herunter. Dazu klickst du auf den Download Button

und gehst als Windows User auf die offizielle GitHub Release Seite.

Dort bekommst du ganz oben die aktuellste Version angezeigt. Hier lädst du dir entweder direkt die ausführbare .exe-Datei herunter und installierst diese oder du holst dir den Source Code und kompilierst selbst.

Ich habe dir hier eine kleine Bilderserie erstellt, die dich durch den Installationsdialog leiten soll:

Jetzt benötigst du noch die Möglichkeit, Jupyter Notebook zu öffnen. Wenn du Python installiert hast, wechselst du einfach in die CMD und gibst den Befehl

pip install jupyterlab

ein. Nach der Installation startest du SageMath und nach ein paar Sekunden Ladezeit sollte sich Jupyter öffnen und du solltest mit einem Klick auf New->SageMath 9.2 ein neues Notebook mit SageMath starten können.

Dort kannst du jetzt in das grüne Feld den Code eingeben, der durch SageMath ausgeführt werden soll.

Wir schreiben uns schnell ein kleines Hallo-Welt-Programm in der gewohnten Python-Syntax und klicken auf den Button Run.

Dann wird unser Code ausgeführt. Alternativ kannst du auch einfach in das Feld, das du ausführen möchtest, klicken und die Tastenkombination STRG+ENTER drücken. Das hat denselben Effekt.

Ich möchte dir nun nacheinander die Ansätze vorstellen, die ich gewählt habe, um die Challenge zu lösen. Die ersten beiden haben zwar nicht funktioniert, sind jedoch für zukünftige Lösungsfindungsprozesse sicherlich erwähnenswert.

Lösungsansatz 1: Bruteforce

Ein erster, zugegebenermaßen naiver Ansatz, besteht darin, die beiden Faktoren unseres $N$s zu berechnen, also die Primzahlen $p$ und $q$. Dabei geht man vom Grundgedanken her sehr ähnlich vor, wie wenn man z. B. $N=21$ in Primfaktoren zerlegen will. Wir starten mit der kleinsten Primzahl, nämlich $p=2$ und schauen, ob sich $N=21$ ohne Rest durch $2$ teilen lässt. Das ist hier nicht der Fall, weshalb wir den Wert von $p$ um $1$ erhöhen und es nun mit $p=3$ versuchen. $N=21$ ist ohne Rest durch $3$ teilbar, d. h. $p=3$ und $N=21$ sind nicht teilerfremd. Unsere Primzahl $q$ ist somit $21\div 3=7$ und wir haben unser $N$ faktorisiert. Mit diesem Wissen können wir nun einen Teil des geheimen Schlüssels über $\varphi(N)$ berechnen.

Wir starten also bei der ersten Primzahl $p=2$ und prüfen in einer while-Schleife, ob $p$ und $N$ teilerfremd sind, d. h. ihr größter gemeinsamer Teiler $1$ ist. Warum das? Nun, wenn $p$ und $N$ nicht teilerfremd sind, dann ist der größte gemeinsame Teiler von $N$ und $p$ unser $p$, da $N$ das Produkt zweier Primzahlen ist. Unser $N$ müssen wir dann nur noch durch den größten gemeinsame Teiler $p$ teilen und erhalten unser $q$. In jedem Schleifendurchlauf erhöhen wir den Wert von $p$ um $1$, um nacheinander alle möglichen Zahlen durchzugehen. Theoretisch müssten wir auch nur Primzahlen für $p$ einsetzen, doch das ist aufgrund der geringen Aussicht auf Erfolg viel zu viel Aufwand.

p = 2
while gcd(N, p) == 1:
    p += 1
print(p)

Wir lassen unser SageMath Programm einfach mal ein bisschen laufen, brechen aber nach ein paar Stunden ab, da die Challenge andernfalls auch ziemlich witzlos wäre. Kurzum: Bruteforce funktioniert hier nicht.

Lösungsansatz 2: GCD-Analyse

Der zweite naive Ansatz fußt auf der Idee, dass ein schlechter Zufallszahlengenerator bestimmte Primzahlen mit einer höheren Wahrscheinlichkeit erzeugt, d. h. die Verteilung ist nicht homogen. Sind die gewählten Primzahlen klein, dann erhöht sich die Wahrscheinlichkeit einer Dopplung. Warum ist das ein Problem? Angenommen, die Primzahl $p$ wird im Rahmen eines rsa_keygens() doppelt erzeugt. Dann hat man ggf. zwei öffentliche Schlüssel $$N_1, N_2$$ mit der Eigenschaft $$N_1=p\cdot q_1$$ und $$N_2=p\cdot q_2$$ Selbst wenn $q_1\neq q_2$ ist, kann man durch Berechnung von $$ggT(N_1, N_2)$$ sehr schnell (im Worst-Case $O(n)$) auf $p$ schließen und hat dann in $O(1)$ auch den zweiten Primfaktor. Die Berechnung des privaten Schlüssels $d$ (mit $d\cdot e\equiv 1\mod\varphi(n)$ aus dem öffentlichen Schlüssel ist dann kein Problem mehr.

Zu diesem Ansatz habe ich übrigens bereits ein YouTube-Video erstellt.

Wie kann man das in SageMath umsetzen? Ganz einfach! Wir starten eine Endlosschleife und erzeugen uns mit der rsa_keygen-Funktion des BND ein paar zufällige Schlüssel. Wenn $N$ und der generierte Schlüssel nicht teilerfremd sind, dann haben wir das gemeinsame $p$ gefunden und können nun wieder unser $q$ durch $N\div p$ berechnen.

while True:
   _, _, key = rsa_keygen()
   if gcd(N, key) != 1:
      print(gcd(N, key))
      break

Leider führt dieser Ansatz auch nach einer halben Stunde immer noch nicht zum Ziel. Das wird vermutlich nicht die Lösung sein.

Lösungsansatz 3: Analyse des Quellcodes

Kommen wir nun zu dem Ansatz, der mich letztendlich dazu befähigt hat, die Geheimbotschaft des BND zu entschlüsseln: Eine Analyse des Quellcodes. Gegeben sind zunächst einmal

e = 65537
N = 6217468290706613301603616005528100131798149079252059573007495519788267044819121069395602245916998799930775648250683389442966714804739613450381148533419461928485596870928541962694971680190134542148996706927335882462229500089986851509475109505459048676123650490359710027902270147490153424656466031170743546488513755685818385587367321466024945007514143310365200975587058348169982977145650693955667384644381937407101389719894018805206516292068437770414857823797915459660636056085645464594641983523102970037856987032167809541108080330794363602778053
c = 2403958089131679913280388000590444805870336793994842072765238389702465658316012937918168208480675977995643226078413644628259138097045221263367315251880579357261568983261767728244111191268740525499918021532930079880132241418326592156659066605343402785460641431875333212535673641255300099993314785755934870975128143213605376650490207877022044023372044186152484758267679564160572404559310873497815049934655680334251964614447413366867181827019553147813581000873134348328652679149309707292737376026040119503186190733157879722025259970612661722013152

Wir müssen irgendwie das c entschlüsseln.

Wie bereits angedeutet, liegt die Schwachstelle vermutlich in der Generierung der beiden Primzahlen, da der Rest der rsa_keygen Funktion des BND identisch zum Ablauf des RSA-Algorithmus ist.

def a(x, y):
   z = 1
   while True:
      if is_prime(x*z + y):
         return x*z + y
      z += 1

Die Primzahl wird aus drei Komponenten gebildet, nämlich einem x, einem y und einem z. Diese werden dann zu $$x\cdot z+y$$ zusammengesetzt und geprüft, ob eine Primzahl herauskommt. Falls das nicht der Fall ist, wird z inkrementiert.

Die Struktur der Primzahlen, die so gebildet werden ist zumindest schon einmal auffällig. Vor allem, weil sie beide auf demselben Geheimnis x beruhen:

x = 0xbb31781a2436fd6833597b61f91b94fba8cc5be702c7084de28625d96823102daf48dd84244fe41d180452a900388d1666ff59981f0912c6640977684c20bcfdcbf365dfcb68c0c5a9fd02576134a0e94ab9e20bbacffb4df5c9c27ae7f5022f6609aefeb9f5249387925ad13ce80a13

Es ist in den seltensten Fällen gut, etwas wiederzuverwenden. Besonders bei der Generierung von sicheren Zufallsschlüsseln. Einzig das y, das der Funktion bei der Generierung der beiden Primzahlen gegeben wird, scheint zufällig zu sein. Hier wird die in SageMath zur Verfügung gestellte Funktion random_prime genutzt, um eine zufällige Primzahl zwischen $2^{127}$ und $2^{128}$ zu würfeln.

random_prime(2^128, None, 2^127)

Um mit diesen Informationen jetzt weiterarbeiten zu können, benötigen wir einen mathematischen Satz:

Satz: Produkt von Kongruenzen modulo n

Gegeben seien $$a\equiv b\mod n$$ und $$c\equiv d\mod n$$ mit $a,b,c,d,n\in\mathbb{Z}$ und $n\in\mathbb{Z}\setminus\left\{0\right\}$. Dann gilt: $$ a\cdot c\equiv b\cdot d\mod n $$

Was hat das jetzt aber mit unserem Problem zu tun? Ganz einfach! Wie du mittlerweile weißt, sind die beiden Primzahlen $p$ und $q$ wie folgt aufgebaut: $$p=x\cdot z + y_1$$ und $$q=x\cdot z + y_2$$ Das können wir auch anders ausdrücken, denn $p=x\cdot z + y_1$ bedeutet nichts anderes als $$p\equiv y_1\mod x$$ und $q=x\cdot z + y_2$ ist $$q\equiv y_2\mod x$$ Dabei ist $z$ einfach nur eine ganze Zahl. Jetzt multiplizieren wir diese beiden Kongruenzen gemäß unserem Satz von vorhin miteinander und erhalten: $$p\cdot q \equiv y_1\cdot y_2\mod x$$ Das Produkt $p\cdot q$ kennen wir. Das ist einfach unser $N$ und $N$ wurde uns im Aufgabentext mitgegeben. Auch $x$ kennen wir, das ist nämlich der fixe Wert

x = 0xbb31781a2436fd6833597b61f91b94fba8cc5be702c7084de28625d96823102daf48dd84244fe41d180452a900388d1666ff59981f0912c6640977684c20bcfdcbf365dfcb68c0c5a9fd02576134a0e94ab9e20bbacffb4df5c9c27ae7f5022f6609aefeb9f5249387925ad13ce80a13

Dort steht also $$N=y_1\cdot y_2\mod x$$

Das einzige, was noch nicht bekannt ist, ist das Produkt $$y_1\cdot y_2$$ Die Berechnung des Produkts ist aber denkbar einfach, da wir nur $N\mod x$ rechnen müssen. Und das können wir, da beides gegeben ist. Das machen wir mithilfe der Funktion

y1y2 = Mod(N,x)

Heraus kommt der Wert

y1y2= 66125408326246957633291817320886184668904992358732144386954697003579825863329

Das ist unser Produkt $y_1\cdot y_2$. Vielleicht haben wir ja Glück und die Primfaktordatenbank factordb kennt die Primfaktoren, die hinter unserem Produkt stecken. Es ist doch schließlich nur eine $77-$stellige Zahl zu faktorisieren.

Und tatsächlich, wir erhalten:

y1 = 297985708820960177865320211443397151633
y2 = 221907985412741132065008213841199453713

Damit können wir jetzt unsere beiden Primzahlen und somit den privaten Schlüssel berechnen. Dazu suchen wir in einer Endlosschleife solange nach einem passenden Wert von $z$, bis der größte gemeinsame Teiler von $N$ und $x\cdot z+y_1$ ungleich $1$ ist, denn dann haben wir eine der beiden Primfaktoren gefunden, aus denen sich $N$ zusammensetzt. Das ist dann unser $p$. $q$ berechnen wir dann einfach, indem wir $N$ durch $p$ teilen. $z$ wird vor der While-Schleife natürlich mit $1$ vorinitialisiert.

z = 1
while True:
   if gcd(N, x * z + y1) != 1:
      p = x * z + y1
      q = N/p
      break
   z += 1

Dadurch kommen wir auf

p = 47901376485330203766695694757223244780763057718906397736458048266763760620415643262568804915903738303469051836278553655407660267194384192301417217870173323689716270949068215642937543630463210843857384149700377528787864613233870517459214640574858766383341142568486718713029
q = 129797278218314100529110914826024276180132156399617335802015356593811480390803678517928374610835936048109688846690274421104627820784782972687711171003050296449553766442636455290540440805126119705936137695962313303812278306827262047308254134074031312785612397826474715942657

$\varphi(N)$ wird dann durch die altbekannte Formel $$\varphi(N)=(p-1)\cdot (q-1)$$ berechnet.

phi_n = (p-1) * (q-1)

Zur Berechnung des multiplikativen Inversen $d$ in $\varphi(N)$ verwenden wir die SageMath Funktion

d = inverse_mod ( e , phi_n )

Das Ergebnis lautet also

d = 3467768107026547385652638598807828312519916128200871775823473514729397520320938286000540898957902515126869436661843385176446317748106368775680640284756421439369120076034163821389280861589483618706566925985548751264810334876318558725999720428964472073154825463083731032087297027362897230895721168475580090760348500981461541577170237929409970063856773739334065914786957420755971894585049822901273421798773066522116201358512033300269512677528703251374687234206800845284169662237729684442740976846102023058025865707418543160234080009299622311844865

Um die Nachricht $c$ zu decodieren, folgen wir dem BND-Beispiel und setzen alles in die Funktion decode ein.

decode(Mod(c, N)^d)

Unsere vollständige Lösung in SageMath, die du direkt ausführen kannst, sieht folgendermaßen aus:

x = 0xbb31781a2436fd6833597b61f91b94fba8cc5be702c7084de28625d96823102daf48dd84244fe41d180452a900388d1666ff59981f0912c6640977684c20bcfdcbf365dfcb68c0c5a9fd02576134a0e94ab9e20bbacffb4df5c9c27ae7f5022f6609aefeb9f5249387925ad13ce80a13

def decode(msg):
    return int(msg).to_bytes(length=len(hex(msg))//2-1, byteorder='big')

def rsa_keygen():
    def a(x, y):
        z = 1
        while True:
            if is_prime(x*z + y):
                return x*z + y
            z += 1

    p = a(x, random_prime(2^128, None, 2^127))
    q = a(x, random_prime(2^128, None, 2^127))
    
    N = p * q
    e = 65537
    
    d = inverse_mod(e, (p-1) * (q-1))
    
    return e, d, N

def rsa_crypt(m, k, n):
    return lift(Mod(m, n) ^ k)

e = 65537
N = 6217468290706613301603616005528100131798149079252059573007495519788267044819121069395602245916998799930775648250683389442966714804739613450381148533419461928485596870928541962694971680190134542148996706927335882462229500089986851509475109505459048676123650490359710027902270147490153424656466031170743546488513755685818385587367321466024945007514143310365200975587058348169982977145650693955667384644381937407101389719894018805206516292068437770414857823797915459660636056085645464594641983523102970037856987032167809541108080330794363602778053
c = 2403958089131679913280388000590444805870336793994842072765238389702465658316012937918168208480675977995643226078413644628259138097045221263367315251880579357261568983261767728244111191268740525499918021532930079880132241418326592156659066605343402785460641431875333212535673641255300099993314785755934870975128143213605376650490207877022044023372044186152484758267679564160572404559310873497815049934655680334251964614447413366867181827019553147813581000873134348328652679149309707292737376026040119503186190733157879722025259970612661722013152

y1 = 297985708820960177865320211443397151633

z = 1
while True:
    if gcd(N, x * z + y1) != 1:
        p = x * z + y1
        q = N/p
        break
    z += 1
    
phi_n = (p-1) * (q-1)
d = inverse_mod ( e , phi_n )
decode(Mod(c, N)^d)

Die Flagge

Wenn wir das Programm nun ausführen erhalten wir als Lösung die Flagge zum Erfolg.

HL{rsa_b4ckd00rz_mad3_s1mpl3}

RSA backdoors made simple! Das kann man wohl sagen :)

Und, war doch gar nicht so schwer, oder? Gut, der Schwierigkeitsgrad wurde vom BND mit medium angegeben und da das der niedrigste Schwierigkeitsgrad bei den Challenges ist, hoffe ich mal, dass es ab hier an anspruchsvoller wird. Kleiner Spoiler: Wird es!

Mathematisches Writeup

Ich habe zusätzlich zur vorgestellten Lösung noch ein Writeup erstellt, das mathematisch wesentlich anspruchsvoller ist und Beweise für die getroffenen Annahmen liefert. Bei Interesse kannst du es dir natürlich gerne hier herunterladen und durcharbeiten.

RSA Key Generation WRITEUP

Vorsicht! Dieses Writeup könnte Spuren von höherer Mathematik enthalten.

RSA_KEY_GENERATION_WRITEUP.pdf

Adobe Acrobat Dokument 237.6 KB

Download