Cryptography – 489 pts (25 solves) – Chall author: qopruzjf
When it comes to signatures, proper randomness is essential. A standard Linear Congruential Generator is not good enough, not by a long shot. In fact, we only need a total of four signatures from the server to completely break it and be able to forge any signature we want ourselves.
Check out write-ups by my teammates on K3RN3L4RMY.com
Exploration
The server we can connect to will sign four separate messages for us free of charge. After which it will prompts us to send it a valid signature of ‘i wish to know the ways of the world’. Basically, the server is asking us to break its signature scheme and forge a signature ourselves. So let’s take a look at the signature scheme of the server.
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def sign(m):
k = next(gen)
r = int((k*G).x) % N
s = ((H(m) + d*r)*inverse(k, N)) % N
return r, s
def verify(r, s, m):
v1 = H(m)*inverse(s, N) % N
v2 = r*inverse(s, N) % N
V = v1*G + v2*pub
return int(V.x) % N == r
Seems like a standard implementation of ECDSA to me without any obvious vulnerabilities. The only note-worthy thing here is how the signature nonce ‘k’ is generated. Let’s take a look at the PRNG used form the nonce generation.
class RNG:
def __init__(self, seed, A, b, p):
self.seed = seed
self.A = A
self.b = b
self.p = p
def gen(self):
out = self.seed
while True:
out = (self.A*out + self.b) % self.p
yield out
:person_facepalming: :person_facepalming: :person_facepalming: :person_facepalming: :person_facepalming:
Signature schemes heavily rely on secure PRNG for their nonces, so I’m sorry but a simple Linear Congruentual Generator (LCG) will not cut it. It means that all generated nonces will be related to each other such that with a given number of valid signatures we should be able to recover all private parameters of the server. The rest of the code is not too interesting.
# Curve parameters
G = P256.G
N = P256.q
# Get random parameters for RNG
seed, A, b = randbelow(N), randbelow(N), randbelow(N)
# Initialise RNG
lcg = RNG(seed, A, b, N)
gen = lcg.gen()
# Get random parameters for W
d = randbelow(N)
pub = d*G
Final note, the server limits us to four signatures before prompting us to forge our own so. But as you will see, four signatures is all we need to crack this server open like… like uuh.. like a Monke cracks nuts? I dunno.
Exploitation
Knowing how the nonces are generated, we can take a look at the equation forms of the four signatures we can request from the server.
\[S_i = k_i^{-1} \left( H(m_i) + d R_i \right)\] \[k_i = S_i^{-1} H(m_i) + d S_i^{-1} R_i = \alpha_i + d \beta_i\]Additionally we can also write the $k_i$ as a function of the previous $k_{i-1}$ due to the LCG PRNG!
\[k_i = A k_{i-1} + B \mod{N}\]This means that we can write out our four signatures as follows.
\[k_1 = \alpha_1 + d \beta_1\] \[A k_1 + B = \alpha_2 + d \beta_2\] \[A^2 k_1 + A B + B = \alpha_3 + d \beta_3\] \[A^3 k_1 + A^2 B + A B + B = \alpha_4 + d \beta_4\]Now we have a system of four equations with exactly four unknowns ($A$, $B$, $d$, and $k_1$) and hence we can expect a unique solution. Note: this statement is generally not necessarily true due to the non-linearity of the equations, but it works out in the end :). I am too lazy to do this by hand as the equations are non-linear so let’s use Python’s Sympy module instead. To retrieve the flag, I used the commented script below.
#!/usr/bin/env sage
#
# Polymero
#
# Imports
from Crypto.Util.number import bytes_to_long, inverse, long_to_bytes
from hashlib import sha256
from secrets import randbelow
from fastecdsa.curve import P256
from gmpy2 import iroot
from sympy import symbols, Eq, solve, simplify, expand
# Hash function (from source)
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
# Build symbols with sympy
A,B,k1,d = symbols('A,B,k1,d')
a1,b1,a2,b2,a3,b3,a4,b4 = symbols('a1,b1,a2,b2,a3,b3,a4,b4')
# Set up equations
eq1 = Eq(k1, a1 + d*b1)
eq2 = Eq(A*k1 + B, a2 + d*b2)
eq3 = Eq(A*A*k1 + A*B + B, a3 + d*b3)
eq4 = Eq(A*A*A*k1 + A*A*B + A*B + B, a4 + d*b4)
# Solve eq1 for k1 (just take RHS)
k1_sym = eq1.rhs
# Solve eq2 for d (substituting k1)
d_sym = solve(eq2.subs(k1,k1_sym),d)[0]
# Substitute k1 and d into eq3 and get rid of the denominator
eq3_tmp = eq3.subs(k1,k1_sym).subs(d,d_sym)
d_denom = (A*b1-b2)
# Solve eq3 for B
B_sym = solve(simplify(Eq(eq3_tmp.lhs*d_denom,eq3_tmp.rhs*d_denom)),B)[0]
# Substitute k1 and d into eq4 and get rid of the denominator
eq4_tmp = eq4.subs(k1,k1_sym).subs(d,d_sym)
eq4_tmp = simplify(Eq(eq4_tmp.lhs*d_denom,eq4_tmp.rhs*d_denom))
# Substitute B into eq4 and get rid of the denominator
eq4_tmp = eq4_tmp.subs(B,B_sym)
B_denom = (A*b1-A*b2-b2+b3)
eq4_tmp = simplify(Eq(eq4_tmp.lhs*B_denom,eq4_tmp.rhs*B_denom))
# Get signature parameters (from remote server)
ms = [b'0',b'1',b'2',b'3'] # 30,31,32,33 in hex
Hs = [H(m) for m in ms]
rs = [96408062461903244424462493680952130645999845214114919082867454931656023397880,
39209896113870565640003488973728365592469957386941720932205122488146133990669,
6749888288691229722422948391388945883249100586766941653610278317192570395661,
110022623018036525811579627549255304474589128734071253958824659389116741174434]
ss = [6523340022753995175439793891612994534142780671491189287537050981787543073947,
94776179905836799422294745929609906345166358705895160035850387547133720892235,
103898263001739120627782879808468321607944043369730184405644409179838290014776,
69351421430917232924782896780640208180098299449449042185491936589328605674934]
# Build equation constants
a1 = inverse(ss[0],N)*Hs[0] % N
b1 = inverse(ss[0],N)*rs[0] % N
a2 = inverse(ss[1],N)*Hs[1] % N
b2 = inverse(ss[1],N)*rs[1] % N
a3 = inverse(ss[2],N)*Hs[2] % N
b3 = inverse(ss[2],N)*rs[2] % N
a4 = inverse(ss[3],N)*Hs[3] % N
b4 = inverse(ss[3],N)*rs[3] % N
# Set up polynomial
R = Integers(N)
P.<X> = PolynomialRing(R)
f = eval(str(eq4_tmp.as_poly())[5:-49].replace('A','X'))
# Get possible solutions for A
A_solves = f.roots()
# Check solutions of A (B, d, k1) againt first signature
for i in range(len(A_solves)):
An = A_solves[i][0]
Bn = ((An**2*a1n*b2n - An**2*a2n*b1n - An*a1n*b3n + An*a3n*b1n + a2n*b3n - a3n*b2n) * inverse(int(An*b1n - An*b2n - b2n + b3n), N)) % N
dn = (-An*a1n - Bn + a2n) * inverse(int(An*b1n - b2n), N) % N
k1n = int(a1n + b1n*dn) % N
r1n = int((int(k1n)*G).x) % N
if r1n == rs[0]:
break
print('N :', N)
print('a :', An)
print('b :', Bn)
print('d :', dn)
print('k1:', k1n)
# Clock RNG
k = k1n
for _ in range(4):
k = (An*k + Bn) % N
print('\nk5:',k)
# Forge signature
mymsg = b'i wish to know the ways of the world'
r5 = int((int(k)*G).x) % N
s5 = ((H(mymsg) + dn*r5)*inverse(int(k), N)) % N
print('r5:', r5)
print('s5:', s5)
print('\nr5(hex):',long_to_bytes(r5).hex())
print('s5(hex):',long_to_bytes(s5).hex())
# OUTPUT
# N : 115792089210356248762697446949407573529996955224135760342422259061068512044369
# a : 7320205395547049143882174558782202768836461372454982359398156041789324050757
# b : 22344967830873912600882613396913586506716724256573552770040600065450914948741
# d : 33113566016937666250061572877894910125405836868557206819655705964069845552265
# k1: 26513677676992322817247894822525705426759137889248432157234819181589947860813
# k5: 80685539897653496582356942694329897254184116503011414910848457304360899892482
# r5: 10491050194927390325147647627859982137400101742100346530944049825258072430915
# s5: 110253130067809232442129105626565659930040185773182311892111515837274838132185
# r5(hex): 1731b9571a197de09b83bdecab03a9ac2f8ed1ae69ce313013b05a4cca3fd943
# s5(hex): f3c10f69ccf2fece2bf6882a187c3cfc6515a8e2b79882b52e34c6a6c97de5d9
Ta-da!
corctf{r3l4ted_n0nce5_4re_d4n6er0us_fde6ebafa842716a}