9
$\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
$\endgroup$
11
  • 1
    $\begingroup$ Could you try Chacha or HChacha and then post your answer with good charts? $\endgroup$
    – kelalaka
    Oct 9, 2020 at 15:36
  • 2
    $\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$ 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

4 Answers 4

6
+500
$\begingroup$

[For devices with the AES-NI instruction set]

I highly recommend looking at the Davies-Meyer construction based on fixed-key AES. By now, it has been used in dozens of different works, and though it is of course not a perfectly standard assumption on AES, it is quite widely accepted as a plausible one. In particular, it provably yields a PRG when modeling AES as a random permutation.

The construction is as follows:

  • Fix two keys $(K_0, K_1)$ once for all. They are public and will never change, hence you will only have to do the key schedule twice.
  • On input $x$ of size 16 Bytes, output $(\mathsf{AES}_{K_0}(x) \oplus x,\mathsf{AES}_{K_1}(x) \oplus x)$.

Note the crucial XOR with $x$ (the construction would of course be insecure without it, as AES is invertible given the keys). A similar variant of the above, which requires a single key schedule and provides the same security (when modeling AES as a permutation) is:

  • Fix one key $K$ once for all.
  • On input $x$ of size 16 Bytes, output $(\mathsf{AES}_{K}(x) \oplus x,\mathsf{AES}_{K}(x\oplus 1) \oplus (x\oplus 1))$.

To read more about this approach, this is the proper starting point. In particular, you will see discussions on related constructions achieving different security properties. I don't think the paper directly proves that the exact constructions I sketched above are PRGs (when modeling AES as a random permutation), but the proof techniques that they use (using Patarin's H-coefficient technique) can be easily adapted to prove it (I worked out this exact analysis over the summer).

There are dozens of papers using this construction to implement the PRG required for the GGM pseudorandom function. This is especially common for implementing function secret sharing, or for building MPC-in-the-head post-quantum signatures (I can provide a sample of pointers upon request).

As for speed, fixed-key AES with the AES-NI assumption can be as fast as 1.3 cycles per Byte, which seems very hard to beat (XORs are of course super fast as well, especially using vector instructions). See e.g. here for a reference that indicates this number.

=== EDIT (answering OP's comment below) ===

As far as I know, Davies-Meyer and Matyas-Meyer-Oseas are two slightly incorrect ways of referring to the same construction (the one I described above). Originally, both Davies-Meyer and Matyas-Meyer-Oseas are compression functions to be used in hash function constructions from block ciphers:

  • Davies-Meyer: $H_i = E_{m_i}(H_{i-1}) \oplus H_{i-1}$ (i.e. the next block is computed from the previous block using the current message block $m_i$ as the key)
  • Matyas-Meyer-Oseas: $H_i = E_{g(H_{i-1})}(m_i) \oplus m_i$ (i.e. the next block is computed from the message block using the some function of the previous block as the key)

In our context, the key is always fixed anyway and there is no compression function - we're building a PRG. But the design is somewhat analogeous to either of the above and can be seen as either with a slight abuse of definitions of what counts as the previous block and what counts as a message block.

I think the terminology Matyas-Meyer-Oseas was the one originally used here, but later works (e.g. this one) switched to Davies-Meyer, probably because it felt a slightly more accurate naming (but both are debatable).

$\endgroup$
4
  • $\begingroup$ Notable fact: the single-key variant is distinguishable from a random function even without knowledge of $K$, because complementing the low-order bit of input $x$ exchanges the halves of the output. However, when the goal is collision-resistance or preimage resistance, that's a non-issue (at worse the cost of brute force w.r.t. cost of an evaluation would be halved). This property can even be a feature when we have to compute or/and store the hashes of consecutive values. And if undesirable, this property can be removed if we restrict input to 127 bits. $\endgroup$
    – fgrieu
    Dec 7, 2023 at 7:55
  • $\begingroup$ Indeed! But here my claim is precisely about pseudorandomness where the game is the following: $x$ is sampled uniformly at random, and a coin is tossed. If the coin returns 0, I send you the output $\mathsf{PRG}(x)$, which has length $2|x|$. If the coin returns 1, I send you a random bitstring of length $2|x|$. The PRG is secure if your advantage over the random guess in guessing what the coin toss was is negligible. $\endgroup$ Dec 7, 2023 at 12:09
  • $\begingroup$ Thank you! It's been a while since my original post, but at the time I ended up using the Matyas-Meyer-Oseas construction, which looks similar to what you suggest. My use case was indeed function secret sharing, so I followed existing FSS work such as Splinter. Could you elaborate on the difference between Davies-Meyer and Matyas-Meyer-Oseas? $\endgroup$
    – d1v
    Dec 8, 2023 at 0:50
  • $\begingroup$ I answered in the post directly, since it does not fit in a short comment :) $\endgroup$ Dec 11, 2023 at 10:20
2
$\begingroup$

These days, on CPUs with AES hardware acceleration, Areion512 looks like a perfect fit and is likely to beat other options from a performance perspective.

Areion512 is a very efficient 512-bit permutation based on the AES round function.

Since introducing a key is an option, you can use $P(m \oplus k) \oplus k$ to efficiently expand 16 bytes into 32 bytes ($P$ being the Areion512 permutation and $m$ padded to 32 bytes).

$\endgroup$
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.

$\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
  • 3
    $\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
1
$\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

$\endgroup$
1
  • 11
    $\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

Your Answer

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

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