Lamport Verify

The challenge:

I finally managed to create a signature verification service powered by time, artificial intelligence, the power of music and the randomness of entanglement (well, Leslie and the Emperor Penguin's randomness also helped). It is resistent to all known and unknown attacks and will always be uncrackable. Leave and believe!

Okay, that doesn’t reveal too much.. The challenge contains one file – verify and that’s it.

Reversing verify

After dedicating some time for reversing the binary, we can describe in general what it’s doing:

  1. Read 0x20 bytes from a file named flag.
  2. Read 0x4000 files from a file named secret_key.
  3. Get 0x20 utf-8 characters from user (@ 0x4011A0). We’ll call it user_input.
  4. Verify if the user_input == flag (Time-safe memcmp) (function @ 0x401290).
  5. If verbose (-v) flag is on – print “the signature” (function @ 0x401290).

Locally, we can control the secret_key file, flag file, and user_input. Remotely, we can only control the user_input, and it seems that the verbose option is always on.

Controlling the flag

Looking further into the signature calculation, it seems that the signature is calculated somehow by the flag and secret_key, and it’s our only observable clue about the flag from the server. Our input has no effect whatsoever on the flag calculation.

This begs the question – how can our input change anything? Luckily – it can. The function that grabs utf-8 input from the user has a buffer overflow, which allows us to write bytes past the end of the buffer allocated for input. (Meaning, we can actually write more than 32 BYTES, but seemingly no more than 32 CHARACTERS).

The structure in memory where the buffers are allocated looks like this:

struct glob
  char key[16384];
  char flag[32];
  char user_input[32];
  unsigned __int64 ptr_flag;
  unsigned __int64 ptr_user_input;
  unsigned __int64 ptr_key;
  unsigned __int64 verbose;

Since we can overflow bytes after the user input, we can controll the ptr_flag field, which is then being used to calculate the signature. If we point ptr_flag to user_input (thanks to no ASLR), we can start controlling the signature calculation, and observe changes in the signature, per our input.

Understanding the signature

After some hand-waving, white-boarding, arguments, trials and failures, we reached the following conclusion – The first 16 lines of the signature (32 bytes * 16) are affected by the first two bytes of the flag. Again, this took some time, trial and error, and simulation using our local binary, and mock test_key and flag files.

The best experiment was using a test_key where each row (32 bytes) has the value of the index of the row. It then really stands out which rows are picked per which combination of bytes.

Extracting the flag

Since we now have an understanding of the signature, and a way to control it, we can do the following:

  1. Send and input which will contain the following: “XX” + stub + (overwrite bytes – ptr_flag points to our input) – where XX are two characters from string.printable.
  2. Observe the first 16 lines of output, and save a dictionary where d[sha1sum(output)] = “XX”. This creates a mapping between each possible characters combination and the output signature it yields.
  3. We do this for each characters combination. It takes a little bit of time to get all the possible outputs from the server.
  4. We now send an input in the following manner: stub + (overwrite bytes ptr_flag points to original flag + index).
  5. The output we receive is affected by the original flag, and since we have every possible output mapped, we can reverse-search the matching characters by using the dictionary – c1c2 = d[sha1sum(new_output)].
  6. We continue this process, but instead of setting ptr_flag to the original flag, we offset the point by 2, to read the next 2 bytes, and repeat the process until we’re done.

…And that’s it! 🙂

As a sidenote / tip:

There’s actually a faster way to do steps 1-3 if you run this “mapping” locally. You first have to grab the first 32 blocks of the original signature. In order to do that, you need to test which bytes yield which rows of the signature (using a local test_key which you know), and then map which rows come out. Send these rows to the server, until you complete the whole 32 byte * 32 rows, and you get your own test_key which matches the server (at least the first, relevant part).

flag sha1sum: 55b09c6c68e3a11ddd776f1e5c96bb800579ff14


import socket
import string
import hashlib
import binascii

mapping = {}

str_list = string.ascii_letters + string.punctuation + string.digits

for char_check1 in str_list:
    for char_check2 in str_list:
        check_pattern = char_check1 + char_check2 + "\x5a"*29 + "\xf0\x90\x80\x40"

        print(char_check1 + char_check2)

        HOST = ""
        PORT = 1337

        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.connect((HOST, PORT))

        data = ""
        while len(data) < 1100:
            data += s.recv(1100-len(data))

        k = hashlib.sha1(data).digest()
        if k in mapping.keys():
        mapping[k] = char_check1 + char_check2

print("Got all mappings")

flag = ""
for idx in range(16):
    check_pattern = "\x5a"*31 + "\xf0" + chr(0x70+idx*2) + "\x80\x40"

    HOST = ""
    PORT = 1337

    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((HOST, PORT))

    data = ""
    while len(data) < 1100:
        data += s.recv(1100-len(data))

    flag += mapping[hashlib.sha1(data).digest()]