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)

Cryptopals - set1

 

Crypotpals challenges are a fun way of learning practical cryptography instead of dry mathematical textbooks, I will be doing the challenges for the next couple of weeks.

Challenge 1:

def convert_hex_to_base64(hex):
    import base64
    return base64.b64encode(hex.decode("hex"))

Challenge 2

def xor_two_strings(s1, s2):
    import binascii
    s1, s2 = s1.decode("hex"), s2.decode("hex")
    res = ""
    for i in range(len(s1)):
        res += chr(ord(s1[i]) ^ ord(s2[i]))
    return binascii.hexlify(res)

Challenge 3

from ch02 import xor_two_strings
from collections import Counter
from string import printable
import binascii


def bruteforce(ch):
    for i in range(256):
        yield xor_two_strings(ch, binascii.hexlify(chr(i)*len(ch))).decode("hex"), i

Doing this the ad-hoc way

def not_so_good_freq(ch, limit=3):
    FREQ = {'\x00': 0.0, '\x83': 0.0, '\x04': 0.0, '\x87': 0.0, '\x08': 0.0, '\x8b': 0.0,
            '\x0c': 0.0, '\x8f': 0.0, '\x10': 0.0, '\x93': 0.0, '\x14': 0.0, '\x97': 0.0,
            '\x18': 0.0, '\x9b': 0.0, '\x1c': 0.0, '\x9f': 0.0, ' ': 0.1601132522827019,
            '\xa3': 0.0, '$': 2.5223225546082834e-06, '\xa7': 0.0, '(': 0.00019043535287292538,
            '\xab': 0.0, ',': 0.016740654794935177, '\xaf': 0.0, '0': 2.5223225546082833e-05,
            '\xb3': 0.0, '4': 1.2611612773041417e-05, '\xb7': 0.0, '8': 2.0178580436866267e-05,
            '\xbb': 1.2611612773041417e-06, '<': 0.0, '\xbf': 1.2611612773041417e-06,
            '@': 2.5223225546082834e-06, '\xc3': 2.5223225546082834e-06, 'D': 0.0012485496645311003,
            '\xc7': 0.0, 'H': 0.0011186500529687736, '\xcb': 0.0, 'L': 0.0010530696665489582, '\xcf': 0.0, 'P': 0.0006255359935428543, '\xd3': 0.0, 'T': 0.002136407203753216, '\xd7': 0.0, 'X': 7.56696766382485e-05, '\xdb': 0.0, '\\': 0.0, '\xdf': 0.0, '`': 0.0, '\xe3': 0.0, 'd': 0.03412197951874086, '\xe7': 0.0, 'h': 0.04803384956868284, '\xeb': 0.0, 'l': 0.02675301417545276, '\xef': 1.2611612773041417e-06, 'p': 0.011935630328406397, '\xf3': 0.0, 't': 0.06602935983453564, '\xf7': 0.0, 'x': 0.000836149926852646, '\xfb': 0.0, '|': 0.0, '\xff': 0.0, '\x80': 0.0, '\x03': 0.0, '\x84': 0.0, '\x07': 0.0, '\x88': 0.0, '\x0b': 0.0, '\x8c': 0.0, '\x0f': 0.0, '\x90': 0.0, '\x13': 0.0, '\x94': 0.0, '\x17': 0.0, '\x98': 0.0, '\x1b': 0.0, '\x9c': 0.0, '\x1f': 0.0, '\xa0': 0.0, '#': 1.2611612773041417e-06, '\xa4': 0.0, "'": 0.0016004136608989558, '\xa8': 0.0, '+': 0.0, '\xac': 0.0, '/': 3.02678706552994e-05, '\xb0': 0.0, '3': 1.6395096604953842e-05, '\xb4': 0.0, '7': 1.7656257882257983e-05, '\xb8': 0.0, ';': 0.001397366695252989, '\xbc': 0.0, '?': 0.0011514402461786813, '\xc0': 0.0, 'C': 0.0009496544418100187, '\xc4': 0.0, 'G': 0.0004855470917620945, '\xc8': 0.0, 'K': 6.93638702517278e-05, '\xcc': 0.0, 'O': 0.00041366089895575846, '\xd0': 0.0, 'S': 0.0011300005044645109, '\xd4': 0.0, 'W': 0.0007630025727690057, '\xd8': 0.0, '[': 2.5223225546082834e-06, '\xdc': 0.0, '_': 0.00022953135246935377, '\xe0': 0.0, 'c': 0.016579226151440245, '\xe4': 0.0, 'g': 0.015338243454572971, '\xe8': 0.0, 'k': 0.005967815164203198, '\xec': 0.0, 'o': 0.05827700146294708, '\xf0': 0.0, 's': 0.04627326842556626, '\xf4': 0.0, 'w': 0.017045855824042777, '\xf8': 0.0, '{': 0.0, '\xfc': 0.0, '\x7f': 0.0, '\x81': 0.0, '\x02': 0.0, '\x85': 0.0, '\x06': 0.0, '\x89': 0.0, '\n': 0.02052035514301569, '\x8d': 0.0, '\x0e': 0.0, '\x91': 0.0, '\x12': 0.0, '\x95': 0.0, '\x16': 0.0, '\x99': 0.0, '\x1a': 0.0, '\x9d': 0.0, '\x1e': 0.0, '\xa1': 0.0, '"': 0.0071646572163648285, '\xa5': 0.0, '&': 0.0, '\xa9': 2.5223225546082834e-06, '*': 0.00011350451495737275, '\xad': 0.0, '.': 0.008594814104827726, '\xb1': 0.0, '2': 1.7656257882257983e-05, '\xb5': 0.0, '6': 1.1350451495737274e-05, '\xb9': 0.0, ':': 0.0003392523835948141, '\xbd': 0.0, '>': 0.0, '\xc1': 0.0, 'B': 0.0006747212833577157, '\xc5': 0.0, 'F': 0.0005511274781819099, '\xc9': 0.0, 'J': 0.0003543863189224638, '\xcd': 0.0, 'N': 0.0005208596075266105, '\xd1': 0.0, 'R': 0.0002774554810069112, '\xd5': 0.0, 'V': 0.0001450335468899763, '\xd9': 0.0, 'Z': 0.0, '\xdd': 0.0, '^': 0.0, '\xe1': 0.0, 'b': 0.009946778994097766, '\xe5': 0.0, 'f': 0.01655400292589416, '\xe9': 0.0, 'j': 0.0005460828330726933, '\xed': 0.0, 'n': 0.052933461131009434, '\xf1': 0.0, 'r': 0.046652877970034805, '\xf5': 0.0, 'v': 0.006418049740200777, '\xf9': 0.0, 'z': 0.00027114967462039046, '\xfd': 0.0, '~': 0.0, '\x01': 0.0, '\x82': 0.0, '\x05': 0.0, '\x86': 0.0, '\t': 0.0, '\x8a': 0.0, '\r': 0.02052035514301569, '\x8e': 0.0, '\x11': 0.0, '\x92': 0.0, '\x15': 0.0, '\x96': 0.0, '\x19': 0.0, '\x9a': 0.0, '\x1d': 0.0, '\x9e': 0.0, '!': 0.0012044090198254553, '\xa2': 0.0, '%': 1.2611612773041417e-06, '\xa6': 0.0, ')': 0.00019043535287292538, '\xaa': 0.0, '-': 0.0030658830651263684, '\xae': 0.0, '1': 7.945316047016092e-05, '\xb2': 0.0, '5': 1.6395096604953842e-05, '\xb6': 0.0, '9': 2.270090299147455e-05, '\xba': 0.0, '=': 0.0, '\xbe': 0.0, 'A': 0.0011312616657418151, '\xc2': 0.0, 'E': 0.0005208596075266105, '\xc6': 0.0, 'I': 0.003624577510972103, '\xca': 0.0, 'M': 0.0020493870756192302, '\xce': 0.0, 'Q': 3.6573677041820106e-05, '\xd2': 0.0, 'U': 0.00010215406346163547, '\xd6': 0.0, 'Y': 0.000552388639459214, '\xda': 0.0, ']': 2.5223225546082834e-06, '\xde': 0.0, 'a': 0.05961509357816678, '\xe2': 0.0, 'e': 0.09386318922463804, '\xe6': 0.0, 'i': 0.04810321343893457, '\xea': 0.0, 'm': 0.01724133582202492, '\xee': 0.0, 'q': 0.0008033597336427383, '\xf2': 0.0, 'u': 0.021007163396055087, '\xf6': 0.0, 'y': 0.014814861524491752, '\xfa': 0.0, '}': 0.0, '\xfe': 0.0}
    l = []
    for br, i in bruteforce(ch):
        score = 0
        for c in br:
            score += FREQ.get(c, 0)
        l.append((i, score, br))
    return sorted(l, key=lambda x: x[1])[::-1][:limit]

Doing it the scientific way, if the two probability distributions are identical the output will converge to zero, so we need to minimize the output:

def chi_squared(ch, limit=3):
    # using a statistical method returns best "limit" candidates
    FREQ = {
        "e": 12.02,
        "t": 9.10,
        "a": 8.12,
        "o": 7.68,
        "i": 7.31,
        "n": 6.95,
        "s": 6.28,
        "r": 6.02,
        "h": 5.92,
        "d": 4.32,
        "l": 3.98,
        "u": 2.88,
        "c": 2.71,
        "m": 2.61,
        "f": 2.30,
        "y": 2.11,
        "w": 2.09,
        "g": 2.03,
        "p": 1.82,
        "b": 1.49,
        "v": 1.11,
        "k": 0.69,
        "x": 0.17,
        "q": 0.11,
        "j": 0.10,
        "z": 0.07}

    ls = []
    for br, i in bruteforce(ch):
        cnt = Counter(br.lower())
        s = 0
        for key, val in cnt.iteritems():
            try:
                e = (len(br) * FREQ[key] / 100)
                s += (val - e)**2 / e
            except KeyError:
                s += val**2

        ls.append((i, s, br))
    return sorted(ls, key=lambda x: x[1])[:limit]

Challenge 5

from itertools import cycle
from binascii import hexlify


