CTF Writeup - Flare-On 2016 - 07: hashes

• Name - hashes
• Category - Reverse Engineering
• Points - 7
• Description - n/a
• Binary - Download here

Running the linux binary with a random parameter and without any parameter we get:

root@kali: ~/Desktop

root@kali:~/Desktop# ./hashes panic: runtime error: index out of range goroutine 16 [running]: goroutine 18 [finalizer wait]: created by runtime_createfing ../../../src/libgo/runtime/mgc0.c:2572 root@kali:~/Desktop# ./hashes 123 Work on your Hash F00! root@kali:~/Desktop#

From this we can straight away tell that the binary has been written using the Go programming language. Running strings also reveals various Go-related functions. The version required for this challenge can be installed by running apt-get install libgo7.

With everything set up, let's start debugging it with IDA. I found it a bit challenging to follow the control flow of the Go binary; sometimes it seems to jump randomly from one place and ends up in a completely different place. Not sure if I should blame my lack of knowledge regarding the Go language, IDA for not handling the binary well or the use of channels, whatever they are, in the Go programming language. If anyone has the answer to why this happens please give me a shout.

Anyways, the main function is called main_main. The first checks on our input string we encounter are in the following location:

The green arrow coming out of the bottom of the image goes to the basic block containing 'Work on your Hash F00!', so we need to avoid it. The compare statement at the top is done against the length of our input and 0x1E; so now we have the correct length of the input. The function sub_8049F6D is then called with parameters: length of input string and the input string itself. Let's look closer at what this does:

The green box at the bottom sets EAX to 1 before the program exists, whilst the red box sets EAX to 0. From the previous image we know that we need EAX to be 1 and hence we have to make sure execution passes via the green box. The function iterates over each character of our input and checks if it is contained (_strings_ContainsAny) in abcdefghijklmnopqrstuvwxyz@-._1234. If not we end up in the red box.

So up to now we know that the string has to be 30 characters in length and has to be made up of only the following characters: abcdefghijklmnopqrstuvwxyz@-._1234.

The program then does the following:

1. Divides the length of the input string (i.e. 30) by 6, which gives us 5
2. Slices the input string in 5 equal substrings
3. Performs SHA1 trice on each of the substrings
4. Appends the results

The last 3 operations, which are looped over 5 times, can be seen here:

The next part of the binary does the validation checking on the result. The routine is simple but debugging it was a nightmare as IDA kept jumping from one function to another. The algorithm does the following steps:

1. Takes the first char of the concatenated, SHA1 string computed above; let's call this Z
2. Adds 0x1CD to it; X = Z + 0x1CD; GOTO 4
3. Adds 0x1CD to itself; X += 0x1CD;
4. Obtains a byte from a fixed array: Y = unk_804BB80[ X % 4096 ]
5. Compares Y with Z
6. Now Z takes the value of the next char of the SHA1 string; GOTO 3

Note that only the first character of the resultant SHA1 string is used as a seed. As the resultant SHA1 string depends on out input, and the comparison string derived from the fixed array depends on the first character of the SHA1 string, and hence our input too, we can't simply first compute the latter and then bruteforce to obtain the former.

Combining all the information we have we can whip up a small program that gives us the first 6 characters of the input string. The decision to do this for only the first 6 chars will become apparent later. So let's start:

    import hashlib
    import itertools

    unk_804BB80 = ['03','72','D7','E5','03','AB','E0','D4','9F',

                    [ .. snip .. ]

                   'EE','46','2B','EE','2C','15','21','42','52',
                   '51','6B','7E','69','4D','28','DC','6C','8B']

    def sha1(input):
        m = hashlib.sha1()
        m.update(input)
        return m.digest()
 
    def triplesha1(input):
        for x in range(3):
            input = sha1(input)
        return input

    allowed_chars = "abcdefghijklmnopqrstuvwxyz@-._1234"

    add_const = "0x1CD"    
 
    for string in itertools.imap(''.join, itertools.product(allowed_chars, repeat=6)):
        found = 0
        temp_triple_sha = triplesha1(string).encode("hex").upper()
        a = int(temp_triple_sha[0:2],16)
        for x in range(20):
            a = a + int(add_const,16)
            translation =  unk_804BB80[a % 4096]
            if translation != temp_triple_sha[x*2:x*2+2]:
                break 
            found = found + 1
        if found == 20:
            print string
            break

After a while we get back h4sh3d. Perfect, we've got the first 6 characters out of 30. Now we could either continue this way and solve the others sequentially (this is because computations depend on the previous result, because of the seed) using the same program or, since we now know what the seed is, which is the first char of sha1(sha1(sha1('h4sh3d'))), we can obtain all 5 hashes directly from the fixed array. Let's go with the latter:

    import hashlib
    import itertools

    unk_804BB80 = ['03','72','D7','E5','03','AB','E0','D4','9F',

                    [ .. snip .. ]

                   'EE','46','2B','EE','2C','15','21','42','52',
                   '51','6B','7E','69','4D','28','DC','6C','8B']

    add_const = "0x1CD"    

    a = 60 #first byte of SHA1(SHA1(SHA1('h4sh3d')))

    for x in range(100):
        a = a + int(add_const,16)
        print unk_804BB80[a % 4096],
        if (x+1) % 20 == 0:
            print '\r\n'

Running the program we get all 5 hashes:

root@kali: ~/Desktop

root@kali:~/Desktop# python hash_finder.py 3C AB 24 65 E9 55 B7 8E 1D C8 4A B2 AA D1 77 36 41 EF 6C 29 4A 1B F8 BD 1E 91 F3 59 3A 6C CC 9C C9 B2 D5 68 2E 62 24 4F 9E 60 61 A3 62 50 E1 C4 7E 69 F0 31 2D B4 E5 61 52 8A 1F B5 06 04 6B 72 1E 18 E2 0B 84 1F 49 7E 25 77 53 B2 31 4B 86 6C CC 72 08 42 D0 88 4D A0 8E 26 D9 FC CB 24 BC 9C 27 BD 25 4E root@kali:~/Desktop#

Double check that the first one is indeed the triple SHA1 of h4sh3d. So now we can bruteforce them at the same time. As we know that the flag ends with @flare-on.com we can also omit the last 2 hashes. The following program bruteforces the 2nd hash in the list:

    import hashlib
    import itertools

    def sha1(input):
        m = hashlib.sha1()
        m.update(input)
        return m.digest()
 
    def triplesha1(input):
        for x in range(3):
            input = sha1(input)
        return input

    allowed_chars = "abcdefghijklmnopqrstuvwxyz@-._1234"

    answer = "4A1BF8BD1E91F3593A6CCC9CC9B2D5682E62244F"
 
    for string in itertools.imap(''.join, itertools.product(allowed_chars, repeat=6)):
        temp_triple_sha = triplesha1(string).encode("hex").upper()
        if temp_triple_sha == answer:
            print string
            break

After running the program for the third hash we get the key: h4sh3d_th3_h4sh3s@flare-on.com


Edit 1: As pointed to me by @winnythomas, there's a shortcut way of cracking this. As we know that the key ends with @flare-on.com we effectively know what the last hash is and hence we can work our way backwards to deduce all the other hashes. This allows us to jump straight to the 3rd script presented above, skipping the first two.