Crypto

DragonSector Crypto 100

In this task we have to win a lottery game:

Basically each coupon costs $5 and we have $100 to spend. If we try to withdraw our money we get the amount of money we need to get our flag:

To show they are playing fairly, the give you a verification id that its the value you have to guess concatenated with a random salt to reach the AES 16 bytes block that is used to encrypt the string. So we get:

AES(<number to guess>#random_salt, ECB_MODE)

We are also given the source code where we can verify this:

from Crypto.Cipher import AES  
from Crypto import Random  
from datetime import datetime  
import random  
import os  
import time  
import sys

flag = open('flag.txt').read()

# config
start_money = 100  
cost = 5     # coupon price  
reward = 100 # reward for winning  
maxNumber = 1000 # we're drawing from 1 to maxNumber  
screenWidth = 79

intro = [  
    '',
    'Welcome to our Lotto!',
    'Bid for $%d, win $%d!' % (cost, reward),
    'Our system is provably fair:',
    '   Before each bid you\'ll receive encrypted result',
    '   After the whole game we will reveal the key to you',
    '   Then, you can decrypt results and verify that we haven\'t cheated on you!',
    '    (e.g. by drawing based on your input)',
    ''
    ]

# expand to AES block with random numeric salt
def randomExtend(block):  
    limit = 10**(16-len(block))
    # salt
    rnd = random.randrange(0, limit)
    # mix it even more
    rnd = (rnd ** random.randrange(10, 100)) % limit
    # append it to the block
    return block + ('%0'+str(16-len(block))+'x')%rnd

def play():  
    # print intro
    print '#' * screenWidth
    for line in intro:
        print  ('# %-' + str(screenWidth-4) + 's #') % line
    print '#' * screenWidth
    print ''

    # prepare everything
    money = start_money

    key = Random.new().read(16) # slow, but secure
    aes = AES.new(key, AES.MODE_ECB)

    # main loop
    quit = False
    while money > 0:
        luckyNumber = random.randrange(maxNumber + 1) # fast random should be enough
        salted = str(luckyNumber) + '#'
        salted = randomExtend(salted)

        print 'Your money: $%d' % money
        print 'Round verification: %s' % aes.encrypt(salted).encode('hex')
        print ''
        print 'Your choice:'
        print '\t1. Buy a coupon for $%d' % cost
        print '\t2. Withdraw your money'
        print '\t3. Quit'

        # read user input
        while True:
            input = raw_input().strip()
            if input == '1':
                # play!
                money -= cost
                sys.stdout.write('Your guess (0-%d): ' % maxNumber)
                guess = int(raw_input().strip())
                if guess == luckyNumber:
                    print 'You won $%d!' % reward
                    money += reward
                else:
                    print 'You lost!'
                break
            elif input == '2':
                # withdraw
                if money > 1337:
                    print 'You won! Here\'s your reward:', flag
                else:
                    print 'You cannot withdraw your money until you get $1337!'
                break
            elif input == '3':
                quit = True
                break
            else:
                print 'Unknown command!'

        print 'The lucky number was: %d' % luckyNumber
        if quit:
            break
        print '[enter] to continue...'
        raw_input()

    print 'Verification key:', key.encode('hex')
    if money <= 0:
        print 'You\'ve lost all your money! get out!'

if __name__ == '__main__':  
    play()

The problem is that we cannot break AES, so we have to outsmart the system in a different way. There are two factors here that can help us with that:

First, the random salt appended to the value to guess is supposed to prevent us from creating a dictionary from Encrypted values to decrypted ones. Since the same value to guess will have many encrypted representations because of the salt appended. So here is the first mistake of the developers. The salt appended to the value to guess is not that random and turns out to be 000000000 many times because of the way the salt is calculated:

# expand to AES block with random numeric salt
def randomExtend(block):  
    limit = 10**(16-len(block))
    # salt
    rnd = random.randrange(0, limit)
    # mix it even more
    rnd = (rnd ** random.randrange(10, 100)) % limit
    # append it to the block
    return block + ('%0'+str(16-len(block))+'x')%rnd

Gynvael explained after the CTF was over than the reason for this was that:

Any number with a 0 as the last digit (i.e. 10% of numbers) rised to a high power will have all 000000000 at end and it gets truncated to % limit characters basically

The second factor is to find the way to play for free and I already showed you how to do it in the second screenshot. For each round we are presented with a verification value and after we choose an option, the value chosen is presented so we can verify that they were not cheating (although they dont give you the key so they could be cheating :D). Anyway, the second option, the one that lets us withdraw money works in the same way and so we can use it to know the number associated to an encrypted value.

So with that, we should be able to play and if we dont know the value associated to the encrypted value presented, we can ask for the withdraw process to get the lucky number associated to the crypto value and add them to a Encrypted-number map. If the encrypted value presented is in our map, then we can bet and win $100. Repeating the process can get us more than $1337 in less than 20 minutes

import socket

def read_until(s, text):  
  buffer = ""
  while text not in buffer:
    buffer = buffer + s.recv(1)
  return buffer

host = "23.253.207.179"  
port = 10001  
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)  
s.connect((host, port))


