Saturday, January 18, 2014

Hack You CTF 2014 - Crypto 400 - CRYPTONET - [Team SegFault]

Challenge description says about use of strange protocol using RSA cryptosystem. We also have access to the client source code and a pcap file. Reading the code we could see that, client receives n and e value from remote system. This value is used to encrypt the message before sending it. The protocol has following format
Receive:
[2 bytes specifying the size zlib compressed e value][zlib compressed e value] [2 bytes specifying the size zlib compressed n value][zlib compressed e value]
Send:
[2 bytes specifying the size zlib compressed m^e mod n] [zlib compressed m^e mod n]
Analyzing the pcap file we could see that client has communicated with some 19 remote machines. First we must extract the values of e and n for all the communication. Initially I checked if those n values are having some common prime, but all the gcd checks ended up as relatively prime. e value was small, 17. Further reading on use of low public exponent took me to Hastad's Broadcast Attack. Code to solve the challenge using Hastad's Broadcast Attack is below:
#!/usr/bin/env python

from scapy.all import *
from sage.all import *
import zlib
import struct

PA = 24L
packets = rdpcap('packets.pcap')
client = '192.168.1.5'
size = 2 # size of e and n is packed into 2 bytes
list_n = []
list_m = []

for packet in packets:
    if packet[TCP].flags == PA:
       if packet.dst == client:
           src = packet[IP].src
           raw_data = packet[TCP].load

           size_e = struct.unpack('!H', raw_data[:size])[0] 
           e = int(zlib.decompress(raw_data[size: size + size_e]))

           size_n = struct.unpack('!H', raw_data[size + size_e: 2 * size + size_e])[0]
           n = int(zlib.decompress(raw_data[2 * size + size_e: ]))
           list_n.append(n)

        if packet[IP].src == client:
            raw_data = packet[TCP].load
            size_m = struct.unpack('!H', raw_data[:size])[0]
            m = int(zlib.decompress(raw_data[size: size + size_m]))
            list_m.append(m)

e_17 = crt(list_m, list_n)
factors = prime_factors(e_17)
enc_message = 1
for num in factors:
    enc_message *= num

print hex(enc_message).decode('hex')
# 'Secret message! CTF{336b2196a2932c399c0340bc41cd362d}\n'
Flag for the challenge is CTF{336b2196a2932c399c0340bc41cd362d}

Hack You CTF 2014 - Crypto 300 - Matrix - [Team SegFault]

We were given source code of encryptor and an encrypted file flag.wmv.out. The encryption algorithm performs the following operation

[*] Generates a 4x4 matrix as key using randint() function. An secret password is used as seed, which we dont know
[*] File is padded with NUL such that size(file) % 16 == 0
[*] Each 16 bytes of file is converted to 4x4 matrix and multiplied with key
[*] Each element of resultant 4x4 matrix is packed into 2 bytes of data and written to file

First we should find the key to perform decryption. The file extension leaves a clue wmv. Using wmv header as known plain text and encrypted header as cipher text, the key could be found as wmv_header.inverse() * enc_header. Once the key found, we have to write decryption routine such that encrypted file is processed in blocks for 32 bytes in a 4x4 matrix. Below is the code to solve this
#!/usr/bin/env python

from sage.all import *
import struct

wmv_header = [[0x30, 0x26, 0xB2, 0x75], [0x8E, 0x66, 0xCF, 0x11], [0xA6, 0xD9, 0x00, 0xAA], [0x00, 0x62, 0xCE, 0x6C]]

def Str2matrix(s):
    #convert string to 4x4 matrix
    return [map(lambda x : ord(x), list(s[i:i+4])) for i in xrange(0, len(s), 4)]
def Matrix2str(m):
    #convert matrix to string
    return ''.join(map(lambda x : ''.join(map(lambda y : struct.pack('!B', y), x)), m))
def PackedStr2matrix(s):
    matrix = [0] * 16 
    for i in range(0, len(s), 2):
        matrix[i/2] = struct.unpack('!H', s[i:i+2])[0]
    matrix = [matrix[i:i+4] for i in range(0,len(matrix), 4)]
    return matrix
