Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

[Watson Ladd <[e-mail]>]

On Mon, May 11, 2015 at 12:36 AM, Brian Smith <[e-mail]> wrote:
> Watson Ladd <[e-mail]> wrote:
>> With your amended proposal, signatures remain secure even with bad
>> randomness (unless we have kleptographic bugs, induced by our good
>> friends at Fort Mead). So what exactly is the point of having all this
>> extra code lying around, and dependencies on randomness?
>
> As far as I understand Dan Brown's argument, he is saying that nobody should
> be *required to depend* on randomness (i.e. purely deterministic signatures
> should be allowed), but any implementation *should be allowed* to use
> randomness if the use of randomness helps prevent side channel attacks.

And no one has disagreed with that: as DJB noted randomized signatures
will still interoperate.

>
> (Quoted out of order):
>
>> 3a is actually a reasonable argument, but
>> there are quite a few cases where power analysis doesn't matter.
>
> The question is whether it is reasonable to assume that there are *no* cases
> where power analysis, EMI, or other side channel attacks matter, that are
> relevant to this decision.
>
> I've read in this thread some suggestions that such side channel attacks do
> not matter for TLS. I don't think that that assertion has been shown to be
> conclusively true, considering that we have to assume that the server doing
> the signing is co-located physically centimeters away from, or even on the
> same system as, systems that may be attacking them.
>
> Timing side channels and the *idea* of developing constant time signing
> implementations to guard against them, are well understood. Yet, even when
> people go out of their way to develop constant-time implementations, they
> frequently get it wrong. In particular, it is pretty common to see
> implementations making wrong assumptions about which C language constructs
> will result in constant-time execution. (This should be unsurprising, since
> C doesn't make any such guarantees.) Therefore, even if timing side channels
> are the only side channels that we are concerned with, it might *still* be
> useful to use randomization on top of a deterministic scheme as a
> defense-in-depth mechanism (as BoringSSL does, for example).
>
> After all, if we're designing under the assumption that implementers cannot
> follow even the most obvious and clear instructions regarding randomizing k
> in ECDSA, then it seems prudent to also assume that they cannot write
> constant-time code that is correct, considering that even incredibly
> well-informed implementers have had difficulties in doing so. (It is not
> hard to find code in major implementations claiming to be constant time that
> isn't actually constant time.)

You assume we're talking about implementors who "can't follow the most
obvious and clear instructions regarding randomizing k", and conclude
they can't protect against side channels. Could you have stopped the
Debian bug if you wrote the OpenSSL ECDSA code? Of course, Dan Brown's
proposal does stop that particular bug. But it doesn't stop you from
mistyping the size of an array, and thus opening the door to much more
effective attacks based on partially known nonces. The advantage of
deterministic schemes is increased testability. (Yes, one could inject
"random numbers" to create test vectors if the generation method was
specified. That involves exposing a function that shouldn't be used in
production).

Randomization alone is insufficient to protect against side channel
attacks. Developing side-channel protected implementations is a
significant effort, and requires knowledge of the side-channel
characteristics of the hardware that the software is running on.
Randomized implementations that have been vulnerable include:

-OpenSSL https://eprint.iacr.org/2014/161.pdf, several other papers
-Smart Cards https://eprint.iacr.org/2013/346.pdf



>
> That said, DJB said:
>> Standard defenses include blinding of each secret bit (splitting b into
>> r and r+b), blinding mod the group order (replacing k with k+rp), etc.;
>> these defenses work for deterministic signing systems too.
>
> I'm not disagreeing with DJB. However, I think it is worth spending time, at
> least, verifying whether this assertion that all relevant side channel
> attacks can be reasonably prevented for purely deterministic signature
> schemes is true. If so, then only a purely deterministic scheme should be
> specified. Otherwise, randomization should be permitted but not required.
>
> Cheers,
> Brian



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.