Easy DSA: Lovely Little Lane

4 minutes to read

We are given the Python source code used to encrypt the flag:

from Crypto.Util.Padding import pad
from Crypto.Util.number import isPrime, getPrime, long_to_bytes
from Crypto.Cipher import AES
from hashlib import sha256
from random import randrange

def gen_key():
    p = 0
    while not isPrime(p):
        q = getPrime(300)
        p = 2*q + 1

    g = randrange(2, p)**2 % p
    x = randrange(2, q)
    y = pow(g, x, p)
    return p, q, g, x, y

def H(msg):
    return int.from_bytes(sha256(msg).digest(), 'big')

def sign(m):
    k = randrange(2, q >> 100)
    r = pow(g, k, p) % q
    s = (H(m) + x*r) * pow(k, -1, q) % q
    return r, s

def verify(m, r, s):
    assert 0 < r < q and 0 < s < q
    u = pow(s, -1, q)
    v = pow(g, H(m) * u, p) * pow(y, r * u, p) % p % q
    return v == r

flag = b"ictf{REDACTED}"
p, q, g, x, y = gen_key()

ms = b"jctf{Puzzler_is_the_best_chall_author}", b"jctf{Wanna_see_you_trying_to_submit_that_flag}", b"jctf{D54_15_345y_4f73r_411}", b"jctf{n0_1d34}", b"jctf{s0_m4ny_fr33_s1g5}"  
sigs = [sign(m) for m in ms]
assert all(verify(m, *sig) for m, sig in zip(ms, sigs))

aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
c = aes.encrypt(pad(flag, 16)).hex()

print(f'{p = }\n{g = }\n{y = }\n{ms = }\n{sigs = }\n{c = }')

And the output of the above script:

p = 4069937001870309288805965623396322384563730096882100588604666667233844487430163449354230919
g = 761690225239056989296458587964224591636809672476899126096331568501041989927462775870169890
y = 3856861197249284776013625513455404101895073264721385255129856925979499627575330256789520929
ms = (b'jctf{Puzzler_is_the_best_chall_author}', b'jctf{Wanna_see_you_trying_to_submit_that_flag}', b'jctf{D54_15_345y_4f73r_411}', b'jctf{n0_1d34}', b'jctf{s0_m4ny_fr33_s1g5}')
sigs = [(1234430664392743787630257388031047316821997031330839787382441766516744619882845371726433479, 883478467757628095229081460742191979896216430167019471897971078418352645136586828118018700), (1748400176200042123708476874280571916114895811026970462791925292863342243844069518123907016, 393625149677662932332357187873198135230656251678930039756678249504827719418549587156831030), (1389075138169306899495492856357153773415775002452775291705585460821530722304723598929266862, 781915465391184160994575003284903630852258678840377022165602064887288442417369465674198668), (1958157337340217176576113705810981137211234690293204330010317484823551198693733909083899867, 10566518658730065027243448201854036747278182399783616747373412863391884773803402507423867), (1502061706004805503203955848190130172580944756057566524292292418223793543600715005832239986, 1945316551688445103622226632281070969908748063265509793926846008296447432175736848474050566)]  
c = '3c5f1079e0d30abf35d059ffea0ac6b460c1cd372d5622ede50df037f733015f'

Source code analysis

The server implements a Digital Signature Algorithm (DSA), and uses a private parameter x as a key to encrypt the flag with AES:

aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)  
c = aes.encrypt(pad(flag, 16)).hex()

Therefore, we will need to find x from the DSA signatures.

DSA implementation

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

It generates prime numbers $p$ and $q$ (such that $p = 2q + 1$)
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{q} $$

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

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

The security flaw

The problem here is that the server generates nonces $k$ in a weird way:

    k = randrange(2, q >> 100)

Since $q$ is a 300-bit prime number and $k$ nonces are 200-bit numbers, we can use a lattice-based attack and LLL to solve the Hidden Number Problem. I found this technique in this website, which points to section 4 of this paper.

The procedure is to define a lattice spanned by the columns of this matrix $M$:

$$ M = \begin{pmatrix} q & 0 & 0 & 0 & 0 & r_1 s_1^{-1} & h_1 s_1^{-1} \\ 0 & q & 0 & 0 & 0 & r_2 s_2^{-1} & h_2 s_2^{-1} \\ 0 & 0 & q & 0 & 0 & r_3 s_3^{-1} & h_3 s_3^{-1} \\ 0 & 0 & 0 & q & 0 & r_4 s_4^{-1} & h_4 s_4^{-1} \\ 0 & 0 & 0 & 0 & q & r_5 s_5^{-1} & h_5 s_5^{-1} \\ 0 & 0 & 0 & 0 & 0 & X / q & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & q \\ \end{pmatrix} $$

Where $h_i = \mathrm{SHA256}{(m_i)}$ and $X$ is an upper-bound for the nonces $k$ (for instance, $2^{200}$).

Once we apply LLL, we will find a vector in the reduced lattice basis that contains all the nonces $k$, so we will be able to find the private key and find the flag.

Flag

If we reproduce the above calculations in Python, we will find x and therefore we can decrypt the AES ciphertext to find the flag:

$ python3 solve.py
ictf{W34k_n0nc3,_345y_ch4LLL}

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