Skip to content

Instantly share code, notes, and snippets.

Last active May 22, 2023 04:21
What would you like to do?

candy_machine writeup (8 points)

In candy_machine, there is a server that will decrypt strings for us with a fixed, unknown secret key. If we provide a base64-encoded string that decrypts to "candykey", then the server will return a flag. In all other cases, it returns an error, and (except for the case of no key at all), it's always the same error.

The solution is to do a padding oracle attack via either a timing side-channel or a debugging side-channel.

The encryption scheme is:

  1. PKCS.7 pad
  2. AES-CBC encrypt, and include the IV at the beginning of the output.
  3. PKCS.7 pad
  4. AES-CBC encrypt, and include the IV at the beginning of the output.

PKCS.7 padding is: Add N bytes each of value N, and choose N so that the resulting string's length is a multiple of 16. N can't be zero. (During padding, the server always chooses the lowest possible N. During unpadding, it actually allows higher values of N.)

Wikipedia has an excellent diagram of cipher block chaining. During encryption, the server always uses the all-zeroes IV, but it allows any IV during decryption.

The general plan will be:

  1. Find a way to tell if a string is padded correctly when it's decrypted.
  2. Find a way to decrypt arbitrary blocks.
  3. Reconstruct a string that decrypt to "candykey"

Timing Side-Channel

Here is the server's top-level code:

// Endpoint to get a candy from the machine
func OpenTheCandyMachine(w http.ResponseWriter, req *http.Request) {
        key, ok := req.URL.Query()["key"]

        if !ok || len(key[0]) < 1 {
		fmt.Fprintf(w, "Missing candy key\n")

        candyKeyStep1, err := DecodeStep1(key[0])

        // Prevent timing attack here
        if err != nil {
                approxSizeOfBuffer := len(key[0]) * 3 / 4;
                DecodeStep2(make([]byte, approxSizeOfBuffer));
                fmt.Fprintf(w, "An error occured\n")

        candyKeyStep2, err := DecodeStep2(candyKeyStep1)

        if err != nil {
                fmt.Fprintf(w, "An error occured\n")

        if !CheckCandyKeyValue(candyKeyStep2) {
                fmt.Fprintf(w, "An error occured\n")

        fmt.Fprintf(w, "Here's your candy : FLAG-....\n")

The // Prevent timing attack here code is extremely suspicious. It does ensure that the server always calls DecodeStep2 for any string, but there are at least two ways that we can still get timing information out of this.

The first is that DecodeStep2 short-circuits on input of the wrong length (not a multiple of 16). So if we can make "real" case and the "fake" case have different lengths, we can possibly observe that difference; we can control them almost completely independently, so this is probably possible.

The second is that approxSizeOfBuffer might be very different from the actual length of the ciphertext. Golang's base64 decode function allows the input to contain arbitrary numbers of extra newlines. So we can make the "fake" case work with a much longer ciphertext than the "real" case ever would.

Both of these are theoretically possible ways to do this challenge. Running in a local server and timing the server-side code, I could reliably detect these differences. But various factors made it basically impossible to detect on the client side.

One major issue is that the server requests the private key over HTTP. It does this twice (once in DecodeStep1 and once in DecodeStep2). It's always twice, so this doesn't give us any extra useful timing information; and these HTTP RPCs are kind of slow, which adds a lot of noise to the timing signal.

Golang PProf Debug Side-Channel

It turns out there is a different part of the code with a much more serious bug.

import (
        _ "net/http/pprof"

Depending on "net/http/pprof" adds a performance debugging endpoint to golang's built in HTTP server. This is presumably useful internally, but please never expose this externally!

This endpoint probably provides a lot of different ways one could get information leaks. I chose to use the "goroutine" info page, which provides a full stack trace for every currently running goroutine. Because the server requests the private key inside DecodeStep2, it is fairly easy to get a stack trace during this part of the code. The line number of OpenTheCandyMachine in this stack trace then tells you if this the "real" case or the "fake" case. Rephrased, the line number tells you whether your ciphertext unpadded correctly.

def is_correctly_padded_pprof(key):
  session = FuturesSession(executor=ThreadPoolExecutor(max_workers=40))
  req = session.get(HOST + '/candy-machine-open', params={"key": urlsafe_b64encode(key)})
  debugs = []
  for i in range(5):
    debugs.append(session.get(HOST + '/debug/pprof/goroutine?debug=1'))
  for d in debugs:
    result = d.result()
    if "DecodeStep2" in result.text:
      return "candymachine/main.go:112" in result.text
  return None

def is_correctly_padded(key):
  result = None
  while result is None:
    result = is_correctly_padded_pprof(key)
  return result

When I ran this code, there was a retry about 5% of the time; not too bad!

Building an Oracle

Given any message, we can now tell if its decryption is correctly padded. We now want to write a function that can AES-decrypt a given block. We work right to left, one byte at a time; first we try and make the decrypted string end in a 1, then two 2s, etc.

def xor_block(a, b):
  return [a[i] ^ b[i] for i in range(16)]

def oracle(to_encipher, start_here=None):
  result = [0]*16

  start_index = 0
  if start_here:
    result = start_here
    while result[-1-start_index]:
      start_index += 1

  for i in range(start_index, 16):
    for b in range(256):
      result[-1-i] = b
      if is_correctly_padded(bytes(xor_block([i+1]*16, result) + to_encipher)):
      raise Exception("bad")
    print(i, result)
  return result

(Technically the very first byte might fail: we might get "unlucky" and hit a string ending in two 2s instead of one 1. You can detect this by varying the penultimate byte as well.)

I specifically included some logging and a way to restart in the middle of the search. This was very helpful on hotel wifi!

This code took about 20-30 minutes per block.

Putting It All Together

Since we can choose our own IVs, we can do everything together with three calls to the oracle.

TARGET = list(b"candykey")
PADDED = TARGET + [16-len(TARGET)]*(16-len(TARGET))
ZERO_DEC        = oracle([0]*16)
BLOCK_TWO       = xor_block([16]*16, ZERO_DEC)
IV = xor_block(xor_block(PADDED, ZERO_DEC), BLOCK_THREE_DEC)

This string decrypts to xor_block(PADDED, ZERO_DEC) + [0]*16 + [16]*16, which unpads to xor_block(PADDED, ZERO_DEC) + [0]*16. That decrypts to PADDED, which unpads to TARGET.

In [106]: payload = {"key": urlsafe_b64encode(bytes(CIPHERTEXT))}
In [107]: r = requests.get(HOST + '/candy-machine-open', params=payload)
In [109]: r.text
Out[109]: "Here's your candy : FLAG-f2e999227239d3269ecbc8b7d07ba6fe\n"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment