Lamport Verify

by: goulov

Category: crypto, rev

Points: 334 (Dynamic, 22 solves)

Description:

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!

nc lamport.forfuture.fluxfingers.net 1337

Given: lamport_verify_64697622e0057029746079ede3bd1034.zip

TLDR

  1. The name and category of the challenge immediately tells we are dealing with Lamport signatures.

  2. Reverse the binary. Check it yields the signature of the flag and give an oracle that checks if our input is the flag.

  3. Exploit a buffer overflow to turn the oracle to our advantage and leak the secret key. Finally get the flag.

Attack

Description

Lamport signatures are a type of one-time signatures (meaning that you can only sign one with a pair of public/secret keys). Wikipedia has a good page on this signature scheme https://en.wikipedia.org/wiki/Lamport_signature.

Basically, this signatures work by sampling 2*L random strings, with L being the length of the message the signer wants to sign. This strings are then labeled into two groups m0[i] and m1[i], where 0<=i<L. These 2*L strings are the secret key, while the public key is the set containing the hash of every string in a predefined order. (In our challenge we aren’t given neither public or secret keys).

To Sign the message m the user writes m as bits, and publishes m_[i], where _ is either 0 or 1 depending on the bit of the message at position i.

To Verify the receiver computes and checks if the hash of each string corresponding to each bit of the message m_[i] is equal to the public key published earlier by the sender.

The binary itself apparently just reads 32 bytes from stdin, and writes a signature (that doesn’t depend on our input) and a message 'The message is not correct.' (or 'The message is correct.' if you get it correct eventually). Since multiple executions yield the same result this suggests that the same secret key is always used and the same message is being signed…

We proceed to reverse the given binary where we find the signature is actually from the flag, and the message is given as correct or not correct depending on if we write the flag to the stdin.

Execution

The (relative) structure of the memory is:

 -----------------------------------------------------------------
|  secret key  |  flag  |  buffer  | addrFlag | addrBuff | addrSk |
 -----------------------------------------------------------------
0           0x4000    0x4020    0x4040     0x4048     0x4050

When running the binary we are asked to input 32 bytes, which are saved into a variable buffer. However, by analysing the function reading our input, we spot a vulnerability. In fact, it writes byte-by-byte the stdin input to buffer until it reaches 32 bytes. But, when the byte given is \xc0, \xe0, or \xf0, it reads extra 1, 2, or 3 bytes (respectively), not checking for overflows to buffer! We confirm this using gdb. (And just yesterday L0rdC0mm4nd3r from my team was telling me I don’t even know how to open gdb… :p)

The message being printed at the end is 'The message is not correct.' or 'The message is correct.' depending on a comparison between what addrFlag is pointing to (supposedly flag) and what addrBuff is pointing to (supposedly buffer).

The binary was compiled without randomized addresses, so we can use this to our advantage as follows:

  1. Write a string of 32 bytes with a \xc0 as the last byte. This allows us write one extra byte and overflow the buffer.

  2. Try every possibility for this new byte. This is the LSB of a pointer to a flag address addrFlag which is the memory allocated right after the buffer (where we are writing to). The oracle gives “correct” when we write there the address of the buffer (as it’s now comparing the buffer with itself).

  3. Since we are given the signature for whatever is in the memory which flag_addr points to, we make the buffer all zero bytes, and point the flag_addr to it (we know the address from 2.).

Now we have the signature for the string made up of all zeros (except for the last byte which must be \xc0, but this we know it’s going to decode to } anyway…) which is the secret key for 0, the group m0[i] for every bit position i.

Finally we compare this to the signature for the flag that we were given at the start and recover the plaintext bit by bit:

flag{u_st4yed&pl4yed!_Ba6,kids!}

Resources:

Exploit in solve.py.