Subject: [Cfrg] Soliciting EC signature scheme proposals

From: Alexey Melnikov <[email-masked]>
Date: Sun, 21 Jun 2015 10:52:26 +0100

Dear CFRG participants,

We are now at the point where we have gathered sufficient requirements 
(not necessarily NIST-compliant, deterministic, IUF interface) where it 
seems sensible to invite proposals for signature schemes meeting those 
requirements.

We would like to have proposals that are reasonably detailed so that 
they can be assessed properly by CFRG readers. We realise that doing 
fully detailed proposals would take a lot work, so we do not expect 
full-fledged proposals in the style of a NIST competition (say). That 
said, we would like to encourage proposers to explain the security 
properties of their proposals as well as their implementation 
characteristics, and to make proposals that are generic in the sense of 
being usable for either of the two curves that we have previously agreed 
upon.

Please submit your proposals within 2 weeks (i.e. by July 5th); e-mails 
to the CFRG list are fine. We encourage constructive questions and 
clarifications about proposals as they are made. At this stage, we 
anticipate needing a longer discussion period that extends beyond the 2 
week submission period. After that, we may poll to decide on CFRG 
recommended scheme. Depending on how the on-list discussions go in the 
next 4 weeks, we might also have face-to-face discussion at the CFRG 
meeting planned for IETF 93 in Prague in July.

Best Regards,
CFRG Chairs.

---

From: Dan Brown <[email-masked]>
Date: Mon, 22 Jun 2015 18:54:54 +0000

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.

The signature scheme ECDSA_CFRG aims to improve on ECDSA upon by
addressing most of the ECDSA security critiques.

Notations

The description assumes an encoding of EC points, indicated with
uppercase letters, and conversion f of point encodings to integers, and
a (wide-pipe) hash function h(), e.g. SHA3.  Some tweaks of h, such as
h', h'', h''', will be considered too.  Fix a base point G with a
prime order n, with integer computations usually done mod n.

Note that in the verification equation h(m||R) would be a truncated
hash when backwards compatibility with ECDSA is needed.

Signature generation, deterministic

As usual, the signer's public key Q = dG for a private key d.

The signer also has a secondary secret u, and computes k = h'(u,m),
where tweak h' indicates a possible extended length to ensure that k
has more bits than n, to avoid bias in k.  Furthermore, we assume that
MAC(u,m) = h'(u,m)G is secure as a MAC.  To help with this task, we
may amend h' to have a form like HMAC.

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.

Side note: the infamous and insecure repeated-k ECDSA failed signature
are also "deterministic" functions of the message.  CFRG should
probably choose a better name here, like "pseudorandom".

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

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.

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

So, s = (h(m||R) + f(R)d)/k, similar to ECDSA, but the signer
must apply multiplicative masking to the inversion.  The actual
inversion of v should be done via Fermat's little theorem, but if
every bit of speed is crucial, then v may be inverted using some form
of Euclidean algorithm.  Note that, unlike some previous ECDSA
standards, k is not inverted directly.

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.

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.

Verification speedups (optional)

The use of (R,s) instead of (r,s) has some known advantages, which are
reviewed here.

Instead of computing 1/s mod n, etc. as some ECDSA standards describe,
one can compute h(R||m)G quickly using pre-computed tables for G, and
then compare this against sR - f(R)Q, which can be computed using
multi-scalar multiplication methods.

Batch verification is fairly straightforward, just add the equations
together (perhaps randomly scaling) etc.

Security arguments against various attacks

Side channels?

Standard side channel protections above are mandated, though perhaps I
missed some.

Signerless (passive, key-only) forgery

Forging ECDSA_CFRG without the help of a signer implies an ECDSA
forgery.

So, ECDSA_CFRG is at least as secure as ECDSA against signerless
(passive) forgers.

Signer-assisted forgery?

