9
$\begingroup$

I'm looking to implement Lamport signatures as a little fun project, and I need a fast one way function that maps $\{0,1\}^{256} \rightarrow \{0,1\}^{256}$.

I was wondering whether I could safely use the ChaCha core for that, by setting the input as the key, the nonce and counter to 0 and truncating the output to 256 bits?

If there are other secure, fast one-way functions I'd love to hear about them.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ If you only need one-way-ness / first pre-image resistance, you should be fine, since that maps directly to a key recovery attack on ChaCha. If you need collision resistance, don't use it. $\endgroup$ – CodesInChaos Oct 23 '13 at 7:41
  • $\begingroup$ @CodesInChaos : $\:$ Do you have any clue regarding that and second-preimage resistance? $\hspace{.9 in}$ $\endgroup$ – user991 Oct 23 '13 at 8:48
  • $\begingroup$ @RickyDemer I don't know much about that, but DJB emphasized that Salsa20 is designed as a cipher, not as a collision resistant hash. He even renamed the core from "hash" to "core" to avoid misunderstandings. "The Salsa20 core does not compress and is not collision-resistant." $\endgroup$ – CodesInChaos Oct 23 '13 at 8:48
  • $\begingroup$ @CodesInChaos I only need preimage resistance for the security of a Lamport signature if I'm not mistaken. $\endgroup$ – orlp Oct 23 '13 at 9:03
  • $\begingroup$ @nightcracker For the one-way function part, yes. But you'll also need a collision resistant hash for the message. $\endgroup$ – CodesInChaos Oct 23 '13 at 9:05
9
$\begingroup$

ChaCha builds on a 512 bit permutation and then applies a feed-forward by xoring the input into the output. Without truncation, that feed forward is essential for one-way-ness.

We're going to build a one-way function that maps a 32 byte value x to another 32 byte value y.

Using truncated ChaCha including the feed-forward

Put the x into the 32 key part of the input, put the normal constant into the 16 constant part and put something public (e.g. a constant or perhaps some kind of tweak) into the 16 byte nonce/offset part. Compute ChaCha including the feed-forward. Take whichever 32 bytes of output you like as y.

Computing x given y implies being able to recover the ChaCha key from the key-stream. So this is a secure one way function if ChaCha is a secure stream cipher.

Using truncated ChaCha without the feed-forward

Since you truncate the output to half the permutation size the feed-forward isn't strictly necessary for one-way-ness.

In practice it doesn't matter which 32 bytes of output you choose, but if you want a security reduction to ChaCha it does.

The idea behind the proof is that the attacker knows 32 bytes of the input: the nonce and the constant. So they can undo that part of the feed-forward. This means that if you choose only the part of the output that's xor-ed with the nonce/constant but not the part of the input that's xor-ed with the key, you can omit the xor while retaining a security proof that this is as strong as ChaCha itself.

This construction mirrors the construction of HSalsa, so you could call it HChaCha. One important issue here is that Salsa puts the key into different words than ChaCha, so you need to take different words from the output in HChaCha.

=> take words 0, 1, 2, 3, 12, 13, 14, 15 as output.

My recommendation is to use HChaCha instead of ChaCha. Same security, better performance.

One interesting modification is to use a different nonce for each call, functioning as a tweak. It probably doesn't gain you much, but shouldn't hurt either.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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