# A fast non-cryptographic hash function that is “strong enough”?

I'm designing a simple one-time-password mechanism for authentication against a possibly-insecure server - i.e. I don't want to use symmetric shared secrets.

The first idea that came into mind was using a hash-chain with a cryptographic hash function, where each device has a random $\text{key}$ and broadcasts $H^n(\text{key}), H^{n-1}(\text{key}), H^{n-2}(\text{key}), \ldots, H^{1}(\text{key}), \text{key}$. However, storing the whole chain requires too much memory for my needs.

I found some techniques here and here to store only few elements from the chain ($H^{n-k}(\text{key}), H^{n-2k}(\text{key}), H^{n-3k}(\text{key}), ...$), and calculate the elements in between dynamically. This converts the "space problem" to a "calculation cycles problem" - unfortunately all the cryptographic hash functions that I've checked require too many cycles (=too much power consumption) for my needs, considering the fact that I have to calculate them multiple times in order to save a significant amount of space.

I consider using less secure hash function for the dynamic hash calculation. This hash will be used only for the elements "between" $H^{n-k}(\text{key}), H^{n-2k}(\text{key}), H^{n-3k}(\text{key}), ...$ so it has to be "unbreakable" only for $k$ time - suppose a key is generated every minute, finding $k$ sequential preimages in $k$ minutes should be "really hard" (but finding them in $10k$ minutes may be possible).

I don't care about second preimage resistance, or defending against very resourceful attackers.

Do you have any suggestions for a hash function? What about SipHash-2-4?

-
AES with a fixed key could be used as one-way function: $H^{i+1}=AES(H^i) \oplus H^i$. But it's not a recommended mode. – CodesInChaos Jan 25 '14 at 23:51
Is SipHash fater or slower than AES? What if I use the less recommended SipHash-1-2 ? – Ozo Jan 25 '14 at 23:59
Just removed my previous silly comment... don't bother replying... You're referring to the Davies-Meyer compression, right? I guess that the Matyas-Meyer-Oseas is also an option. – Ozo Jan 26 '14 at 0:20
You should definitely check this answer at Programmers.SE, which was posted to a similar question. – e-sushi Jan 26 '14 at 2:04
@e-sushi The OP obviously needs first pre-image resistance, those don't offer it. – CodesInChaos Jan 26 '14 at 11:03

So what you need is a fast cryptgraphically secure hash function? There are some. If you're in hardware Keccak might be an option as it uses many bit-permutations.

If you're in software there are Skein and Blake2b/s/bp/sp. Skein was the fastest hash-function of the SHA-3 competition and Blake2 is the successor to BLAKE, the second fastest hash-function in the SHA-3 competition.

-
Bit permutations in software are not as bad as most people think (at least for 32-bit or 64-bit CPUs), see Knuth: The Art of Computer Programming Vol. 4, 7.1.3, p.13. – j.p. Aug 25 '15 at 13:05
Skein wasn't necessarily the fastest SHA-3 finalist. That depends on what machine you're benchmarking on. Here are a lot of them: bench.cr.yp.to/results-hash.html NIST wrote this into the final SHA-3 report: “Skein and BLAKE have the best overall software performance.” blake2.net/acns/slides.html – Zooko Oct 26 '15 at 17:24