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:
- PKCS.7 pad
- AES-CBC encrypt, and include the IV at the beginning of the output.
- PKCS.7 pad
- 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:
- Find a way to tell if a string is padded correctly when it's decrypted.
- Find a way to decrypt arbitrary blocks.
- Reconstruct a string that decrypt to "candykey"
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")
return
}
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")
return
}
candyKeyStep2, err := DecodeStep2(candyKeyStep1)
if err != nil {
fmt.Fprintf(w, "An error occured\n")
return
}
if !CheckCandyKeyValue(candyKeyStep2) {
fmt.Fprintf(w, "An error occured\n")
return
}
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.
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):
sleep(0.1)
debugs.append(session.get(HOST + '/debug/pprof/goroutine?debug=1'))
req.result()
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 resultWhen I ran this code, there was a retry about 5% of the time; not too bad!
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)):
break
else:
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.
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)
BLOCK_TWO_DEC = oracle(BLOCK_TWO)
BLOCK_THREE = BLOCK_TWO_DEC
BLOCK_THREE_DEC = oracle(BLOCK_TWO)
IV = xor_block(xor_block(PADDED, ZERO_DEC), BLOCK_THREE_DEC)
CIPHERTEXT = IV + BLOCK_THREE + BLOCK_TWO + [0]*16This 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"