Bsides 2020, chameleon reverse engineering writeup

 

Introduction

BsidesSF had really really good reverse engineering challenges, but I loved two challenges. One windows reverse challenge called chameleon and another esp32 firmware reverse challenge called smart-locky which I didn't manage to solve in time.

The challenge

Problem statement

We are given two files chameleon.exe and flag.png.enc, this looks trivial enough we need to reverse the encryption algorithm to give us the original flag.png.

The problem statment also says that file was encrypted in the last months.

Reading the statment it looked like a simple challenge where you brute force the seed of a default mt19937 implementation, but the problem had only two solves, so I thought there must be some twist.

First glance at the binary

When you first execute the binary it gives you two options, to encrypt or decrypt files.

Usage: chameleon.exe [--encrypt|<--decrypt --id=<id>>] <infile> <outfile>

Example: chameleon.exe --encrypt plaintext.txt ciphertext.txt
Example: chameleon.exe --decrypt --id=abcd1234 ciphertext.txt plaintext.txt

I knew where to look and I didn't focus on the decryption stuff to be honest.

Reversing the binary

After identifying the encrypt function and changing some function names here is what the assembly looks like (you might want to zoom):

    

And here is what the hexrays decompiler gives us after changing some types and variable names:

void __usercall encrypt(const CHAR *output@<ebx>, const CHAR *input)
{
  void *file_content;
  BYTE *new_file_ptr;
  FILE *v4;
  DWORD pdwDataLen;
  HCRYPTKEY phKey;
  HCRYPTPROV phProv;
  byte pbData[20];
  char v9[8];

  file_content = read_file(input, &pdwDataLen);
  new_file_ptr = (BYTE *)realloc(file_content, pdwDataLen + 16);
  if ( !CryptAcquireContextA(&phProv, 0, "Microsoft Enhanced Cryptographic Provider v1.0", 1u, 0xF0000000) )
    goto failure;
  mersenne_twister((int)v9);                    // generate 8 byte key
  *(_WORD *)&pbData[2] = 0;
  pbData[0] = 8;
  *(_DWORD *)&pbData[8] = 8;
  *(_DWORD *)&pbData[12] = *(_DWORD *)v9;
  *(_DWORD *)&pbData[16] = *(_DWORD *)&v9[4];
  pbData[1] = 2;
  *(_DWORD *)&pbData[4] = 26113;
  if ( !CryptImportKey(phProv, pbData, 0x14u, 0, 1u, &phKey)
    || !CryptEncrypt(phKey, 0, 1, 0, new_file_ptr, &pdwDataLen, pdwDataLen + 8) )
  {
failure:
    v4 = _iob_func();
    fprintf(v4 + 2, "Encryption failed\n");
    exit(1);
  }
  sub_E51AA0((int)v9);
  sub_E51F50(output, new_file_ptr, pdwDataLen);
  free(new_file_ptr);
}

All right looks simple enough, here are the algorithm steps:

• call to CryptAcquireContextA, this is like an encryption algorithm factory in windows
• call to a function that I called mersenne_twister
• sets some values in pbData
• call to CryptImportKey
• call to CryptEncrypt

If you read this tutorial you can understand how CryptImportKey works.

This is an example key blob from the page above:

BYTE DesKeyBlob[] = {
    0x08,0x02,0x00,0x00,0x01,0x66,0x00,0x00, // BLOB header 
    0x08,0x00,0x00,0x00,                     // key length, in bytes
    0xf1,0x0e,0x25,0x7c,0x6b,0xce,0x0d,0x34  // DES key with parity
    };

We can see that our example also uses DES using CBC mode of operation, we also see that the DES key is passed as the last 8 bytes (with byte of parity) of the array.

Ok so the bread and butter of this problem is knowing how the mersenne twister works.

Reversing mersenne_twister

This is what the code looks like:

We can see that there are two loops.

Here is the decompiled code, it looks really clean after some type changes

char __usercall mersenne_twister@<al>(int a1@<edi>)
{
  int v1; // eax
  signed int v2; // ecx
  unsigned int v3; // esi
  char result; // al

  v1 = time64(0);
  v2 = 0;
  do
  {
    v1 = 29945647 * v1 - 1;
    mt[v2++] = v1;
  }
  while ( v2 < 351 );
  dword_E54018 = v2;
  v3 = 0;
  do
  {
    result = getrandom() ^ 0x55;
    *(_BYTE *)(v3++ + a1) = result;
  }
  while ( v3 < 8 );
  return result;
}

If you implemented mersenne twister, the first loop is the set seed function, this is gonna put numbers in an array I call mt.

