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
        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

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 🙂


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s