def Multiply(A,B):
    #multiply two 4x4 matrix
    C = [[0 for i in xrange(4)] for j in xrange(4)]
    for i in xrange(4):
        for j in xrange(4):
            for k in xrange(4):
                C[i][j] += A[i][k] * B[k][j]
    return C
        
header =  matrix(wmv_header)
encrypted_wmv = open('flag.wmv.out','rb').read()
size = struct.unpack('!I', encrypted_wmv[:4])
enc_header = encrypted_wmv[4:36]
enc_header = matrix(PackedStr2matrix(enc_header))

# sage: header = matrix([[48, 38, 178, 117], [142, 102, 207, 17], [166, 217, 0, 170], [0, 98, 206, 108]])
# sage: enc_header = matrix([[6025, 10758, 8274, 14059], [10718, 11769, 5025, 15260], [19537, 18796, 14142, 15035], [7648, 8842, 7254, 17852]])
# sage: header.inverse() * enc_header
# [31 51 20  0]
# [53 10  6 45]
# [ 3 13  3 49]
# [17 48 56 31]
# sage: key.inverse()
# [  5732/2519421  96221/5038842 -41017/2519421 -10009/5038842]
# [ 65399/2519421 -67381/5038842  44957/2519421 -44311/5038842]
# [-49681/2519421  22679/5038842 -51064/2519421 128507/5038842]
# [-14660/2519421  10597/5038842  45127/2519421   4501/5038842]

key = header.inverse() * enc_header
key_inverse = key.inverse()

out = open('flag.wmv','wb')
encrypted_wmv = encrypted_wmv[4:]

for i in xrange(0, len(encrypted_wmv), 32):
    unpacked_data = matrix(PackedStr2matrix(encrypted_wmv[i:i+32]))
    decrypted = unpacked_data * key_inverse
    out.write(Matrix2str(decrypted))
out.close()

# CTF{b699a72e2692d16f65ec9626055aa740}
We get a decrypted wmv file which has the flag.
root@sagepc:~ $file flag.wmv
flag.wmv: Microsoft ASF
Flag for the challenege is CTF{b699a72e2692d16f65ec9626055aa740}

Hack You CTF 2014 - Crypto 200 - Hashme - [Team SegFault]

We have access to the source code of a remote service which allows users to register and login.

Register:
[*] Everytime a new login is created, hash of string SALT+login={username}&role=anonymous is computed
[*] Computed hash is appended to login={username}&role=anonymous, encrypted with a key using xor and then encoded using base64
[*] The generated base64 string is our certificate for login

Login:
[*] The user provided certificate is base64 decoded and decrypted using xor
[*] Hash of SALT+login={username}&role=anonymous is computed and checked with the user supplied hash. If it matches, then login is provided
[*] Administrator gets access to flag file

We have to find a way to get administrator access by forging the request. Ok, first we have to find the key used in the remote machine. This can be done by registering a user with long username
client sends: username as "A"*1000 # login={username}&role=anonymous is our known plain text
server sends: XOR(login={username}&role=anonymous + HASH) # cipher text
Using the plain text - cipher text combination, the KEY can be found.
Now we have to find a way to compute valid hash without knowing the SALT. Thanks to my friend who pointed me out the Hash Length Extension attack. The final 32 byte of hash comes from A,B,C and D of used hash algorithm
A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
X = [int(0xFFFFFFFF * sin(i)) & 0xFFFFFFFF for i in xrange(256)]

for i,ch in enumerate(s):
    k, l = ord(ch), i & 0x1f
    A = (B + ROL(A + F(B,C,D) + X[k], l)) & 0xFFFFFFFF
    B = (C + ROL(B + G(C,D,A) + X[k], l)) & 0xFFFFFFFF
    C = (D + ROL(C + H(D,A,B) + X[k], l)) & 0xFFFFFFFF
    D = (A + ROL(D + I(A,B,C) + X[k], l)) & 0xFFFFFFFF