The interesting part to notice is the call to time64, the twister is seeded with current time.

Let's reverse getrandom now

Reversing getrandom

Here is what the code looks like:

The decompiled code looks good enough.

int getrandom()
{
  int v0; // eax
  int v1; // eax
  int *v2; // ecx
  int v3; // esi
  int v4; // eax
  int v5; // edi
  unsigned int v6; // esi
  int v7; // eax
  int v8; // esi
  unsigned int v9; // edi
  int v10; // eax
  int v11; // edi
  unsigned int v12; // esi
  int v13; // eax
  unsigned int v14; // esi
  unsigned int v15; // ecx
  int v16; // ecx

  v0 = dword_E54018;
  if ( dword_E54018 >= 351 )
  {
    v1 = 175;
    v2 = &dword_E54384;
    do
    {
      v3 = *v2;
      v4 = v1 + 1;
      *(v2 - 1) = ((*(v2 - 1) ^ (*v2 ^ *(v2 - 1)) & 0x7FFFFu) >> 1) ^ dword_E5437C[v4] ^ -((*((_BYTE *)v2 - 4) ^ (unsigned __int8)(*(_BYTE *)v2 ^ *((_BYTE *)v2 - 4))) & 1) & 0xE4BD75F5;
      if ( v4 >= 351 )
        v4 = 0;
      v5 = v2[1];
      v6 = ((v3 ^ (v3 ^ v2[1]) & 0x7FFFFu) >> 1) ^ mt[v4] ^ -(((unsigned __int8)v3 ^ (unsigned __int8)(v3 ^ *((_BYTE *)v2 + 4))) & 1) & 0xE4BD75F5;
      v7 = v4 + 1;
      *v2 = v6;
      if ( v7 >= 351 )
        v7 = 0;
      v8 = v2[2];
      v9 = ((v5 ^ (v5 ^ v2[2]) & 0x7FFFFu) >> 1) ^ mt[v7] ^ -(((unsigned __int8)v5 ^ (unsigned __int8)(v5 ^ *((_BYTE *)v2 + 8))) & 1) & 0xE4BD75F5;
      v10 = v7 + 1;
      v2[1] = v9;
      if ( v10 >= 351 )
        v10 = 0;
      v11 = v2[3];
      v12 = ((v8 ^ (v8 ^ v2[3]) & 0x7FFFFu) >> 1) ^ mt[v10] ^ -(((unsigned __int8)v8 ^ (unsigned __int8)(v8 ^ *((_BYTE *)v2 + 12))) & 1) & 0xE4BD75F5;
      v13 = v10 + 1;
      v2[2] = v12;
      if ( v13 >= 351 )
        v13 = 0;
      v14 = ((v11 ^ (v11 ^ v2[4]) & 0x7FFFFu) >> 1) ^ mt[v13] ^ -(((unsigned __int8)v11 ^ (unsigned __int8)(v11 ^ *((_BYTE *)v2 + 16))) & 1) & 0xE4BD75F5;
      v1 = v13 + 1;
      v2[3] = v14;
      if ( v1 >= 351 )
        v1 = 0;
      v2 += 5;
    }
    while ( (signed int)v2 < (signed int)&dword_E548FC );
    dword_E548F8 = dword_E54638 ^ ((dword_E548F8 ^ (dword_E548F8 ^ mt[0]) & 0x7FFFFu) >> 1) ^ -(((unsigned __int8)dword_E548F8 ^ (unsigned __int8)(dword_E548F8 ^ LOBYTE(mt[0]))) & 1) & 0xE4BD75F5;
    v0 = 0;
  }
  v15 = mt[v0];
  dword_E54018 = v0 + 1;
  v16 = ((((v15 >> 11) ^ v15) & 0xCABCA5) << 7) ^ (v15 >> 11) ^ v15;
  return (unsigned __int8)(v16 ^ ((((v16 & 0xFFFFFFAB) << 15) ^ v16) >> 17));
}

Looks like a normal getrandom function from mt19937 but the thing is, it is not. Because the length of the array is 351, this is called mt11213.

Putting it all together

After looking on the internet for some constants I found this page, maybe we can work with that.

The only difference with the program was the factor, also I had to change from long to int because this was written for a 32 bit machine (I spent two hours debugging this lol).

I wrote a program to generate all possible keys from october 2019 to february 2020.

#include <math.h>
#include <stdio.h>

#define RAND_MASK 0x3FFFFFFF

#define N 351
#define M 175
#define R 19
#define TEMU 11
#define TEMS 7
#define TEMT 15
#define TEML 17

