Der BND hat mal wieder einen öffentlichen Einstellungstest, dem wir uns erfreuen dürfen. Ideal, um sich mal etwas in CTF-Writeups zu probieren!

Aus der Kategorie Cryptography schauen wir uns mal die (einzige) Challenge an: Analysieren einer Backdoor in einem RSA-Schlüsselerzeugungsalgorithmus.

Folgender Code wurde uns bereitgestellt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
### Excerpt 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')

### Excerpt 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)

(wer kein SageMath installiert hat, kann diese Online-Version verwenden)

Zu dem Code haben wir folgende Zahlen enthalten, die wir entschlüsseln sollen:

e = 65537
N = 6217468290706613301603616005528100131798149079252059573007495519788267044819121069395602245916998799930775648250683389442966714804739613450381148533419461928485596870928541962694971680190134542148996706927335882462229500089986851509475109505459048676123650490359710027902270147490153424656466031170743546488513755685818385587367321466024945007514143310365200975587058348169982977145650693955667384644381937407101389719894018805206516292068437770414857823797915459660636056085645464594641983523102970037856987032167809541108080330794363602778053
c = 2403958089131679913280388000590444805870336793994842072765238389702465658316012937918168208480675977995643226078413644628259138097045221263367315251880579357261568983261767728244111191268740525499918021532930079880132241418326592156659066605343402785460641431875333212535673641255300099993314785755934870975128143213605376650490207877022044023372044186152484758267679564160572404559310873497815049934655680334251964614447413366867181827019553147813581000873134348328652679149309707292737376026040119503186190733157879722025259970612661722013152

Hierbei ist c ein Ciphertext und (e, N) der öffentliche Schlüssel.

Lösung

Die Backdoor soll in rsa_keygen sein. Schauen wir noch mal bei Wikipedia nach RSA.

Soweit sieht das alles identisch mit dem Standard-RSA-Vorgehen aus, bis auf diese Funktion a und der offenbar willkürlich gewählten Konstante x.

Um die gegebene Nachricht c zu entschlüsseln, brauchen wir das Inverse d (mod phi(N)).
Dieses wird mit inverse_mod(e, (p-1) * (q-1)) berechnet. (p-1) * (q-1) ist hierbei phi(N), die Eulersche Phi-Funktion von N. phi(N) lässt sich einfach berechnen, wenn man die Primzahlfaktorzerlegung (PFZ) von N hat.
Unser N ist nun das Produkt der Primzahlen p und q, die wir nicht kennen.

Wenn wir also p und q hätten, könnten wir daraus (p-1) * (q-1) und somit d berechnen.
Da die PFZ einer Zahl eindeutig ist, müssten wir “nur” N faktorisieren, um zur Lösung zu kommen. Aus wie vielen Bits besteht denn N?

>>> import math
>>> math.log2(N)
1806.4432827685064

Uff, 1800 Bit! Bei der Faktorisierungs-Rekordliste auf Wikipedia liegt der Rekord aktuell bei 829 Bit und benötigte 2700 CPU-Jahre.

Damit kommen wir hier nicht weiter.

p und q fallen aus der Funktion a(x, y) heraus. Schauen wir uns mal die Funktion a an:

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

y ist hierbei eine 127- bis 128-Bit-Primzahl.
Die Funktion addiert so lange x hinzu, bis das Ergebnis wieder prim ist.
Es wird also zumindest eine “echte” Primzahl zurückgegeben.

Die zurückgegebene Primzahl hat aber eine interessante Eigenschaft:
Nimmt man sie modulo x, erhalten wir das ursprüngliche y, also (x*z + y) % x == y (wenn z eine ganze Zahl ist).

Wir schreiben für die ursprünglichen Primzahlen:

py = p (mod x)
qy = q (mod x)

py und qy sind die Zahlen, die der entsprechende random_prime-Aufruf zurückgegeben hat.
Wenn wir diese beiden Zahlen hätten, könnten wir daraus p und q, damit phi(N) und den privaten Schlüsselexponenten d berechnen.
Wir wären also damit am Ziel.

Wir haben jetzt:

N = p * q

Mit dem Wissen über p und q bzw. py und qy und modularer Arithmetik können wir N % x wie folgt schreiben:

N (mod x) = (p * q) (mod x)
# =>
N (mod x) = (py (mod x)) * (qy (mod x)) (mod x)
# =>
N (mod x) = py * qy (mod x)

Wir kennen py und qy zwar nicht, aber dafür können wir leicht N % x berechnen. Machen wir das einfach mal:

>>> N % x
66125408326246957633291817320886184668904992358732144386954697003579825863329
# == py * qy (mod x)

Wir haben jetzt also py * qy. Vielleicht können wir das faktorisieren?

>>> math.log2(N % x)
255.19173993737596

255 Bit, das sieht vielversprechend aus. Das ist sogar so klein, dass wir diese Zahl mit SageMath oder Pari/GP faktorisieren können. Letzteres läuft auch im Browser mit WebAssembly:

? factor(N % x)
%1 = [
    221907985412741132065008213841199453713, 1;
    297985708820960177865320211443397151633, 1
]

Das hat ein paar Minuten gedauert, aber es funktioniert! Wir haben jetzt also py/qy und können die einfach in den beretgestellten SageMath-Code einsetzen:

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, 221907985412741132065008213841199453713) # py eingesetzt
    q = a(x, 297985708820960177865320211443397151633) # qy eingesetzt

    N = p * q
    e = 65537

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

    return e, d, N

e, d, N = rsa_keygen()
# d ist
# 3467768107026547385652638598807828312519916128200871775823473514729397520320938286000540898957902515126869436661843385176446317748106368775680640284756421439369120076034163821389280861589483618706566925985548751264810334876318558725999720428964472073154825463083731032087297027362897230895721168475580090760348500981461541577170237929409970063856773739334065914786957420755971894585049822901273421798773066522116201358512033300269512677528703251374687234206800845284169662237729684442740976846102023058025865707418543160234080009299622311844865

Jetzt können wir die ursprüngliche Nachricht entschlüsseln:

>>> decode(rsa_crypt(c, d, N))
b'HL{rsa_b4ckd00rz_mad3_s1mpl3}'

Fertig!

Takeaway und Weiterführendes

Nach Außen hin sah der generierte Schlüssel sicher aus. Kennt der Angreifer aber die (ggf. sogar geheime) Konstante x, kann er das Kryptosystem mit einem Desktoprechner brechen. Das x dient damit als Generalschlüssel für alle mit dem Verfahren erzeugten Schlüsselpaare.

In vielen Verfahren werden “Nothing-up-my-sleeve”-Zahlen verwendet. So kann man zeigen, dass man nicht mit einer geschickt gewählten Konstante versucht, eine Backdoor einzubauen (wie z. B. mit P und Q beim CSPRNG Dual_EC_DRBG).