Upon reading through the source code of Rainbow, a post-quantum signature algorithm, I found a hashing function that, using SHA-512, produced a variable length digest.

This was achieved was by initially hashing the message to obtain a 64 byte digest, and then hashing that digest, and again, each time hashing the N - 1 digest. It's essentially being used as a deterministic CSPRNG.

Is this secure? Can SHA-512's digest be stretched out indefinitely like this? And why didn't Rainbow simply use a well-studied CSPRNG like ChaCha20?


Section 2.6 of their submission talks about this. There they state that for most cases they simply use SHA-256, -384 or -512. In the (uncommon?) case that a hash function with a larger output is needed, they use the OFB-like1 construction. The rationale being that a collision on the OFB construction would immediately imply a collision on the underlying hash function - as the direct output is part of the expanded output. This also explains why they don't want to involve another (more efficient) function: To reduce security guarantees and prefer simplicity over optimization for rarely needed scenarios.

1: OFB-Mode is a way to construct a PRG and an CPA-secure encryption scheme out of a fixed-length PRF. It works essentially as $K_i=F_k(K_{i-1})$ outputting $K_1\|K_2\|\ldots\|K_\ell$ for a PRF $F$ and a secret random key $k$.

  • 1
    $\begingroup$ OFB mode and PRGs, in which $f$ is a private random function, are a lot different than hashing, where $f$ is a public random function. If $f$ is a public random oracle, and $K_i = f(K_{i-1})$ then I can easily distinguish $K_1\|K_2\|\cdots\|K_n$ from random. $\endgroup$ – Mikero Nov 2 '20 at 21:48
  • $\begingroup$ @Mikero excellent point, I have adapted my answer to no longer potentially confuse people into using OFB as an RO extender. $\endgroup$ – SEJPM Nov 2 '20 at 22:21

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.