def play_round(mydict):  
    store = False
    read_until(s,"Your money: $")
    money = int(read_until(s,"\n")[:-1])
    read_until(s,"Round verification: ")
    encrypted = read_until(s,"\n")[:-1]
    if encrypted in mydict:
        guess = mydict[encrypted]
    else:
        guess = None
        store = True
    menu = read_until(s,"Quit\n")
    if guess is not None:
        # Bet
        s.send("1\n")
        read_until(s,"0-1000): ")
        try:
            guess = int(guess)
        except:
            guess = 1
        s.send("{0}\n".format(guess))
    else:
        # Pass
        s.send("2\n")
    response = read_until(s,"The lucky number was: ")
    num = read_until(s,"\n")[:-1]
    if store:
        mydict[encrypted] = num
    if "won" in response:
        print "win, money %d" % money
        print "Guess %s Verification %s LuckyNum %s" % (str(guess), encrypted, num,)
        if money > 1337:
            print money
            num = read_until(s,"\n")[:-1]
            print num
            s.send("\n")
            print read_until(s,"Quit\n")
            s.send("2\n")
            print read_until(s,"\n")
            print read_until(s,"\n")
            print read_until(s,"\n")
            exit()
    if "lost" in response:
        print "WTF"
        exit()

    num = read_until(s,"\n")[:-1]
    s.send("\n")

mydict = {}  
while True:  
    play_round(mydict)

The result:

NuitDuHack 2014 Crypto Write Ups

Carbonara

We are given the following ciphertext:

%96 7=28 7@C E9:D 492= :D iQx>A6C2E@C xF=:FD r26D2C s:GFDQ]

A simple shift shows interesting results:

ciphertext = "%96 7=28 7@C E9:D 492= :D iQx>A6C2E@C xF=:FD r26D2C s:GFDQ]"  
size = len(ciphertext)  
for i in range(0,100):  
    result=""
    for c in ciphertext:
        if ord(c) > 126 or ord(c) < 33:
            result += c
        else:
            first = ord(c)+i
            if first > 90:
                first = 64 + (first - 90)
            result += chr(first)
    print(result)

Here is were the history classes prove valuable, flag is:

Imperator Iulius Caesar Divus

Worthless

We are given a bunch of 0's and 1's.

00010111000001110001010001100011 00001001000111010000001000001000 01110001000001010000000000000011  
01100011000110110001100100001010 00011100011100010000000000000111 00010000000011110110111100011000  
00010000011011110001011100001111 00000000000100100000000000000110 00011111000000100001101000010010  
00001010000000010001100000001011 00000110000111010000101000011111 00011000000011110000011000010111  
00001010000011000001000000010111 00000110000111100000110101100001  

If we group them by bytes we get a 56 length binary. Our favorite xor key guessing tool: xortool by Hellman shows that a key of length 3n is possible. However it fails decrypting the message with " " (supposing it is a text) as the most frequent char. That is normal in such short texts. The idea to solve it is to pass all characters as most frequent chars for the analysis and then grep the results for words you may be expecting such "flag".

from xortool.xortool import process  
import os

def search(text):  
    rootdir = './xortool_out'
    for subdir, dirs, files in os.walk(rootdir):
        for file in files:
            if ".out" in file:
                f = open(os.path.join(subdir,file),'r')
                contents = f.read()
                if text in contents:
                    print "\"%s\" found at %s: %s" % (text, os.path.join(subdir,file), contents,)

original = "0001011100000111000101000110001100001001000111010000001000001000011100010000010100000000000000110110001100011011000110010000101000011100011100010000000000000111000100000000111101101111000110000001000001101111000101110000111100000000000100100000000000000110000111110000001000011010000100100000101000000001000110000000101100000110000111010000101000011111000110000000111100000110000101110000101000001100000100000001011100000110000111100000110101100001"  
bytes = []  
for i in range(0,len(original),8):  
    test = hex(int(original[i:i+8], 2))
    bytes.append(test[2:].zfill(2))
