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)

Author: Mohamed Aziz Knani

Date: 2019-11-21 Thu 06:21

Emacs 26.3 (Org mode 9.2.6)

Validate

hacker emblem