ASIS Quals 2019 Hash collision

2 minute read

CTF Name: ASIS_CTF

Title: Flag Collision

Category: scripting

Timestamp: Sat, 20 Apr 2019 16:01:37 GMT

Tags:

  • Captcha
  • Hash collision

Tasks:

  • Solve catpcha
  • Find collisions

Challenge Description

Warm-up your fingers to capture next flags!

Steps to solutions/discovery

First of all, We need to write a script to bruteforce the captcha. The idea behind it is looping through all possible digits and then comparing part of the hash with given string. See the first script.

For the second part, we need to generate hash collisions of given length in format of two equal length strings inside “ASIS{HASH}” so that the hashes are equal. To do that we generate a random strings hash them and store in the list and compare generated hashes with listed ones each iteration.

To speed up the process, I generated a simple rainbow table of hashes and got the flag ASIS{3asy_c0din9_############}.

Captcha+Rainbow_table:

from pwn import *
import hashlib
import random
import string
import re
def randomstring(stringLength):
    letters = string.ascii_letters
    return ''.join(random.choice(letters) for i in range(stringLength))
r = remote('37.139.9.232', 19199)
chall1=r.recv()
print(chall1)
if 'md5(X)' in chall1:
    i=0
    while True:
        i+=1
        if hashlib.md5(str(i)).hexdigest()[-6:] == chall1[-7:-1]:
            print(i)
            r.sendline(str(i))
            break
elif 'sha256(X)' in chall1:
    i=0
    while True:
        i+=1
        if hashlib.sha256(str(i)).hexdigest()[-6:] == chall1[-7:-1]:
            print(i)
            r.sendline(str(i))
            break
elif 'sha512(X)' in chall1:
    i=0
    while True:
        i+=1
        if hashlib.sha512(str(i)).hexdigest()[-6:] == chall1[-7:-1]:
            print(i)
            r.sendline(str(i))
            break
elif 'sha224(X)' in chall1:
    i=0
    while True:
        i+=1
        if hashlib.sha224(str(i)).hexdigest()[-6:] == chall1[-7:-1]:
            print(i)
            r.sendline(str(i))
            break
elif 'sha384(X)' in chall1:
    i=0
    while True:
        i+=1
        if hashlib.sha384(str(i)).hexdigest()[-6:] == chall1[-7:-1]:
            print(i)
            r.sendline(str(i))
            break
elif 'sha1(X)' in chall1:
    i=0
    while True:
        i+=1
        if hashlib.sha1(str(i)).hexdigest()[-6:] == chall1[-7:-1]:
            print(i)
            r.sendline(str(i))
            break
# fiji=r.recv()+r.recv()
# print(fiji)
# matches = re.findall('= (.*) and',fiji)
# print(matches)
# val=int(matches[0])
# if val==15:
#     r.sendline('ASIS{wpQ78d6lk}, ASIS{4LEVv9no8}')
# elif val==16:
#      r.sendline('ASIS{qubsKcybHl}, ASIS{CaONHXZNWT}')
# elif val==17:
#      r.sendline('ASIS{PSfkkxHxgvt}, ASIS{bLSAexEVJkk}')
# payload='ASIS{'+randomString(val-6)+'}, ' + 'ASIS{'+randomString(val-6)+'}'
# print(payload)
# r.sendline(payload)

r.sendline('ASIS{wpQ78d6lk}, ASIS{4LEVv9no8}')
print(r.recvuntil('gj, go to the next level :)\n'))
while True: 
    paylo = int(re.findall('= (.*) and',r.recv())[0])
    print(paylo)
    if paylo==16:
        r.sendline('ASIS{qubsKcybHl}, ASIS{CaONHXZNWT}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==17:
        r.sendline('ASIS{PSfkkxHxgvt}, ASIS{bLSAexEVJkk}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==18:
        r.sendline('ASIS{sVEPAmaknMqV}, ASIS{PkADjNCvbeAo}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==19:
        r.sendline('ASIS{iugFGXjiLbaaN}, ASIS{isAQPzOXEZALc}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==20:
        r.sendline('ASIS{nnMJbtmnwpfBVV}, ASIS{SGdOgCrFPSoOBT}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==21:
        r.sendline('ASIS{QKBUvcJWGidwZzZ}, ASIS{tyIoliYtuENmdxe}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==22:
        r.sendline('ASIS{DloywwnmYnuAHGPy}, ASIS{jKnDnbnkMgPfCkJS}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==23:
        r.sendline('ASIS{AVBZlSmZNMBxEvAus}, ASIS{kzaWAcdgqzgAGAxaF}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==24:
        r.sendline('ASIS{ZbbwvobHKMLwrwvQsx}, ASIS{DHvcQszqlOtaUqbiaF}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==25:
        r.sendline('ASIS{PKgKzXavlECawFYsJlC}, ASIS{dIZyazieOzjALLaCEDN}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==27:
        r.sendline('ASIS{CUWzVcqkzGqZVIwQDXDrf}, ASIS{WCCCyYpOYyyHsCKdeULTb}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==36:
        r.sendline('ASIS{LqbLJOoaRNxfKDCHHGSaiorPEOvTEo}, ASIS{nyjfMtRijthoWLNwrXNyjxyRsjaomw}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==38:
        r.sendline('ASIS{spYVTPJkIlpRRtlwHpyNdKxbtdmPZoDN}, ASIS{mikldUyZSXNhJCGGTBYukrRPtOcdbaLO}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==34:
        r.sendline('ASIS{RhfoBbwJnxcVHnDQbXebFNqTrAcq}, ASIS{rKrMpZWMmKraEHEqIiMWFZCanqbl} ')
        print(r.recvuntil('gj, go to the next level :)\n'))
    elif paylo==40:
        r.sendline('ASIS{QXoRCVRnIvgxFuKhPgPksVxUkVENUzpvJD}, ASIS{OUXVBjbpfiEhcWlrZBsKFqaQKZzhmyOaKJ}')
        print(r.recvuntil('gj, go to the next level :)\n'))
    else:
        r.interactive()
        break
r.close()

Hash generator:

import zlib
import string
import random
def randomstring(stringLength):
    letters = string.ascii_letters
    return ''.join(random.choice(letters) for i in range(stringLength))
hashlist=list()
def gethash(vals):
    while True:
        val1='ASIS{'+randomstring(vals-6)+'}'
        hashs=zlib.crc32(val1)
        for i in hashlist:
            if i[0]==hashs:
                print(i[1]+', '+val1)
                return (i[1]+', '+val1)
                break
        hashlist.append((hashs,val1))