# VolgaCTF – Lazy

The description of the challenge was as follows:

There’s some valuable data on the server. However, to retrieve it we can only execute “signed” commands. We have the server script and some other files. Dare to take a look at it?

nc lazy.2016.volgactf.ru 8889

As usual in CTFs, the RSA-flavoured challenge was one of the simpler crypto tasks, mainly consisting of algebraic manipulation. The system used two functions $\textsf{Sign}$ and $\textsf{Verify}$ embodied in Python as below:

def sign(data, p, q, g, x, k):
r = pow(g, k, p) % q
s = (invert(k, q) * (SHA1(data) + x * r)) % q
return (r, s)

def verify(data, p, q, g, y, r, s):
if not (r > 0 and r < q): return False     if not (s &gt; 0 and s &lt; q): return False
w = invert(s, q)
u1 = (SHA1(data) * w) % q
u2 = (r * w) % q
v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
if v == r:
return True
else:
return False


We are also given two signatures $(r_1,s_1)$ and $(r_2,s_2)$, where $r_1 = r_2$. Looking at the equation for signing, we note that the only thing which differs is SHA(data) from two different signatures. Here, $x,k$ are unknown values. Let $d_1,d_2$ be the known signed strings. So, if we compute

$s_1 - s_2 = k^{-1} \cdot \left(\texttt{SHA1}(d_1) + x \cdot r - \texttt{SHA1}(d_2) - x \cdot r\right) = k^{-1} \cdot \left(\texttt{SHA1}(d_1) - \texttt{SHA1}(d_2)\right)$,

we have something which only depends on $k$. It is now easy to determine the unknown $k$.

k = invert(((s1 - s2)*invert(SHA1(d1) - SHA1(d2), q)) % q, q)


Next, we can also find the unknown $x$ by computing

x = ((s1 * k - SHA1(d1))*invert(r1,q)) % q


These unknowns can now be used to generate valid signatures for any command one would like to send to the server, so the rest is trivial. Using the code below, we connect to the server and unravel the flag:

import string
import hashlib
import itertools
import socket
import struct
from server import *

def bruteforce(prefix):
print "[ ] Running proof-of-work bruteforce routine..."
for lsuffix in itertools.product(string.printable,repeat=5):
suffix = ''.join(lsuffix)
sha_hash = hashlib.sha1(prefix+suffix).digest()
if sha_hash[-3:] == '\xff\xff\xff':
return prefix+suffix

sock = socket.socket(socket.AF_INET,socket.SOCK_STREAM)

challenge = data[-16:].replace("\n","")

print "[+] Challenge:", challenge
response = bruteforce(challenge)

send_message(sock, response)
print "[+] Response:", response

# pre-signed command, using sign() and the unravelled secrets
cmd = ['618115531371374705088478644225735834217345085623', \
'108118980045367256474213546635114425133447666132', \
'cat flag.txt']

send_message(sock, '\n'.join(cmd))

This gives us VolgaCTF{Do_not_be_lazy_use_nonce_only_once}. Great 🙂