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:

    Sorry, your browser does not support SVG.

  • Decryption:

    Sorry, your browser does not support SVG.

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)


Author: Mohamed Aziz Knani

Date: 2019-06-17 Mon 20:45

Emacs 26.2 (Org mode 9.2.1)

Validate

hacker emblem