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

[Ilari Liusvaara <[e-mail]>]

On Thu, Jun 04, 2015 at 12:04:49AM +0100, Stephen Farrell wrote:
> 
> I'd hate to miss one of Alexey's polls:-)
> 
> I'm almost neutral on this one. While we have historically preferred
> #1 for the reason noted in the subject line, there are really very few
> cases where that turns out to be a real issue, as opposed to being a
> theoretical one.
> 
> So I think we could probably live with #2, and that could suffice for
> TLS and DNSSEC and other applications, even though #2 would mean
> that users of the signature scheme (e.g. IETF protocol developers) may
> need to learn something new, which is a downside.
> 
> While #3 seems superficially attractive, my guess is it'd cause more
> confusion and interop issues, and is of course offering a choice to
> users of the scheme and so I don't like that one:-)

Having an option of hashing the message first (with an indication that
message was prehashed or even what hash was used) would be #3.

Conversely, that would be the most reasonable implementation of #3.

The reason for including hash function is to guard against trying to
confuse implementations over what hash function is used, allowing
forging signatures using stronger hashes by abusing weaker ones. The
internal hash function is much less of concern due to natural
strengthtening from hashing in various things derived from key.


> So put me down for (#2 or #1) for this one, with a very very tiny
> preference for #2 and documenting that one ought not use this for
> signing large things directly (which one probably ought not do in any
> case). But #1 would also be an acceptable outcome from my POV since
> we're in practice already dependent on the collision resistance of
> all the relevant hash functions and that won't ever really go away
> as long as there are RSA/SHA256 certificates out there which'll be
> the case for years and maybe decades to come. So the security
> benefit of #2 isn't so great, although it's real.

The problem with #1 isn't so much the CR requirement, but what it will
do to implementation safety:

Basically, it is difficult to do #1 without either:
- Prehashing the message with something capabile of signing much larger
  things. Adding an indication that this prehash has been done would give
  #3).
- Making scheme that is dangerous by breaking basic safety.


The basic safety requirements I am thinking are:

1) Determinism.

The scheme is fully deterministic.

Breaking this makes the implementations very hard to test.

2) No random/unpredictable inputs except key.

No input to functions except key may be assumed random in any way nor
unpredictable.

Breaking this makes primitive easy to misuse in ways that cause
catastrophic breakage (reveal signing private key).

3) No scalar inversions or square roots for signature

Signing must not need computing 1/x mod l or sqrt(x) mod l.

Breaking this doesn't just make scheme slow, but also causes severe
side-channel hazards.

And sidechannels matter: Modern CPUs and OSes are ridiculously vulernable,
with attackers capable of exploiting such bugs across virtual machines on
the same physical hardware.

4) No nonces in main mode

The main mode may not assume any input is not repeated.

Breaking this again makes scheme easy to misuse with very bad results
(hopefully anything using special modes will read the caveats).


Breaking any of these will cause real-world failures, as has been
demonstrated many times by ECDSA.


-Ilari