404CTF “La fonte des hashs” Write-up

Within the eShard intern team we are eager to learn about security, and we challenge ourselves by subscribing to the 404CTF organized by DGSE and Télécom SudParis.

In this article, I will explain how I solved the following one.

My free translation of this challenge:

The goal is to recover the flag which hashed is equal to the provided digest.

hash_we_try_to_get = '18f2048f7d4de5caabd2d0a3d23f4015af8033d46736a2e2d747b777a4d4d205'

TL;DR

After getting the Hallebarde hash code, I played with it by submitting short messages. I knew the starting characters of the hashed message ‘404CTF{’ and realized that the beginning of the hash fits with the targeted hash. This drove me to an incremental brute force straight to the flag recovery. In the meantime, I sent the Hallebarde hash.py code to eShard Team, and they came back to me with the reverse of the hash function and the flag.

Get the hash code and play with it

In hash.py we have:

import base64, codecs
magic = 'IyEvdXNyL2Jpbi9weXRob24KIyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KaW1wb3J0IHN5cwoKCgojIGZyb20gaHR0cHM6Ly9hc2VjdXJpdHlzaXRlLmNvbS9zdWJqZWN0cy9jaGFwdGVyODgKc2JveCA9IFsnMDExMDAwMTEnLCAnMDExMTExMDAnLCAnMDExMTAxMTEnLCAnMDExMTEwMTEnLCAnMTExMTAwMTAnLCAnMDExMDEwMTEnLCAnMDExMDExMTEnLCAnMTEwMDAxMDEnLCAnMDAxMTAwMDAnLCAnMDAwMDAwMDEnLCAnMDExMDAxMTEnLCAnMDAxMDEwMTEnLCAnMTExMTExMTAnLCAnMTEwMTAxMTEnLCAnMTAxMDEwMTEnLCAnMDExMTAxMTAnLCAnMTEwMDEwMTAnLCAnMTAwMDAwMTAnLCAnMTEwMDEwMDEnLCAnMDExMTExMDEnLCAnMTExMTEwMTAnLCAnMDEwMTEwMDEnLCAnMDEwMDAxMTEnLCAnMTExMTAwMDAnLCAnMTAxMDExMDEnLCAnMTEwMTAxMDAnLCAnMTAxMDAwMTAnLCAnMTAxMDExMTEnLCAnMTAwMTExMDAnLCAnMTAxMDAxMDAnLCAnMDExMTAwMTAnLCAnMTEwMDAwMDAnLCAnMTAxMTAxMTEnLCAnMTExMTExMDEnLCAnMTAwMTAwMTEnLCAnMDAxMDAxMTAnLCAnMDAxMTAxMTAnLCAnMDAxMTExMTEnLCAnMTExMTAxMTEnLCAnMTEwMDExMDAnLCAnMDAxMTAxMDAnLCAnMTAxMDAxMDEnLCAnMTExMDAxMDEnLCAnMTExMTAwMDEnLCAnMDExMTAwMDEnLCAnMTEwMTEwMDAnLCAnMDAxMTAwMDEnLCAnMDAwMTAxMDEnLCAnMDAwMDAxMDAnLCAnMTEwMDAxMTEnLCAnMDAxMDAwMTEnLCAnMTEwMDAwMTEnLCAnMDAwMTEwMDAnLCAnMTAwMTAxMTAnLCAnMDAwMDAxMDEnLCAnMTAwMTEwMTAnLCAnMDAwMDAxMTEnLCAnMDAwMTAwMTAnLCAnMTAwMDAwMDAnLCAnMTExMDAwMTAnLCAnMTExMDEwMTEnLCAnMDAxMDAxMTEnLCAnMTAxMTAwMTAnLCAnMDExMTAxMDEnLCAnMDAwMDEwMDEnLCAnMTAwMDAwMTEnLCAnMDAxMDExMDAnLCAnMDAwMTEwMTAnLCAnMDAwMTEwMTEnLCAnMDExMDExMTAnLCAnMDEwMTEwMTAnLCAnMTAxMDAwMDAnLCAnMDEwMTAwMTAnLCAnMDAxMTEwMTEnLCAnMTEwMTAxMTAnLCAnMTAxMTAwMTEnLCAnMDAxMDEwMDEnLCAnMTExMDAwMTEnLCAnMDAxMDExMTEnLCAnMTAwMDAxMDAnLCAnMDEwMTAwMTEnLCAnMTEwMTAwMDEnLCAnMDAwMDAwMDAnLCAnMTExMDExMDEnLCAnMDAxMDAwMDAnLCAnMTExMTExMDAnLCAnMTAxMTAwMDEnLCAnMDEwMTEwMTEnLCAnMDExMDEwMTAnLCAnMTEwMDEwMTEnLCAnMTAxMTExMTAnLCAnMDAxMTEwMDEnLCAnMDEwMDEwMTAnLCAnMDEwMDExMDAnLCAnMDEwMTEwMDAnLCAnMT'
love = 'RjZQRkZGRaYPNaZGRjZGNjZQNaYPNaZGRkZQRkZGRaYPNaZGNkZQRjZGNaYPNaZGRkZGRjZGRaYPNaZQRjZQNjZGRaYPNaZQRjZQRkZQRaYPNaZQNkZGNjZGRaYPNaZGNjZQNkZQRaYPNaZQRjZQNkZQRaYPNaZGRkZGRjZQRaYPNaZQNjZQNjZGNaYPNaZQRkZGRkZGRaYPNaZQRjZGNjZQNaYPNaZQNkZGRkZQNaYPNaZGNjZGRkZGRaYPNaZGNkZQRjZQNaYPNaZQRjZGNjZQRaYPNaZGNkZQNjZGRaYPNaZQRjZQNjZQNaYPNaZGNjZQRkZGRaYPNaZGNjZGNjZGNaYPNaZGNjZGRkZQRaYPNaZQNkZGRjZQNaYPNaZGRkZGNkZQRaYPNaZGNkZGRkZQNaYPNaZGNkZGNkZGNaYPNaZGRjZGRjZGNaYPNaZQNkZQNjZQRaYPNaZQNjZGNjZQNaYPNaZGRkZGRkZGRaYPNaZGRkZGNjZGRaYPNaZGRjZGNjZGNaYPNaZGRjZQRkZQRaYPNaZQNjZQRkZQNaYPNaZQNjZGNjZGRaYPNaZGRkZQRkZQNaYPNaZQRjZGRkZGRaYPNaZGNjZGNkZGRaYPNaZQRjZQNkZQNaYPNaZQNjZGNkZGRaYPNaZGRjZQNkZQNaYPNaZGNkZQNkZGRaYPNaZQRkZGRkZGNaYPNaZQNkZGRkZQRaYPNaZQRkZQNkZQNaYPNaZQRjZGRkZQRaYPNaZQNjZGRjZQRaYPNaZQRkZGNjZGRaYPNaZQRkZQNjZQNaYPNaZGNjZQNjZQRaYPNaZQRjZQRkZGRaYPNaZGRjZGRkZQNaYPNaZQNkZQNjZGNaYPNaZQNkZQRjZGNaYPNaZGNjZGNjZQNaYPNaZGNjZQRjZQNaYPNaZQRjZQNkZGNaYPNaZGRkZQRkZGNaYPNaZGNkZGRjZQNaYPNaZQNjZGNkZQNaYPNaZGRjZGRkZGNaYPNaZQRjZGRkZGNaYPNaZQNjZQRjZGRaYPNaZGRjZGRjZGRaYPNaZGRkZQNjZQNaYPNaZQNkZGNjZGNaYPNaZQNkZGRjZGNaYPNaZQNjZQRjZGNaYPNaZQRjZQRjZQRaYPNaZQNjZQNkZGNaYPNaZQNkZQNkZQNaYPNaZQRjZGRkZQNaYPNaZGRjZQNjZGNaYPNaZGRjZGNjZGRaYPNaZGNkZQRkZQNaYPNaZQRkZQNjZGNaYPNaZGNjZGNjZQRaYPNaZGNjZGNkZQRaYPNaZGRkZQNkZQNaYPNaZQRkZGRjZQRaYPNaZGRkZQNkZGRaYPNaZGRjZQRjZQNaYPNaZQNkZGNkZGRaYPNaZQRkZQRkZQRaYPNaZGNjZQRkZQRaYPNaZGRjZGNkZQRaYPNaZQRjZQRkZGNaYPNaZGNkZQRjZQRaYPNaZQRkZQRkZQNaYPNaZQRjZGNkZGNaYPNaZGRkZGNkZQNaYPNaZGRkZQRjZGNaYPNaZQRkZQNkZQRaYPNaZQRkZGRjZGNaYPNaZGNkZQRkZGNaYPNaZQNjZQRjZQNaYPNaZGNkZGRjZGNaYPNaZQRkZGRjZQNaYPNaZQNkZQNkZQRaYPNaZQNkZQRkZGNaYPNaZQNjZGRkZQNaYPNaZGNkZQNkZGNaYPNaZGNkZGNkZQNaYPNaZGRjZQNkZGNaYPNa'
god = 'MTExMDEwMDAnLCAnMTEwMTExMDEnLCAnMDExMTAxMDAnLCAnMDAwMTExMTEnLCAnMDEwMDEwMTEnLCAnMTAxMTExMDEnLCAnMTAwMDEwMTEnLCAnMTAwMDEwMTAnLCAnMDExMTAwMDAnLCAnMDAxMTExMTAnLCAnMTAxMTAxMDEnLCAnMDExMDAxMTAnLCAnMDEwMDEwMDAnLCAnMDAwMDAwMTEnLCAnMTExMTAxMTAnLCAnMDAwMDExMTAnLCAnMDExMDAwMDEnLCAnMDAxMTAxMDEnLCAnMDEwMTAxMTEnLCAnMTAxMTEwMDEnLCAnMTAwMDAxMTAnLCAnMTEwMDAwMDEnLCAnMDAwMTExMDEnLCAnMTAwMTExMTAnLCAnMTExMDAwMDEnLCAnMTExMTEwMDAnLCAnMTAwMTEwMDAnLCAnMDAwMTAwMDEnLCAnMDExMDEwMDEnLCAnMTEwMTEwMDEnLCAnMTAwMDExMTAnLCAnMTAwMTAxMDAnLCAnMTAwMTEwMTEnLCAnMDAwMTExMTAnLCAnMTAwMDAxMTEnLCAnMTExMDEwMDEnLCAnMTEwMDExMTAnLCAnMDEwMTAxMDEnLCAnMDAxMDEwMDAnLCAnMTEwMTExMTEnLCAnMTAwMDExMDAnLCAnMTAxMDAwMDEnLCAnMTAwMDEwMDEnLCAnMDAwMDExMDEnLCAnMTAxMTExMTEnLCAnMTExMDAxMTAnLCAnMDEwMDAwMTAnLCAnMDExMDEwMDAnLCAnMDEwMDAwMDEnLCAnMTAwMTEwMDEnLCAnMDAxMDExMDEnLCAnMDAwMDExMTEnLCAnMTAxMTAwMDAnLCAnMDEwMTAxMDAnLCAnMTAxMTEwMTEnLCAnMDAwMTAxMTAnXQoKCgoKZGVmIHN0cmluZzJiaXRzKHM9JycpOgogICAgdG1wID0gW10KICAgIGZvciB4IGluIHMgOgogICAgICAgIGJ5dGUgPSBiaW4ob3JkKHgpKVsyOl0KICAgICAgICBpZiBsZW4oYnl0ZSkgPiA4OgogICAgICAgICAgICBpbmRpY2VzID0gW2kgZm9yIGkgaW4gcmFuZ2UoMCwgbGVuKGJ5dGUpLCA4KV0KICAgICAgICAgICAgcGFydHMgPSBbIiIuam9pbihieXRlW2k6al0pLnpmaWxsKDgpIGZvciBpLGogaW4gemlwKGluZGljZXMsIGluZGljZXNbMTpdK1tOb25lXSldCiAgICAgICAgICAgIHRtcCArPSAocGFydHMpCiAgICAgICAgZWxzZSA6CiAgICAgICAgICAgIGJ5dGUgPSBieXRlLnpmaWxsKDgpCiAgICAgICAgICAgIHRtcC5hcHBlbmQoYnl0ZSkKICAgIHJldHVybiB0bXAKCmRlZiBwYWRkaW5nKGJpbmFyeSk6CiAgICBpZigobGVuKGJpbmFyeSkgKyAxICkgJSAzMiA9PSAwKToKICAgICAgICBiaW5hcnkuYXBwZW5kKCcwMDAwMDAwMScpCiAgICAgICAgYmluYXJ5LmFwcGVuZCgnMDAwMDAwMDAnKQogICAgaWYobGVuKGJpbmFyeSklMzIgIT0gMCBvciBsZW4oYmluYXJ5KSA9PSAwKToKICAgICAgICBiaW5hcnkuYXBwZW5kKCcwMD'
destiny = 'NjZQNjZFpcPvNtVPNtVPNtq2ucoTHtoTIhXTWcozSlrFxyZmVtVG0tZQbXVPNtVPNtVPNtVPNtLzyhLKW5YzSjpTIhMPtaZQNjZQNjZQNaXDbXMTIzVUuipvuuYTVcBtbtVPNtpzImVQ0tVvVXVPNtVTMipvOcVTyhVUWuozqyXTkyovuuXFx6PvNtVPNtVPNtVPNtVUWyplNeCFOmqUVbnJ50XTSonI0cVS4tnJ50XTWonI0cXDbtVPNtpzI0qKWhVUWypjbXMTIzVUAvo3uso3OyXTWcozSlrFx6PvNtVPOzo3VtnFOcovOlLJ5aMFufMJ4bLzyhLKW5XFx6PvNtVPNtVPNtnJ5xMKttCFOcoaDbLzyhLKW5J2yqYQVcPvNtVPNtVPNtLzyhLKW5J2yqVQ0tp2WirSgcozEyrS0XPzEyMvOjnTSmMGRbLzyhLKW5XGbXVPNtVT0tCFOcoaDboTIhXTWcozSlrFxtYlNmZvxXVPNtVUEgpPN9VSgqPvNtVPOzo3VtnFOcovOlLJ5aMFtjYPOfMJ4bLzyhLKW5XFjtoFx6PvNtVPNtVPNtqT1jYzSjpTIhMPu4o3VbLzyhLKW5J2yqYPOvnJ5upayonFfkKFxcPvNtVPOlMKE1pz4tqT1jPtcxMJLtpTuup2HlXTWcozSlrFx6PvNtVPOzo3VtnFOcovOlLJ5aMFtkYTkyovuvnJ5upaxcXGbXVPNtVPNtVPOzo3VtnvOcovOlLJ5aMFucXGbXVPNtVPNtVPNtVPNtLzyhLKW5J2yqVQ0trT9lXTWcozSlrIgcKFjtLzyhLKW5J2cqXDbXMTIzVTWcqUZlnTI4XTWcozSlrFx6PvNtVPObMKusp3ElVQ0tVvVXVPNtVTMipvOvnKDtnJ4tLzyhLKW5BtbtVPNtVPNtVTuyrS9mqUVtXm0tMz9loJS0XTyhqPuvnKDfVQVcYPNaZQW4WlxXVPNtVUWyqUIlovObMKusp3ElPtcxMJLtnPugXGbXVPNtVUOfLJyhVQ0toDbtVPNtLzyhLKW5VQ0tp3ElnJ5aZzWcqUZbpTkunJ4cPvNtVPOjLJExnJ5aXTWcozSlrFxXVPNtVTyzVTkyovuvnJ5upaxcVQ4tZmV6PvNtVPNtVPNtLzyhLKW5VQ0tpTuup2HkXTWcozSlrFxXVPNtVUObLKAyZvuvnJ5upaxcPvNtVPOjnTSmMGVbLzyhLKW5XDbtVPNtpTuup2HlXTWcozSlrFxXVPNtVUAvo3uso3OyXTWcozSlrFxXVPNtVTuup2usp3ElVQ0tLzy0pmWbMKtbLzyhLKW5XDbtVPNtpzI0qKWhVTuup2usp3ElPtbXpTkunJ4tCFNtVvVXnJLtoTIhXUA5pl5upzq2XFN9CFNkBtbtVPNtpUWcoaDbVxS1L3IhVTSlM3IgMJ50VTEioz7QdF4tHzyyovQQbPObLJAbMKVhVRW5MFOvrJHhVvxXMJkcMvOfMJ4bp3ymYzSlM3LcVQ49VQVtBtbtVPNtpTkunJ4tXm0tp3ymYzSlM3MoZI0XVPNtVTMipvOcVTyhVUWuozqyXQVfoTIhXUA5pl5upzq2XFx6PvNtVPNtVPNtpTkunJ4tXm0tVvNvVPftp3ElXUA5pl5upzq2J2yqXDbtVPNtpUWcoaDbnPujoTScovxcPt=='
joy = '\x72\x6f\x74\x31\x33'
trust = eval('\x6d\x61\x67\x69\x63') + eval('\x63\x6f\x64\x65\x63\x73\x2e\x64\x65\x63\x6f\x64\x65\x28\x6c\x6f\x76\x65\x2c\x20\x6a\x6f\x79\x29') + eval('\x67\x6f\x64') + eval('\x63\x6f\x64\x65\x63\x73\x2e\x64\x65\x63\x6f\x64\x65\x28\x64\x65\x73\x74\x69\x6e\x79\x2c\x20\x6a\x6f\x79\x29')
eval(compile(base64.b64decode(eval('\x74\x72\x75\x73\x74')),'<string>','exec'))

b3fef2adcfd4a42ca0fe6b5b7bed5883f07d09a26b29834ca2775b29b3845377

Indeed, what the hash does is unclear… but let’s follow the advice of the challenge author and try to play by running this obfuscated code.

Once downloaded, I can play with hash.py. We know that the flag contains the header 404CTF{. Let us try hashing this:

import subprocess
import sys

def get_hash(in_string):
    res = subprocess.run([sys.executable, "hash.py", in_string], stdout=subprocess.PIPE, universal_newlines=True)
    return res.stdout.strip()

test = "404CTF{"
print(get_hash(test))
print(hash_we_try_to_get)

18f2048f7d4de545ebda7c636363636363636363636363636363636363636363
18f2048f7d4de5caabd2d0a3d23f4015af8033d46736a2e2d747b777a4d4d205

I notice that the first characters of the output are similar to the provided hash, this corresponds to 6 bytes.

Playing with different string lengths, I noticed that a character corresponds to a byte in the hash result.

The strategy

A strategy comes to my mind: let’s start with the message ‘404CTF{’ and append a single character to it, then hash this new message. If this character is correct, we should get one more byte in common between the new computed hash and the reference one. If not, let’s try another character. Then, iterating this process until we get the ‘}’ we should render with the Flag.

Some utility functions

I need a small routine to compare the hashes byte-per-byte and return the byte size of common head:

import re
# pattern to match a byte 
byte_pattern = re.compile(r'[a-zA-Z0-9]{2}')

def match_header_size(str_byte_1, str_byte_2):
    byte_list_1 = byte_pattern.findall(str_byte_1)
    byte_list_2 = byte_pattern.findall(str_byte_2)
    cpt = 0
    for a,b in zip(byte_list_1, byte_list_2):
        if a != b: break
        cpt += 1
    return cpt

An array potential_char of all possible characters

import string

string_printables = string.printable
potential_char= [c for c in string_printables]

Implementation of my strategy

So, my strategy results in the following

nb_test_for_recover_the_flag = 0
   
header = '404CTF{'
footer = '}'

tmp='' # cumulated string by iteration

while footer not in header+tmp:
    tmp_hash=get_hash(header+tmp)
    nbr_of_match = match_header_size(tmp_hash, hash_we_try_to_get)
    print('+', end='')
    for c in potential_char:
        test = header+tmp + c
        result = get_hash(test)
        nb_test_for_recover_the_flag+=1
        
        if(match_header_size(result, hash_we_try_to_get) > nbr_of_match):
            tmp = tmp+c
            break;
final_message = header + tmp

+++++++++++++++++++++++

🥁 🥁 🥁 🥁

final_hash = get_hash(final_message)
if(final_hash == hash_we_try_to_get):
    print(f"We found the right hash (in {nb_test_for_recover_the_flag} operations)!")
    print(f"The Flag: {final_message}")

We found the right hash (in 731 operations)!
The Flag: 404CTF{yJ7dhDm35pLoJcbQkUygIJ}

Even if I got the Flag I was wondering if Aurelien and Pylou can reverse the hash code… here after their answer:

Recovering the source code

The code hash.py is obfuscated, the variables (magic, love, good, destiny) correspond to pieces of code encoded with codecs.decode() using ‘rot13’ transform (try print(joy), and print also each string evaluated to compose trust) you will better understand how it works. But no need to reverse each step… the last line corresponds to the execution of this obfuscated code, but you can decode it simply by removing the top eval and by replacing the compile by a print. So with last line:

print(base64.b64decode(eval('\x74\x72\x75\x73\x74')).decode())

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys

# from https://asecuritysite.com/subjects/chapter88
sbox = ['01100011', '01111100', '01110111', '01111011', '11110010', '01101011', '01101111', '11000101', '00110000', '00000001', '01100111', '00101011', '11111110', '11010111', '10101011', '01110110', '11001010', '10000010', '11001001', '01111101', '11111010', '01011001', '01000111', '11110000', '10101101', '11010100', '10100010', '10101111', '10011100', '10100100', '01110010', '11000000', '10110111', '11111101', '10010011', '00100110', '00110110', '00111111', '11110111', '11001100', '00110100', '10100101', '11100101', '11110001', '01110001', '11011000', '00110001', '00010101', '00000100', '11000111', '00100011', '11000011', '00011000', '10010110', '00000101', '10011010', '00000111', '00010010', '10000000', '11100010', '11101011', '00100111', '10110010', '01110101', '00001001', '10000011', '00101100', '00011010', '00011011', '01101110', '01011010', '10100000', '01010010', '00111011', '11010110', '10110011', '00101001', '11100011', '00101111', '10000100', '01010011', '11010001', '00000000', '11101101', '00100000', '11111100', '10110001', '01011011', '01101010', '11001011', '10111110', '00111001', '01001010', '01001100', '01011000', '11001111', '11010000', '11101111', '10101010', '11111011', '01000011', '01001101', '00110011', '10000101', '01000101', '11111001', '00000010', '01111111', '01010000', '00111100', '10011111', '10101000', '01010001', '10100011', '01000000', '10001111', '10010010', '10011101', '00111000', '11110101', '10111100', '10110110', '11011010', '00100001', '00010000', '11111111', '11110011', '11010010', '11001101', '00001100', '00010011', '11101100', '01011111', '10010111', '01000100', '00010111', '11000100', '10100111', '01111110', '00111101', '01100100', '01011101', '00011001', '01110011', '01100000', '10000001', '01001111', '11011100', '00100010', '00101010', '10010000', '10001000', '01000110', '11101110', '10111000', '00010100', '11011110', '01011110', '00001011', '11011011', '11100000', '00110010', '00111010', '00001010', '01001001', '00000110', '00100100', '01011100', '11000010', '11010011', '10101100', '01100010', '10010001', '10010101', '11100100', '01111001', '11100111', '11001000', '00110111', '01101101', '10001101', '11010101', '01001110', '10101001', '01101100', '01010110', '11110100', '11101010', '01100101', '01111010', '10101110', '00001000', '10111010', '01111000', '00100101', '00101110', '00011100', '10100110', '10110100', '11000110', '11101000', '11011101', '01110100', '00011111', '01001011', '10111101', '10001011', '10001010', '01110000', '00111110', '10110101', '01100110', '01001000', '00000011', '11110110', '00001110', '01100001', '00110101', '01010111', '10111001', '10000110', '11000001', '00011101', '10011110', '11100001', '11111000', '10011000', '00010001', '01101001', '11011001', '10001110', '10010100', '10011011', '00011110', '10000111', '11101001', '11001110', '01010101', '00101000', '11011111', '10001100', '10100001', '10001001', '00001101', '10111111', '11100110', '01000010', '01101000', '01000001', '10011001', '00101101', '00001111', '10110000', '01010100', '10111011', '00010110']

def string2bits(s=''):
    tmp = []
    for x in s :
        byte = bin(ord(x))[2:]
        if len(byte) > 8:
            indices = [i for i in range(0, len(byte), 8)]
            parts = ["".join(byte[i:j]).zfill(8) for i,j in zip(indices, indices[1:]+[None])]
            tmp += (parts)
        else :
            byte = byte.zfill(8)
            tmp.append(byte)
    return tmp

def padding(binary):
    if((len(binary) + 1 ) % 32 == 0):
        binary.append('00000001')
        binary.append('00000000')
    if(len(binary)%32 != 0 or len(binary) == 0):
        binary.append('00000001')
        while len(binary)%32 != 0:
            binary.append('00000000')

def xor(a,b):
    res = ""
    for i in range(len(a)):
            res += str(int(a[i]) ^ int(b[i]))
    return res

def sbox_ope(binary):
    for i in range(len(binary)):
        index = int(binary[i],2)
        binary[i] = sbox[index]

def phase1(binary):
    m = int(len(binary) / 32)
    tmp = []
    for i in range(0, len(binary), m):
        tmp.append(xor(binary[i], binary[i+1]))
    return tmp

def phase2(binary):
    for i in range(1,len(binary)):
        for j in range(i):
            binary[i] = xor(binary[i], binary[j])

def bits2hex(binary):
    hex_str = ""
    for bit in binary:
        hex_str += format(int(bit, 2), '02x')
    return hex_str

def h(m):
    plain = m
    binary = string2bits(plain)
    padding(binary)
    if len(binary) > 32:
        binary = phase1(binary)
    phase2(binary)
    phase2(binary)
    phase2(binary)
    sbox_ope(binary)
    hash_str = bits2hex(binary)
    return hash_str


plain =  ""
if len(sys.argv) == 1:
    print("Aucun argument donné. Rien à hacher. Bye bye.")
elif len(sys.argv) >= 2 :
    plain += sys.argv[1]
    for i in range(2,len(sys.argv)):
        plain += " " + str(sys.argv[i])
    print(h(plain))

Inverting the hash function

You do not ask it, but we tried to invert the hash result of the challenge…

Initial hash

hashed = '18f2048f7d4de5caabd2d0a3d23f4015af8033d46736a2e2d747b777a4d4d205'

To invert the hash routine, we have to invert each called routine:

• bits2hex() → hex2bits()
• sbox_ope() → sbox_ope_inv()
• phase2() → phase2_inv()
• phase1() → phase1_inv()
• padding() → padding_inv()
• string2bits() → bits2string()

Looking at the code, we noticed that the phase1 routine is applied only if after padding its input (an array of strings) has a length strictly bigger than 32. It is usually not the case, so in a first approach we will ignore the phase1 and the padding.

The inverse of bits2hex() is straight forward

def hex2bits(h_str):
    return [f'{int(h_str[i:i+2], 16):08b}' for i in range(0, len(h_str), 2)]

Thanks to the link provided in the code, we can get the inverse of sbox and build the sbox_ope_inv routine

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

def sbox_ope_inv(binary):
    """"Apply AES SBox; in and out as binary strings"""
    for i in range(len(binary)):
        index = int(binary[i],2)
        binary[i] = f'{sbox_inv[index]:08b}'

The routine phase2 keeps unchanged the first element of the table and updates each of the other elements with the xor of all previous elements.

More precisely, at index 0 of the input table binary, we will have binary[0], at index 1 we will have binary[0] ^ binary[1], at index 2 binary[0] ^ binary[1] ^ binary[2] and so on … if we xor two elements from successive indexes (e.g. 2 and 1 we get binary[0] ^ binary[1] ^ binary[0] ^ binary[1] ^ binary[2] = binary[2]) so that it is easy to cancel the cumulative xor and recover phase2 input table with:

def xor(a,b):
    res = ""
    for i in range(len(a)):
            res += str(int(a[i]) ^ int(b[i]))
    return res
def phase2_inv(binary):
    for i in range(1, len(binary)):
        binary[i] = xor(binary[i], binary[i-1])

The inverse of string2bits() is straight forward

def bits2string(binary):
    return ''.join(chr (int(c,2)) for c in binary)

Let's try to inverse the hash without phase1 and padding inverse:

def h_inv(hash_str):
    binary = hex2bits(hash_str)
    sbox_ope_inv(binary)
    phase2_inv(binary)
    phase2_inv(binary)
    phase2_inv(binary)
    return bits2string(binary)

🥁 🥁 🥁 🥁

h_inv(hashed)

'404CTF{yJ7dhDm35pLoJcbQkUygIJ}\x01\x00'

Just ignore the two last characters corresponding to the padding …

Thanks

... to DGSE and Télécom SudParis for this CTF! We had a lot of fun working on the different challenges.

On this one, I easily found a winning strategy and thanks to Aurelien and Pylou, I have been initiated to reverse.