4
$\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$
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
    $\begingroup$ Many thanks! I didn't know of scrypt before, so this also very interesting! $\endgroup$ – Chris Aug 14 '15 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$
  • $\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$ – Chris Aug 14 '15 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$ – SEJPM Aug 14 '15 at 20:11
  • $\begingroup$ I think if I buy 10000 servers I'll get a reduction on the price. :) $\endgroup$ – Chris Aug 14 '15 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.