KlášteRSA - Autorské řešení úlohy

Solution #

Při pohledu na zdrojový kód si můžeme všimnout několika zajímavostí:

• naprosto stejnou zprávu šifrujeme pomocí různých klíčů
• hodnota e (ve zdrojovém souboru prayer_level) je vždy 521, což není moc obvyklá hodnota, ale oproti běžně používáné hodnotě 65537 je poměrně nízká
• dle zadání má vlajka 38 znaků, a ze zdrojového kódu je patrné, že neprobíhá žádný padding. Velikost plaintextu tedy bude zhruba 304 bitů

A znalý kryptograf by již měl vidět, že se jedná o problém řešitelný pomocí už klasické metody využívající Čínskou větu o zbytcích (CRT).

Čínská věta o zbytcích

Uvažujme soustavu lineárních kongruencí: $$\begin{align*} x \equiv &\ c_1 \pmod{n_1}, \ x \equiv &\ c_2 \pmod{n_2}, \\vdots &\ \ x \equiv &\ c_E \pmod{n_E},\end{align*}$$ kde $n_1,n_2,\dots,n_E \geq 2$ jsou jsou navzájem nesoudělná pro každá $i\neq j$.

Řešení této soustavy vždy existuje a umíme jej najít. Všechna řešení jsou kongruentní modulo $M$, kde $$M = \prod_{i=1}^Ec_i$$.

Důkazem věty se zde zabývat nebudeme (zájemci si jistě dohledají ve své oblíbené učebnici teorie čísel), je však pro nás důležité vědět, že nejen že řešení existuje, ale umíme jej najít v rozumném čase ($\mathcal O(M)$)

Útočník si může vyžádat od serveru více různých šifrovaných zpráv, přičemž každá z nich je zašifrována stejnou zprávou pomocí rozdílných RSA modulů. Tím, že získáme alespoň e (t.j. 521) takových zpráv, můžeme využít fakt, že pro každou zašifrovanou zprávu platí: $$m^e \equiv c_i \pmod{n_i}$$.

Pomocí Čínské věty o zbytcích pak získáme číslo, které splňuje: $M=m^e$

Za předpokladu, že $m^e$ je menší než součin všech modulů (což platí díky dostatečně malé velikosti zprávy), můžeme jednoduše vypočítat $\sqrt[521]{M}$ a získat tak původní zprávu $m$.

V praxi však ke správnému řešení můžeme dojít i s menším množstvím kongruencí (a tedy zpráv), což můžeme snadno ověřit díky naší znalosti flag formátu, hledání tak můžeme o něco urychlit.

Exploit script #

import requests
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from sympy.ntheory.modular import crt

cs = []
ns = []

for i in range(521):
    print(i)
    decoded = requests.get("http://localhost:1337/blessing").json()
    c = int(decoded["blessing"], 16)
    n = int(decoded["harmony"], 16)
    e = int(decoded["sacred_number"], 16)

    ns.append(n)
    cs.append(c)

    m_pow_e = crt(ns, cs)
    m = iroot(int(m_pow_e[0]), e)[0]
    plaintext = long_to_bytes(m)

    if b"FGSL" in long_to_bytes(m):
        print(long_to_bytes(m))
        break