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. 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. Jan 26 '14 at 2:04
• @e-sushi The OP obviously needs first pre-image resistance, those don't offer it. Jan 26 '14 at 11:03