Re: [Cfrg] Recommended bit length before truncating a hash mod p

[Sam Scott <[e-mail]>]

A couple of people have suggested concatenating hash outputs to get enough
bits.
While this is useful feedback - we may need to specify this explicitly
anyway, and in this case it might be the right approach regardless - the
question was primarily around what is understood to be "enough" bits in
this case.

For a prime p, taking floor(log(p))+1 random bits and reducing mod p
results in some amount of bias on the distribution [0, p-1]. Due to this,
the NIST recommendation Chris linked above recommends taking log(p)+64 bits
to smooth out the bias. In that instance, the output is used directly as a
private key. Whereas in `hash2base` the output is fed into another encoding
algorithm, which itself introduces bias as well.

The options as we see them are:

 1. Be more permissive, require only floor(log(p))+1 random bits, allowing
combinations such as SHA256 + Curve25519 (with a single hash).
 2. Require floor(log(p)) + 64 bits, resulting in combinations such as
SHA512 + Curve25519, or SHA256 with concatenated outputs.

The conclusion was this was a subtle enough trade off, that it seemed worth
raising to the list to see if there were any objections/insights into the
two options.

Thanks all,

Sam

On Thu, 21 Mar 2019 at 21:20, Christopher Wood <[e-mail]>
wrote:

> Hi folks,
>
> In draft-irtf-cfrg-hash-to-curve, we define a utility function called
> `hash2base` as follows [1]:
>
> ~~~
> hash2base(x).  This method is parametrized by p and H, where p is the
> prime order of the base field Fp, and H is a cryptographic hash
> function which outputs at least floor(log2(p)) + 1 bits.  The function
> first hashes x, converts the result to an integer, and reduces modulo
> p to give an element of Fp.  We provide a more detailed algorithm in
> Appendix C.7.
> ~~~
>
> Some existing standards [2] recommend taking at least log2(p) + 64
> bits “so that bias produced by the mod function … is negligible.” If
> we were to follow this guidance for hash2curve, we’d lose out on
> several ciphersuite combinations, such as P-256 and Curve25519 with
> SHA256.
>
> So, our question to the group is, how many extra bits are necessary?
>
> Thanks,
> Chris
>
> [1] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-03#section-4
> [2]
> https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>