Unstoppable force meets immovable object 2

Author: Nolawz
Category: Web
Points: 159
Solves: 62
Files: UFMIO2.zip
Flag: Blitz{b1r7hd4y_p4r4d0x_3475_5h177y_h45h35_l1k3_7h15}

Just because I was in a happy mood to give an easy challenge due to my birthday doesn’t mean I can’t increase its difficulty.

http://ufmiotwo-asdhwsad.blitzhack.xyz/

This challenge used another custom hash instead of the simple one in the first challenge. Although the algorithm for it might seem complicated, there is one thing that we can exploit about it. The output produced by this hash function only 40 bits long. Therefore, we can exploit this using Birthdy Attack. So a collision can probably be found within sqrt(2^40) = 1048576 tries which is a reasonable amount of tries to brute force.

Here is the solution script for this challenge:

1
import random
2
import string
3
import requests
4

5

6
def complex_custom_hash(data_string):
7
    data_bytes = data_string.encode("utf-8")
8

9
    P = 2**61 - 1
10
    B = 101
11

12
    hash_val = 0
13

14
    for byte_val in data_bytes:
15
        hash_val = (hash_val * B + byte_val) % P
16

17
    length_mix = (len(data_bytes) * 123456789) % P
18
    hash_val = (hash_val + length_mix) % P
19

20
    chunk_size = 40
21
    num_chunks = 64 // chunk_size
22

23
    folded_hash = 0
24
    temp_hash = hash_val
25

26
    for _ in range(num_chunks):
27
        chunk = temp_hash & ((1 << chunk_size) - 1)
28
        folded_hash = (folded_hash + chunk) % (1 << chunk_size)
29
        temp_hash >>= chunk_size
30

31
    final_small_hash = folded_hash
32

33
    scrambled_hash = 0
34
    for _ in range(3):
35
        scrambled_hash = (
36
            final_small_hash ^ (final_small_hash >> 7) ^ (final_small_hash << 3)
37
        ) & ((1 << chunk_size) - 1)
38
        final_small_hash = scrambled_hash
39

40
    return f"{scrambled_hash:04x}"
41

42

43
def generate_random_string(min_len=10, max_len=50):
44
    length = random.randint(min_len, max_len)
45
    characters = (
46
        string.ascii_letters + string.digits + string.punctuation + string.whitespace
47
    )
48
    return "".join(random.choices(characters, k=length))
49

50

51
def find_collision(hash_function, max_attempts=2000000):
52
    found_hashes = {}
53
    attempts = 0
54

55
    while attempts < max_attempts:
56
        attempts += 1
57
        print(f"{attempts}/{max_attempts}")
58
        input_string = generate_random_string()
59
        current_hash = hash_function(input_string)
60

61
        if current_hash in found_hashes:
62
            colliding_input = found_hashes[current_hash]
63
            if colliding_input != input_string:
64
                print(f"[!!!] Collision found after {attempts} attempts!")
65
                print(f"Input 1: {colliding_input.encode()}")
66
                print(f"Input 2: {input_string.encode()}")
67
                print(f"Both hash to: {current_hash}")
68
                return input_string, colliding_input
69

70
        found_hashes[current_hash] = input_string
71

72
    print(f"Search completed. No collision found within {max_attempts} attempts.")
73
    return None, None
74

75

76
url = "http://ufmiotwo-asdhwsad.blitzhack.xyz/"
77
username, password = find_collision(complex_custom_hash)
78

79
r = requests.post(url, data={"username": username, "password": password})
80
print(r.text)