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

[Peter Gutmann <[e-mail]>]

Alexey Melnikov <[e-mail]> writes:

>However, this approach implies that the signing algorithm would have to
>buffer the entire message. That could lead to unacceptable memory usage for
>applications that sign very large messages.

It's also pretty much an instant fail for any API-based security toolkit that
implements streaming/staged message processing via the init/update/final
model, which seems to be pretty much all of them (using PKCS #11 as a
representative example, you've got "begin", "update", "update", [...], "end",
which hardcodes a single pass over the data, OpenSSL does the same thing, as
does CryptoAPI, Java (JCE/Bouncy Castle/whatever), my own cryptlib, and I'd
guess most other libraries).

>Penalising large messages might be seen as a positive by some because signing
>arbitrarily large messages invites implementations to process unauthenticated
>data because of its potential size. 

In most cases where you're processing large messages you don't have any
choice, and the signing is often done for things like accounting purposes
rather than because the devices involved are trying to enter into a legal
agreement.  For example medical images, which have to be uncompressed in order
to avoid introducing compression artefacts, are enormous, streamed out to a
remote system in a single pass, and signed purely for accounting/bookkeeping
purposes.  So you've got something where you absolutely need one-pass
processing, and the app/users couldn't care less about any fancy properties
that two-pass processing provides.

>#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.

+1.  Without having done a survey of all implementers, I do however get the
feeling that this is the only option available for practical use, meaning the
choice would be to either go with this option or have whatever other option
you select ignored because it's impractical for general use.

Peter.