San Diego CTF 2021: A Prime Hash Candidate | szymanski.ninja

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):

PASSWORE@HASHINEH
O`SSWORE@HASHINEH
NSSWORE@HASHINEH
P@rSWORE@HASHINEH
O_rSWORE@HASHINEH
N~rSWORE@HASHINEH
P?SWORE@HASHINEH
O^SWORE@HASHINEH
N}SWORE@HASHINEH
PARrWORE@HASHINEH

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
PASSWORE@HASHINEH
Login successful!
Flag: sdctf{st1ll_3553nt14lly_pl@1n_txt}

nc phc1.sdc.tf 1337

Please enter password below
O`SSWORE@HASHINEH
Login successful!
Flag: sdctf{st1ll_3553nt14lly_pl@1n_txt}

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

submit

Flag

sdctf{st1ll_3553nt14lly_pl@1n_txt}