qcg-k

5 minutes to read

We are provided with the Python source code to encrypt the 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())

We also have the output 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

And we also have a file called 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!

Source code analysis

The server uses DSA to sign the above quotes. After that, the flag is encrypted using the DSA private key $x$ as input for the AES key. We are given the signatures of the previous quotes, so the objective is to find the private key from the signatures and then decrypt the flag.

DSA implementation

The code for the DSA is almost correct (more information here):

It generates prime numbers $p$ and $q$ (such that $p = mq + 1$ for some integer $m$)
Then public values $g$ and $y$
And private values $k$ and $x$

In order to sign messages, it uses SHA256 as hash function and computes:

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

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

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

And the output is the pair $(r, s)$.

The security flaw

The problem here is how the nonces $k$ are generated:

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

Each nonce $k$ is the next output of the above PRNG implementation. It is a quintadecic congruential generator (QCG). So, for an initial state $s$, we have:

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

Then, $k_1$ will be

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

And so on.

Since we are given a total of $18$ signatures, we end up with $16$ unknown coefficients $a_i$, plus the initial state $s$ and the private key $x$. That is, we have a total of $18$ unknowns. Therefore, it is likely that we will find a solution to this problem.

Implementation

According to this paper, when the nonces $k$ follow an unknown recurrence relation (which is the case), it is possible to substitute each $k$ by

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

As a result, we will end up with a one-variable polynomial on $x$ (which is what we want to know). This can be achieved by eliminating all the coefficients $a_i$. The author of the paper proposes a recursive function named dpoly for that, which is implemented here. This is a performance improvement of the previous code:

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]

I use functools.cache to improve the performance of the recursive function dpoly.

Now, we can parse the information we have and find the roots of the polynomial. Once we have it, we will be able to decrypt the ciphertext:

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

If we run the script, we will find the flag:

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

The full script can be found in here: solve.py.