What’s this? Yet another crypto problem?

You’ve got to be kidding me!

Running at yacp.chal.pwning.xxx:7961

TL;DR: doit.py

# Introduction

We are given an archive containing three files:

• yacp
• libc​.so​.6
• libcrypto​.so​.1​.0​.0

The first is a 32 bit ELF binary and the latter two are presumably versions of libraries running on the remote server.

First, the program requires a proof of work. We are given a 16 byte prefix which is the hex-encoding of 8 random bytes read from /dev​/urandom. The goal is then to find a 32 byte string starting with that prefix whose SHA-256 sum’s 28 upper bits are 1.

This check can however be disabled by giving the program any number of command line arguments. This is very convenient during exploit development.

The actual program is some sort of “crypto service”. We are presented with a main menu where we can choose to:

• Generate random data
• Hash data
• Encrypt data
• Decrypt data
• Display data

Data is kept in 32 buffers each 2048 bytes which are statically allocated in the data segment. The datum sizes are 4 byte unsigned integers and are also stored in the data segment, right after the buffers.

For hashing and encryption/decryption OpenSSL EVP is used. Pointers to the EVP digest/cipher being used and corresponding digest/cipher contexts are stored after the buffer sizes.

The (relevant part of) data segment is laid out like this:
0x0804c0e0: Buffer #0
…
0x0805b8e0: Buffer #31
0x0805c0e0: Size of datum #0
…
0x0805c15c: Size of datum #31
0x0805c160: OpenSSL EVP digest object (24 bytes)
0x0805c178: OpenSSL EVP cipher object (140 bytes)
0x0805c204: Pointer to EVP digest
0x0805c208: Pointer to EVP cipher

# Vulnerabilities

I spotted two mistakes in the program:

• The largest message that can be encrypted is a full buffer. But because of plaintext padding the resulting ciphertext may be larger than a full buffer.

• If an unknown digest/cipher algorithm is selected an error message is printed but the program does not actually exit. The currently selected digest/cipher will continue to be used.

For the first error consider this diagram which shows encrypting a full buffer with AES-256 in CBC mode.

Since a block of padding is added to the message we have a one block overflow past the end of the ciphertext buffer. If the ciphertext is placed in buffer #31 this overflow will overwrite the first four datum sizes.

The second error can be relevant depending on the exact exploit you decide to implement. In the exploit I’ll describe below it will not be relevant. Exercise to the reader: what exploit, then, will rely on this error?

# Information leak

By overwriting the size of datum #0 and then display it we can leak the data segment. But we need to be able to control the size, not just overwrite it. Consider the diagram above again. For convenience we define $$x_n = c_{n-1} \oplus p_0$$.

Then we have

\begin{align} size_{0-3} & = c_{128} \\ & = E(x_{128}) \\ & = E(\texttt{"\x10}\ldots\texttt{"} \oplus c_{127}) \\ & = E(\texttt{"\x10}\ldots\texttt{"} \oplus E(x_{127})) \\ & = E(\texttt{"\x10}\ldots\texttt{"} \oplus E(p_{127} \oplus c_{126})) \end{align}

Solving for $$size_{0-3}$$ we get

\begin{align} size_{0-3} & = E(\texttt{"\x10}\ldots\texttt{"} \oplus E(p_{127} \oplus c_{126})) \\ D(size_{0-3}) & = \texttt{"\x10}\ldots\texttt{"} \oplus E(p_{127} \oplus c_{126}) \\ \texttt{"\x10}\ldots\texttt{"} \oplus D(size_{0-3}) & = E(p_{127} \oplus c_{126}) \\ D(\texttt{"\x10}\ldots\texttt{"} \oplus D(size_{0-3})) & = p_{127} \oplus c_{126} \\ c_{126} \oplus D(\texttt{"\x10}\ldots\texttt{"} \oplus D(size_{0-3})) & = p_{127} \\ \end{align}

