# SHA-512 partial preimage

I was looking at how SHA-512 works, and I have a question. Imagine I want an input $N$ of 512 bits whose hash in hexadecimal starts with the digits 12345678. How could I determine an input $N$ to get that hash output?

As far as we know, SHA512 acts like a random function. So, the only way we know to find a preimage whose hash starts with 0x12345678, is to go through distinct preimages, and hash each one until we find one that starts with 0x12345678.

If the output of SHA512 is equidistributed (and we have no reason to believe it isn't), then the probability of any hash starting with 0x12345678 is $2^{-32}$, hence the expected number of hashes you would need to perform is $2^{32}$, which is an achievable work effort.

• I would like to try it. There is any kind of code in internet to test this? (maybe you know) – Gerardo May 14 '15 at 19:38
• Perhaps OpenSSL... – poncho May 14 '15 at 19:43
• How should I proceed? – Gerardo May 14 '15 at 19:50
• Write a quick program that selects a preimage, calls OpenSSL to generate the SHA512 hash, then look at the value it generated; if it didn't start with the value you were looking for, try again with a different preimage. You can optionally keep a count of how many iterations you go through before you succeed. – poncho May 14 '15 at 19:59

Bitcoin uses a problem similar to that as a proof of work, although it uses SHA256 (actually SHA256 twice in a specified fashion), and you're modifying a small part of a larger message.

With Bitcoin, you're trying to find a message which hashes to a value less than a specified target, which is expressed as a difficulty level. The higher the difficulty, the smaller the target and the longer it takes to modify the message until you find one that matches.

In particular, the first part of the hash will be all zeroes, a rough estimate of the current difficulty in the Bitcoin network is how many leading zeroes you need to get. For example, currently the Bitcoin network is generating close to 300 million giga-hashes per second (300 quadrillion, 3E17) in order to find one block approximately every 10 minutes with 50 leading 0 bits (more specifically, where the first bits are less than 0x00000000000000001717F, currently).

Changing it to match a given bit pattern as you're doing is exactly the same type of problem, where the chance of any one attempt is $1/2^n$ if $n$ is the number of bits you want to pre-determine. On average you'd have to try $2^{32}$ hashes to find one with 32 bits specified, such as 0x12345678 as the first 32 bits.

• Actually, on average, you'd have to try $2^{32}$ hashes to find one with 32 bits specified. – poncho Apr 29 '15 at 18:39
• I was thinking of an exhaustive search, where each attempt reduces the pool of items to try. With a truly random independent guess, ln(0.5)/ln(1 - 1/2^32)is about 2^31.47, where the chance of having found it hits 50%. – Steve Peltz May 1 '15 at 6:03
• @StevePeltz Average != median. – CodesInChaos May 1 '15 at 9:45
• Average can mean median, mean, mode, but I see what you mean. If you're trying to figure out how long it will take to guess n hashes, you want the mean. Thanks, I was careless! – Steve Peltz May 1 '15 at 10:44