<- CORCTF

qcg-k

5 minutos de lectura

Se nos proporciona el código fuente en Python para cifrar la flag:

from random import randint
from Crypto.Util.number import inverse, bytes_to_long
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha256
import os

class PRNG:
    def __init__(self, mod):
        self.coeffs = [randint(1,mod) for _ in range(16)]
        self.mod = mod
        self.state = randint(1, mod)
    def next(self):
        self.state = sum(coeff * self.state**i for i,coeff in enumerate(self.coeffs)) % self.mod
        return self.state

q = 77897050769654696452572824710099972349639759246855689360228775736949644730457
p = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634183738667876030053003528149973545862146652611656961993385485831857222177076627368030677  
g = 8986665761954289500303442250714013257267958541522625625218561169199279419042595142610100040988087502082590727136475698540201993746428470373168993292913039320311763660217801850784878564935450880018874371587199649965685742134884651107493812479234148805689664214460255588413695390568080942032263992785493208738282307168575867379095610792294961396770216272833435684440954774251862518243249608047971545524864083813237641522093309769070100469565960964654622352499351408269623653746705149014123772757153278180752939277436109738789404154406479625797746665884100327134640664657032784940498017583213619767216652249367376800156

x = randint(1, q - 1)
y = pow(g,x,p)

kPRNG = PRNG(q)

def hsh(msg):
    return bytes_to_long(sha256(msg).digest())

def sign(msg):
    k = kPRNG.next()
    r = pow(g,k,p) % q
    s = (inverse(k, q) * (hsh(msg) + x*r)) % q
    if r == 0 or s == 0:
        return sign(msg)
    return r,s

with open("quotes.txt") as f:
    for quote in f:
        quote = quote.strip().encode()
        print(sign(quote))

key = sha256(str(x).encode()).digest()
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = open("flag.txt", "rb").read()
enc = cipher.encrypt(pad(flag,16))
print(enc.hex())
print(iv.hex())

También tenemos la salida qcgk_out.txt:

(18538567231722685945797090783936295118823595361506914721726634489965878792092, 9534500652632125634641876250092080183022575098656254339710484313801309472341)
(40044335674682415732639880026587948909196723753135121574060780874843579410557, 76755192691649792821295616424843334044612875347700299959188607327429110569741)  
(2354723963412226581169794277209672044088677508387496233761833060810264808231, 5551814301579042319401049594982676781614581827314369121943697647500899474585)
(14093923028246393297069042751983458176109781481046947646639026276847250726706, 5966017748063940832254730003836052881852251005352472060682280217053032195300)
(4014765488361029504603813500011952364985952600385248394691633390934121671638, 43702163923447954902581376740902009790945099624966271668886069327224057509197)
(33320362558911096263218285582752153454035706900512140217061134612279280605530, 55621822855942828900530370711412325355228953261548439732516443961531185672785)
(25160615972298537371673601850415528212191506841772438416323832922823918992227, 47838286666519542737986196417534649038701562822516156929692625820411124736822)
(67721441286907686310143244051075422954425087819878628785916761447408774584610, 67982686215688928646989388928814155324855633145598362679304573976166564738098)
(24661179247566534781699006791985721659287829094731174001544218540965635242424, 41011417955752087480149446286867692645860955541134878271531648518816810638373)
(47825677733740373715626546697162261646224585180632889561648544717783870069773, 47397061912116791076055610725360612986492233424852629013617141397873508135961)
(56214875726675855773849633789547793285928866507786116870553159594456424132929, 73787143038855400899435998884004416911690611257527586287850912648034316749374)
(66090293157110548354823579640523712717496617810652122101402179294476896865163, 26048601001607455761235719651296992553246571102644863095804242708580979881608)
(46910704853715119271638553031970231889568517262792480450420926279068345986271, 39543512796296412664033164341732081379003276801490586137252212511203868006554)
(43034089872458231114272691108307410824083767874322135932939953165817406850602, 70889206719142775720065482040705094267113253214859027608980507917778769957802)
(49709542769456331944923513326975032411263533977242095848438289028572643203475, 14819725718698091260168544912180055472396277986076910924440970372186252693523)
(17764504015651672846684285092864690099217722428895504734442699959347212362037, 30779217842704892252035433779617527921162461631960501087609900998923135679130)
(21272382615812322008384551095993338983724664215044648211287586348066520680680, 76234915224008564080339245480384629164844938101293210735761572964852490657975)
(44328884017702092473987937364445697471806015364781147510625199931394522728808, 33906721853286250970929437613890497457945785213637484981974847684609039591314)
5c9d830f422288b4a9a37dc6b1cf68bfb7ee1acadb428d9fee6b17a8b8cbc5e7d871314bf090e4faa083d68162414b72992a60119ceb9c67f928d224f44f14c5
bf549fa30bef66988268f357e1014c8d

Y también tenemos un archivo llamado quotes.txt:

