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 > 0 and s < 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 🙂