ciphertext = ''.join(bytes).decode('hex')


# try lower letters as most frequest chars
process(ciphertext, [i for i in range(97,122)])  
search("lag")

# try upper letters as most frequest chars
process(ciphertext, [i for i in range(65,90)])  
search("LAG")  

The result of running the script:

Voila!

#hackyou2014 Crypto400 write-up

In this level we are said that:

We have intercepted communication in a private network. It is used a strange protocol based on RSA cryptosystem.

Can you still prove that it is not secure enough and get the flag?

We are given a pcap file with a bunch of transmissions generated with this script:

#!/usr/bin/python
import sys  
import struct  
import zlib  
import socket

class Client:  
    def __init__(self, ip):
        #init
        self.ip = ip
        self.port = 0x1337
        #connect
        self.conn = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.conn.connect((self.ip, self.port))
        #recieve e
        self.e = self.Recv()
        #recieve n
        self.n = self.Recv()
        self.e, self.n = int(self.e), int(self.n)

    def Recv(self):
        #unpack data
        length = struct.unpack('!H', self.conn.recv(2))
        data = zlib.decompress(self.conn.recv(length[0]))
        return data

    def Pack(self, data):
        #compress data
        data = zlib.compress('%s' % data)
        length = struct.pack('!H', len(data))
        return '%s%s' % (length, data)

    def Send(self, msg):
        #send message
        msg = int(msg.encode('hex'),16)
        assert(msg < self.n)
        msg = pow(msg, self.e, self.n)
        self.conn.send(self.Pack(msg))
        print '[+] Message send'

    def __del__(self):
        #close connection
        self.conn.close()

if len(sys.argv) != 2:  
    print 'Usage: %s <ip>' % sys.argv[0]
    sys.exit(0)

flag = open('message.txt').readline()  
test = Client(sys.argv[1])  
test.Send(flag)  

Analyzing the protocol it looks like it goes something like:

  • Message to be send is read from external file
  • Connection is established against given IP on port 4919 (0x1337)
  • Server sends "e" packet [data lengt + zlib(data)]
  • Server sends "n" packet [data lengt + zlib(data)]
  • Both "e" and "n" are casted to integers
  • Client encodes message as integer
  • Client verifies message < n
  • Client encrpyts message using: enc = pow(message, e, n)
  • Client sends encrypted message packet [data lengt + zlib(data)]

If we explore the pcap with wireshark we can see a bunch of transmissions from Client to Server. We will need to process it in order to extract the message, the following python+scapy script will read all the interesting elements being transmited for each communication: e, n and flag:

#!/usr/bin/python
from scapy.all import *  
from struct import *  
import zlib

pkts = PcapReader("packets.pcap")  
for p in pkts:  
    pkt = p.payload
    if pkt.getlayer(Raw):
        raw = pkt.getlayer(Raw).load
        print "{0}:{1} -> {2}:{3}".format(pkt.src,pkt.sport,pkt.dst,pkt.dport)
        if str(pkt.sport) == "4919":
            elength = struct.unpack("!H",raw[0:2])[0]
            ezip = raw[2:2 + elength]
            e = int(zlib.decompress(ezip))
            nlength = struct.unpack("!H",raw[elength + 2 :elength + 4])[0]
            nzip =  raw[elength + 4:elength + 4 + nlength]
            n = int(zlib.decompress(nzip))
            print "e = {0}".format(e)
            print "n = {0}".format(n)
        if str(pkt.dport) == "4919":
            flaglength = struct.unpack("!H",raw[0:2])[0]
            flagzip = raw[2:2 + flaglength]
            encflag = int(zlib.decompress(flagzip))
            print "encflag = {0}".format(encflag)

As an example of one communication:

alvaro@winterfell ~/D/h/crypto400> python decrypter.py  
WARNING: No route found for IPv6 destination :: (no default route?)  
192.168.1.10:4919 -> 192.168.1.5:41260  
e = 17  
n = 27658060678038715780470429570597987144542213875178081185638364125349217264266787337266356239252353691015124430930507236433817624156361120645134956689683794554169169254645287613480048966030722812191823753459580311585866523664171185580520752591976764843551787247552790540802105791272457516072210641470817920157370947681970410336005860197552073763981521526496955541778866864446616347452950889748333309771690509856724643918258831575902389005661750464296924818808365029037591660424882588976607197196824985084365272217072807601787578262208488572448451271800547820717066767396857464594301327160705353075064322975430897551911  
192.168.1.5:41260 -> 192.168.1.10:4919  
encflag = 11433488612991990768536086698965180146550356348457563234735402111134701115830423042016221831657484325065472609147436229496479358788735270448637824809543880271526735635196884978639585020518147152207002685868984199742884443523231593245377292570809368330956970290791633106067116466080014631110596564728982066569618319541351401820732547227122970369299780366876340403436785218211729531092484723580223801525992510782266856454394478372421830988205823368541860973674259795969870252832216828042174346473447490557323038031625277043161510854825069681462499200978561823301487118145650943076528233694749306585201212677836363102350  

