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

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 <mjos@iki.fi>

On Fri, Mar 22, 2019 at 10:13 AM David Núñez <david@nucypher.com> wrote:
>
> 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 <madalier@antarateknik.com>
>> To: Christopher Wood <christopherwood07@gmail.com>, <cfrg@irtf.org>
>> 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" <cfrg-bounces@irtf.org on behalf of christopherwood07@gmail.com> 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
>>     Cfrg@irtf.org
>>     https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg