Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

[Simon Josefsson <[e-mail]>]

Andrey Jivsov <[e-mail]> writes:

> On 06/05/2015 06:53 PM, Simon Josefsson wrote:
> ...
>>> Yes, but what cost "no problems" actually has in some cases?
>>>
>>> Before: one could hash during streaming.
>>> After: one extra re-hashing is needed, denying the benefit of hashing
>>> while streaming.
>>
>> I believe you are mistaken.  OpenPGP with EdDSA only hashes once, during
>> streaming.
>
> For example, GnuPGP, which follows the
> https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-02#section-5 
> (search for "a digest of the message is used as input"), hashes the
> message three times.

Well, not really, it hashes the message (the data to sign) once, and
then signs the hash value using EdDSA.  Yes, EdDSA internally hashes its
input (the hash value) twice, but that won't require buffering the
entire data to sign (the message).  I believe it was that property
("hash entire message once or multiple times") that was under
discussion.  So I think we actually agree on everything except we had
different contexts of this discussion.

> _gcry_ecc_eddsa_sign hashes the input twice (per EdDSA spec), and the
> 'gcry_mpi_t input', the input to the EdDSA sign function, is the hash
> of the message (note that the input is the MPI, not a file or a
> buffer). The higher-level code hashed the actual input into that MPI
> passed to _gcry_ecc_eddsa_sign.
>
> By doing so GnuPG implementation and the spec above depend on the
> poll's #3 as the only mode (for large or small messages alike).

Right.  Thanks for analysis.

> It follows that GnuPG signing method always depends on collision
> resistance of the hash function, (always with ECDSA, and always with
> EdDSA). This means that the 2 extra hashings done in the EdDSA sign
> function don't buy much (at least they don't free one from using a
> collision resistant function).

Right.

>>> To fix this new demand of low-level crypto there needs to be an
>>> engineering fix at a higher level. In the case of OpenPGP applications
>>> this means the buffering of the entire input must happen, somehow.
>>
>> This is false, there is no need to buffer the entire message.  Just hash
>> the stream and sign the hash.
>
> Correct. This is poll's #3. One would need to buffer during streaming
> with poll's #2.

Not so fast -- it would be perfectly fine for CFRG to stop and only do
#2 and leave the #3 part to higher-level protocols, like OpenPGP and
S/MIME which has the large-message-concern.  It seems OpenPGP has
already done this.

/Simon