Analyzing the traffic, there are 19 communications with different modulos but always same exponent (e=17) which simplifies the problem

encrypted = (flag^17) % modulo  

We should only care to find F so that:

encflag1 = F % n1  
encflag2 = F % n2  
...
...
encflag18 = F % n18  
encflag19 = F % n19  

In order to solve the equation we can use the Chinese Remainder Theorem (CRT). For which I found a Python implementation that I needed to adjust a little bit:

from operator import mod

def eea(a,b):  
    """Extended Euclidean Algorithm for GCD"""
    v1 = [a,1,0]
    v2 = [b,0,1]
    while v2[0]<>0:
       p = v1[0]//v2[0] # floor division
       v2, v1 = map(lambda x, y: x-y,v1,[p*vi for vi in v2]), v2
    return v1

def inverse(m,k):  
     """
     Return b such that b*m mod k = 1, or 0 if no solution
     """
     v = eea(m,k)
     return (v[0]==1)*(v[1] % k)

def crt(ml,al):  
     """
     Chinese Remainder Theorem:
     ms = list of pairwise relatively prime integers
     as = remainders when x is divided by ms
     (ai is 'each in as', mi 'each in ms')

     The solution for x modulo M (M = product of ms) will be:
     x = a1*M1*y1 + a2*M2*y2 + ... + ar*Mr*yr (mod M),
     where Mi = M/mi and yi = (Mi)^-1 (mod mi) for 1 <= i <= r.
     """

     M  = reduce(lambda x, y: x*y,ml)        # multiply ml together
     Ms = [M/mi for mi in ml]   # list of all M/mi
     ys = [inverse(Mi, mi) for Mi,mi in zip(Ms,ml)] # uses inverse,eea
     return reduce(lambda x, y: x+y,[ai*Mi*yi for ai,Mi,yi in zip(al,Ms,ys)]) % M

F = crt(modulos,remainders)  

Once we find F, we can calculate its 17th root in order to find the integer version of the flag:

def root(x,n):  
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

intflag = root(F,17)  

And from there its easy to get the flag:

flag = hex(intflag)[2:-1].decode('hex')  

Running our script returns:

alvaro@winterfell ~/D/h/crypto400> python decrypter.py  
WARNING: No route found for IPv6 destination :: (no default route?)  
Secret message! CTF{336b2196a2932c399c0340bc41cd362d}  

Cool!!!!

This is the full script:

#!/usr/bin/python
from scapy.all import *  
from struct import *  
import zlib  
from operator import mod

def eea(a,b):  
    """Extended Euclidean Algorithm for GCD"""
    v1 = [a,1,0]
    v2 = [b,0,1]
    while v2[0]<>0:
       p = v1[0]//v2[0] # floor division
       v2, v1 = map(lambda x, y: x-y,v1,[p*vi for vi in v2]), v2
    return v1

def inverse(m,k):  
     """
     Return b such that b*m mod k = 1, or 0 if no solution
     """
     v = eea(m,k)
     return (v[0]==1)*(v[1] % k)

def crt(ml,al):  
     """
     Chinese Remainder Theorem:
     ms = list of pairwise relatively prime integers
     as = remainders when x is divided by ms
     (ai is 'each in as', mi 'each in ms')

     The solution for x modulo M (M = product of ms) will be:
     x = a1*M1*y1 + a2*M2*y2 + ... + ar*Mr*yr (mod M),
     where Mi = M/mi and yi = (Mi)^-1 (mod mi) for 1 <= i <= r.
     """

     M  = reduce(lambda x, y: x*y,ml)        # multiply ml together
     Ms = [M/mi for mi in ml]   # list of all M/mi
     ys = [inverse(Mi, mi) for Mi,mi in zip(Ms,ml)] # uses inverse,eea
     return reduce(lambda x, y: x+y,[ai*Mi*yi for ai,Mi,yi in zip(al,Ms,ys)]) % M

def root(x,n):  
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

pkts = PcapReader("packets.pcap")  
modulos = []  
remainders = []  
exponents = []  
for p in pkts:  
    pkt = p.payload
    if pkt.getlayer(Raw):
        raw = pkt.getlayer(Raw).load
        if str(pkt.sport) == "4919":
            elength = struct.unpack("!H",raw[0:2])[0]
            ezip = raw[2:2 + elength]
            e = int(zlib.decompress(ezip))
            nlength = struct.unpack("!H",raw[elength + 2 :elength + 4])[0]
            nzip =  raw[elength + 4:elength + 4 + nlength]
            n = int(zlib.decompress(nzip))
            modulos.append(n)
            exponents.append(e)
        if str(pkt.dport) == "4919":
            flaglength = struct.unpack("!H",raw[0:2])[0]
            flagzip = raw[2:2 + flaglength]
            encflag = int(zlib.decompress(flagzip))
            remainders.append(encflag)

F = crt(modulos,remainders)  
intflag = root(F,17)  
flag = hex(intflag)[2:-1].decode('hex')  
print flag  

Thanks for reading!

References:

#hackyou2014 Crypto300 write-up

In this level we are presented with a crypto system based on Matrix operations:

#!/usr/bin/python
import random  
from struct import pack

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 : pack('!H', y), x)), m))

def Generate(password):  
    #generate key matrix
    random.seed(password)
    return [[random.randint(0,64) for i in xrange(4)] for j in xrange(4)]

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

def Encrypt(fname):  
    #encrypt file
    key = Generate('')
    data = open(fname, 'rb').read()
    length = pack('!I', len(data))
    while len(data) % 16 != 0:
        data += '\x00'
    out = open(fname + '.out', 'wb')
    out.write(length)
    for i in xrange(0, len(data), 16):
        cipher = Multiply(Str2matrix(data[i:i+16]), key)
        out.write(Matrix2str(cipher))
    out.close()

Encrypt('flag.wmv')  

The Encrypt() function generates a 4x4 matrix based on a seed not providen. This matrix is used to encrypt a byte array. Here is how:

  • File to be encrypted is padded with 0 until its a factor of 16.
  • Then it is split in 16 bytes chunks that are reordened as 4x4 lists
  • Each of this 4x4 matrix is multiplied by the key matrix
  • The encrypted file is generated by appending the length of the encrpyted data and the encrypted bytes

Matrix multiplications are reversible using inverse matrixes so if E = P * K then P.I * E = P.I * P * K so K = P.I * E where:

  • P is a plaintext matrix
  • E is a encrypted matrix of plaintext matrix
  • P.I is the inverse of P

So if we want to extract the key we need to know at least one plaintext 4x4 matrix (P). Fortunately for us the file we need to decrypt is "flag.wmv.out" sounds like it is a WMV file and we know that its magic number is:

3026b2758e66cf11a6d900aa0062ce6c  

Thats exactly 16 bytes :D So to extract the key:

#!/usr/bin/python
import random  
from struct import pack  
from struct import unpack  
from numpy import *

def Str2matrix(s):  
    return [map(lambda x : ord(x), list(s[i:i+4])) for i in xrange(0, len(s), 4)]

def DecStr2matrix(s):  
    matrix = []
    row = []
    rowcount = 0
    for i in xrange(0, len(s), 2):
        item = int(s[i:i+2].encode("hex"),16)
        row.append(item)
        rowcount += 1
        if rowcount==4:
            rowcount=0
            matrix.append(row)
            row=[]
    return matrix

def Matrix2str(m):  
    return ''.join(map(lambda x : ''.join(map(lambda y : pack('!H', y), x)), m))

def DecMatrix2str(m):  
    return ''.join(map(lambda x : ''.join(map(lambda y : pack('!B', y), x)), m))

def Generate(password):  
    random.seed(password)
    return [[random.randint(0,64) for i in xrange(4)] for j in xrange(4)]

def Multiply(A,B):  
    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

def Encrypt(fname,mkey):  
    key = Generate(5)
    data = open(fname, 'rb').read()
    length = pack('!I', len(data))
    while len(data) % 16 != 0:
        data += '\x00'
    out = open(fname + '.out', 'wb')
    out.write(length)
    for i in xrange(0, len(data), 16):
        cipher = Multiply(Str2matrix(data[i:i+16]), key)
        mclear = matrix(Str2matrix(data[i:i+16]))
        mcipher = matrix(cipher)
        mcipher = mclear*mkey
        out.write(Matrix2str(cipher))
    out.close()
    return cipher

