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


We are given an archive containing three files:

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:

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


I spotted two mistakes in the program:

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.


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:

24 struct evp_cipher_ctx_st {
25     const EVP_CIPHER *cipher;
26     ENGINE *engine;             /* functional reference if 'cipher' is
27                                  * ENGINE-provided */
28     int encrypt;                /* encrypt or decrypt */
29     int buf_len;                /* number we have left */
30     unsigned char oiv[EVP_MAX_IV_LENGTH]; /* original iv */
31     unsigned char iv[EVP_MAX_IV_LENGTH]; /* working iv */
32     unsigned char buf[EVP_MAX_BLOCK_LENGTH]; /* saved partial block */
33     int num;                    /* used by cfb/ofb/ctr mode */
34     /* FIXME: Should this even exist? It appears unused */
35     void *app_data;             /* application stuff */
36     int key_len;                /* May change for variable length cipher */
37     unsigned long flags;        /* Various flags */
38     void *cipher_data;          /* per EVP data */
39     int final_used;
40     int block_mask;
41     unsigned char final[EVP_MAX_BLOCK_LENGTH]; /* possible final block */
42 } /* EVP_CIPHER_CTX */ ;

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

109 struct evp_cipher_st {
110     int nid;
111     int block_size;
112     /* Default value for variable length ciphers */
113     int key_len;
114     int iv_len;
115     /* Various flags */
116     unsigned long flags;
117     /* init key */
118     int (*init) (EVP_CIPHER_CTX *ctx, const unsigned char *key,
119                  const unsigned char *iv, int enc);
120     /* encrypt/decrypt data */
121     int (*do_cipher) (EVP_CIPHER_CTX *ctx, unsigned char *out,
122                       const unsigned char *in, size_t inl);
123     /* cleanup ctx */
124     int (*cleanup) (EVP_CIPHER_CTX *);
125     /* how big ctx->cipher_data needs to be */
126     int ctx_size;
127     /* Populate a ASN1_TYPE with parameters */
128     int (*set_asn1_parameters) (EVP_CIPHER_CTX *, ASN1_TYPE *);
129     /* Get parameters from a ASN1_TYPE */
130     int (*get_asn1_parameters) (EVP_CIPHER_CTX *, ASN1_TYPE *);
131     /* Miscellaneous operations */
132     int (*ctrl) (EVP_CIPHER_CTX *, int type, int arg, void *ptr);
133     /* Application data */
134     void *app_data;
135 } /* EVP_CIPHER */ ;

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:

1 EVP_CIPHER_CTX_init(cipher_ctx);
2 EVP_CipherInit_ex(cipher_ctx, cipher, 0, &buffers[2048 * key], &buffers[2048 * iv], 0);
3 EVP_CipherUpdate(cipher_ctx, &buffers[2048 * out], &outl, &buffers[2048 * in], sizes[in]);
4 EVP_CipherFinal_ex(cipher_ctx, &buffers[2048 * out + outl] + outl, &outl_final);
5 EVP_CIPHER_CTX_cleanup(cipher_ctx);

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:

224 int EVP_CipherFinal_ex(EVP_CIPHER_CTX *ctx, unsigned char *out, int *outl)
225 {
226     if (ctx->encrypt)
227         return EVP_EncryptFinal_ex(ctx, out, outl);
228     else
229         return EVP_DecryptFinal_ex(ctx, out, outl);
230 }

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

379 int EVP_EncryptFinal_ex(EVP_CIPHER_CTX *ctx, unsigned char *out, int *outl)
380 {
381     int n, ret;
382     unsigned int i, b, bl;
384     if (ctx->cipher->flags & EVP_CIPH_FLAG_CUSTOM_CIPHER) {
385         ret = ctx->cipher->do_cipher(ctx, out, NULL, 0);
386         if (ret < 0)
387             return 0;
388         else
389             *outl = ret;
390         return 1;
391     }
392 // ...

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)