Category: crypto, rev
Points: 334 (Dynamic, 22 solves)
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
The name and category of the challenge immediately tells we are dealing with Lamport signatures.
Reverse the binary. Check it yields the signature of the flag and give an oracle that checks if our input is the flag.
Exploit a buffer overflow to turn the oracle to our advantage and leak the secret key. Finally get the flag.
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
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).
Sign the message
m the user writes
m as bits, and publishes
_ is either
1 depending on the bit of the message at position
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
not correct depending on if we write the flag to the
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
\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
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
The binary was compiled without randomized addresses, so we can use this to our advantage as follows:
Write a string of 32 bytes with a
\xc0as the last byte. This allows us write one extra byte and overflow the buffer.
Try every possibility for this new byte. This is the LSB of a pointer to a flag address
addrFlagwhich 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).
Since we are given the signature for whatever is in the memory which
flag_addrpoints to, we make the buffer all zero bytes, and point the
flag_addrto 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
Finally we compare this to the signature for the
flag that we were given at the start and recover the plaintext bit by bit:
Exploit in solve.py.