Platypuses are the only mammals to lay eggs.
Look at me, I'm the captain now.
A person who thinks all the time has nothing to think about except thoughts.
Happy Birthday Grimace!
I'm sorry, but I cannot fulfill your request. As an AI language model,
The industrial revolution and its consequences have been a disaster for the human race.
erb-Ferb atin-Lerb
I don't have friends, I got family.
Fun isn't something one considers when balancing the universe.
The deprecated memory allocation hooks __malloc_hook, __realloc_hook, __memalign_hook and __free_hook are now removed from the API.  
First learn stand
Then learn fly
Pride is not the opposite of shame, but its source.
It is what it is
There are only two ways to live your life. One is as though nothing is a miracle. The other is as though everything is a miracle.
We do a little trolling
Who are you talking to right now? Who is it you think you see?
You can't handle the truth!

Análisis del código fuente

El servidor usa DSA para firmar las citas anteriores. Después de eso, la flag se cifra utilizando la clave privada del DSA $x$ como entrada para la clave de AES. Se nos dan las firmas de las citas anteriores, por lo que el objetivo es encontrar la clave privada a partir de las firmas y luego descifrar la flag.

Implementación del DSA

El código para el DSA es casi correcto (más información aquí):

  • Genera números primos $p$ y $q$ (tales que $p = mq + 1$ para cierto entero $m$)
  • Luego valores públicos $g$ e $y$
  • Y valores privados $k$ y $x$

Para firmar mensajes, utiliza SHA256 como función de hash y calcula lo siguiente:

$$ r = (g^k \mod{p}) \mod{q} $$

$$ h = \mathrm{SHA256}{(m)} $$

$$ s = k^{-1} \cdot \left(h + x \cdot r\right) \mod{q} $$

Y la firma es el par $(r, s)$.

El problema de seguridad

El problema aquí es cómo se generan los nonces $k$:

class PRNG:
    def __init__(self, mod):
        self.coeffs = [randint(1,mod) for _ in range(16)]
        self.mod = mod
        self.state = randint(1, mod)
    def next(self):
        self.state = sum(coeff * self.state**i for i,coeff in enumerate(self.coeffs)) % self.mod  
        return self.state

Cada nonce $k$ es la siguiente salida del PRNG anterior. Se trata de un generador de congruencial quintadécico (QCG). Entonces, para un estado inicial $s$, tenemos:

$$ k_0 = a_0 + a_1 s + a_2 s^2 + \dots + a_{15} s^{15} \mod{q} $$

Luego, $k_1$ será

$$ k_1 = a_0 + a_1 k_0 + a_2 k_0^2 + \dots + a_{15} k_0^{15} \mod{q} $$

Y así sucesivamente.

Como se nos da un total de $18$ firmas, terminamos con $16$ coeficientes desconocidos $a_i$, más el estado inicial $s$ y la clave privada $x$. Es decir, tenemos un total de $18$ incógnitas. Por lo tanto, es probable que encontremos una solución a este problema.

Implementación

De acuerdo con este paper, Cuando los nonces $k$ siguen una relación de recurrencia desconocida (que es el caso), es posible sustituir cada $k$ por

$$ k = s^{-1} \cdot \left(h + x \cdot r\right) \mod{q} $$

Como resultado, terminaremos con un polinomio de una variable en $x$ (que es lo que queremos hallar). Esto se puede lograr eliminando todos los coeficientes $a_i$. El autor del paper propone una función recursiva llamada dpoly para eso, que está implementada aquí. Esta es una mejora de rendimiento del código anterior:

from functools import cache

from sage.all import GF, PolynomialRing


def k_ij(i, j):
    return x * (r[i] / s[i] - r[j] / s[j]) + h[i] / s[i] - h[j] / s[j]


@cache
def dpoly(n, i, j):
    if i == 0:
        return k_ij(j + 1, j + 2) ** 2 - k_ij(j + 2, j + 3) * k_ij(j, j + 1)

    left = dpoly(n, i - 1, j)
    for m in range(1, i + 2):
        left *= k_ij(j + m, j + i + 2)

    right = dpoly(n, i - 1, j + 1)
    for m in range(1, i + 2):
        right *= k_ij(j, j + m)

    return left - right


q = 77897050769654696452572824710099972349639759246855689360228775736949644730457  
Fq = GF(q)

x = PolynomialRing(Fq, 'x').gens()[0]

Utilizo functools.cache para mejorar el rendimiento de la función recursiva dpoly.

Ahora, podemos analizar la información que tenemos y encontrar las raíces del polinomio. Una vez que las tengamos, podremos descifrar el texto cifrado:

from ast import literal_eval
from hashlib import sha256

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad


h, r, s = [], [], []

with open('quotes.txt', 'rb') as quotes, open('qcgk_out.txt') as out:
    for m, r_s in zip(quotes, out):
        h.append(Fq(int(sha256(m.strip()).hexdigest(), 16)))
        r.append(Fq(literal_eval(r_s)[0]))
        s.append(Fq(literal_eval(r_s)[1]))

    ct = bytes.fromhex(out.readline())
    iv = bytes.fromhex(out.readline())

N = 18
pol = dpoly(N - 4, N - 4, 0)
secret = pol.roots()[0][0]

key = sha256(str(secret).encode()).digest()
print(unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(ct), AES.block_size).decode())

Flag

Si ejecutamos el script, encontraremos la flag:

$ python3 solve_QCG-k.py
corctf{wh4t_d0_y0u_m34n_1_C4Nt_jU5t_4dd_m0re_c03FFs?!??!?!????}

El script completo se puede encontrar aquí: solve.py.