Cryptopals Set 3

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

rand_key = None

# Slight modification of the previously defined aes_128_cbc_dec function.
# We don't unpad the decrypted ciphertext in this method.
def aes_128_cbc_dec(ciphertext, key, iv):
    plaintext = bytearray(len(ciphertext))
    prev_block = iv
    for i in range(0, len(ciphertext), AES.block_size):
        plaintext[i: i + AES.block_size] = xor(
            aes_128_ecb_dec(bytes(ciphertext[i: i + AES.block_size]), key),
            prev_block
        )
        prev_block = ciphertext[i: i + AES.block_size]
    return plaintext

def cbc_enc_random_string(input_strings):
    global rand_key
    rand_key = random_key(AES.block_size)
    input_string = input_strings[randint(0, len(input_strings) - 1)]
    iv = random_key(AES.block_size)
    return aes_128_cbc_enc(input_string, bytes(rand_key), iv), iv

def padding_oracle(ciphertext, iv):
    input_string = aes_128_cbc_dec(ciphertext, bytes(rand_key), iv)
    try:
        unpad_valid_pkcs7(input_string)
        return True
    except:
        return False

def crack_block(block, iv):
    plaintext_block = bytearray()
    start_guess = 0
    while len(plaintext_block) < AES.block_size:
        for guess in range(start_guess, 256):
            padding = len(plaintext_block) + 1
            # Copy the IV so we don't corrupt it for future guesses
            corrupted_iv = bytearray(iv)
            for byte in range(1, padding + 1):
                # Use the "correct" guesses of plaintext block bytes
                if byte < padding:
                    corrupted_iv[-byte] =  bytes(xor(
                        xor(
                            bytearray([iv[-byte]]),
                            bytearray(chr(plaintext_block[-byte]))
                        ),
                        bytearray(chr(padding))
                    ))
                # Guess the correct byte
                else:
                    corrupted_iv[-byte] =  bytes(xor(
                        xor(bytearray([iv[-byte]]), bytearray(chr(guess))),
                        bytearray(chr(padding))
                    ))
            if padding_oracle(block, corrupted_iv):
                # If the padding oracle doesn't complain... we've guessed the
                # correct byte!
                plaintext_block = bytearray(chr(guess)) + plaintext_block
                start_guess = 0
                break
        else:
            # If we cannot find a correct padding, the guess for the previous
            # byte was incorrect... so try another one!
            try:
                start_guess = int(plaintext_block[0]) + 1
                plaintext_block = plaintext_block[1:]
            except:
                # This occurs if the last ciphertext block is just a padding
                # block... I don't know why my encryption is sometimes adding
                # an extra block
                return bytearray()
    return plaintext_block

def crack(ciphertext, iv):
    ciphertext = iv + ciphertext
    plaintext = ''
    for i in range(len(ciphertext) / AES.block_size):
        # We only really need to pass two blocks to the padding oracle...
        # The block to the decrypt, and the one before it which we corrupt
        plaintext += crack_block(
            ciphertext[(i + 1) * AES.block_size: (i + 2) * AES.block_size],
            ciphertext[i * AES.block_size: (i + 1) * AES.block_size]
        )
    return unpad_valid_pkcs7(plaintext)

ciphertext, iv = cbc_enc_random_string(input_strings)
plaintext = crack(ciphertext, iv)
print plaintext

def aes_128_ctr_keystream_block(key, nonce, block_count):
    return aes_128_ecb_enc(
        # '<Q' format is a little endian unsigned long long (64 bits)
        bytearray(pack('<Q', nonce)) + bytearray(pack('<Q', block_count)),
        key
    )

def aes_128_ctr_keystream_generator(key, nonce):
    block_count = 0
    while True:
        x = aes_128_ctr_keystream_block(bytes(key), nonce, block_count) 
        for byte in x:
            yield byte
        block_count += 1

