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

From: Christopher Wood <[email-masked]>
Date: Thu, 21 Mar 2019 18:19:54 -0700

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

---

From: Mehmet Adalier <[email-masked]>
Date: Thu, 21 Mar 2019 19:11:47 -0700

Would this work?

1) generate two hashes with two different x values, 
2) concatenate the two outputs 
3) take however many high order bits you need (with at least 64 additional bits per spec)

In our regular P256 implementation we use a 512-bit value before we perform reduction.

mA

On 3/21/19, 6:20 PM, "Cfrg on behalf of Christopher Wood" <[email-masked] on behalf of [email-masked]> wrote:

    Hi folks,

    ~~~

    
    Thanks,
    Chris

    _______________________________________________
    Cfrg mailing list
    [email-masked]
    https://www.irtf.org/mailman/listinfo/cfrg

---

From: Sam Scott <[email-masked]>
Date: Fri, 22 Mar 2019 09:59:39 -0400

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 <[email-masked]>
wrote:

> [2]
> https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf
>

---

From: Dan Brown <[email-masked]>
Date: Fri, 22 Mar 2019 14:49:13 +0000

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Christopher Wood
> 
> 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.
> 

Zero (or perhaps less?) extra bits are necessary, at least for some hashes mentioned in Section 10:

 Elligator2, for example, only maps strings to "about half of all curve points,"
 whereas Icart's method only covers about 5/8 of the points.

The output points (for these hashes) are already biased and easily distinguishable from general points, hence biased field elements should thus be tolerable too. 

I vaguely recall reading about some of the hash-to-point functions aiming to produce a uniformly distributed point.  I am not sure if your draft includes such hashes.  If it does, the uniform field elements would likely be needed for those hashes, if only because uniformity is advertised.

Best regards,

Dan

PS

By "less" than zero extra bits, I meant using, say, SHA1 to map a bit string into a P256 point.  The only possible gain of such would be compression if one use a variable-length point representation.  This *might* be safe in some applications, similar in safety to the way that using a ECDH generator with a small coordinate might be safe, and the way of using points with 1 bit of bias is.  (I am ignoring the general questionability of SHA1, just focusing on its shorter length.)

The requirements from NIST SP 800-56a are about private key generation, where uniformity is more important, e.g. in signatures, and perhaps MQV.