def Decrypt(fname,key):  
    data = open(fname, 'rb').read()
    length = int(unpack('!I', data[0:4])[0])
    data = data[4:]
    out = open(fname + '.orig', 'wb')
    for i in xrange(0, len(data), 32):
        mdata = DecStr2matrix(data[i:i+32])
        clear = matrix(mdata)*key.I
        m = clear.round().tolist()
        m = [[int(item) for item in row] for row in m]
        out.write(DecMatrix2str(m))
    out.close()
    return clear

def ExtractKey(fname, clearstring):  
    data = open(fname, 'rb').read()
    cipher = data[4:36]
    clear = clearstring.decode("hex")
    mclear = matrix(Str2matrix(clear))
    mcipher = matrix(DecStr2matrix(cipher))
    mkey = mclear.I*mcipher
    return mkey

#Encrypt('flag.wmv')
ourkey = matrix(Generate(5))  
print"[+] Extract key"  
key = ExtractKey("flag.wmv.out", "3026b2758e66cf11a6d900aa0062ce6c")  
print("[+] Key:\n{0}".format(key))  
print"[+] Decrypt video"  
clear = Decrypt("flag.wmv.out",key)  

So running the script gets the vide decrypted:

alvaro@winterfell ~/D/h/crypto300> python crack2.py  
[+] Extract key
[+] Key:
[[ 31.  51.  20.   0.]
 [ 53.  10.   6.  45.]
 [  3.  13.   3.  49.]
 [ 17.  48.  56.  31.]]
[+] Decrypt video

#hackyou2014 Crypto200 write-up

In this level we are said that our challange is login with administrator role in a service listening on hackyou2014tasks.ctf.su 7777
We are given the following source code:

#!/usr/bin/python
from math import sin  
from urlparse import parse_qs  
from base64 import b64encode  
from base64 import b64decode  
from re import match

SALT = ''  
USERS = set()  
KEY = ''.decode('hex')

def xor(a, b):  
    return ''.join(map(lambda x : chr(ord(x[0]) ^ ord(x[1])), zip(a, b * 100)))

def hashme(s):  
    #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
    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]))

def gen_cert(login):  
    global SALT, KEY
    s = 'login=%s&role=anonymous' % login
    s += hashme(SALT + s)
    print("decrypted cert: %s" % s)
    s = b64encode(xor(s, KEY))
    print("encrypted cert: %s" % s)
    return s

def register():  
    global USERS
    login = raw_input('Your login: ').strip()
    if not match('^[\w]+$', login):
        print '[-] Wrong login'
        return
    if login in USERS:
        print '[-] Username already exists'
    else:
        USERS.add(login)
        print '[+] OK\nYour auth certificate:\n%s' % gen_cert(login)

def auth():  
    global SALT, KEY
    cert = raw_input('Provide your certificate:\n').strip()
    try:
        cert = xor(b64decode(cert), KEY)
        print cert
        auth_str, hashsum = cert[0:-32], cert[-32:]
        print auth_str
        print hashsum
        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
        else:
            print '[-] Auth failed'
    except:
        print '[-] Error'


def start():  
    while True:
        print '======================'
        print '[0] Register'
        print '[1] Login'
        print '======================'
        num = raw_input().strip()
        if num == '0':
            register()
        elif num == '1':
            auth()

start()  

The service generates certificate when you register that you need to present in order to login in.
The certificate is a XOR encrypted version of the following string:

login=<login>&role=anonymous<salted hash of login+role string>  

The problem is that we dont know the encryption key nor the hash salt. So let's take it one step at a time:

Getting the key to the kingdom

Getting the key was the easy part as the cert is encrypted in an ECB way, we only need to send a login name long enough so that the whole key is xored with our know long login name, so we register the user:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA  

And get the cert:

RK5yZMJaRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pGmAVEztJkUZfC1QZOZsfcZlXz4V1qj5TTm1j2pJnepqTLNKoeqfSlYQa9IahiQhPbSkaYBUTO0mRRl8LVBk5mx9xmVfPhXWqPlNObWPakmd6mpMs0qh6p9KVhBr0hqGJCE9tKRpgFRM7SZFGXwtUGTmbH3GZV8+Fdao+U05tY9qSZ3qakyzSqHqn0pWEGvSGoYkIT20pA6zemHJWmU2UgJoSMhYT7cXe0kyoN7cakrNq0lu7MgSaJYz0p/rb3NpE6FqpgZQ  