Unfortunately, I don't have a way to directly convert a more general
ECDSA_CFRG forger, i.e., one that exploits the signer as an oracle,
into the corresponding ECDSA forger, because an ECDSA signer does not
seem to convertible into an ECDSA_CFRG signer.

This theoretical obstacle might mean that there are some degenerate
forms of hash functions in which exploiting an ECDSA_CFRG signer makes
forgery easier.

Repudiation and MAC

Suppose an ECDSA_CFRG forgery (R',s') of message m has the property
that R' = h'(u,m)G, so that (R',s') is the same signature that the
honest signer would produce.  Since the signer did not sign m, the
forger has essentially defeated the security of MAC(u,m) = h'(u,m)G.

It seems reasonable to conjecture that this is infeasible of h'(u,m)
is a secure MAC.

Otherwise the forgery (R',s') is not what the signer would produce,
and in particular, R' is not of the form h'(u,m) G.  An ECDSA_CFRG
signer can try to repudiate the forgery (R',s') as follows.  The
signer generates signature (R,s) and then provides a zero-knowledge
proof that R = h'(u,m)G, provide that the signer has a previously
register commitment to the value of u.  (Or, the signer could keep the
seed from which d and u are derived, and then provide a ZK proof that
R and Q are ultimately derived from the same seed.)

Of course, such a repudiation does not help in real-time
authentication, but in many authentication, there are good
non-signature forms to authentication, such as authenticated key
agreement.

Collision resilience and wide pipe hashing?

If h is a wide-pipe hash, then ECDSA_CFRG does not rely on collision
resistance of h, at least strictly speaking

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.

