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

From: David Núñez <[email-masked]>
Date: Fri, 22 Mar 2019 11:12:25 +0100

Hi Christopher,
for this exact problem, we follow the approach described by Mehmet:

Hash512(x) = Hash256(0||x) || Hash256(1||x)

This way we can take up to 512 bits using a 256-bit hash function. You can
find an example implementation of this (for Keccak256) here:
https://github.com/nucypher/pyUmbral/blob/master/umbral/random_oracles.py#L84

Regards,
David

> ---------- Forwarded message ----------
> From: Mehmet Adalier <[email-masked]>
> To: Christopher Wood <[email-masked]>, <[email-masked]>
> Cc:
> Bcc:
> Date: Thu, 21 Mar 2019 19:11:47 -0700
> Subject: Re: [Cfrg] Recommended bit length before truncating a hash mod p
> 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,
>
>     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
>     [email-masked]
>     https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Markku-Juhani Olavi Saarinen <[email-masked]>
Date: Fri, 22 Mar 2019 10:38:42 +0000

Hi,

Some notes since this is a standardization forum:

- It is generally not advisable to say "Keccak" when you mean SHA3.
The padding mechanism was slightly changed from the "final competition
round" Keccak 3.0 proposal to FIPS 202, making the two incompatible.
Some cryptocurrencies (e.g. Monero) actually use the obsolete
pre-standardization version and talk of "Keccak" when they refer to
it.
- FIPS 202 defines not only an actual SHA3-512 but also
Extendable-Output Functions (XOFs) that allow hashes of any output
size. The source code link provides a ExtendedKeccak(Hash) method
which is a "doubly standard-violating" ad hoc construction, having
nothing to do with the faster, standardized XOFs (SHAKE128 and
SHAK256).

Cheers,
- markku

Dr. Markku-Juhani O. Saarinen <[email-masked]>

On Fri, Mar 22, 2019 at 10:13 AM David Núñez <[email-masked]> wrote:
> This way we can take up to 512 bits using a 256-bit hash function. You can find an example implementation of this (for Keccak256) here:
>> 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,
>>
>>     [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: David Núñez <[email-masked]>
Date: Fri, 22 Mar 2019 12:01:47 +0100

Hi Markku,
Yes, we were aware of all those caveats. We use the term "Keccak256"
deliberately, since we need to be interoperable with Ethereum's EVM, whose
default hash function is the pre-standardized version. There was some
confusion in the past to this regard, since Ethereum initially called this
"SHA3", even if it wasn't the standardized version, but the previous one.
For the same reason, we don't have native access to XOFs, as the EVM only
gives you Keccak256, SHA256 and RIPEMD160.

Regards,
David

On Fri, Mar 22, 2019 at 11:38 AM Markku-Juhani Olavi Saarinen <[email-masked]>
wrote:

> > This way we can take up to 512 bits using a 256-bit hash function. You
> can find an example implementation of this (for Keccak256) here:
> >

---

From: Gilles Van Assche <[email-masked]>
Date: Fri, 22 Mar 2019 14:18:48 +0100

Dear Markku,

> round" Keccak 3.0 proposal to FIPS 202, making the two incompatible.

I agree with you on avoiding confusion between Keccak and SHA-3.

However, for the sake of completeness, I wanted to point out that the
padding scheme wasn't changed between the final-round proposal and the
FIPS 202 standard. As you know, the FIPS 202 functions are merely
appending a suffix to the input before calling the original final-round
proposal Keccak, for the purpose of domain separation between SHA-3 and
SHAKE.

> pre-standardization version and talk of "Keccak" when they refer to it.

I wouldn't use qualifiers like pre- and post-standardization versions,
but instead say that SHA-3 and SHAKE are built on top of Keccak.
Alternatively, they are a subset of Keccak in the sense that only part
of its input space can be addressed through them.

> nothing to do with the faster, standardized XOFs (SHAKE128 and SHAK256).

Indeed, referring back to the original discussion, having a XOF
interface would simplify the way some protocols are written. (I
deliberately wrote "XOF interface" to include both native XOFs and
traditional fixed-length hash functions with an MGF1-like mode. Of
course, I could only recommend to use native XOFs.)

Kind regards,
Gilles

---

From: Markku-Juhani Olavi Saarinen <[email-masked]>
Date: Fri, 22 Mar 2019 15:30:22 +0000

Gilles,

Thanks for clarifications. The name Keccak, of course, is entirely
appropriate when we discuss the family of cryptographic primitives,
the permutation, and other internal hashing operations.

> proposal Keccak, for the purpose of domain separation between SHA-3 and

It is indeed very unfortunate that adding these padding suffix bits is
not possible via the byte-oriented API calling interfaces commonly in
use. Therefore a higher-level "Keccak" primitive -- as understood and
used by the cryptocurrency people -- can only rarely be used to
compute an SHA-3 hash.

Cheers,
- markku