Easy DSA: Elated once
8 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 H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
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 gen_nonces():
a = randrange(2, q)
b = randrange(2, q)
k = 0
while 1:
k = (a*k + b) % q
yield k
def sign(m):
k = next(nonces)
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()
nonces = gen_nonces()
ms = b'jctf{f4k3_f!4g_7h3_f1r57}', b'jctf{f4k3_f!4g_7h3_53c0nd}', b'jctf{f4k3_f!4g_7h3_7h1rd}'
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 = 2418412161587048618911490514475907960012278945420538846001723790372197085472346428648374919
g = 2064228484934656182476030526252687681657855524182393204180796682805474532697783234019522938
y = 894978350337386203714743526086207453830598544444498469056621877210054843512079994718204008
ms = (b'jctf{f4k3_f!4g_7h3_f1r57}', b'jctf{f4k3_f!4g_7h3_53c0nd}', b'jctf{f4k3_f!4g_7h3_7h1rd}')
sigs = [(942248975683680318753150798164591935683431794761521087381578596465811760180113404300321118, 342812233069446068155480770741216218496427109436740920046532418711028275917065308430519273), (102001584770818641493080724572692756389337862746330230381962190229233871531362789283064508, 482354383195776716833349859090850583242412163611214463003633128285976770958780493119871011), (187377473811032611481162139226326301755478417757273410261128557099065854699728324076093828, 1171449558094661271371246349171199670184901923277811515634255397001853557943612820379515494)]
c = '4c76bd5dc8d57984526385d696fa0665e4c18f60b8593d42897aff792ec893d826c253646b9cb6875c91f2dfa25eedd4cc2936a3fe3174aa5b677a30ef965a7aa5dbf12c0c8234a73d0c5db5aea76644'
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 uses a Linear Congruential Generator (LCG) to generate the nonces $k$ and we are given three different messages and signatures and the seed for the LCG.
Therefore, we have
$$ \begin{cases} s_1 k_1 - r_1 x = h_1 \mod{q} \\ s_2 k_2 - r_2 x = h_2 \mod{q} \\ s_3 k_3 - r_3 x = h_3 \mod{q} \\ \end{cases} $$
Where $h_i = \mathrm{SHA256}{(m_i)}$. And the nonces are:
$$ \begin{cases} k_0 & = 0 \\ k_1 & = a k_0 + b = b & \mod{q} \\ k_2 & = a k_1 + b = ab + b & \mod{q} \\ k_3 & = a k_2 + b = a^2 b + ab + b & \mod{q} \\ \end{cases} $$
If we add these relations to the previous system of equations, we get a system of 3 modular equations on 3 unknowns ($x$, $a$, $b$):
$$ \begin{cases} s_1 b & - r_1 x = h_1 \mod{q} \\ s_2 (ab + b) & - r_2 x = h_2 \mod{q} \\ s_3 (a^2 b + ab + b) & - r_3 x = h_3 \mod{q} \\ \end{cases} $$
Notice that we are working modulo $q$, which is a prime number, so all operations are within $\mathbb{F}_q$. Since this is a field, we can “add, substract, multiply and divide”. Therefore, we can solve the system of equations using symbolic math forgetting about the modulo and then apply the operations modulo $q$.
Using Maxima, we get these expressions:
$ maxima
Maxima 5.46.0 https://maxima.sourceforge.io
usando Lisp SBCL 2.3.0
Distribuido bajo la Licencia Pública GNU. Consulte el fichero de DERECHO DE REPRODUCCIÓN.
Dedicado a la memoria de William Schelter.
La función bug_report() proporciona informes de defectos.
(%i1) solve([s1 * b - r1 * x = h1, s2 * (a * b + b) - r2 * x = h2, s3 * (a^2 * b + a * b + b) - r3 * x = h3], [x, a, b]);
2 2 2 2 2
(%o1) [[x = - (s1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ (2 h1 r1 s2 + ((- h1 r2) - h2 r1) s1 s2 + 2 h2 r2 s1 ) s3
2 2 2 2 2
+ ((- h1 r3) - h3 r1) s1 s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2 2 2 2 2 2
- 2 r1 r3 s1 s2 ), a = - (sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 ) + (h1 r2 - h2 r1) s3
+ (h3 r1 - h1 r3) s2)/((2 h1 r2 - 2 h2 r1) s3),
2 2 2 2 2
b = - (r1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ ((h1 r1 r2 - h2 r1 ) s2 + (2 h2 r1 r2 - 2 h1 r2 ) s1) s3
2 2 2 2 2 2
+ (h1 r1 r3 - h3 r1 ) s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2 2 2
- 2 r1 r3 s1 s2 )], [x = (s1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2
2 2 2 2 2
- 3 h2 r1 ) s3 + (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 )
2 2
s2 + ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ ((- 2 h1 r1 s2 ) + (h1 r2 + h2 r1) s1 s2 - 2 h2 r2 s1 ) s3
2 2 2 2 2
+ (h1 r3 + h3 r1) s1 s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2 2 2 2 2 2
- 2 r1 r3 s1 s2 ), a = (sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 ) + (h2 r1 - h1 r2) s3
+ (h1 r3 - h3 r1) s2)/((2 h1 r2 - 2 h2 r1) s3),
2 2 2 2 2
b = (r1 s2 sqrt(((- 3 h1 r2 ) + 6 h1 h2 r1 r2 - 3 h2 r1 ) s3
2 2
+ (((2 h1 r2 - 2 h1 h2 r1) r3 - 2 h1 h3 r1 r2 + 2 h2 h3 r1 ) s2
2 2
+ ((4 h2 r1 - 4 h1 h2 r2) r3 + 4 h1 h3 r2 - 4 h2 h3 r1 r2) s1) s3
2 2 2 2 2
+ (h1 r3 - 2 h1 h3 r1 r3 + h3 r1 ) s2 )
2 2
+ ((h2 r1 - h1 r1 r2) s2 + (2 h1 r2 - 2 h2 r1 r2) s1) s3
2 2 2 2 2 2
+ (h3 r1 - h1 r1 r3) s2 )/((2 r1 s2 - 2 r1 r2 s1 s2 + 2 r2 s1 ) s3
2
- 2 r1 r3 s1 s2 )]]
Let’s translate the expression for $x$ to Python code (we don’t care about $a$ and $b$):
x=-(s1*s2*sqrt((-3*pow(h1,2,q)*pow(r2,2,q)+6*h1*h2*r1*r2-3*pow(h2,2,q)*pow(r1,2,q))*pow(s3,2,q)+(((2*pow(h1,2,q)*r2-2*h1*h2*r1)*r3-2*h1*h3*r1*r2+2*h2*h3*pow(r1,2,q))*s2+((4*pow(h2,2,q)*r1-4*h1*h2*r2)*r3+4*h1*h3*pow(r2,2,q)-4*h2*h3*r1*r2)*s1)*s3+(pow(h1,2,q)*pow(r3,2,q)-2*h1*h3*r1*r3+pow(h3,2,q)*pow(r1,2,q))*pow(s2,2,q))+(2*h1*r1*pow(s2,2,q)+(-h1*r2-h2*r1)*s1*s2+2*h2*r2*pow(s1,2,q))*s3+(-h1*r3-h3*r1)*s1*pow(s2,2,q))/((2*pow(r1,2,q)*pow(s2,2,q)-2*r1*r2*s1*s2+2*pow(r2,2,q)*pow(s1,2,q))*s3-2*r1*r3*s1*pow(s2,2,q))
We have changed all the powers to power with modulo. Now, we need to change the division by a multiplicative inverse modulo $q$:
x=-(s1*s2*sqrt((-3*pow(h1,2,q)*pow(r2,2,q)+6*h1*h2*r1*r2-3*pow(h2,2,q)*pow(r1,2,q))*pow(s3,2,q)+(((2*pow(h1,2,q)*r2-2*h1*h2*r1)*r3-2*h1*h3*r1*r2+2*h2*h3*pow(r1,2,q))*s2+((4*pow(h2,2,q)*r1-4*h1*h2*r2)*r3+4*h1*h3*pow(r2,2,q)-4*h2*h3*r1*r2)*s1)*s3+(pow(h1,2,q)*pow(r3,2,q)-2*h1*h3*r1*r3+pow(h3,2,q)*pow(r1,2,q))*pow(s2,2,q))+(2*h1*r1*pow(s2,2,q)+(-h1*r2-h2*r1)*s1*s2+2*h2*r2*pow(s1,2,q))*s3+(-h1*r3-h3*r1)*s1*pow(s2,2,q))*pow(((2*pow(r1,2,q)*pow(s2,2,q)-2*r1*r2*s1*s2+2*pow(r2,2,q)*pow(s1,2,q))*s3-2*r1*r3*s1*pow(s2,2,q)),-1,q)
Finally, the square root can be implemented using Cipolla’s Algorithm, so we have everything.
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{P!3453_53r10u5!y_570p_u51ng_57r4ng3_w4y5_70_g3n3r473_n0nc35}
The full script can be found in here: solve.py.