Furthermore, it was one of the security goals of the SHA-3 competition
to act like a ROM.  An internal, extendable collision (m,m') such that
h(m||R) = h(m'||R) for all R is a very non-ROM property.
Consequently, there was considerable incentive during the SHA-3
competition to find such an attack, and none was found for SHA-3
(right?).

So, collision resistance is not necessary for ECDSA_CFRG, if we assume
a new conjecture security property of wide-pipe hashes like SHA-3.  In
other words, ECDSA_CFRG_SHA3 is superficially resilient to SHA-3
collisions.

Re-using old security proofs?

I expect that if we invoke ROM, then the Pointcheval-Stern forking
lemma prove would apply to ECDSA_CFRG.  (I think that they even
proposed such a modification to ECDSA).

I expect that generic group model proofs for ECDSA could be adapted to
ECDSA_CFRG.  (I think Koblitz and Menezes recently suggested this.)

Conclusion

Security is well-covered, on the theory and practice sides.
Efficiency may not be optimal, but it is still pretty good.

Best regards,

Dan

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
> Sent: Sunday, June 21, 2015 5:52 AM
> To: [email-masked]
> Subject: [Cfrg] Soliciting EC signature scheme proposals
> 
> Dear CFRG participants,
> 
(not
> necessarily NIST-compliant, deterministic, IUF interface) where it seems
> sensible to invite proposals for signature schemes meeting those
requirements.
> 
> We would like to have proposals that are reasonably detailed so that they
can
> be assessed properly by CFRG readers. We realise that doing fully detailed
> proposals would take a lot work, so we do not expect full-fledged
proposals in
> the style of a NIST competition (say). That said, we would like to
encourage
> proposers to explain the security properties of their proposals as well as
their
> implementation characteristics, and to make proposals that are generic in
the
> sense of being usable for either of the two curves that we have previously
> agreed upon.
> 
> Please submit your proposals within 2 weeks (i.e. by July 5th); e-mails to
the
> CFRG list are fine. We encourage constructive questions and clarifications
> about proposals as they are made. At this stage, we anticipate needing a
longer
> discussion period that extends beyond the 2 week submission period. After
> that, we may poll to decide on CFRG recommended scheme. Depending on
> how the on-list discussions go in the next 4 weeks, we might also have
face-to-
> face discussion at the CFRG meeting planned for IETF 93 in Prague in July.
> 
> Best Regards,
> CFRG Chairs.
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Mon, 22 Jun 2015 12:28:17 -0700

> using an ECDSA verifier, provided a compatible f is used.

Could you explain how NSS, just to pick one example, would be able to
verify these signatures? It seems that the constraints on encoding would
force the use of Weierstrass big endian form, or sufficently big changes to
make adding another scheme a rounding error in complexity. (I also suspect
a typo in above: f(R)/s would be more believable to me)

There is also a cross protocol attack if the same key is used for ECDSA
and this scheme.

> may amend h' to have a form like HMAC.

MAC security is not sufficient. We need PRF.

> is computed using additive masking to protect against side channels.

This masking is deterministic: repeated signatures with of the same message
can be averaged to amplify observations.
It's also clear that masking of nG with various countermeasures can be
applied to all schemes in a variety of ways.

> seem to convertible into an ECDSA_CFRG signer.

There already is a deterministic, batchable version of ECDSA: transmit R
instead of r.
> least as I understand it.

They are (conjectureally) separated: consider truncating SHA-2 to 64 bits
as an example.

> > We would like to have proposals that are reasonably detailed so that
they
> > Please submit your proposals within 2 weeks (i.e. by July 5th); e-mails
to

---

From: Dan Brown <[email-masked]>
Date: Mon, 22 Jun 2015 20:43:40 +0000

From: Watson Ladd [mailto:[email-masked]]
> using an ECDSA verifier, provided a compatible f is used.

Could you explain how NSS, just to pick one example, would be able to verify these signatures? It seems that the constraints on encoding would force the use of Weierstrass big endian form, or sufficently big changes to make adding another scheme a rounding error in complexity. (I also suspect a typo in above: f(R)/s would be more believable to me)

[DB] Fair enough.  So, if the new CFRG curves have their own point encodings, and would need their own method to convert a point encoding to an integer (the function f), then a version of ECDSA could be defined accordingly.  I don’t think that the existing ECDSA implementation support this yet.  So, the point is that ECDSA_CFRG is used with an old curve, e.g. P256, it can easily verified with an existing ECDSA verifier implementation.  Meanwhile, for new curves, one can just plug in the curve-specific encodings and conversions, and have one unified ECDSA verifier.

There is also a cross protocol attack if the same key is used for ECDSA  and this scheme.

[DB] Ok, but please expand a little.  Protocols should probably identify themselves in the messages they sign.

[DB]  Yes, certainly, a PRF is still needed!  The point about HMAC is to emphasize that one should ensure extension attacks on h’(u,m), rather than think h’=ROM, everything A-OK.  I think the claims about SHA-3 are the h’(u,m) is a good PRF and a good MAC.

> is computed using additive masking to protect against side channels.

This masking is deterministic: repeated signatures with of the same message can be averaged to amplify observations.
It's also clear that masking of nG with various countermeasures can be applied to all schemes in a variety of ways.

[DB] Good point.  Ok, make the masking non-deterministic.

Yes, masking seems to protect all schemes equally well, I was just thinking that we should include some kind of side channel protection in the description in the signature generation.

> seem to convertible into an ECDSA_CFRG signer.

There already is a deterministic, batchable version of ECDSA: transmit R instead of r.

[DB] I know about batchable ECDSA, but I’m not quite sure why you’ve put a batching comment here in the security arguments section.  Are you saying that the main defect of plain ECDSA is the lack of batching and that further modifying ECDSA by using h(m||R) instead of h(m) to provided limited collision resilience does not outweigh the gap in security analysis that I pointed out?

> least as I understand it.

They are (conjectureally) separated: consider truncating SHA-2 to 64 bits as an example.

[DB] Yes, SHA-2 truncated to 64 bits is like a wide-pipe.  You’re agreeing with me, I think, - thanks.

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 23 Jun 2015 13:17:55 +0300

> using an ECDSA verifier, provided a compatible f is used.

I don't think any kind of ECDSA compatiblity is a goal.
 
> 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).
- Inversion mod order in signing.

> 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).
 