def repeating_xor(text, key):
    l = ""
    k = 0
    for i in cycle(key):
        try:
            l += chr(ord(i) ^ ord(text[k]))
        except IndexError:
            return l
        k += 1

Challenge 6

import sys
from random import randint


def popcount(x):
    setBits = 0
    while (x > 0):
        setBits += x & 1
        x /= 2
    return setBits


def hamming_distance(s1, s2):
    assert len(s1) ==  len(s2)
    f = 0
    for i in range(len(s1)):
        f += popcount(ord(s1[i]) ^ ord(s2[i]))
    return f


def find_keysize(cipher, keysize):
    blocknum = randint(1, 40)
    blocknum2 = randint(1, 40)
    if blocknum2 == blocknum:
        blocknum2 = randint(1, 40)
    block1, block2 = cipher[keysize*(blocknum-1):keysize*blocknum], cipher[keysize*(blocknum2-1):keysize*(blocknum2)]
    return float(hamming_distance(block1, block2)) / keysize


def transpose(cipher, keysize):
    cipher = cipher + (keysize - (len(cipher) % keysize)) * "\x00"
    blocks = [cipher[i:i+keysize] for i in range(0, len(cipher), keysize)]
    return "".join(["".join(c) for c in zip(*blocks)])

With enough number of simulations the keysize will converge to the correct value, because the blocks are randomized each time

def simulation(cipher):
    smallestScore = sys.maxint
    keysize = 0
    for KEYSIZE in range(10, 41):
        distance = find_keysize(cipher, KEYSIZE)
        if distance < smallestScore:
            smallestScore = distance
            keysize = KEYSIZE
    return keysize

Challenge 7

from Crypto.Cipher import AES


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

def unpadpkcs7(s):
    i = ord(s[-1])
    return s[0:-i]

def aes_ecb_decrypt(cipher, key):
    aes = AES.new(key, AES.MODE_ECB, "\x00" * 16)
    return aes.decrypt(cipher)

Challenge 8

def probably_ecb(cipher):
    blocks = [cipher[i:i+16] for i in range(0, len(cipher), 16)]
    for i, block1 in enumerate(blocks):
        for j, block2 in enumerate(blocks):
            if block1 == block2 and i != j:
                return True
    return False

Testing

To test it all up, here is the code:

#!/usr/bin/env python

import binascii
from base64 import b64decode
from test import support
import unittest
from ch01 import convert_hex_to_base64
from ch02 import xor_two_strings
from ch03 import chi_squared, bruteforce, not_so_good_freq
from ch05 import repeating_xor
from ch06 import simulation, hamming_distance, transpose
from ch07 import aes_ecb_decrypt, unpadpkcs7
from ch08 import probably_ecb
from collections import Counter