return ''.join(map(lambda x : hex(x)[2:].strip('L').rjust(8, '0'), [B, A, D, C]))
We can use the HASH(login={username}&role=anonymous) sent by remote service as initial values, then compute the hash values of newly appended string without knowing the SALT. But one value we need to know is the length of SALT. This can be easily bruteforced.
Below is the code for checking login and administrator.
if hashme(SALT + auth_str) == hashsum:  
    data = parse_qs(auth_str, strict_parsing = True)
    print '[+] Welcome, %s!' % data['login'][0]
    if 'administrator' in data['role']:
    flag = open('flag.txt').readline()
    print flag
We need a craft a input as login={username}&role=anonymous&role=administrator so that parse_qs() sets data['role'] to ['anonymous','administrator'] and if 'administrator' in data['role'] is passed. Finally, find the valid hash value for string login={username}&role=anonymous&role=administrator to get the flag. Below is the code used
#!/usr/bin/env python

import base64
from math import sin

def hashme(length, s, state):
    # my secure hash function
    def F(X,Y,Z):
        return ((~X & Z) | (~X & Z)) & 0xFFFFFFFF
    def G(X,Y,Z):
        return ((X & Z) | (~Z & Y)) & 0xFFFFFFFF
    def H(X,Y,Z):
        return (X ^ Y ^ Y) & 0xFFFFFFFF
    def I(X,Y,Z):
        return (Y ^ (~Z | X)) & 0xFFFFFFFF
    def ROL(X,Y):
        return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF

    #A = 0x67452301
    #B = 0xEFCDAB89
    #C = 0x98BADCFE
    #D = 0x10325476
    B = int(hash[:8],16)
    A = int(hash[8:16],16)
    D = int(hash[16:24],16)
    C = int(hash[24:],16)

    X = [int(0xFFFFFFFF * sin(i)) & 0xFFFFFFFF for i in xrange(256)]

    for i,ch in enumerate(s):
        k, l = ord(ch), (i+length) & 0x1f
        A = (B + ROL(A + F(B,C,D) + X[k], l)) & 0xFFFFFFFF
        B = (C + ROL(B + G(C,D,A) + X[k], l)) & 0xFFFFFFFF
        C = (D + ROL(C + H(D,A,B) + X[k], l)) & 0xFFFFFFFF
        D = (A + ROL(D + I(A,B,C) + X[k], l)) & 0xFFFFFFFF

    return ''.join(map(lambda x : hex(x)[2:].strip('L').rjust(8, '0'), [B, A, D, C]))



login = "A"*1000 
user_data = 'login=%s&role=anonymous' % login

encoded_user_data = "RK5yZMJaRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJkUZfC1QZOZsfcZlXz4V1qj5TTm1j2pJnepqTLNKoeqfSlYQa9IahiQhPbSkaYBUTO0mRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJkUZfC1QZOZsfcZlXz4V1qj5TTm1j2pJnepqTLNKoeqfSlYQa9IahiQhPbSkaYBUTO0mRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJkUZfC1QZOZsfcZlXz4V1qj5TTm1j2pJnepqTLNKoeqfSlYQa9IahiQhPbSkaYBUTO0mRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJkUZfC1QZOZsfcZlXz4V1qj5TTm1j2pJnepqTLNKoeqfSlYQa9IahiQhPbSkaYBUTO0mRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJkUZfC1QZOZsfcZlXz4V1qj5TTm1j2pJnepqTLNKoeqfSlYQa9IahiQhPbSkaYBUTO0mRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJkUZfC1QZOZsfcZlXz4V1qj5TTm1j2pJnepqTLNKoeqfSlYQa9IahiQhPbSkaYBUTO0mRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJiIqUgB0GMZDU+ldcxAh5N2LaUrM/hIw788YPMU42cruOSc3SaRv/lVRTMODTfQl" 

decoded_user_data = base64.b64decode(encoded_user_data)