> aims to protect against a poorly chosen u, and consequent predictable

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

> t = (h(m||R) + f(R) d) / v

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

> tandem, without buffering the whole of m, as required by the IUF

I think such double computations would cause problems in some
protocols (e.g. TLS 1.2).
 
> 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).

> together (perhaps randomly scaling) etc.

I thought batch verification needs R? 
 
> Standard side channel protections above are mandated, though perhaps I

Inversion... Yes, fermat is side-channel safe, except it is quite a bit
slower than EGCD, which isn't.

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

And this is compounded here by the fact that hash is computed twice
(pehaps even with in parallel with other hashes).

-Ilari

---

From: "Dang, Quynh" <[email-masked]>
Date: Tue, 23 Jun 2015 15:14:01 +0000

Hi all, 

Looking at this ebash website at http://bench.cr.yp.to/results-sha3.html, it looks like Keccak [c = 512] does perform comparatively to SHA-512,  or even better over all. 

Keccak [ c = 256] (SHAKE128) (for 256-bit hash output)  is expected to have roughly 25% better performance than Keccak [ c = 512].

Quynh.

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 23 Jun 2015 19:29:11 +0300

> Looking at this ebash website at http://bench.cr.yp.to/results-sha3.html, it looks like Keccak [c = 512] does perform comparatively to SHA-512,  or even better over all. 

The naming seems bit odd. The one labeled "keccakc512" (sic) looks to be
256-bit output, not 512-bit output needed.

The one with Keccakc1024 (dead last in speed) is the 512-bit output one.

All the others are named after bitlengths. E.g. "skein10241024" is really
1024-bit output hash (the 512-bit widepipe variant runs at the same speed,
as only initialization and finalization differ).

-Ilari

---

From: David Leon Gil <[email-masked]>
Date: Tue, 23 Jun 2015 09:37:30 -0700

Keccak uses an internal 200-byte state. Thus, for SHAKE128, the maximum
output length without reapplying the permutation, setting c = s * 2, is 200
- c = 168 bytes, and for SHAKE256 is 136 bytes.

And so, for both the specified SHAKE instances, holding input length
fixed/security strength fixed, any output length from 0-136 bytes has
exactly the same performance as any other output length in that range.

On Tue, Jun 23, 2015 at 9:29 AM, Ilari Liusvaara <
[email-masked]> wrote:

> > Looking at this ebash website at http://bench.cr.yp.to/results-sha3.html,
> it looks like Keccak [c = 512] does perform comparatively to SHA-512,  or
> even better over all.
>

---

From: "Dang, Quynh" <[email-masked]>
Date: Tue, 30 Jun 2015 15:00:01 +0000

Hi IIari and all,

We decided to use security levels to name the SHAKEs: SHAKE128 and SHAKE256.

SHA-256 has 64 rounds and SHA-512 has 80 rounds. SHA-512 has (80 - 64) 16/64 = 25% more rounds than SHA-256 has. 

SHA-512 has word size of 64 bits and input block size of 1024 bits which are twice as large as word size and input block size of SHA-256.

Therefore, I think it would be reasonable to expect that SHA-512 has much better performance than SHA-256 on 64-bit machines generally ( 2 / 1.25 = 1.6). 

Below were some performance data references that I saw in the past, a few years ago.

http://bench.cr.yp.to/xweb-hash/long- sha256.html (This one did not work when I tried to access it today or it does not exist anymore.)

Gueron, S., S. Johnson, and J. Walker. 2011. SHA-512=256, 2011 Eighth International Conference on Information Technology: New Generation.

That was why we specified SHA-512/256 as an alternative to SHA-256.

Quynh. 

________________________________________
From: Dang, Quynh
Sent: Tuesday, June 23, 2015 11:14 AM
To: [email-masked]'
Subject: Performance of SHA-512 vs Keccak [c = 512] ( SHAKE256) for 512-bit hash output.

Hi all,

Quynh.