Sdctf 2021

A prime hash candidate

Solved by : thewhiteh4t

• We are given a hash function in this challenge which we had to reverse
• hash initializes a variable out
• then it iterates over every character of the password given to it
• for every character it multiplies out by 31
• then adds the ascii value of the character to it

Reverse :

• first I defined a character set which contains :
  • alphabets in both cases
  • numbers
  • symbols
• then I randomized the character set
• the PASSWD is a long integer, python has accuracy problems with long integers so I used decimal library to set precision
• now we don’t know which characters were processed by the hash function, we just have the output so we need to brute force each character of the actual password
• we can get the the ascii value of the characters by using ord() function in python
• since we are going reverse we will subtract the ascii value found from the target hash
• in the hash function the result was being multiplied by 31, so if we have the correct character, the result of hash - ord(character) % 31 will be 0 because it will be fully divisible by 31.
• during testing I saw that multiple characters from our character set produced 0 modulus at a certain point which hints that one password generated by our reverse function may not be correct, hence we are randomizing the character set and generating more random passwords
• so whenever the modulus is 0 we will divide the hash by 31 eventually reducing it
• when enough characters are found and hash reduces to 0 we pass the newly generated password into the hash function provided by the challenge to verify if it matches the challenge hash
• if we get a correct match we send it to the server and get our flag!

#!/usr/bin/env python3

import random
import decimal
from pwn import *

PASSWD = "59784015375233083673486266"
found = False

def hash(data):
    out = 0
    for c in data:
        out *= 31
        out += ord(c)
    return str(out)

def submit(password):
    host = 'phc1.sdc.tf'
    port = 1337
    conn = remote(host, port)
    conn.send(password.encode() + '\n'.encode())
    flag = conn.recvuntil('}').decode().split('\n')[2]
    print(f'\n{flag}\n')

def plain(data):
    global found

    decimal.getcontext().prec = 100
    chars = 'aAbBcCdDeEfFgGHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ1234567890@#$%^&*()_+[]/,.-+=;"'
    tmp_lst = list(chars)
    random.shuffle(tmp_lst)
    chars = ''.join(tmp_lst)
    num = 31
    enc = decimal.Decimal(data).to_integral_exact()
    tmp = 0
    password = ''
    positive = True
    while positive:
        for char in chars:
            if tmp < 0:
                positive = False
            chr_int = ord(char)
            tmp = enc - chr_int
            rem = tmp % num
            if rem == 0:
                enc = decimal.Decimal(tmp / num).to_integral_exac()
                password += char
    password = password[::-1]
    print(f'[!] Trying : {password}')
    pass_hash = hash(password)
    if pass_hash == PASSWD:
        print('[+] Correct Password!')
        submit(password)
        found = True
    else:
        print('[-] Incorrect! Skipping...\n')
while not found:
    plain(PASSWD)