5
$\begingroup$

If I have to chose a 64 bit preimage resistant hash function; will there be any difference in security between

How long will it take an attacker to find a 64 bit preimage (e.g., minutes, weeks or years)?

$\endgroup$

2 Answers 2

5
$\begingroup$

SipHash doesn't claim to be a secure hash function. Only a secure MAC. So if you try to use it as a hash function, with a constant, public key, you are on your own.

SHA-512/64 should be a "secure" 64-bit hash, which is of course not enough for a truly secure hash, since it only has 32-bit collision resistance. However, since you only desire preimage resistance, it may have its uses.

How long will it take an attacker to find a 64 bit preimage (e.g., minutes, weeks or years)?

That depends on the attacker's computational power, of course. With a typical desktop CPU you can calculate around $2^{20}$ to $2^{25}$ SHA-512 hashes per second. So a brute force preimage search would take maybe $2^{40}$ seconds, or tens of thousands of years. GPUs could reduce that by a large factor, but it would still likely be centuries.

However, the whole bitcoin userbase is currently (as of early 2016) hashing over $2^{60}$ hashes per second, and even taking into account a small additional factor from SHA-512 vs. SHA-256, you'd be inverting the hash in less than a minute at that rate.

If you want something that takes longer to invert, you should use a password-hashing function, like scrypt with sufficiently large parameters.

$\endgroup$
1
  • 1
    $\begingroup$ Many thanks! I didn't know of scrypt before, so this also very interesting! $\endgroup$ Commented Aug 14, 2015 at 20:24
2
$\begingroup$

A quick resarch showed that there are no (good) attacks on Siphash. For SHA-512 there are defintely no known attacks. The first 64 bits of SHA-512 should have the same security guarantees as full SHA-512 has.

So breaking any of the two comes down to how fast they are.
SHA-512 is slower, in particular it achieves 192.5 cycles / byte in a 64-bit C implementation on an Intel Core 2 Duo with 10 byte messages (enough to find preimages for 64-bit truncation). This means you'd need 1925 cycles to test any potential pre-image. Now let's quickly multiply this by the number of tries you have to do: $1925\times 2^{64} \approx 2^{75}$, meaning you need to invest $\approx 2^{75}$ cycles to find a pre-image for SHA-512. Now let's assume you run a 2GHz CPU, this means you'd need $2^{75} / 2^{31}\approx 2^{44}$ seconds resulting in 557k years a single 2GHz Intel Core 2 Duo CPU would need. Now assume that you have a supercomputer with 1.5 million cores, meaning you'd need $\approx 0.33$ years to find a pre-image with this setup.

Now consider that Intel Core 2 Duos are rather old and SHA-512 can be significantly faster with newer CPUs and that this was a C implementation, whereas an optimized assembler implementation also is somewhat faster. And now also consider that SipHash is faster in usage than SHA-512 meaning that you need even less time.

Concerning whether there will be any difference in security:
No, there shouldn't be any difference in security other than implied by the speed-up when using SipHash.

TL;DR:

One needs a few months at maximum if there are enough ressources to find a 64-bit pre-image.

$\endgroup$
3
  • $\begingroup$ Ok, thanks! So if I assume that SipHash is 15 times faster than SHA-512, then finding a preimage for SipHash on a single 2GHz Intel Core 2 Duo will take 37 years, and on the Stanford supercomputer it will take about a week. $\endgroup$ Commented Aug 14, 2015 at 20:04
  • 1
    $\begingroup$ @Chris, replace 37 with 37k = 37000 then yes. However I think that this may be feasible if an attacker is well-funded assuming you can indeed get a significant speed-up by using ASM, modern processors and more cores (something like 10 servers with a full set of 8 Xeon E7 8890v3 equipped, hint: this is 1440 physical cores for a mere $560k) - Or by simply directly using FPGAs and ASICs for this pupose... (but you could build up your own small EC2 with such computing power ;) $\endgroup$ Commented Aug 14, 2015 at 20:11
  • $\begingroup$ I think if I buy 10000 servers I'll get a reduction on the price. :) $\endgroup$ Commented Aug 14, 2015 at 20:33

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.