def aes_128_ctr(buffer, key, nonce):
    def xor(b1, b2):
        b = bytearray()
        for byte in b1:
            # Note, we need to use b2.next() as it's a generator
            b.append(ord(byte) ^ b2.next())
        return b
    return xor(buffer, aes_128_ctr_keystream_generator(key, nonce))

# Don't forget to decode this string!
ciphertext = bytearray("L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==").decode("base64")
print aes_128_ctr(
    ciphertext,
    pad_pkcs7(bytearray("YELLOW SUBMARINE"), AES.block_size),
    0
)
# Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby

def crack_keystream(ciphertexts):
    keystream = bytearray()
    max_ciphertext_length = max(map(len, ciphertexts))
    for i in range(max_ciphertext_length):
        bytes_at_index = map(
            ord, # Convert bytes to ints for XOR'ing
            filter(
                lambda x: x, # Filter out empty bytes
                map(
                    lambda x: x[i:i + 1], # Try to get the byte at i index
                    ciphertexts
                )
            )
        )
        max_score = None
        key = None
        for guess in range(256):
            b2 = [guess] * len(bytes_at_index)
            decrypted_bytes = bytes(xor(bytes_at_index, b2))
            pscore = score(decrypted_bytes)
            if pscore > max_score or not max_score:
                max_score = pscore
                key = chr(guess)
        keystream.append(key)
    return keystream

key = random_key(AES.block_size)
FIXED_NONCE = 0
ciphertexts = []
for encoded_plaintext in list(open("19.txt", "r")):
    plaintext = bytearray(encoded_plaintext).decode("base64")
    ciphertexts.append(aes_128_ctr(plaintext, key, FIXED_NONCE))

keystream = crack_keystream(ciphertexts)
for ciphertext in ciphertexts:
    print xor(ciphertext, keystream)
# i have met them at close of dau                            
# coming with vivid faces                                    
# from counter or desk among greu                            
# eighteenth-century houses.                                 
# i have passed with a nod of thidhi 6                       
# or polite meaningless words,                               
# or have lingered awhile and sae                            
# polite meaningless words,                                  
# and thought before I had done                              
# of a mocking tale or a gibe                                
# to please a companion                                      
# around the fire at the club,                               
# being certain that they and I                              
# but lived where motley is worn6                            
# all changed, changed utterly:                              
# a terrible beauty is born.                                 
# that woman's days were spent                               
# in ignorant good will,                                     
# her nights in argument                                     
# until her voice grew shrill.                               
# what voice more sweet than her                             
# when young and beautiful,                                  
# she rode to harriers?                                      
# this man had kept a school                                 
# and rode our winged horse.                                 
# this other his helper and frieb                            
# was coming into his force;                                 
# he might have won fame in the i*d                          
# so sensitive his nature seemed                             
# so daring and sweet his thoughxj                           
# this other man I had dreamed                               
# a drunken, vain-glorious lout.                             
# he had done most bitter wrong                              
# to some who are near my heart,                             
# yet I number him in the song;                              
# he, too, has resigned his part                             
# in the casual comedy;                                      
# he, too, has been changed in he7 x4                        
# transformed utterly:                                       
# a terrible beauty is born.

key = random_key(AES.block_size)
FIXED_NONCE = 0
ciphertexts = []
for encoded_plaintext in list(open("20.txt", "r")):
    plaintext = bytearray(encoded_plaintext).decode("base64")
    ciphertexts.append(aes_128_ctr(plaintext, key, FIXED_NONCE))

# Trim the ciphertexts to the length of the least long one
min_ciphertext_length = min(map(len, ciphertexts))
ciphertexts = [bytes(ciphertext[:min_ciphertext_length]) for ciphertext in ciphertexts]
b = bytearray("".join(ciphertexts))
print repr(b)

block_bytes = [[] for _ in range(min_ciphertext_length)]
for i, byte in enumerate(b):
    block_bytes[i % min_ciphertext_length].append(byte)