#define MATRIX_A 0xE4BD75F5
#define TEMB     0x655E5280
#define TEMC     0xFFD58000

static unsigned int mt[N];
static int mti=N;


extern void set_seed (int seed) {
  unsigned int s = (unsigned int)seed;
  for (mti=0; mti<N; mti++) {
    // s = s * 29943829 - 1;
    s = s *  29945647 - 1;
    mt[mti] = s;
  }
  return;
}

void dump() {
    for (int i = 0; i < N; i++) {
       printf("%x\n", mt[i]);
    }
}

int genrandom () {
  unsigned int y;
  if (mti >= N) {
    const unsigned int LOWER_MASK = (1u << R) - 1;
    const unsigned int UPPER_MASK = -1 << R;
    int kk, km;
    for (kk=0, km=M; kk < N-1; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
      mt[kk] = mt[km] ^ (y >> 1) ^ (-(y & 1) & MATRIX_A);

      if (++km >= N) km = 0;
    }
    y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
    mt[N-1] = mt[M-1] ^ (y >> 1) ^ (-(unsigned int)(y & 1) & MATRIX_A);
    mti = 0;
  }
  y = mt[mti++];
  y ^=  y >> TEMU;
  y ^= (y << TEMS) & TEMB;
  y ^= (y << TEMT) & TEMC;
  y ^=  y >> TEML;

  return y&0xff;
}

int main(void) {
    for (int t = 1569888000 /*1546300800*/; t < 1582583270; t++) {
        set_seed(t);
        for (int i = 0; i<8; i++) {
            printf("%x", genrandom() ^ 0x55);
        }
        printf("\n");
    }
}

This generates a 263 MiB file:

gcc  bruteforce.c && ./a.out > keys.txt

Then I wrote a little program in python to try to brute force the key, since we know that the file is png, and the first 8 bytes are fixed.

from Crypto.Cipher import DES
cipher = "cd0c8716e99ae841".decode("hex")

with open("keys.txt") as myfile:
    lines = myfile.read().splitlines()
p = 0.01
pas = p
l = float(len(lines))
for i, key in enumerate(lines):
    if i / l >= p:
        print("{}%".format(p * 100))
        p += pas
    keyh = key
    key = key.zfill(16).decode("hex")
    out = DES.new(key).decrypt(cipher)
    if out[0] == chr(0x89) and out[1] == chr(0x50) and out[2] == chr(0x4e) and out[3] == chr(0x47) and \
        out[4] == chr(0x0d) and out[5] == chr(0xa) and out[6] == chr(0x1a) and out[7] == chr(0x0a):
        print("FOUND .....")
        print(keyh)
        exit(0)

After 5 minutes I find the key, and I decrypt the image:

from Crypto.Cipher import DES
key = "a051b8a16f8542da".decode("hex")
with open("flag.png.enc") as myfile:
    image=  myfile.read()

content = DES.new(key, DES.MODE_CBC, IV="\x00" * 8).decrypt(image)

with open("flag.png", "w") as myfile:
    myfile.write(content)

And yaas! we have the flag

Cryptopals - set3

 

Challenge 17

attacking CBC with a padding attack was really interesting, here is my solution

from set2 import aes_cbc_decrypt, aes_cbc_encrypt, paddpkcs7, validatepkcs7, split_blocks
from Crypto import Random
from Crypto.Util.strxor import strxor


def get_block(text, block, blocksize):
    return split_blocks(text, blocksize)[block]


def produce_ciphertext(plaintext, key):
    blocksize = len(key)
    iv = Random.new().read(blocksize)
    return iv + aes_cbc_encrypt(paddpkcs7(plaintext, blocksize), key, iv)


def cbc_padding_oracle(ciphertext, key):
    blocksize = len(key)
    iv = ciphertext[:blocksize]
    return validatepkcs7(aes_cbc_decrypt(ciphertext[blocksize:], key, iv))


def break_cbc_padding_oracle(oracle, ciphertext, blocksize=16):
    plaintext_block = ""
    plaintext = ""
    prefix = ""
    for block_counter in range(1, len(split_blocks(ciphertext, blocksize))):
        current_block = get_block(ciphertext, block_counter, blocksize)
        last_block = get_block(ciphertext, block_counter-1, blocksize)
        for j in range(blocksize-1, -1, -1):
            for i in range(255)[::-1]:
                guessed_block = strxor(last_block,
                                       ("\x00" * j) + chr(i) + strxor(plaintext_block, (chr((blocksize - j)))*len(plaintext_block)))
                if oracle(prefix + guessed_block + current_block):
                    plaintext_block = chr(i ^ (blocksize - j)) + plaintext_block
                    break
        plaintext += plaintext_block
        plaintext_block = ""
        prefix += last_block
    return plaintext

