San Diego CTF 2021: A Prime Hash Candidate

A Prime Hash Candidate

Category: Crypto

chal

MEDIUM

After the rather embarrassing first attempt at securing our login, our student intern has drastically improved our security by adding more parameters. Good luck getting in now!

server.py

https://cdn.discordapp.com/attachments/840019144870592552/840020988179906591/server.py

Connect via

nc phc2.sdc.tf 1337

server.py

#!/usr/bin/env python3
PASSWD = "59784015375233083673486266"

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

Solution

At a glance the hash algorithm has huge amount of collisions. I’ve created the script to recover all possible passwords.

#!/usr/bin/env python3
from itertools import product

PASSWD = "59784015375233083673486266"

def recover(data):
    length = -1
    c = data
    while c > 0:
        length += 1
        c = c // 31
    opt = [2, 3, 4]
    for i in product(opt, repeat=length):
        c = data
        password = ''
        for j, k in enumerate(i):
            d = c % 31
            password = chr(d + 31 * k) + password
            c = c - (d + 31 * k)
            assert(c % 31 == 0)
            c = c // 31
        if c == 0:
            print(password)

recover(int(PASSWD))

Output (first ten rows):

First recovered password seemed to be the right one, however I’ve checked few and all were suitable ;-)

nc phc1.sdc.tf 1337

Please enter password below
[email protected]
Login successful!
Flag: sdctf{[email protected]_txt}
nc phc1.sdc.tf 1337

Please enter password below
O`[email protected]
Login successful!
Flag: sdctf{[email protected]_txt}

I can’t agree with the flag sentence, in my opinion it’s worse than plaintext ;-)

submit

Flag

sdctf{[email protected]_txt}

Privacy Policy
luc © 2021