keys = ""
for bbytes in block_bytes:
    keys += break_single_key_xor(bbytes)[0]
key = bytearray(keys * len(b))
plaintext = bytes(xor(b, key))

print plaintext
# N'm rated "R"...this is a warning, ya better void / PDuz I came back to attack others in spite- ...

seed = None

def get_rand_int():
    # Use Python's PRNG to sleep for a random time period
    sleep(randint(40, 1000))
    # For testing purposes
    global seed
    seed = int(time())
    rand_int = MT19937(seed).extract_number()
    sleep(randint(40, 1000))
    return rand_int

def crack_seed():
    rand_int = get_rand_int()
    current_time = int(time())
    for seed in range(current_time, current_time - 2500, -1):
        if MT19937(seed).extract_number() == rand_int:
            return seed
    raise Exception('Could not crack MT19937 seed.')

print crack_seed()
# 1499970065

def unshift_right_xor(value, shift):
    result = 0
    for i in range(32 / shift + 1):
        result ^= value >> (shift * i)
    return result

# Borrowed from https://jazzy.id.au/2010/09/22/cracking_random_number_generators_part_3.html
def unshift_left_mask_xor(value, shift, mask):
    result = 0
    for i in range(0, 32 / shift + 1):
        part_mask = (0xffffffff >> (32 - shift)) << (shift * i)
        part = value & part_mask
        value ^= (part << shift) & mask
        result |= part
    return result

def untemper(y):
    value = y
    value = unshift_right_xor(value, 18)
    value = unshift_left_mask_xor(value, 15, 4022730752)
    value = unshift_left_mask_xor(value, 7, 2636928640)
    value = unshift_right_xor(value, 11)
    assert temper(value) == y
    return value

def copy_MT19937_prng(prng):
    untempered_values = []
    for i in range(624):
        untempered_values.append(untemper(prng.extract_number()))
    copied_prng = MT19937.create_from_state(untempered_values)
    return copied_prng

def assert_prngs_equal(prng1, prng2):
    for _ in range(1000):
        assert prng1.extract_number() == prng2.extract_number()

prng = MT19937(19) # Arbitrary seed
copied_prng = copy_MT19937_prng(prng)
assert_prngs_equal(prng, copied_prng)

def trivial_keystream_generator(seed):
    prng = MT19937(seed)
    while True:
        # Generate bytes
        yield prng.extract_number() % pow(2, 8)

def trivial_stream_cipher(buffer, seed):
    def xor(b1, b2):
        b = bytearray()
        for byte in b1:
            b.append(byte ^ b2.next())
        return b
    return xor(buffer, trivial_keystream_generator(seed))

plaintext = bytearray("MY NAME IS MICHAEL")
# Create a 16-bit seed
seed = randint(0, pow(2, 16))
ciphertext = trivial_stream_cipher(plaintext, seed)
assert plaintext == trivial_stream_cipher(ciphertext, seed)

def crack(ciphertext):
    for seed in range(pow(2, 16)):
        possible_plaintext = trivial_stream_cipher(ciphertext, seed)
        if possible_plaintext[-14:] == bytearray(["A"] * 14):
            return seed

plaintext = random_key(randint(0, 256)) + bytearray(["A"] * 14)
seed = randint(0, pow(2, 16))
ciphertext = trivial_stream_cipher(plaintext, seed)
assert seed == crack(ciphertext)

def password_token_product_of_MT19937(password_token):
    current_time = int(time())
    MIN_IN_SEC = 60
    # Assume the password token was generated within the last 10 minutes
    for seed in range(current_time - 10 * MIN_IN_SEC, current_time):
        # Try extracting 1000 random numbers from the PRNG
        prng = MT19937(seed)
        for _ in range(1000):
            if password_token == prng.extract_number():
                return True
    return False

prng = MT19937(int(time()))
for _ in range(randint(0, 1000)):
    password_token = prng.extract_number()
assert password_token_product_of_MT19937(password_token)