Challenge 18

In this challenge, you implement CTR mode which turns a block cipher into a stream cipher.

from set2 import aes_ecb_encrypt
import struct
from Crypto.Util.strxor import strxor
from set2 import split_blocks


def form_nonce(nonce):
    return struct.pack("<Q", nonce)


def aes_ctr_produce_blocks(nonce):
    # xrange doesn't support 64 bit numbers 
    for counter in xrange(2**32-1):
        yield nonce + struct.pack("<Q", counter)


def aes_ctr_encrypt_block(block, key):
    return aes_ecb_encrypt(block, key)


def aes_ctr_encrypt_decrypt(text, key, nonce):
    blocksize = len(key)
    ctr_block_gen = aes_ctr_produce_blocks(nonce)
    output = ""
    for block in split_blocks(text, blocksize):
        blk = next(ctr_block_gen)
        blk = aes_ctr_encrypt_block(blk, key)
        blk = blk[:len(block)]
        output += strxor(blk, block)

    return output

Challenge 19

This is still unimplemented

Challenge 20

This is still unimplemented

Challenge 21

In this challenge, I implemented the mersenne twister

class MT19937(object):

    W, N, M, R = 32, 624, 397, 31
    A = 0x9908B0DF
    U, D = 11, 0xFFFFFFFF
    S, B = 7, 0x9D2C5680
    T, C = 15, 0xEFC60000
    L = 18
    F = 1812433253
    LOWER_MASK = (1 << R) - 1
    UPPER_MASK = (~LOWER_MASK) & 0xffffffff

    def __init__(self, seed):
        self.mt = []

        self.mt.append(seed)
        for i in range(1, self.N):
            self.mt.append(self.F * (self.mt[i - 1] ^ (self.mt[i - 1] >> (self.W - 2))) + i& 0xffffffff)
        self.index = self.N

    def extract_number(self):
        if self.index == self.N:
            self.twist()

        y = self.mt[self.index]
        y ^= (y >> self.U) & self.D
        y ^= (y << self.S) & self.B
        y ^= (y << self.T) & self.C
        y ^= (y >> self.L)

        self.index += 1
        return y & 0xffffffff

    def twist(self):
        for i in range(self.N):
            x = (self.mt[i] & self.UPPER_MASK) + (self.mt[(i + 1) % self.N] & self.LOWER_MASK)
            xA = x >> 1
            if x & 1 != 0:
                xA ^= self.A

            self.mt[i] = self.mt[(i + self.M) % self.N] ^ xA

        self.index = 0

Challenge 22

This challenge teaches why you shouldn't see your MT19937 with curent time

from set3 import MT19937


def break_mt19937_seeded_time(timestamp, num, lim=1000):
    for i in range(timestamp-lim, timestamp):
        obj = MT19937(i)
        num2 = obj.extract_number()
        if num2 == num:
            return i
    return None

Challenge 23

Given enough consecutive outputs, you can clone the mersenne twister, 624 in the case of MT19937:

from set3 import MT19937


def clone_mt19937(numbers):
    T, C = 15, 0xEFC60000
    L = 18
    U, D = 11, 0xFFFFFFFF
    S, B = 7, 0x9D2C5680
    mt = []
    for number in numbers:
        y = number
        y ^= (y >> L)
        y ^= (y << T) & C
        for _ in range(S):
            y ^= (y << S) & B
        for _ in range(U):
            y ^= (y >> U) & D
        mt.append(y & 0xffffffff)
    obj = MT19937(0)
    obj.mt = mt
    obj.index = obj.N
    return obj

If you think about how to protect this, the weak link is the temper function which can be easily "untempered", so you can implement one way functions like hashing functions, which will render untempering, computationally unfeasible.

Challenge 24

Recovering a 16 bit seed used for encryption:

from set3 import MT19937
from Crypto.Util.strxor import strxor
from Crypto.Random import random
from Crypto.Util.number import long_to_bytes


class MT19937Cipher(MT19937):

    def __init__(self, seed):
        super(MT19937Cipher, self).__init__(seed & 0xffff)

    def gen_8_bit_val(self):
        return self.extract_number() & 0xff


