Subject: [Cfrg] ECDSA_CFRG ... RE: Soliciting EC signature scheme proposals

From: Dan Brown <[email-masked]>
Date: Tue, 23 Jun 2015 13:50:24 +0000

Hi Ilari,

Thanks for the feedback.  Responses in-line.

I renamed this thread to ECDSA_CFRG, for better specificity (also making it 
easier to ignore).

> -----Original Message-----
> From: Ilari Liusvaara [mailto:[email-masked]]
> Sent: Tuesday, June 23, 2015 6:18 AM
>
> On Mon, Jun 22, 2015 at 06:54:54PM +0000, Dan Brown wrote:
> > Hi CFRG,
> >
> > Consider an ECDSA_CFRG signature (R,s) of a message m under public key
> > Q to be valid if:
> >
> > sR = h(m||R)G + f(R) Q
> >
> > An ECDSA_CFRG signature can be converted to a plain ECDSA signature
> > (f(R),s) on message m||R under public key Q, so it can be verified
> > using an ECDSA verifier, provided a compatible f is used.
>
> I don't think any kind of ECDSA compatiblity is a goal.

[DB] Ok, it was my individual goal, just a bonus for CFRG.

>
> > The signature scheme ECDSA_CFRG aims to improve on ECDSA upon by
> > addressing most of the ECDSA security critiques.
>
> I have two main critiques of ECDSA:
> - Requiring highly random k (one can pseudorandomly generate one if
>   one doesn't care about strict ECDSA compliance).

[DB]  All DL-based signatures, not just ECDSA, require, for _security_, k of 
sufficient quality.  By strict ECDSA compliance, I assume you refer to 
standards, and by highly random, maybe you mean entropy per k?  Recent ECDSA 
standards require a well-seeded CSPRNG, with re-trials or extra bits, but this 
does not require new entropy per k.  Older ECDSA standards are more vague, so 
it's hard to pin down "strict compliance".

> - Inversion mod order in signing.
[DB] I said _security_ critiques: so I suggested two security protections.
[DB] You didn't list ECDSA's need for collision resistance (in other words, 
lack of collision resilience).  I think a few others wanted that.

> > The signer computes R = (k+h(u,k)n)G, where here mod n is not applied.
> > So, R is a deterministic function of m, as CFRG has required, and it
> > is computed using additive masking to protect against side channels.
>
> Most software does not need additive masking against side channels, only
> devices in hostile environments do. Also, the masking if present needs to be
> random, not deterministic (as noted by Ladd).
>
> > The private key d and the secondary secret u should (must?) be derived
> > from a common secret seed (which is then destroyed - except see below).
> > (I think EdDSA works this way, right?) E.g d||u = h'''(seed).  (This
> > aims to protect against a poorly chosen u, and consequent predictable
> > k.)
>
> EdDSA can store either the derived components or the seed used to generate
> those. The hashing somewhat protects against poor choices of the derived
> parameters.
>
> > Optionally: the signer can also prepare some single-use pairs (z,Z=zG)
> > and compute R as R = (((k/z) mod n) + h(u,k)n) Z.  Note: this is
> > multiplicative masking; because it is more expensive, it is optional.
> > The pair (z,Z) can be computed before m is received.
>
> I don't see benefit in doing this, since it seemingly does not cut latency
> (prederiving R would, as it would just leave the scalar part to be done 
> after
> signing).
>
[DB] The benefit is security, not efficiency.  Multiplicative masking offers 
an extra degree of side channel protection, because the scalar multiplication, 
the largest potential side channel, is now completely independent of the k, 
which is critical to protect from side channel.  Note that the additive 
masking and constant-time implementation do not offer full independence, 
because k enters in the scalar multiplication.  In this multiplicative k only 
enters into a mod n multiplication k * (1/z) mod n, which, as a simpler 
computation, ought to be easier to protect against side channels.

> > Optionally, the signer can use a single-affine-coordinate Montgomery
> > differential-addition chain ladder to compute R.  The full coordinate
> > representation of R can be recovered.
> >
> > The signer then computes (mod n)
> >
> > v = h''(u,k) k.
> >
> > t = (h(m||R) + f(R) d) / v
> >
> > s = h''(u,k) t
>
> Inversion mod order there?
>
> The major problem I have with inversions mod order are:
> - Those are slow, especially if you want side channel resistance.
> - Those easily open up side channels (modern OSes and hardawre are
>   ridiculously vulernable here).
>
[DB]  Yes, it may be slow.  Multiplicative masking is used.  Perhaps v should 
be randomized, rather than deterministic.

By the way, all DL-based already need inversion mod field size to switch from 
projective to affine.   Smart and Malone-Lee [+others?] showed that projective 
coordinates leak, so one should already be taking side channel protections for 
inversion.

If the inversion mod field size uses Fermat inversion, and the inversion mod 
order can be done with EGCD (assuming the multiplicative masking 
countermeasure works), the relative cost of the inversion mod order should be 
quite low.

> > For a long message m, the signer computes k = h'(u,m) and h(m||R) in
> > tandem, without buffering the whole of m, as required by the IUF
> > condition.
>
> I think such double computations would cause problems in some protocols
> (e.g. TLS 1.2).

[DB]  Hmm, why?  Is it too slow?

I suppose that a less conservative approach that I mentioned in a previous 
email (suffix ...) could avoid the double comp, by deriving R from an internal 
state of SHA3, ... I'd have to look into the SHA3/Keccak specification to see 
if they already offer such a mechanism, else it would be a hack.

>
> > Overall, the signature generation process aims to reduce the risk of
> > side channels associated with k, because this is a known critical area
> > of most DL-based signatures.
>
> Also, if one does serious software sidechannel checks, blinding is not 
> enough to
> pass those, one needs already constant-time code (one can then implement
> blinding on top if one needs to).
>
[DB] Yes, we should mandate constant-code for the signer.

> > Verification speedups (optional)
> >
> > The use of (R,s) instead of (r,s) has some known advantages, which are
> > reviewed here.
> >
> > Batch verification is fairly straightforward, just add the equations
> > together (perhaps randomly scaling) etc.
>
> I thought batch verification needs R?
>
[DB] Huh?  I wrote above that ECDSA_CFRG provides R, I thought this was clear.

> > Security arguments against various attacks
> >
> > Side channels?
> >
> > Standard side channel protections above are mandated, though perhaps I
> > missed some.
>
> Inversion... Yes, fermat is side-channel safe, except it is quite a bit 
> slower than
> EGCD, which isn't.
>
[DB] Multiplicatively masking is the protection. Never mind EGCD: suppose the 
v above is public.  I already sent an email to CFRB about this, and I don't 
recall any complaints.  What's your attack?

> > Collision resilience and wide pipe hashing?
> >
> > As Kenny pointed in response to Watson, for a narrow-pipe hash,
> > finding an extensible mid-pipe collision is known to be as easy as
> > finding a collision.  For a wide-pipe hash this is not known: that is
> > one the promising security aspects of wide pipe hash functions, at
> > least as I understand it.
>
> Unfortunately, there doesn't seem to be good wide-pipe hashes at lengths
> needed. I know two wide-pipe hashes at 512 bits with serious analysis:
>
> 1) Skein-1024-512 (SHA-3 finalist). ~6.83 cpb on Haswell. About 15%
>    faster than SHA-512.
> 2) Keccak-512 (SHA-3 winner). ~16.57 cpb on Haswell. About half(!) of
>    SHA-512 speed.
>
> None of the other SHA-3 finalists (or derivates thereof) are capable of
> widepipe at 512-bits.
>
[DB] Ok, I just assumed SHA-3 could do this.  Looking on Wikipedia, I see 
SHA-3-512 has a capacity of 1024 and rate of 576, so this seems wide-pipe to 
me.  Also, Wikipedia says that the capacity must be double the security level 
for collision resistance. But I'm no expert: what am I missing?

> And this is compounded here by the fact that hash is computed twice (pehaps
> even with in parallel with other hashes).
>
[DB] Ok, a highly constrained of long messages could shortcut the R 
computation, as I alluded to above.  Of course, this should be well-specified 
to avoid self-rolling pitfalls.  I will look into this.