Now if we xor the two together (adding "login=" before the login name) we get the key and since our login name was long enough we can extract the key that is repeated several times:

28c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e5  

Now we can decrypt our cert and extrack the login string and hashsum:

[+] Credentials: login=pwntester&role=anonymous
[+] Hashsum: 3e4d482fd5ce578af79312466b50b8f6

Putting some salt

Our goal is to submit an "administrator" version of the string so we need to know the salt in order to produce the right hash that is going to be checked in the server ... or not?
Well, actually, the hashing function is not reversible and no collisions are found easy, but there is still hope in the way of Length extension attacks. Actually is even simpler since we dont have to care about the padding!
Ok, so here is the idea.

  • The Hashing state machine starts in a initial state (that we know, check A,B,C,D in the hashme function)
  • The hashing machine iterates over all the characters (abcd) and ends in a different state that is returned as the hashsum
  • If we extend the original characters (abcd1234) and pass it to the hash function, we can do two things:
    • Start from scratch, reset the hash FSM, and calculate process it till there are no more characters and we return the last state in the form of a hashsum
    • Since we already hashed some characters and know the machine state, we can modify the hash FSM so its initial state is the one returned when we hashed (abcd) and then just continue from that state with the new characters (1234) until there are no more characters and we return the state in the form of a hashsum

Well, the server is going to do the first approach, but we can do the second without knowing the Salt!! So we know that "login=pwntester&role=anonymous" hash is 3e4d482fd5ce578af79312466b50b8f6.

Lets say we want to calculate the hash of "login=pwntester&role=anonymousNEWSTUFFHERE", we can reset the Hash machine so its initial state is 3e4d482fd5ce578af79312466b50b8f6 and then just hash the "NEWSTUFFHERE", the result will be the same hash as hashing the whole string.

Now, if we focus on the auth() method:

def auth():  
    global SALT, KEY
    cert = raw_input('Provide your certificate:\n').strip()
    try:
        cert = xor(b64decode(cert), KEY)
        print cert
        auth_str, hashsum = cert[0:-32], cert[-32:]
        print auth_str
        print hashsum
        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
        else:
            print '[-] Auth failed'
    except:
        print '[-] Error'

We can see that the auth string is parsed as a query string (parse_qs) so if we pass different parameters with the same name, they will be treated as an array.
Then the "if 'administrator' in data['role']" will pass if one of them is administrator

So now we know what we need to hash:

login=pwntester&role=anonymous&role=administrator  

This is the function I wrote to hash from a given state:

def hashmeFromState(s,hash,init):  
    #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


    B = int(hash[0:8], 16)
    A = int(hash[8:16], 16)
    D = int(hash[16:24], 16)
    C = int(hash[24:32], 16)

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

    i = init
    for j,ch in enumerate(s):
        # We add the length of the previous state (we dont know secret length so we have to brute force it) to restaurate the state
        k, l = ord(ch), i & 0x1f
        if j==0:
            print("hashmeext pos:{0} char:{1} l:{2}".format(j,ch,l))
        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
        i += 1

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

Note that we dont know the length of the Salt, so we need to brute force it to initialize the hash FST in the right state. After running the script against the live service, we get that the right length is 18:

alvaro@winterfell ~/D/h/crypto200> python crack.py  
[+] Concatenated key (250 bytes): 28c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e528c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e528c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e528c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e528c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e5
[+] Key: 28c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e5
[+] Credentials: login=pwntester&role=anonymous
[+] Hashsum: 3e4d482fd5ce578af79312466b50b8f6
[+] User Credentials: login=pwntester&role=anonymous3e4d482fd5ce578af79312466b50b8f6
[+] User Cert: RK5yZMJadC9TGHRW00hOoVZxEzGqiNZjFo2jRH2vmE45lj/YmbhvIjJPpmz/BAZLzNYZ8yE7mgUxaF9UdxM=
[-] Auth failed
hashmeext pos:0 char:& l:1  
[+] Admin Credentials (secret length=1: login=pwntester&role=anonymous&role=administrator72d2e3d8de7b390f146cc6b5e8552ea8)
[+] Admin Cert (secret length=1: RK5yZMJadC9TGHRW00hOoVZxEzGqiNZjFo2jRH2vjVlinm7dyrpmfj9D4C+1BBQTh9IapSdonwM8PFhbcxaeHVq2ECgcN6GLjWlAwfsZbb2T)
[+] Admin Cert decoded (secret length=1: login=pwntester&role=anonymous&role=administrator72d2e3d8de7b390f146cc6b5e8552ea8)

