Tuesday, November 19, 2013

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

We were given two files for the challenge - public key and encrypted message. Reading the public key with openssl we got
[ctf@renorobert 400]$ openssl rsa -in public.pem -pubin -text -noout 
Public-Key: (768 bit)
Modulus:
    00:ca:d9:84:55:7c:97:e0:39:43:1a:22:6a:d7:27:
    f0:c6:d4:3e:f3:d4:18:46:9f:1b:37:50:49:b2:29:
    84:3e:e9:f8:3b:1f:97:73:8a:c2:74:f5:f6:1f:40:
    1f:21:f1:91:3e:4b:64:bb:31:b5:5a:38:d3:98:c0:
    df:ed:00:b1:39:2f:08:89:71:1c:44:b3:59:e7:97:
    6c:61:7f:cc:73:4f:06:e3:e9:5c:26:47:60:91:b5:
    2f:46:2e:79:41:3d:b5
Exponent: 65537 (0x10001)
[ctf@renorobert 400]$ openssl rsa -in public.pem -pubin -text -noout | grep '^ ' | tr -dc '[0-9a-f]'
00cad984557c97e039431a226ad727f0c6d43ef3d418469f1b375049b229843ee9f83b1f97738ac274f5f61f401f21f1913e4b64bb31b55a38d398c0dfed00b1392f0889711c44b359e7976c617fcc734f06e3e95c26476091b52f462e79413db5
Its a RSA-768 and the N value is already factorized. Factors are available publicly
p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
Generate private key for p and q values and decrypt the file
sage: p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
sage: q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
sage: phi_n = (p-1) * (q-1)
sage: e = 65537
sage: d = inverse_mod(e, phi_n)
sage: d
703813872109751212728960868893055483396831478279095442779477323396386489876250832944220079595968592852532432488202250497425262918616760886811596907743384527001944888359578241816763079495533278518938372814827410628647251148091159553
>>> from Crypto.PublicKey import RSA
>>> keypair = RSA.generate(1024)
>>> keypair.n = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
>>> keypair.e = 65537
>>> keypair.d = 703813872109751212728960868893055483396831478279095442779477323396386489876250832944220079595968592852532432488202250497425262918616760886811596907743384527001944888359578241816763079495533278518938372814827410628647251148091159553
>>> keypair.p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
>>> keypair.q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
>>> private = open('private.pem', 'w')
>>> private.write(keypair.exportKey())
>>> private.close()
[ctf@renorobert 400]$ openssl rsautl -decrypt -in message.enc -out /dev/tty -inkey private.pem
F4ct0r!zaTi0N
Flag for the challenge is F4ct0r!zaTi0N

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