Find a string for which hash() starts with 0000

Question

I've got a task from my professor and unfortunately I'm really confused.

The task:

Find a string D1 for which hash(D1) contains 4 first bytes equal 0. So it should look like "0000....."

As I know we cannot just decrypt a hash, and checking them one by one is kind of pointless work.

Answer 1

I've got a task from my professor...

Find a string D1 for which hash(D1) contains 4 first bytes equal 0. So it should look like "0000....."

As I know we cannot just decrypt a hash, and checking them one by one is kind of pointless work.

In this case it seem like the work is not really "pointless." Rather, you are doing this work because your professor asked you to do it.

Some commenters have mentioned that you could look at the bitcoin blockchain as a source of hashes, but this will only work if your hash of interest is the same one use by bitcoin (double-SHA256!)

The easiest way to figure this out in general is just to brute force it:

Pseudo-code a la python

for x in range(10*2**32):  # Any number bigger than about 4 billion should work
    x_str = str(x)  # Any old method to generate some bytes to hash should work
    x_bytes = x_str.encode('utf-8')
    hash_bytes = hash(x_bytes)  # assuming hash() returns bytes 
    if hash_bytes[0:4] == b'\x00\x00\x00\x00':
        print("Found string: {}".format(x_str))
        break

Answer 2

I wrote a short python3 script, which repeatedly tries hashing random values until it finds a value whose SHA256 hash has four leading zero bytes:

import secrets
import hashlib

while(True):
    p=secrets.token_bytes(64)
    h=hashlib.sha256(p).hexdigest()
    if(h[0:8]=='00000000'): break

print('SHA256(' + p.hex() + ')=' + h)

After running for a few minutes (on my ancient Dell laptop), it found a value whose SHA256 hash has four leading zero bytes:

SHA256(21368dc16afcb779fdd9afd57168b660b4ed786872ad55cb8355bdeb4ae3b8c9891606dc35d9f17c44219d8ea778d1ee3590b3eb3938a774b2cadc558bdfc8d4)=000000007b3038e968377f887a043c7dc216961c22f8776bbf66599acd78abf6

The following command-line command verifies this result:

echo -n '21368dc16afcb779fdd9afd57168b660b4ed786872ad55cb8355bdeb4ae3b8c9891606dc35d9f17c44219d8ea778d1ee3590b3eb3938a774b2cadc558bdfc8d4' | xxd -r -p | sha256sum

As expected, this produces:

000000007b3038e968377f887a043c7dc216961c22f8776bbf66599acd78abf6

---

Edit 5/8/21

Optimized version of the script, based on my conversation with kelalaka in the comments below.

import secrets
import hashlib

N=0
p=secrets.token_bytes(32)
while(True):
    h=hashlib.sha256(p).digest()
    N+=1
    if(h.hex()[0:8]=='0'*8): break
    p=h

print('SHA256(' + p.hex() + ')=' + h.hex())
print('N=' + str(N))

Instead of generating a new random number in each iteration of the loop to use as the input to the hash function, this version of the script uses the output of the hash function from the previous iteration as the input to the hash function in the current iteration. On my system, this quadruples the number of iterations per second. It found a match in 1483279719 iterations in a little over 20 minutes:

$ time python3 findhash2.py
SHA256(69def040a417caa422dff20e544e0664cb501d48d50b32e189fba5c8fc2998e1)=00000000d0d49aaaf9f1e5865c8afc40aab36354bc51764ee2f3ba656bd7c187
N=1483279719

real    20m47.445s
user    20m46.126s
sys 0m0.088s

Answer 3

The sha256 hash of the string $Eo is 0000958bc4dc132ad12abd158073204d838c02b3d580a9947679a6

This was found using the code below which restricts the string to only UTF8 keyboard characters. It cycles through the hashes of each 1 character string (technically it hashes bytes, not strings), then each 2 character string, then each 3 character string, then each 4 character string (it never had to go to 4 characters, so I'm not 100% sure the math for that part of the function is correct).

The 'limit" value is included to prevent the code from running forever in case a match is not found. This ended up not being necessary as a match was found in 29970 iterations and the execution time was nearly instantaneous.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from hashlib import sha256

utf8_chars = list(range(0x21,0x7f))

def make_str(attempt):
    if attempt < 94:
        c0 = [attempt%94]
    elif attempt >= 94 and attempt < 8836:
        c2 = attempt//94
        c1 = attempt%94
        c0 = [c2,c1]
    elif attempt >= 8836 and attempt < 830584:
        c3 = attempt//8836
        c2 = (attempt-8836*c3)//94
        c1 = attempt%94
        c0 = [c3,c2,c1]
    elif  attempt >= 830584 and attempt < 78074896:
        c4 = attempt//830584
        c3 = (attempt-830584*c4)//8836
        c2 = ((attempt-830584*c4)-8836*c3)//94
        c1 = attempt%94
        c0 = [c4,c3,c2,c1]
    return bytes([utf8_chars[i] for i in c0])

target = '0000'
limit = 1200000
attempt = 0
hash_value = sha256()
hash_value.update(make_str(attempt))
while hash_value.hexdigest()[0:4] != target and attempt <= limit:
    hash_value = sha256()
    attempt += 1
    hash_value.update(make_str(attempt))
t = ''.join([chr(i) for i in make_str(attempt)])
print([t, attempt])