key = []
for i in range(len(user_data)):
    key.append(ord(decoded_user_data[i]) ^ ord(user_data[i])) 
key = key[:50]  # sizeof key is 50 bytes

# key
# [40, 193, 21, 13, 172, 103, 4, 88, 61, 108, 17, 37, 167, 45, 60, 135, 36, 30, 127, 84, 151, 233, 184, 12, 120, 244, 206, 43, 8, 220, 171, 43, 13, # 242, 11, 224, 171, 222, 11, 23, 81, 42, 147, 91, 199, 101, 96, 124, 245, 229]

login = "A"
user_data = 'login=%s&role=anonymous' % login
encoded_user_data = "RK5yZMJaRX5PA31AmkxS6EpnEjvimo81G82rT2q5n0k9ym/Tme47IDcT92z2UVJOxNEe+CE5"
decoded_user_data = base64.b64decode(encoded_user_data)

decrypted_data = ''

for i in range(len(decoded_user_data)):
    decrypted_data += chr(ord(decoded_user_data[i]) ^ key[i % len(key)])

target = "&role=administrator"
hash = decrypted_data[-32:]

length_of_salt = 0
length_of_user_data = len(user_data)

for length_of_salt in range(1,30):
    forged_hash = hashme(length_of_salt + length_of_user_data, target, hash)
    string_to_enc = user_data + target + forged_hash
    enc_payload = ''

    for i in range(len(string_to_enc)):
        enc_payload += chr(ord(string_to_enc[i]) ^ key[i % len(key)])

    print "%d : %s" % (length_of_salt, base64.b64encode(enc_payload))
We get successful login and flag, when length of SALT is 20 bytes.
RK5yZMJaRX5PA31AmkxS6EpnEjvimp5+F5irFmm4xkJjm3iU2b9/eCNM8TimAFcdwYca8CU8nQI8OVxbdRefTgzjFi0bMaPejw==
[+] Welcome, A!
CTF{40712b12d4be002e20f51424309a068c}

Hack You CTF 2014 - Crypto 100 - Easy One - [Team SegFault]

Source file of the encryption algorithm was given. Also, we have plain text and cipher text combination for one message
 FILE* input  = fopen(argv[1], "rb");
 FILE* output = fopen(argv[2], "wb");
 char k[] = "CENSORED";
 char c, p, t = 0;
 int i = 0;
 while ((p = fgetc(input)) != EOF) {
     c = (p + (k[i % strlen(k)] ^ t) + i*i) & 0xff;
     t = p;
     i++;
     fputc(c, output);
 }
Find the key:

[*] Algorithm coverts one byte of plain text to one byte of cipher text using equation of the form c = (p + (k[i % len(k)] ^ t) + i*i) mod 256
[*] Using the plain text - cipher text combination, the equation can be written as k[i] = ((c[i] - (i*i) - p[i]) ^ t) & 0xff to find the key. Here c,i,p and t are known values

The key used is VeryLongKeyYouWillNeverGuess. Once the key is found, the decryption algorithm is straight forward. Below is the code
#!/usr/bin/env python

plain_text = open('msg001','r').read().strip()
cipher_text = open('msg001.enc','r').read().strip()

plain_text = [ord(i) for i in plain_text]
cipher_text = [ord(i) for i in cipher_text]

t = 0
key = ''

for i in range(len(plain_text)):
    c = ((cipher_text[i] - (i*i) - plain_text[i]) ^ t) & 0xff
    key += chr(c)
    t = plain_text[i]
#print key

cipher_text = open('msg002.enc','r').read().strip()
key = 'VeryLongKeyYouWillNeverGuess'

key= [ord(i) for i in key]
cipher_text = [ord(i) for i in cipher_text]

t = 0
plain = ''

for i in range(len(cipher_text)):
    c = (cipher_text[i] - (key[i % len(key)] ^ t) - i*i) & 0xff
    plain += chr(c)
    t = c
print plain
Flag for the challenge is CTF{6d5eba48508efb13dc87220879306619}