Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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
up vote 2 down vote accepted

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.

You might find this page helpful.

share|improve this answer
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: NIST wrote this into the final SHA-3 report: “Skein and BLAKE have the best overall software performance.” – Zooko Oct 26 '15 at 17:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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