Writeup

Description

Its just RSA. I even used padding. Nothing can go wrong right?

Quellcode

# pip install pycryptodome
from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long
from Crypto.Util.Padding import pad

FLAG = b"KDCTF{e_equals_three_wasnt_that_good_of_an_idea}"
NUM_BITS = 1024

e = 0x3
p = getPrime(NUM_BITS)
q = getPrime(NUM_BITS)
n = p*q

ct = pow(bytes_to_long(pad(data_to_pad=FLAG, block_size=(NUM_BITS*2)//8, style='pkcs7')), e, n)

print("This ist just RSA; Just decrypt it")
print(f"{e = :x}")
print(f"{n = :x}")
print(f"{ct = :x}")

Notation

Im nachfolgenden werden folgende Mathematische Notationen verwendet:
$a \equiv b \pmod{n}$ bezeichnet eine Wikipedia: Kongruenz (Youtube: What does a ≡ b (mod n) mean? Basic Modular Arithmetic, Congruence ).
$a\in \lbrace x, y\rbrace$ bedeutet, dass a eine Zahl ist, die zwischen den beiden Zahlen x und y liegt.

Solution

Wenn man sich den Quellcode ansieht, dann erkennt man recht schnell, dass es sich um RSA handelt. Dabei werden folgende Parameter gewählt:
$e = 3$
$p, q \in \lbrace2^{1024}, 2^{1025}-1\rbrace$

Außerdem gilt $n =p*q$

Ein erste Ansatz

Unter normalen Umständen wäre die wahl von $e=3$ für Textbook-RSA gefärlich, da in Textbook-RSA kein Padding angewandt wird. Das liegt daran, weil dann eine Modulo-Reduktion nicht garantiert werden kann. Normalerweise gilt:
$CT \equiv PT^{e} \pmod{N}$
Falls $PT$ nun klein ist und $PT^{e} < N$ gilt, dann kommt die Modulo-Operation nicht zum Tragen und es gilt:
$CT = PT^{e}$
Um an den Plaintext zu kommen, kann man also die e-th Wurzel ziehen
$PT = \sqrt[e]{CT}$

Das gilt in diesem Fall aber leider nicht, da wir aus dem oberen Quelltext entnehmen können das eine Padding-Funktion verwendet wird. Damit wird der zu verschlüsselnde Text vor der Verschlüsselung auf eine gewünschte Länge gebracht (gepadde) und dann erst verschlüsselt. Dadurch können wir aber nicht die (in diesem Fall) dritte Wurzel ziehen, weil $CT = PT^{e}$ nicht erfüllt ist.

Die Schwachstelle

Der erste Ansatz hat also nicht funktioniert, weil eine Padding-Funktion zum Einsatz gekommen ist. Außerdem weist die Challengebeschreibung explizit auf das Padding hin:

Its just RSA. I even used padding. Nothing can go wrong right?

Aus dem Quelltext wissen wir, dass der pkcs7-Paddingstyle verwendet wird. Wikipedia weis dazu folgendes (Padding (cryptography):PKCS#5 and PKCS#7):

The value of each added byte is the number of bytes that are added, i.e. N bytes, each of value N are added. The number of bytes added will depend on the block boundary to which the message needs to be extended.

Wenn die restlichen Bytes immer mit der Anzahl der gepaddeden Bytes aufgefüllt werden, dann bedeutet das aber auch, dass eine Nachricht nach der Padding-Funktion genau so aussieht wie nach der Padding-Funktion. Das bedeutet, dass die gleiche nachricht gepadded mit PKCS#7 immer gleich aussieht, weil kein random Padding verwendet wird. Randomness ist in der Cryptographie aber oft wichtig, so auch hier. Dass PKCS#7 ein konstantes Padding und kein zufälliges Padding ist führt hier dazu, dass JRSA für einen sogenannten Broadcast-Angriff anfällig ist.

Aus dem Wikipedia-Artikel zum RSA-Kryptosystem:

Die Wahl eines e kleiner als die Fermat-Zahl $F_4 = 216 + 1 = 65537$ kann zu Angriffsmöglichkeiten führen, etwa in Form des von Johan Håstad publizierten „Broadcast“-Angriffs, bei dem der Versand einer Nachricht an mehrere Empfänger zu einer Dechiffrierung über den chinesischen Restsatz führen kann.

Das trifft alles auf JRSA zu, da ein konstantes Padding verwendet wird und die Nachricht an mehrere Personen geschickt wird.

Johan Håstad's Broadcasting Attack

Aus SOLVING SIMULTANEOUS MODULAR EQUATIONS OF LOW DEGREE von Johan Håstad

Assume that 3 is chosen as the exponent and that alice wants to send the same message m to users U1, U2 and U3. She will compute and send $y_{i} \equiv m^3 \pmod{n_{i}}$ with i = 1,2,3. If someone gains access to $y_1$ , $y_2$ and $y_3$ then by using the fact that $n_1$, $n_2$ and $n_3$ will be relatively prime he can combine the messages by chinese remaindering to get $m^3 \pmod{n_1 * n_2 * n_3}$ and since $m3 < n_1 * n_2 * n_3$ the attacker can recover m.

Wir wissen also, dass wir mit Hilfe von drei Ciphertexten (wenn $e=3$ gilt) und dem chinesischen Restsatz $PT^3$ berechnen können. Sobald wir das haben, können wir die dritte Wurzel ziehen und haben den Plaintext gefunden.

Der chinesischen Restsatz

Mit Hilfe des chinesische Restsatz (englisch "Chinese remainder theorem" kurz CRT) ist es möglich sogenannte simultane Kongruenz zu finden. Vereinfacht gesagt versucht man folgendes Gleichungssystem zu lösen (Wikipedia: Chinesischer Restsatz):
$x \equiv a_{1} \pmod{n_{1}}$
$x \equiv a_{2} \pmod{n_{2}}$
$x \equiv a_{3} \pmod{n_{3}}$
...
$x \equiv a_{m} \pmod{n_{m}}$

Diesen Algorithmus verwenden wir um $PT^3 \pmod{n_1 * n_2 * n_3}$ zu finden.

Exploit

Der Nachfolgende Exploit verwendet SageMath, eine auf Python aufbauende Mathematiksoftware.

# pip install pwntools
import pwn
# pip install pycryptodome
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes

BLOCKSIZE = (2*1024)//8
e = 0x3

def main() -> int:
    # Wir erstellen uns drei Listen um die Modulie (N) und die Residuen (CT) zu sammeln
    modulie = []
    residues = []
    
    # Wir bauen drei verbindungen zum Service auf und fügen den Modulus n und den Ciphertext ct den listen hinzu
    for _ in range(e):
        # Verbindungsaufbau zum bereitgestellten Sourcecodefile
        connection = pwn.process(["python", "main.py"])
        
        # Empfangen der Werte
        connection.recvuntil(b"n = ")
        n = int(connection.recvline().decode().strip(), 16)
        connection.recvuntil(b"ct = ")
        ct = int(connection.recvline().decode().strip(), 16)
        
        # Verbindungsabbau
        connection.close()
        
        # Hinzufügen zu den Listen
        modulie.append(n)
        residues.append(ct)
    
    # Hier wird die in Sagemath verfügbare CRT (chinese remainder theorem) Funktion aufgerufen
    result = crt(residues, modulie)
    # Anschließend müssen wir noch die dritte Wurzel ziehen
    # > result.nth_root(e)
    # dann den Zahlenwert zu Bytes konvertieren
    # > long_to_bytes(result.nth_root(e))
    # und das padding richtig entfernen
    # > unpad(long_to_bytes(result.nth_root(e)), BLOCKSIZE)
    flag = unpad(long_to_bytes(result.nth_root(e)), BLOCKSIZE).decode()
    pwn.log.success(f"{flag = }")

    return 0


if __name__ == "__main__":
    main()

MarkusOstermayer/JRSA_Writeup.md

Select an option

No results found