OK, so to compute plaintext which will let us control $$size_{0-3}$$ we first encrypt 127 arbitrary data blocks ($$p_0 \ldots p_{126}$$) with an arbitrary key and IV, then derive the last plaintext block per the equations above.

# Memory write

By setting the size of datum #0 and encrypting/decrypting it into buffer #31 we can overflow arbitrarily far into the data segment. The part that will overflow past buffer #31 should be placed in buffer #1, which is convenient since that will not change the size of datum #0. One (and the easiest, IMO) way to carry out this attack is to place the encrypted overflow in buffer #1, then decrypt datum #0 (with its size set appropriately) into buffer #31. This diagram should make it clear:

Another thing to note is that the plaintext doesn’t need to have the correct padding because the decryption function never checks the return value of EVP_DecryptFinal_ex.

From the diagram it is clear that the “IV” for the ciphertext in buffer #1 is the last block in buffer #0. And if we never actually write anything to buffer #0 then it will be all zeros.

# Exploit

Note: There are many ways to exploit this service given the vulnerabilities outlined above. The one I’ll go through here is actually not the one I wrote during the CTF (this one’s prettier). During the CTF I used sizes of “big enough” and weeded out segfaults using a combination of GDB (gdb​.attach) and cyclic until I had a working exploit.

On to the exploit. So we can read and write memory in the data segment. What can we do with that?

We can overwrite the digest/cipher contexts and pointers. Lets have a look at the OpenSSL source code. At the time of this writing the latest commit was d396da, so the code below is taken from that commit.

The definition of a cipher context is given in crypto​/evp​/evp_locl​.h:

And the definition of a cipher is given in crypto​/include​/internal​/evp_int​.h:

See all those juicy pointers? We can overflow into the cipher field of the cipher context and point it to somewhere we control (say one of the buffers) and place a fake cipher there.

The program has this sequence of calls in its decryption function:

The function EVP_CipherUpdate encrypts/decrypts a number of full blocks and saves any remaining data in an internal buffer. It will make the exploit easier if we overflow a number of full blocks. So keep that in mind when reading the final exploit.

When EVP_CipherFinal is called the overflow will have happened and (part of) cipher_ctx is controlled by us. So lets have a look at that function:

For this exploit it doesn’t matter whether EVP_EncryptFinal_ex or EVP_DecryptFinal_ex is called, so let’s just pick EVP_EncryptFinal_ex as that will allow for a wider range of values in ctx->encrypt ($$2^{32} - 1$$ vs. 1):

If the condition in the if-statement is satisfied the do_cipher function pointer is called. Note that the cipher context is given as the first argument. If we set do_cipher to be the address of system then the context will be run as a shell command. The first four bytes are the address of the faked cipher. They will probably not be a valid command (or one that hangs anyway) so if we follow them with ";sh ​#" we should be able to get a shell.

The final challenge is figuring out the address of system. We can use the information leak described above to leak the address current cipher. Since we’re given the server’s versions of libc​.so and libcrypto​.so we can then calculate the address of system.

In the information leak we set the size of buffer #0. The size should be set to

\begin{align} 32 \cdot 2048 &+ \hspace{5em} \textrm{(buffers)} \\ 32 \cdot 4 &+ \hspace{5em} \textrm{(sizes)} \\ 24 &+ \hspace{5em} \textrm{(digest context)} \\ 140 &+ \hspace{5em} \textrm{(cipher context)} \\ 4 &+ \hspace{5em} \textrm{(digest pointer)} \\ 4 &+ \hspace{5em} \textrm{(cipher pointer)} \\ &= 65836 \end{align}

## Proof of work

As mentioned yacp requires a proof of work, but this can be disabled. Of course I disabled the check when I was reversing and exploiting the program.

Unfortunately I then forgot about it and when time came to fire off the exploit against the real service I was in for an unpleasant reminder. It was 10 or 15 minutes till the end of the CTF and I failed to implement proof of work generation in that time.

Bitterness prompted me to write a more general proof of work generation tool, so I won’t end up in this situation again. You can find it on Github here: POW.

(To top)