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

[Ilari Liusvaara <[e-mail]>]

On Thu, May 21, 2015 at 08:41:34AM -0700, Laurens Van Houtven wrote:
> On May 20, 2015, at 2:16 PM, Alexey Melnikov <[e-mail]> wrote:
> > 
> > #1: The signature scheme should follow the traditional model of hashing
> > the message to be signed, thus trivially supporting IUF APIs in
> > constant-space, at the cost of requiring collision resistant hash
> > functions.
> > 
> > #2: The signature scheme should not depend on collision resistance, at the
> > cost of the signing algorithm having to buffer messages to be signed.
> > 
> > #3: option #2, but with an additional "large message" mode defined for
> > protocols that feel that they need it, where the message to be signed is
> > actually a hash of the true message.
> > 
> > _______________________________________________
> > Cfrg mailing list
> > [e-mail]
> > http://www.irtf.org/mailman/listinfo/cfrg
> 
> Picking 1: #1. In order of preference: #1, #3, #2.
> 
> #2, for reasons already elucidated, is a non-starter. A collision-resistance
> constraint is nowhere near as painful as a one-shot constraint. #3 solves
> that, but at the expense of additional complexity.

"Traditional model" already introduces a fair bit of the complexity. The
problem is that protocol may very well have a preference on "inner" hash,
but that hash is unsuitable for "outer" hash, due to insufficient length.

For example, let's take TLS 1.2 CertificateVerify message[1]. It signs
potentially lengthy data. But it just so happens that TLS 1.2 keeps running
hash of just that data, using so called "prf-hash" (which happens to be
also need to be CR).

So, the TLS 1.2 endpoint would very much prefer to use prf-hash as "inner"
hash. The problem is, that prf-hash is probably SHA-256, which has
insufficient output length. Or if it isn't SHA-256, it is probably SHA-384,
which doesn't work too well for 448-bit signatures.

One would probably want to have separation between hashes. One way would
be to stick an algorithm identifier[2]. Presumably there then could be
algorithm identifier for identity transform, which would then give #3
with very little additional complexity.

Of course, protocols would then get the fun of negotiating the mess...


If one wanted to add contexts to this[3], contexts would then appear only
in outer hash (in both generation of R and in final hash). Contexts are
short and should be pulled out of executable/firmware image anyway, so
no need to support IUF for those.



[1] This does not apply to TLS 1.3 current draft, where amount of data
to sign is always small. Also, TLS 1.2 ServerKeyExchange message signs
reasonable amount of data.

[2] Whatever the identifer, it needs to be handled as a blob.

[3] Contexts are meant to prevent cross-protocol attacks (those seem to
be common). The contexts must match on both sides, or signature fails to
verify.



-Ilari