6
$\begingroup$

I am looking for a cryptographic hash function optimized for speed on short inputs, in order to implement a pseudorandom generator with expansion factor 2 (e.g. takes 16 bytes of input and outputs 32 pseudorandom bytes).

Here are some natural candidates I tried:

  • SHA256: good baseline
  • Blake2: designed for speed on large inputs, does not perform as well on short inputs
  • AES-CTR: faster than SHA256 when the hardware supports AES-NI. The input is used as a key for AES to encrypt a predefined byte array of the desired output length. However, re-initializing the cipher for each call to the hash function is costly.

I also found this interesting construction: STHash. It is a keyed cryptographic hash function optimized for speed on large inputs. I don't mind having a keyed hash function instead of a general-purpose one.

Is there any analogous construction for short inputs, or a more efficient way to leverage AES-NI than AES-CTR?

Some informal benchmarks

For each hash function, I hash an array of 16 bytes into a 32 bytes array, and I repeat 10 million times. For stream ciphers like AES and ChaCha, I create a new cipher at each iteration with the input as key on a public fixed plaintext and nonce. If the cipher needs a 32-bit key, I just pad the input with 0. If the hash function does not produce enough bits (e.g. SipHash outputs only 128 bits), I run it several times.

I am running Rust Nightly on an Intel® Core™ i7-1065G7 CPU @ 1.30GHz × 8, the experiments run on a single thread.

  • SipHash 1-3: 476.9ms
  • Chacha8: 590.4ms
  • SipHash: 670.3ms
  • AES-128: 665.3ms
  • SHA256: 780.4ms
  • Blake2s: 1413.9ms

For information, some results about Haraka (using a not well-known optimized implementation):

  • Haraka-v2 256-5: 55.2ms
  • Haraka-v2 256-6: 69.9ms
Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Could you try Chacha or HChacha and then post your answer with good charts? $\endgroup$
    – kelalaka
    Oct 9, 2020 at 15:36
  • 1
    $\begingroup$ Another thing to think about, other than @kelalaka's suggestion of (H)ChaCha, would be Haraka v2 (eprint.iacr.org/2016/098), which is specifically designed as a short-input hash for post-quantum hash-based schemes. SipHash is short-input, but entirely unusable as a general-purpose hash. $\endgroup$
    – xorhash
    Oct 11, 2020 at 14:18
  • 1
    $\begingroup$ And, actually, you can post your current results, and add new ones over time. During this, you will get more comments and points :) $\endgroup$
    – kelalaka
    Oct 11, 2020 at 14:30
  • 1
    $\begingroup$ Haraka uses the AES instruction set to accelerate its performance, and is designed from the start for short inputs. Try running 1MB through that vs SHA256 on a system without AESNI, and you will see a very different result $\endgroup$
    – Richie Frame
    Oct 12, 2020 at 23:41
  • 1
    $\begingroup$ Caution: AES (esp. AES-256) is not designed to be used with adversaries in control of "input used as a key", that is for resistance to related-key attacks. Things are not as bad as with TEA being used that way in the hash for the code authentication of the Xbox (1) but that's still a dangerous line. Post Scriptum: Details on that hash-second-preimage attack of the Xbox become hard to find, there's not much in this. $\endgroup$
    – fgrieu ♦
    Oct 15, 2020 at 5:43

2 Answers 2

Reset to default
2
$\begingroup$

You can use HighwayHash. It is a fast SIMD-based keyed hash function (5x faster than SipHash) with security claims and suitable for hashing short inputs.

enter image description here

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ As for their security claim, to quote the paper: "We are not experienced cryptographers", "we rely on statistical testing to validate our main claim" - I wouldn't rely on that very heavily at all... $\endgroup$
    – poncho
    Oct 19, 2020 at 21:42
1
$\begingroup$

Did you try SipHash, especially the reduced-round version SipHash-1-3?

It was explicitly designed for short input, doesn’t require key expansion, is fast on pretty much all kind of architectures, and can output 64 or 128 bit.

The name might be confusing, though: a key is required, but since you mentioned that it wasn’t an issue for your use case, give it a try.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the suggestion, SipHash 1-3 performs quite well (I edited the benchmarks). However I am unsure of the cryptographic strength of SipHash: the documentation mentions "Although the SipHash algorithm is considered to be generally strong, it is not intended for cryptographic purposes. As such, all cryptographic uses of this implementation are strongly discouraged." Also, since the output is just 128 bits, I have to run it several times to produce 32 bytes). Is SipHash suitable for a cryptographic PRG? $\endgroup$
    – d1v
    Oct 18, 2020 at 21:36
  • 1
    $\begingroup$ @d1v: SipHash positively requires a (128-bit) secret key to be secure against collision. SipHash-2-4 (with secret key) is the minimum parametrization that I see supported as safe in the defining paper. But if SipHash-1-3 is broken, I missed it. The best attack I found is in Differential Cryptanalysis of SipHash. Also see Christoph Dobraunig's master thesis. $\endgroup$
    – fgrieu ♦
    Oct 19, 2020 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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