CSCAMP CTF Quals 2013 - Crypto 300 - [Team SegFault]

We were given about 12 encrypted messages and the challenge description said Many Time Pad and 12th message holds the flag. Below is the encryption algorithm

import os

key = os.urandom(1024)
messages = [message.rstrip('\n') for message in open("messages")]

def xor_string(x, y):

    if len(x) > len(y):
        return ''.join([chr(ord(z) ^ ord(p)) for (z, p) in zip(x[:len(y)], y)])
    else:
        return ''.join([chr(ord(z) ^ ord(p)) for (z, p) in zip(x, y[:len(x)])])

print key.encode('hex')

for i in range(0, len(messages)):
    print "Message #{0}: {1}".format(i, xor_string(key, messages[i]).encode('hex'))

The messages are encrypted by XOR encryption using randomly chosen key whose length is equal to length of plain text. To decrypt the flag message we decided to bruteforce the key. Below is the idea:

[*] Bruteforce key in range of 0 to 0xff for each byte of 12 cipher texts
[*] See if the chosen key is able to decrypt a byte of cipher text to a printable character in charset [space, 0-9, A-Z, a-z] for all 12 given cipher texts
[*] Such a chosen key is a possible candidate to be final key

The above method created some collisions but was good enough to retrieve the flag. Below is the code

#!/usr/bin/env python
# cry300.py

ciphers = ['2838febbef072500b57a8e41119b051ad0174127b3f11208bd094d092bb9b6edfe0b655377a1dd6ccb5870d3ae250d91b9d097b5d13b569545c9fd0f3940195356d89ed9a99140b44fca2e5dffe40f37f07a',
'3a39badcc70c6143b47e981500974057dd100626a9f10e09af5d021731b9a8e1ec4c671c71abdd79cd5970fdac204a90f0c998f1f33012c14edeb802244215071edbccdeaddc14b14b862f1cece10572e56c80fb267a0a0b93e0458fdc3059c95ba33af02189', '2b23eebbdf0d6141b47ed9121081051ac816473be7a50e05fc17180438f4a4e2f90b6d5a38829269855523b4a0224e9aa2c297bfd37f028e0dd8af16244f514611df85d8b7c514a8428f271cfae70831eb298ef52772431cc1f65198d1740dc957ed29eb',
'2838febbef072500a57a950d0097404ed41b062bb5a8460cbd1309401af8b3f8e50b63527ce58965c01c37f5b5294887b9c899f1c030118459c4b8117048170702d68996b3d040b958996a5fece30d37e72985ff6a4c4f0992a54595dd743ece5aa33df933c489caa16c8290717a85d2d470f6a6529d', '2f39e8bbdc002452a33b9012459d0f1ace1b553fa2b21240b31b4d103aebb2e3e358224b71b1952de25334', '213fe9bbc00d2044e67a9705459b09499c164726b5a24617b90f084028f1a8f8e80b6e5573a0dd7aca533cb4a0320d82b8cf8ab4943e05c15ec2b21470461f4356d685c5e4d44db959ca3d59ffea4133f0298cba2c734b0584a54b9d993210d35b', '2838febbdc002400a36d9c0f0c9d071add10426fb3b90340b1121f0e36f7a6acfa4e705938b19568855a39f2b5290d91b1df', '2533eebbce092d4ce67a95120ad31355d11b0620a1f11208b95d050131fda7f9e15822537ee58d78d74c3fe7a4614b9aa28696b4c67f178f498cb1063151140702d689dbe4c55cbd5eca3954e8af0c33fa298af62f7e444895ed4196993517c51ef12bfa318f9882a87dd0d96b3586', '3d3effbbe4271364e6739c001797404ed41b0639a8b80505fc120b4026f6b4fead5c6d4e7cb6dd6ccb5870e3a0320d82a2c98ab9943e18850ddfaa022242515417c785d8a3', '3d3effbbe4271364e662961417d32755d85e5127aeb20e40bb1208137ffba4eae259671c61aa882dcd5970e7a9204199f0c097b6dc2b568742defd1a3f52514615dd83c4a0d85abb0a9e251cece30d72f7618cee6a774f4885ec40dbdf3b0b8147ec3bb82d8adde7a761d28d253897d5c822f4e94496af2235eb4bab26',
'2b23eebbc91b6146a969d9180a86404ec90c486fbebe1340bd1309402bf8aae9ad526d496ae59762d04e3ef1b861449ba4c9dea5dc3a569644c0b90622491454059e8ecfe4c55cb90a9d2b45ade00772f76188ba187a4e4892e045', '2437e3f9cd48384fb3718c1211950f4fd21a4b2ea9a80d05a50e4d092cb9b5e4e80b63526bb2987f85453fe1e1324890bb']

# possible charset space, 0-9, A-Z, a-z
charset = [32] + range(48, 58) + range(65, 91) + range(97, 123)
poss = []
exception = False

# for all characters in cipher text of flag message
for i in range(len(ciphers[11].decode('hex'))): 
    sol = []
    for key in range(256):   # for all possible keys
        pad_size = 0
        for cipher in range(len(ciphers)): # for each cipher text
            try:
                byte = ord(ciphers[cipher].decode('hex')[i])
            except IndexError:
                exception = True
                continue
            if (byte ^ key) in charset:  # check if a key can decrypt to printable text
                pad_size += 1
                if not exception:
                    if pad_size == len(ciphers):
                        sol.append(chr(byte ^ key))
                else:
                    if pad_size == len(ciphers) - 1:
                        sol.append(chr(byte ^ key))
    poss.append(sol)
print poss

[ctf@renorobert CSCAMP]$ python cry300.py
[['m', 'n', 'h', 'i', 'j', 'M', 'N', 'H', 'I', 'J'], ['g', 'f', 'e', 'c', 'b', 'a', 'm', 'l', 'G', 'F', 'E', 'C', 'B', 'A', 'M', 'L'], ['i', 'h', 'o', 'n', 'l', 'y'], ['q', 'p', 's', 'r', 'u', 't', 'w', 'v', 'b'], ['H', 'K', 'E', 'G', 'F', 'A', 'h', 'k', 'e', 'g', 'f', 'a'], [' '], ['y', 'l', 'm', 'o'], ['o', 'z', 'y'], ['u', 'c', 'b'], ['z', 'j'], ['u'], ['s', 'e'], ['t'], ['f'], ['o'], ['m', 'l', 'b', 'u'], ['n'], ['d'], ['m', 'y'], ['a'], ['n'], ['y'], ['k', 'y', 'z'], ['e'], ['l', 'n', 'y'], ['s'], [' '], ['i'], ['s'], [' '], ['u', 't', 'w', 'v', 'p', 'e', 'k', 'U', 'T', 'W', 'V', 'P', 'E', 'K'], ['h'], ['e'], [' ', '1', '0', '6', '5', '4'], ['a', 'w', 't'], ['n'], ['s'], ['w', 'a'], ['e'], ['r'], [' '], ['y'], ['o'], ['e', 'd', 'u'], [' '], ['s', 'b', 'c', 'a'], ['e'], ['S', 'X', 'Y', 'B', 'C', 'D', 'E', 'F', 'G', 's', 'x', 'y', 'b', 'c', 'd', 'e', 'f', 'g'], ['z', 's', 'r', 'k']]

Some characters decrypted without collisions, rest of the characters were guessed as youjustfoundmanykeys is the answer you seek. Flag for the challenge is youjustfoundmanykeys