Is it possible to crack SHA256, when you know the answer is a coordinate?

Question

I need to crack a sha256 hash, and I know the answer is in coordinates, but I don't know what are the coordinate values example:

3f1c756daec9ebced7ff403acb10430659c13b328c676c4510773dc315784e4e
58.375782 26.742632

Is it possible to create a python script that makes two variables (both with the value 00.000000), then add them togheter (ex: k=i+" "+j), then converts k into sha256 and compares it to the sha256, I'm trying to crack. If it doesn't equal the sha256 being cracked, then it adds i a value (i=i+00.000001) and triess again. and so on and so on

Solution

Producing all possible coordinates between 00.000000 and 99.999999 is easy enough:

from itertools import product
import hashlib

digits = '0123456789'

for combo in product(digits, repeat=16):
    coords = '{}.{} {}.{}'.format(
        ''.join(combo[:2]), ''.join(combo[2:8]),
        ''.join(combo[8:10]), ''.join(combo[10:]))
    hash = hashlib.sha256(coords).hexdigest()
    if hash == '3f1c756daec9ebced7ff403acb10430659c13b328c676c4510773dc315784e4e':
        print coords
        break

This'll brute-force all 10**16 (a big number) combinations. Sit back and relax, this'll take a while.

And by 'a while', we really mean not in your lifetime, or anyone else's. Just iterating over all possible combinations produced by product() takes a huge amount of time, as each added digit to try increases the time required by a factor of 10:

>>> from collections import deque
>>> from itertools import product
>>> from timeit import timeit
>>> digits = '0123456789'
>>> timeit(lambda: deque(product(digits, repeat=8), 0), number=5)
3.014396679995116
>>> timeit(lambda: deque(product(digits, repeat=9), 0), number=5)
30.99540744899423

If producing all possible combinations of 8 digits takes .8 seconds (4s divided by 5 repetitions), 9 digits takes 8 seconds, you can extrapolate from that that 10 digits takes almost 1.5 minutes, etc. Just producing all possible combinations of 16 digits takes 1 million (10 ** 6) times as much time as 10 digits, so 963 days or just onder 3 years to run those in a loop. You could split this task up across 2000 different processes on a large number of computers with enough cores in total to run those processes in parallel, to reduce that to under 12 hours.

Then the loop body itself takes about 2.4 seconds per million iterations:

>>> from random import choice
>>> combo = tuple(choice(digits) for _ in range(16))  # random combination for testing
>>> timeit("""\
... coords = '{}.{} {}.{}'.format(
...     ''.join(combo[:2]), ''.join(combo[2:8]),
...     ''.join(combo[8:10]), ''.join(combo[10:]))
... hash = hashlib.sha256(coords).hexdigest()
... if hash == '3f1c756daec9ebced7ff403acb10430659c13b328c676c4510773dc315784e4e': pass
... """, 'from __main__ import combo; import hashlib')
2.3429908752441406

But you have 10 ** 10 (10 thousand million) more times work than that, totaling roughly 743 years of computation work. Even being able to run 20 thousand parallel processes won't reduce that to a reasonable number (that's still about 13.5 years of work).

Python is just not fast enough for this task. Using GPUs it should be possible to reach 500 million hashes per second (0.5 Gigahash / s), at which point you could run the above brute-force operation and find a solution in about 230 days on such a system. At a cost, of course, because such a rig would cost about $3000-$4000 a month to run! But with enough dedicated hardware you can certainly 'crack' the hash in 'humane' timeline.

Comments

[Admin]

Though "a while" is much better than "longer than the time left until the heat death of the universe". My guesstimate is something in the order of a few years (at best three months), assuming no parallelization.

[flyingfoxlee]

Maybe you could only count the coordinates of the land area on earth to eliminate the unnecessary computation.

[Yolanda Ruiz]

They seem to be global positionning coordinates though, so the ranges are probably [-180..+180], [-90..+90]