def mt19937_cipher_oracle(ciphertext, key):
    obj = MT19937Cipher(key)
    randlen = random.choice(range(10))
    ciphertext += long_to_bytes(random.getrandbits(randlen * 8))
    s = ""
    for i in range(len(ciphertext)):
        s += long_to_bytes(obj.gen_8_bit_val())
    return strxor(s, ciphertext)


def break_mt19937_cipher(ciphertext, plaintext):
    for i in range(0xffff):
        obj = MT19937Cipher(i)
        s =""
        for _ in range(len(ciphertext)):
            s += long_to_bytes(obj.gen_8_bit_val())
        if plaintext in strxor(s, ciphertext):
            return i

Tests

#!/usr/bin/env python

import unittest
from base64 import b64decode
from test import support
from set3 import produce_ciphertext, break_cbc_padding_oracle, cbc_padding_oracle, form_nonce, aes_ctr_encrypt_decrypt,\
    break_ctr_reused_nonce_substitutions, MT19937, break_mt19937_seeded_time, clone_mt19937,\
    mt19937_cipher_oracle, break_mt19937_cipher

from set2 import encryption_get_oracle_func, generate_random_key
from set1 import unpadpkcs7
from Crypto.Random import random


class Set3(unittest.TestCase):
    def test_ch17(self):
        key = generate_random_key()
        oracle = encryption_get_oracle_func(key, cbc_padding_oracle)

        lst = ["MDAwMDAwTm93IHRoYXQgdGhlIHBhcnR5IGlzIGp1bXBpbmc=", 
               "MDAwMDAxV2l0aCB0aGUgYmFzcyBraWNrZWQgaW4gYW5kIHRoZSBWZWdhJ3MgYXJlIHB1bXBpbic=",
               "MDAwMDAyUXVpY2sgdG8gdGhlIHBvaW50LCB0byB0aGUgcG9pbnQsIG5vIGZha2luZw==",
               "MDAwMDAzQ29va2luZyBNQydzIGxpa2UgYSBwb3VuZCBvZiBiYWNvbg==",
               "MDAwMDA0QnVybmluZyAnZW0sIGlmIHlvdSBhaW4ndCBxdWljayBhbmQgbmltYmxl",
               "MDAwMDA1SSBnbyBjcmF6eSB3aGVuIEkgaGVhciBhIGN5bWJhbA==",
               "MDAwMDA2QW5kIGEgaGlnaCBoYXQgd2l0aCBhIHNvdXBlZCB1cCB0ZW1wbw==",
               "MDAwMDA3SSdtIG9uIGEgcm9sbCwgaXQncyB0aW1lIHRvIGdvIHNvbG8=",
               "MDAwMDA4b2xsaW4nIGluIG15IGZpdmUgcG9pbnQgb2g=",
               "MDAwMDA5aXRoIG15IHJhZy10b3AgZG93biBzbyBteSBoYWlyIGNhbiBibG93"]

        for plaintext in lst:
            #test funcs
            ciphertext = produce_ciphertext(plaintext, key)
            self.assertTrue(oracle(ciphertext))

            self.assertEqual(unpadpkcs7(break_cbc_padding_oracle(oracle, ciphertext)), plaintext)

    def test_ch18(self):
        cipher = b64decode("L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==")
        key = "YELLOW SUBMARINE"
        nonce = form_nonce(0)

        self.assertEqual(aes_ctr_encrypt_decrypt(cipher, key, nonce),
                         "Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby ")

    def test_ch19(self):
        # this is a many time pad problem
        plaintexts = []
        ciphertexts = []

        key = generate_random_key(16)

        with open('static/19.txt', 'r') as myfile:
            for line in myfile.read().splitlines():
                plaintexts.append(b64decode(line))

        for plaintext in plaintexts:
            nonce = form_nonce(0)
            ciphertexts.append(aes_ctr_encrypt_decrypt(plaintext, key, nonce))

        break_ctr_reused_nonce_substitutions(ciphertexts)
        raise NotImplementedError

    def test_ch20(self):
        plaintexts = []
        ciphertexts = []

        key = generate_random_key(16)

        with open('static/19.txt', 'r') as myfile:
            for line in myfile.read().splitlines():
                plaintexts.append(b64decode(line))

        for plaintext in plaintexts:
            nonce = form_nonce(0)
            ciphertexts.append(aes_ctr_encrypt_decrypt(plaintext, key, nonce))

        raise NotImplementedError

    def test_ch21(self):
        obj = MT19937(1337)
        self.assertEqual(obj.extract_number(), 1125387415)

    def test_ch22(self):
        import time
        time.sleep(random.choice(range(1, 10)))

        time_now = int(time.time())
        orig_seed = time_now
        obj = MT19937(time_now)
        num = obj.extract_number()

        time.sleep(random.choice(range(1, 10)))

        i = break_mt19937_seeded_time(int(time.time()), num)
        self.assertEqual(i, orig_seed)

    def test_ch23(self):

        for randseed in [random.choice(range(100000)) for _ in range(10)]:
            obj = MT19937(randseed)
            numbers = []
            for i in range(624):
                f = obj.extract_number()
                numbers.append(f)
            obj2 = clone_mt19937(numbers)
            self.assertEqual(obj.extract_number(), obj2.extract_number())

    def test_ch24(self):
        randseed = random.choice(range(0xffff))
        plaintext = "A" * 14
        cipher = mt19937_cipher_oracle(plaintext, randseed)
        self.assertEqual(randseed, break_mt19937_cipher(cipher, plaintext))