...
...
...

[-] Auth failed
hashmeext pos:0 char:& l:18  
[+] Admin Credentials (secret length=18: login=pwntester&role=anonymous&role=administrator6ca059630c51cb32e3d791aeca560eae)
[+] Admin Cert (secret length=18: RK5yZMJadC9TGHRW00hOoVZxEzGqiNZjFo2jRH2vjVlinm7dyrpmfj9D4C+1BBQTh9NLoCU4lVE3aF5ZIEbFHg7iF3pIbaaI3W8Zwfgbbb3O)
[+] Admin Cert decoded (secret length=18: login=pwntester&role=anonymous&role=administrator6ca059630c51cb32e3d791aeca560eae)

[+] Welcome
Eureka!!  

Now we can use the cert to login and get the flag:

RK5yZMJadC9TGHRW00hOoVZxEzGqiNZjFo2jRH2vjVlinm7dyrpmfj9D4C+1BBQTh9NLoCU4lVE3aF5ZIEbFHg7iF3pIbaaI3W8Zwfgbbb3O  
alvaro@winterfell ~/D/h/crypto200> nc hackyou2014tasks.ctf.su 7777                                                                                                                                                                                                            1  
======================
[0] Register
[1] Login
======================
1  
Provide your certificate:  
RK5yZMJadC9TGHRW00hOoVZxEzGqiNZjFo2jRH2vjVlinm7dyrpmfj9D4C+1BBQTh9NLoCU4lVE3aF5ZIEbFHg7iF3pIbaaI3W8Zwfgbbb3O  
[+] Welcome, pwntester!
CTF{40712b12d4be002e20f51424309a068c}  

#hackyou2014 Crypto100 write-up

In this level we are asked to break a code and decrypt msg002.enc. We are given the encryptor code without the key:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {  
    if (argc != 3) {
        printf("USAGE: %s INPUT OUTPUT\n", argv[0]);
        return 0;
    }
    FILE* input  = fopen(argv[1], "rb");
    FILE* output = fopen(argv[2], "wb");
    if (!input || !output) {
        printf("Error\n");
        return 0;
    }
    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);
    }
    return 0;
}

And we are also given a plaintext (msg001) and its corresponding cryptotext (msg001.enc) so we can easily extract the key with something like:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {  
    if (argc != 2) {
        printf("USAGE: %s CRYPTO \n", argv[0]);
        return 0;
    }
    FILE* input  = fopen(argv[1], "rb");
    if (!input) {
        printf("Error\n");
        return 0;
    }

    char c, p, t = 0;
    int i = 0;

    // We use the following loop to get the key knowing the cryptotext(input) and plaintaext(w[])
    char w[] = "Hi! This is only test message";
    unsigned int j = 0;
    while ((p = fgetc(input)) != 0) {
        // printf("read %d", p);
        for (j=31;j<125;j++) {
            c = (p - (j ^ t) - i*i) & 0xff;
            if (c == w[i]) {
                printf("%c\n",j);
                t = c;
                i++;
                break;
            }
        }
    }
    return 0;
}

The resulting key is: VeryLongKeyYouWillNeverGuess
Now we can use a decryptor to extract msg002:

 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>

 int main(int argc, char **argv) {
    if (argc != 3) {
         printf("USAGE: %s INPUT OUTPUT\n", argv[0]);
         return 0;
     }
     FILE* input  = fopen(argv[1], "rb");
     FILE* output = fopen(argv[2], "wb");
     if (!input || !output) {
         printf("Error\n");
         return 0;
     }


     char c, p, t = 0;
     int i = 0;

    char k[] = "VeryLongKeyYouWillNeverGuess";
    i = 0;
    c, p, t = 0;
    int g = 0;
    while ((p = fgetc(input)) != 1) {
        c = (p - (k[i % strlen(k)] ^ t) - i*i) & 0xff;
         printf("Decrypting %x i=%d t=%d k=%d -> %d\n",p,i,t,(k[i % strlen(k)] ^ t),c);
        t = c;
        i++;
         //printf("%c",c);
         fputc(c, output);
         g++;
         if (g>450) {break;}
    }

    return 0;
 }

And the results are:

The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has samples of both the plaintext (called a crib), and its encrypted version (ciphertext). These can be used to reveal further secret information such as secret keys and code books. The term "crib" originated at Bletchley Park, the British World War II decryption operation. The flag is CTF{6d5eba48508efb13dc87220879306619}