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 = ''
    port = 1337
    conn = remote(host, port)
    conn.send(password.encode() + '\n'.encode())
    flag = conn.recvuntil('}').decode().split('\n')[2]

def plain(data):
    global found

    decimal.getcontext().prec = 100
    chars = 'aAbBcCdDeEfFgGHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ1234567890@#$%^&*()_+[]/,.-+=;"'
    tmp_lst = list(chars)
    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!')
        found = True
        print('[-] Incorrect! Skipping...\n')
while not found:

Published on : 10 May 2021