if __name__ == "__main__":
    support.run_unittest(Set3)

Cryptopals - set2

 

This set was much more fun than the other one, I started doing some basic attacks on ecb and cbc.

I tried to make my code much more decoupled so that I can reuse my code in other challenges.

Challenge 9

First task is to implement pkcs7 padding, pretty easy

def paddpkcs7(s, n=16):
    s = str(s)
    return s + ((n - len(s)) % n) * chr(n - len(s) % n)

Challenge 10

from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
from set1.ch07 import aes_ecb_decrypt


def split_blocks(cipher, keysize):
    return [cipher[i:i+keysize] for i in
            range(0, len(cipher), keysize)]


def aes_ecb_encrypt(cipher, key):
    aes = AES.new(key, AES.MODE_ECB)
    return aes.encrypt(cipher)

This is pretty straight forward because this is how CBC works:

• Encryption:

• Decryption:

def aes_cbc_encrypt(cipher, key, iv="\x00" * 16):
    last_block = iv
    output = ""
    for block in split_blocks(cipher, len(key)):
        last_block = aes_ecb_encrypt(strxor(last_block, block), key)
        output += last_block
    return output


def aes_cbc_decrypt(cipher, key, iv="\x00" * 16):
    last_block = iv
    output = ""

    for block in split_blocks(cipher, len(key)):
        output += strxor(aes_ecb_decrypt(block, key), last_block)
        last_block = block
    return output

Challenge 11

from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
from Crypto.Random import random
from Crypto import Random
from set2.ch10 import aes_cbc_encrypt, aes_ecb_encrypt
from set1.ch07 import paddpkcs7
from functools import partial

AES_CBC_MODE = 0
AES_ECB_MODE = 1


def generate_random_key(keysize=16):
    return Random.new().read(keysize)


def encryption_oracle(cleartext, key):
    choice = random.choice([AES_ECB_MODE, AES_CBC_MODE])
    if choice == AES_ECB_MODE:
        func = lambda x: aes_ecb_encrypt(x, key)
    else:
        IV = Random.new().read(16)
        func = lambda x: aes_cbc_encrypt(x, key, IV)
    return func(paddpkcs7(Random.new().read(random.choice(range(5, 11))) +
                          cleartext + Random.new().read(random.choice(range(5, 11))), 16)), choice

This is an oracle generator, it uses partial from functools.

def encryption_get_oracle_func(key, oracle_func):
    """
    Return partially applied oracle
    """
    # return lambda x: oracle_func(x, key)
    return partial(oracle_func, key=key)

This could also be done with a side channel attack because CBC needs an IV, it could be fixed by getting the IV generation out of the branch.

def check_block_mode(oracle=encryption_oracle):
    out, result = oracle("\xff" * 48)
    if out[16:32] == out[32:48]:
        return AES_ECB_MODE, result
    else:
        return AES_CBC_MODE, result

Yeah this is lame.

def check_block_mode_decoupled(oracle=encryption_oracle):
    """
    Lame but I need the ret value of the other one
    """
    out = oracle("\xff" * 48)
    if out[16:32] == out[32:48]:
        return AES_ECB_MODE
    else:
        return AES_CBC_MODE

Challenge 12

from set2 import aes_ecb_encrypt
from set1 import paddpkcs7
from string import printable
import base64


def encryption_oracle(plaintext, key):    
    buff = "Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg\
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq\
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg\
YnkK"
    return aes_ecb_encrypt(paddpkcs7(plaintext + base64.b64decode(buff), 16), key)

This tries to generate 2 consecutive blocks, if the goal is found stop, that's the block size.

