Disclaimer: Im August 2026 fand die Qualifikation für das Finale von Deutschlands Bester Hacker statt, welches ich auf Platz 1 abschließen konnte. Nur zwei Teilnehmer waren in der Lage, alle Challenges zu lösen. Dieses Writeup wurde mit KI auf Basis meiner Notizen erstellt und kann Fehler enthalten, bei Fragen bitte direkt an mich wenden im DBH-Discord.
| Wettbewerb | Deutschlands Bester Hacker 2026 — Qualifikation |
| Kategorie | Crypto |
| Punkte | 50 |
| Angriffsklasse | RSA mit kleinem Exponenten / CoppersmithCoppersmith-AngriffVerfahren, das RSA bricht, wenn ein kleiner Teil der Nachricht oder des Schlüssels unbekannt ist. Stereotyped Message |
| Flag | DBH{KL31N3R_3XPON3NT_XXX_GR055ES_L3CK} |
Die Challenge
Gegeben war eine JSON-Datei mit einem RSA-Modulus, einem kleinen Exponenten und einem Chiffrat. Zusätzlich war die Struktur des Flags teilweise bekannt:
n = grosser RSA-Modulus
e = 3
c = RSA-Chiffrat
prefix = DBH{KL31N3R_3XPON3NT_
suffix = _GR055ES_L3CK}
unknown_length = 64Das Flag hat also die Form:
DBH{KL31N3R_3XPON3NT_<64 unbekannte Zeichen>_GR055ES_L3CK}Der Untertitel der Challenge — „e = 3 reicht doch, oder?“ — sagt schon, worum es geht.
Aufklärung
Ein kleiner Exponent ist bei RSA nicht automatisch kaputt. Problematisch wird es, wenn die Nachricht nicht sicher gepaddet wird und ein großer Teil der Nachricht bekannt ist. Hier ist beides der Fall: RSA verschlüsseltEncryptionWandelt Klartext mithilfe eines Schlüssels in nicht lesbaren Geheimtext um. roh
c = m^3 mod nund von m sind nur 64 Bytes unbekannt.
Die Schwachstelle
Die Nachricht ist ein Byte-String der Form prefix || unknown || suffix. Interpretiert man
sie als Big-Endian-Integer, gilt:
m = P * 256^(64 + len(suffix)) + x * 256^len(suffix) + Smit P = Integerdarstellung des Präfix, S = Integerdarstellung des Suffix, x = die 64
unbekannten Bytes. Damit wird aus RSA ein Polynom mit kleiner Nullstelle:
(P * 256^(64 + len(suffix)) + x * 256^len(suffix) + S)^3 - c == 0 mod nGesucht ist also x mit 0 <= x < 256^64 — genau der Fall, für den Coppersmiths Methode
gebaut ist.
Der Angriff
Für den Small-Root-Schritt ist SageMath praktisch, weil small_roots() bereits eine
Implementierung für Coppersmith-artige Angriffe mitbringt:
import json
with open('challenge.json', 'r') as f:
data = json.load(f)
n = Integer(data['n'], 16)
e = Integer(data['e'])
c = Integer(data['c'], 16)
prefix = data['hint']['prefix'].encode()
suffix = data['hint']['suffix'].encode()
unknown_len = Integer(data['hint']['unknown_length'])
P = Integer.from_bytes(prefix, 'big')
S = Integer.from_bytes(suffix, 'big')
B = 256 ** len(suffix)
A = P * 256 ** (unknown_len + len(suffix)) + S
X = 256 ** unknown_len
R.<x> = PolynomialRing(Zmod(n))
f = (A + x * B) ** e - c
roots = f.monic().small_roots(X=X, beta=1, epsilon=0.03)
print(roots)Die gefundene Nullstelle ist der unbekannte Mittelteil als Integer und wird zurück in 64 Bytes gewandelt:
x0 = Integer(roots[0])
unknown = int(x0).to_bytes(int(unknown_len), 'big')
flag = prefix + unknown + suffix
print(flag.decode())Anschließend die Gegenprobe ohne jedes Geheimwissen:
m = Integer.from_bytes(flag, 'big')
assert pow(m, e, n) == cDiese Prüfung ist wichtig: sie zeigt, dass nicht nur ein plausibler Text gefunden wurde,
sondern exakt die RSA-Nachricht, die zu c gehört.
Die Flag
DBH{KL31N3R_3XPON3NT_XXX_GR055ES_L3CK}Was ich mitnehme
Der Angriff funktioniert, weil mehrere ungünstige Bedingungen zusammenkommen:
- sehr kleiner Exponent
e = 3 - keine sichere Padding-Struktur wie OAEP
- großer bekannter Nachrichtenanteil
- begrenzte Länge des unbekannten Teils
Fällt auch nur eine dieser Bedingungen weg, trägt der Angriff nicht mehr. In der Praxis heißt das: RSA nie roh verwenden — für Verschlüsselung ist RSA-OAEP der übliche sichere Ansatz.