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 and 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 and , where . Looking at the equation for signing, we note that the only thing which differs is SHA(data) from two different signatures. Here, are unknown values. Let be the known signed strings. So, if we compute

,

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

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

Next, we can also find the unknown 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

addr = 'lazy.2016.volgactf.ru'
sock = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
sock.connect((addr, 8889))

print "[+] Connected to", addr
data = read_message(sock)
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))
print read_message(sock)

This gives us VolgaCTF{Do_not_be_lazy_use_nonce_only_once}. Great 🙂