def guess_block_size(oracle):
    """
    Only works for ecb mode
    """
    prevblock = None

    for i in range(2, 40):
        block = oracle("\xff" * i)[:i]
        if prevblock:
            if block[:i-1] == prevblock:
                return len(block) - 1
        prevblock = block

    raise Exception

Added the prefix to use the attack for the harder challenge.

def break_ecb_oracle(oracle, blocksize, prefix="", startindex=0):
    found = ""
    bl = startindex // blocksize
    while 1:
        lookup = {}
        bts = prefix + "A" * ((blocksize - (len(found) % blocksize)) - 1)
        for c in printable:
            lookup[oracle(bts + found + c)[startindex:blocksize * (len(found) // blocksize+1+bl)]] = c
        try:
            found += lookup[oracle(bts)[startindex:blocksize * (len(found) // blocksize+1+bl)]]
        except KeyError:
            break
    return found

Challenge 13

import urlparse
from collections import OrderedDict
from set2 import aes_ecb_encrypt, paddpkcs7, aes_ecb_decrypt
from set1 import unpadpkcs7


def key_value_parse(s):
    d = {}
    for k, v in urlparse.parse_qs(s).items():
        d[k] = v[0]
    return d


def profile_for(email):
    email = email.replace('=', '').replace('&', '')
    d = OrderedDict()
    d['email'] = email
    d['uid'] = '10'
    d['role'] = 'user'
    return '&'.join(map(lambda x: x[0] + '=' + x[1], d.items()))


def encryption_oracle(cleartext, key):
    return aes_ecb_encrypt(paddpkcs7(profile_for(cleartext), 16), key)


def decryption_oracle(cipher, key):
    return key_value_parse(unpadpkcs7(aes_ecb_decrypt(cipher, key)))

The attack is straight forward as the name implies:

encrypted("email=someemail.com&uid=10&role=") + encrypted("admin" + padding)

def cut_and_paste_attack(email, enc_oracle, dec_oracle):
    # encrypted("email=someemail.com&uid=10&role=") + encrypted("admin" + padding)
    first_part = enc_oracle(email)[:48]
    second_part = enc_oracle("AAAABBBBCC" + "admin" + '\x0b' * 0x0b)[16:32]

    ciphertext = first_part + second_part
    return dec_oracle(ciphertext)

Challenge 14

from set2 import aes_ecb_encrypt
from set1 import paddpkcs7
import base64


def encryption_oracle(plaintext, key, randomdata):
    buff = "Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg\
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq\
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg\
YnkK"
    return aes_ecb_encrypt(
        paddpkcs7(randomdata + plaintext + base64.b64decode(buff), 16), key)

This code kinda works, checks for two consecutive blocks as always.

def get_random_data_length(oracle, blocksize=16):
    randlen = 0
    bl = 0
    for i in range(2, 100):
        block = oracle("\xff" * i)
        # check 10 consecutive blocks
        for j in range(1, 11):
            if 16*(j+2) > len(block):
                break
            if block[16*j:16*(j+1)] == block[16*(j+1):16*(j+2)]:
                randlen = i
                bl = j
                break
        if randlen:
            break
    return (blocksize * bl - randlen - blocksize * bl * 2)\
        % (blocksize * bl) or blocksize * bl

Challenge 15

def validatepkcs7(s, blocksize=16):
    lastchar = ord(s[-1])
    if lastchar > blocksize:
        raise ValueError("Padding char is bigger than blocksize")
    if s[-((lastchar - blocksize) % blocksize):] == lastchar * chr(lastchar):
        return True
    return False

Challenge 16

from set2 import paddpkcs7, aes_cbc_encrypt, aes_cbc_decrypt
from set1 import unpadpkcs7
from Crypto import Random 


def clean(t):
    return t.replace(';', '?').replace('=', '?')


def encryption_oracle(plaintext, key, blocksize=16):
    app = ";comment2=%20like%20a%20pound%20of%20bacon"
    prefix = "comment1=cooking%20MCs;userdata="
    plaintext = clean(plaintext)
    iv = Random.new().read(blocksize)
    return iv + aes_cbc_encrypt(paddpkcs7(prefix + plaintext + app, blocksize),
                                key, iv)


def decryption_oracle(ciphertext, key, blocksize=16):
    iv = ciphertext[:blocksize]
    return unpadpkcs7(aes_cbc_decrypt(ciphertext[blocksize:], key, iv))

This is how to do the bit flipping attack, one thing to note is that some chars are non printable, I need to improve this.

def break_cbc_oracle(enc_oracle, dec_oracle, blocksize=16):
    g = enc_oracle(";admin=true;")
    iv, c = g[:blocksize], g[blocksize:]

    d1 = ord('?') ^ ord(";") ^ ord(c[blocksize])
    d2 = ord('?') ^ ord("=") ^ ord(c[blocksize+6])
    d3 = ord('?') ^ ord(";") ^ ord(c[blocksize+11])

    nc = c[:blocksize] + chr(d1) + c[blocksize+1:blocksize+6] \
        + chr(d2) + c[blocksize+7:blocksize+11] + chr(d3) + c[blocksize+12:]

    return dec_oracle(iv + nc)

Tests

As always here are the unit tests:

#!/usr/bin/env python

from ch09 import paddpkcs7
from ch10 import aes_cbc_decrypt
from test import support
from base64 import b64decode
from set1.tests import Set1
from set1 import unpadpkcs7
from set2 import encryption_oracle1, generate_random_key, AES_ECB_MODE,\
    AES_CBC_MODE, check_block_mode, guess_block_size, encryption_get_oracle_func,\
    check_block_mode_decoupled, encryption_oracle1, encryption_oracle2, break_ecb_oracle,\
    encryption_oracle13, decryption_oracle13, cut_and_paste_attack, encryption_oracle14,\
    get_random_data_length, validatepkcs7, decryption_oracle16, encryption_oracle16,\
    break_cbc_oracle
from functools import partial
import unittest
from Crypto import Random
from Crypto.Random import random


class Set2(unittest.TestCase):
    poem = Set1.poem

    def test_ch9(self):
        result = paddpkcs7("YELLOW SUBMARINE", 20)
        self.assertEqual(result, "YELLOW SUBMARINE\x04\x04\x04\x04")
        result = paddpkcs7("YELLOW SUBMARINE HEH", 20)
        self.assertEqual(result, "YELLOW SUBMARINE HEH")

    def test_ch10(self):
        with open("static/10.txt", "r") as myfile:
            cipher = b64decode(myfile.read())
        key = "YELLOW SUBMARINE"
        self.assertEqual(unpadpkcs7(aes_cbc_decrypt(cipher, key)), self.poem)

    def test_ch11(self):
        key = generate_random_key()
        oracle = encryption_get_oracle_func(key, encryption_oracle1)
        for _ in range(20):
            result, correct_result = check_block_mode(oracle)
            self.assertEqual(result, correct_result)

    def test_ch12(self):
        cleartext = b64decode("Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg\
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq\
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg\
YnkK")
        key = generate_random_key()
        oracle = encryption_get_oracle_func(key, encryption_oracle2)

        mode = check_block_mode_decoupled(oracle)
        self.assertEqual(mode, AES_ECB_MODE)

        block_size = guess_block_size(oracle)
        self.assertEqual(16, block_size)

        self.assertEqual(break_ecb_oracle(oracle, block_size), cleartext)

    def test_ch13(self):
        key = generate_random_key()
        dec_oracle = encryption_get_oracle_func(key, decryption_oracle13)
        enc_oracle = encryption_get_oracle_func(key, encryption_oracle13)

        obj = cut_and_paste_attack("abcdabcdefsomeone10@gmail.com", enc_oracle, dec_oracle)
        self.assertEqual("admin", obj["role"])

    def test_ch14(self):
        cleartext = b64decode("Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg\
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq\
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg\
YnkK")
        key = generate_random_key()
        block_size = len(key)
        randomdata = Random.new().read(random.choice(range(1, 31)))
        oracle = partial(encryption_get_oracle_func(key, encryption_oracle14), randomdata=randomdata)
        self.assertEqual(len(randomdata), get_random_data_length(oracle))

        filling_text = (block_size - (len(randomdata) % block_size)) * "A"

        out = break_ecb_oracle(oracle, block_size, filling_text,
                               startindex=len(filling_text)+len(randomdata))

        self.assertEqual(out, cleartext)

    def test_ch15(self):
        self.assertTrue(validatepkcs7("ICE ICE BABY\x04\x04\x04\x04"))
        self.assertFalse(validatepkcs7("ICE ICE BABY\x05\x05\x05\x05"))
        self.assertFalse(validatepkcs7("ICE ICE BABY\x01\x02\x03\x04"))

    def test_ch16(self):
        key = generate_random_key()

        dec_oracle = encryption_get_oracle_func(key, decryption_oracle16)
        enc_oracle = encryption_get_oracle_func(key, encryption_oracle16)

        self.assertIn("admin=true", break_cbc_oracle(enc_oracle, dec_oracle))

if __name__ == "__main__":
    support.run_unittest(Set2)