class Set1(unittest.TestCase):
    poem = "I'm back and I'm ringin' the bell \nA rockin' on the mike while the fly girls yell \nIn ecstasy in the back of me \nWell that's my DJ Deshay cuttin' all them Z's \nHittin' hard and the girlies goin' crazy \nVanilla's on the mike, man I'm not lazy. \n\nI'm lettin' my drug kick in \nIt controls my mouth and I begin \nTo just let it flow, let my concepts go \nMy posse's to the side yellin', Go Vanilla Go! \n\nSmooth 'cause that's the way I will be \nAnd if you don't give a damn, then \nWhy you starin' at me \nSo get off 'cause I control the stage \nThere's no dissin' allowed \nI'm in my own phase \nThe girlies sa y they love me and that is ok \nAnd I can dance better than any kid n' play \n\nStage 2 -- Yea the one ya' wanna listen to \nIt's off my head so let the beat play through \nSo I can funk it up and make it sound good \n1-2-3 Yo -- Knock on some wood \nFor good luck, I like my rhymes atrocious \nSupercalafragilisticexpialidocious \nI'm an effect and that you can bet \nI can take a fly girl and make her wet. \n\nI'm like Samson -- Samson to Delilah \nThere's no denyin', You can try to hang \nBut you'll keep tryin' to get my style \nOver and over, practice makes perfect \nBut not if you're a loafer. \n\nYou'll get nowhere, no place, no time, no girls \nSoon -- Oh my God, homebody, you probably eat \nSpaghetti with a spoon! Come on and say it! \n\nVIP. Vanilla Ice yep, yep, I'm comin' hard like a rhino \nIntoxicating so you stagger like a wino \nSo punks stop trying and girl stop cryin' \nVanilla Ice is sellin' and you people are buyin' \n'Cause why the freaks are jockin' like Crazy Glue \nMovin' and groovin' trying to sing along \nAll through the ghetto groovin' this here song \nNow you're amazed by the VIP posse. \n\nSteppin' so hard like a German Nazi \nStartled by the bases hittin' ground \nThere's no trippin' on mine, I'm just gettin' down \nSparkamatic, I'm hangin' tight like a fanatic \nYou trapped me once and I thought that \nYou might have it \nSo step down and lend me your ear \n'89 in my time! You, '90 is my year. \n\nYou're weakenin' fast, YO! and I can tell it \nYour body's gettin' hot, so, so I can smell it \nSo don't be mad and don't be sad \n'Cause the lyrics belong to ICE, You can call me Dad \nYou're pitchin' a fit, so step back and endure \nLet the witch doctor, Ice, do the dance to cure \nSo come up close and don't be square \nYou wanna battle me -- Anytime, anywhere \n\nYou thought that I was weak, Boy, you're dead wrong \nSo come on, everybody and sing this song \n\nSay -- Play that funky music Say, go white boy, go white boy go \nplay that funky music Go white boy, go white boy, go \nLay down and boogie and play that funky music till you die. \n\nPlay that funky music Come on, Come on, let me hear \nPlay that funky music white boy you say it, say it \nPlay that funky music A little louder now \nPlay that funky music, white boy Come on, Come on, Come on \nPlay that funky music \n"
    def test_ch1(self):
        self.assertEqual(convert_hex_to_base64("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d"), "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t")


    def test_ch2(self):
        self.assertEqual( xor_two_strings("1c0111001f010100061a024b53535009181c", "686974207468652062756c6c277320657965"), "746865206b696420646f6e277420706c6179")

    def test_ch3(self):
        ch = "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
        res = chi_squared(ch)
        results = []
        for key in res:
            results.append(xor_two_strings(ch, binascii.hexlify(chr(key[0])*len(ch))).decode("hex"))
        self.assertIn("Cooking MC's like a pound of bacon", results)

    def test_ch4(self):
        l = []
        with open("4.txt") as myfile:
            f = myfile.read()
            for line in f.splitlines():
                for result, i in bruteforce(line):
                    l.append(result)
        self.assertIn("Now that the party is jumping\n", l)

    def test_ch5(self):
        f = """Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal"""
        r = """0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f"""
        self.assertEqual(binascii.hexlify(repeating_xor(f, "ICE")), r)

    def test_ch6(self):
        with open("6.txt", "r") as myfile:
            cipher = b64decode(myfile.read())

        self.assertEqual(hamming_distance("this is a test", "wokka wokka!!!"), 37)
        l = []
        for _ in range(50):
            l.append(simulation(cipher))
        keysize = Counter(l).most_common()[0][0]

        self.assertEqual(keysize, 29)
        self.assertEqual(transpose("abcdefg", 2), "acegbdf\x00")

        transposed = transpose(cipher, keysize)
        recovered_key = ""
        for block in [transposed[i:i+(len(transposed)/keysize)] for i in
                      range(0, len(transposed), len(transposed)/keysize)]:
            recovered_key += chr(not_so_good_freq(binascii.hexlify(block))[0][0])
        self.assertEqual(recovered_key, "Terminator X: Bring the noise")
        self.assertEqual(repeating_xor(cipher, recovered_key), self.poem)


    def test_ch7(self):        
        with open("7.txt", "r") as myfile:
            cipher = b64decode(myfile.read())
        out = unpadpkcs7(aes_ecb_decrypt(cipher, "YELLOW SUBMARINE"))
        self.assertEqual(out, self.poem)

    def test_ch8(self):
        with open("8.txt", "r") as myfile:
            lines = myfile.read().splitlines()
        for line in lines:
            if probably_ecb(binascii.unhexlify(line)):
                self.assertEqual(line, "d880619740a8a19b7840a8a31c810a3d08649af70dc06f4fd5d2d69c744cd283e2dd052f6b641dbf9d11b0348542bb5708649af70dc06f4fd5d2d69c744cd2839475c9dfdbc1d46597949d9c7e82bf5a08649af70dc06f4fd5d2d69c744cd28397a93eab8d6aecd566489154789a6b0308649af70dc06f4fd5d2d69c744cd283d403180c98c8f6db1f2a3f9c4040deb0ab51b29933f2c123c58386b06fba186a")
                break

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