Subject: [Cfrg] Elliptic Curves - signature: shorter signatures versa batch verification (ends on August 21st)

From: Alexey Melnikov <[email-masked]>
Date: Fri, 14 Aug 2015 11:55:32 +0100

Dear CFRG participants,

Of the various proposals, one ("hamburg", see 
<http://ed25519.cr.yp.to/cfrg/signatures.py>) takes the option of 
shortening the final signature by using a method known as Schnorr's 
trick, while the others do not. This means that the "hamburg" scheme 
enjoys shorter signatures (e.g. 48 bytes instead of 64 bytes at the 
128-bit security level). But it removes the ability of the scheme to 
support fast batch verification of signatures. Some concerns about the 
security implications of the approach adopted in the "hamburg" scheme 
have also been voiced on list:

<http://www.ietf.org/mail-archive/web/cfrg/current/msg07122.html>

with a response here:

<http://www.ietf.org/mail-archive/web/cfrg/current/msg07135.html>

The chairs would like to conduct a poll to ask, in view of the available
information, whether the "hamburg" approach should be adopted by CFRG or
not.

[Note that the phrasing does not preclude other proposers from modifying
their schemes to use the Schnorr trick if that's what CFRG
collectively wants to do. So this is not a poll on "hamburg" scheme 
versa all others.]

Please don't discuss any other topics in this thread.

Best Regards,
Alexey and Kenny

---

From: "D. J. Bernstein" <[email-masked]>
Date: 14 Aug 2015 12:02:12 -0000

I don't think this question is characterizing the choices accurately.
The real choice---I'll illustrate for Curve25519---is between

   (1) using a 128-bit hash function ('hamburg') and
   (2) using a >=256-bit hash function (the others).

The core argument for #1 is that compressed signatures save some space
(see page 9 of the Ed25519 paper). The core argument for #2 is security
(see http://www.ietf.org/mail-archive/web/cfrg/current/msg07122.html and
http://www.ietf.org/mail-archive/web/cfrg/current/msg07135.html).

Both choices support fast batch verification of _uncompressed_
signatures. For #1 this means specifying two signature formats, a
compressed format to save space and an uncompressed format to allow fast
batch verification. For #2 there's no point in specifying the
"compressed" format.

The question makes #1 sound slower than #2, but anyone who needs the
speed of fast batch verification will be just as happy with the
uncompressed option of #1---in fact, the shorter hashes make #1 slightly
faster---while #1 also provides the option of compression for protocols
that want it. The argument for #2 isn't speed; it's security.

---Dan

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 14 Aug 2015 12:49:03 +0000

Dan

Thanks for expressing this viewpoint - it's a useful input.

We don't want to change the poll (restated at the bottom for everyone's
convenience), but we are happy to make the following clarifications in the
light of your message:

- signatures as proposed in the "hamburg" scheme can be transformed to a
second format so as to allow them to be efficiently batch verified (though
this second format is not formally part of the "hamburg" scheme as
proposed).

- however, the "hamburg" scheme uses a half-size hash output as compared
to the other schemes, which leads to the security concerns evinced in
<http://www.ietf.org/mail-archive/web/cfrg/current/msg07122.html>

Cheers,

Kenny (for the chairs)

>that want it. The argument for #2 isn't speed; it's security.

On 14/08/2015 11:55, "Cfrg on behalf of Alexey Melnikov"
<[email-masked] on behalf of [email-masked]> wrote:

>_______________________________________________
>Cfrg mailing list
>[email-masked]
>https://mail.ietf.org/mailman/listinfo/cfrg
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 14 Aug 2015 14:04:12 +0000

And based on your explanation, I vote for #2.
-- 
Regards,
Uri Blumenthal

---

From: Dan Brown <[email-masked]>
Date: Fri, 14 Aug 2015 14:53:20 +0000

no to allowing shortened hashes

because

1) Neven-Smart-Warinschi (NSW) 2009 showed K‎elsey-Kohno herding could be used to forge Schnorr with short narrow-pipe hash (as DJB also described to CFRG in 2015). By the way, this is also what I called a "deletion" attack (I mistakenly renamed, thinking it a special case, sorry.)

2) ‎NSW's security proof for Schnorr is uselessly loose for half-length hash.

3) As DJB pointed out, success rate to computation costs vary differently between ECC and symmetric crypto like hashes. Even though a 128-bit hash could achieve a similar tradeoff to AES128 it may be good to have a margin for error, etc., better matching ECC256.

4) There exist nearly reasonable short hashes that seem to meet the NSW security conditions for which Schnorr is forgeable. That's a bad indicator. Formally it means short Schnorr lacks any non-random-oracle-hash security proof.

Perhaps some of these problems can be fixed with a 3/4 length hash (eg 192 instead of 128 for ecc256), but I haven’t looked at it yet: will try next week.

  Original Message
From: Paterson, Kenny
Sent: Friday, August 14, 2015 8:49 AM
To: D. J. Bernstein; [email-masked]
Subject: Re: [Cfrg] Elliptic Curves - signature: shorter signatures versa batch verification (ends on August 21st)

Dan

Cheers,

Kenny (for the chairs)

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 14 Aug 2015 22:50:51 +0200

> no to allowing shortened hashes

+1

Your paper https://eprint.iacr.org/2015/169 is relevant here, but
perhaps your modesty did not allow you to mention it. :-)

/Simon

> because
>
> 1) Neven-Smart-Warinschi (NSW) 2009 showed K‎elsey-Kohno herding could
> be used to forge Schnorr with short narrow-pipe hash (as DJB also
> described to CFRG in 2015). By the way, this is also what I called a
> "deletion" attack (I mistakenly renamed, thinking it a special case,
> sorry.)
>
> 3) As DJB pointed out, success rate to computation costs vary
> differently between ECC and symmetric crypto like hashes. Even though
> a 128-bit hash could achieve a similar tradeoff to AES128 it may be
> good to have a margin for error, etc., better matching ECC256.
>
> 4) There exist nearly reasonable short hashes that seem to meet the
> NSW security conditions for which Schnorr is forgeable. That's a bad
> indicator. Formally it means short Schnorr lacks any
> non-random-oracle-hash security proof.
>
> Perhaps some of these problems can be fixed with a 3/4 length hash (eg
> 192 instead of 128 for ecc256), but I haven’t looked at it yet: will
> try next week.
>
>
>
>   Original Message
> From: Paterson, Kenny
> Subject: Re: [Cfrg] Elliptic Curves - signature: shorter signatures
> versa batch verification (ends on August 21st)
>
>
> Dan
>

---

From: Dan Brown <[email-masked]>
Date: Fri, 14 Aug 2015 21:32:21 +0000

I did refer to a paper of mine (reason 4) but was too lazy to cite it‎, link to it, etc. I am on vacation...

  Original Message
From: Simon Josefsson
Sent: Friday, August 14, 2015 4:51 PM
To: Dan Brown
Cc: Paterson, Kenny; D. J. Bernstein; [email-masked]
Subject: Re: Elliptic Curves - signature: shorter signatures versa batch verification (ends on August 21st)

+1

/Simon

---

From: "Jim Schaad" <[email-masked]>
Date: Fri, 14 Aug 2015 16:42:32 -0700

Looking at things from the constrained space, it would be nice to have
shorter signatures even if we lose some amount of security in the process as
the power consumption is a problem

+1 to keeping this as option.

Jim

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey
Melnikov
> Sent: Friday, August 14, 2015 3:56 AM
> To: [email-masked]
> Subject: [Cfrg] Elliptic Curves - signature: shorter signatures versa
batch
> verification (ends on August 21st)
> 
> Dear CFRG participants,
> 
shortening
> the final signature by using a method known as Schnorr's trick, while the
others
> do not. This means that the "hamburg" scheme enjoys shorter signatures
(e.g.
> 48 bytes instead of 64 bytes at the 128-bit security level). But it
removes the
> ability of the scheme to support fast batch verification of signatures.
Some
> concerns about the security implications of the approach adopted in the
> "hamburg" scheme have also been voiced on list:
> 
their
> schemes to use the Schnorr trick if that's what CFRG collectively wants to
do. So
> this is not a poll on "hamburg" scheme versa all others.]
> 
>

---

From: Derek Atkins <[email-masked]>
Date: Sun, 16 Aug 2015 12:38:52 -0400

Jim,

Is the issue of signature length a question of data storage,
transmission time, or CPU computation time?  I'm only curious because
we're working on signature scheme which trades off signature length for
significant verification computation speed.  (and by significant I mean
a factor of like 50-100x faster verification time).

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Watson Ladd <[email-masked]>
Date: Sun, 16 Aug 2015 22:28:57 -0700

Let's not forget that constrained devices can use other schemes, such
as pairing based signatures. Ed25519 signatures aren't any longer than
ECDSA signatures: designs that could use ECDSA can use Ed25519
instead. In fact, if size really matters pairings are the best choice.

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

---

From: "Jim Schaad" <[email-masked]>
Date: Sun, 16 Aug 2015 22:48:57 -0700

I am not the expert, but most of the people that I am talking to are mostly
worried about power usage from transmission of the data.   They believe that
20 bytes is potentially significant.

Jim

> From: Derek Atkins [mailto:[email-masked]]
> Sent: Sunday, August 16, 2015 9:39 AM
> To: Jim Schaad
> Cc: [email-masked]
> Subject: Re: [Cfrg] Elliptic Curves - signature: shorter signatures versa
batch
> Is the issue of signature length a question of data storage, transmission
time, or
> CPU computation time?  I'm only curious because we're working on signature
> scheme which trades off signature length for significant verification
> computation speed.  (and by significant I mean a factor of like 50-100x
faster
> verification time).
> > shorter signatures even if we lose some amount of security in the
> > process as the power consumption is a problem
> >
> >> concerns about the security implications of the approach adopted in
> >> the "hamburg" scheme have also been voiced on list:
> >>
> >> The chairs would like to conduct a poll to ask, in view of the
> >> available information, whether the "hamburg" approach should be
> >> adopted by CFRG or not.
> >>

---

From: Göran Selander <[email-masked]>
Date: Mon, 17 Aug 2015 06:36:09 +0000

I am not the expert either, but the issue with message size exceeding
certain frame sizes has been raised in certain IoT settings, and the
difference between 64 bytes and 48 bytes signature may be the difference
between fitting into the frame or not. The implications includes
fragmentation, which may have security implications in itself, but
apparently also bad transmission characteristics and high energy
consumption since in certain settings the main power consumption is
related to (wireless) transmission.

If CFRG will not provide a recommendation of an algorithm with shorter
signature, it may happen that applications that are restricted in message
size will either only encrypt or try to do something with symmetric
algorithms instead (which of course not necessarily gives the appropriate
security properties).

I agree it would be good to have an algorithm with shorter signature, with
a caveat spelling out the security implications.

Göran

On 2015-08-17 07:48, "Jim Schaad" <[email-masked]> wrote:

>>versa
>>transmission

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 18 Aug 2015 21:29:54 +0100

I assume that any shorter signature will be an optional
feature. I don't think it's a good idea to have options
so I would prefer to not have support for short signatures
unless that is the only option (and therefore considered
sufficiently secure). I do not believe that to be the case
for the schemes proposed.

So I'm "no to hamburg" in Alexey terms and (2) in response
to Dan's mail.

For those who want shorter signatures and are willing to
possibly sacrifice security for that, I think that ought
be a separate algorithm identifier and should not be the
first signature scheme based on the new curves work in
CFRG. In other words, please prioritise security now for
the new curves signature scheme and also prioritise the
"normal" computing environment and not the small-device
or small-MTU environment. Small-devices and small-MTU
cases can be handled later. For now, we want signatures
that will mainly be used for TLS server certificates for
the "no RSA at all" use-cases for TLS and short-signatures
are just not the priority there.

I'd also ask that folks with more of an interest in what's
called IoT please consider that perhaps in this case, we
should first prioritise that "normal" TLS server and then
come back for a short signature scheme later. (If that's
enough to convince someone to change their opinion, please
do send to the list a 2nd time:-)

S.

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 18 Aug 2015 18:02:04 -0700

> From: Cfrg [mailto:[email-masked]] On Behalf Of Stephen
Farrell
> Sent: Tuesday, August 18, 2015 1:30 PM
> To: Alexey Melnikov; [email-masked]
batch
> I assume that any shorter signature will be an optional feature. I don't
think it's a
> good idea to have options so I would prefer to not have support for short
> signatures unless that is the only option (and therefore considered
sufficiently
> secure). I do not believe that to be the case for the schemes proposed.
> 
> So I'm "no to hamburg" in Alexey terms and (2) in response to Dan's mail.
> 
> For those who want shorter signatures and are willing to possibly
sacrifice
> security for that, I think that ought be a separate algorithm identifier
and should

I would agree that the algorithm should be identified separately if it does
have worse security properties.

> not be the first signature scheme based on the new curves work in CFRG. In
> other words, please prioritise security now for the new curves signature
scheme
> and also prioritise the "normal" computing environment and not the small-
> device or small-MTU environment. Small-devices and small-MTU cases can be
> handled later. For now, we want signatures that will mainly be used for
TLS
> server certificates for the "no RSA at all" use-cases for TLS and
short-signatures
> I'd also ask that folks with more of an interest in what's called IoT
please
> consider that perhaps in this case, we should first prioritise that
"normal" TLS
> server and then come back for a short signature scheme later. (If that's
enough
> to convince someone to change their opinion, please do send to the list a
2nd
> time:-)

I do have some of the same worries that you do for delivery of an answer.
For both the TLS case and for the IoT world case.  I don't want to wait 5
years for TLS to get an answer, but waiting 5 years for the IoT solution
might be even worse.

No answer to the problem that people have suggested seems to be any better
than this answer, but I am not anything more than a Holiday Inn
Cryptographer.

Jim

> > [Note that the phrasing does not preclude other proposers from
> > modifying their schemes to use the Schnorr trick if that's what CFRG

---

From: Watson Ladd <[email-masked]>
Date: Tue, 18 Aug 2015 18:04:53 -0700

> algorithms instead (which of course not necessarily gives the appropriate

Once again, see my above comment. The existence of some
recommendations shouldn't be taken to disallow the creation of others
when some requirements are tighter. In fact, I don't see why you can't
write a draft describing what you want and get feedback on it now.

>>> >> modifying

---

From: Adam Langley <[email-masked]>
Date: Wed, 19 Aug 2015 11:04:17 -0700

> <http://www.ietf.org/mail-archive/web/cfrg/current/msg07122.html>

I hope, in the future, that batch verification can be used to positive
effect and I dislike having to worry about two different signature
formats. Thus I think I would prefer (2).

Cheers

AGL

---

From: Göran Selander <[email-masked]>
Date: Thu, 20 Aug 2015 07:33:12 +0000

>write a draft describing what you want and get feedback on it now.

If it would be possible to consider signature schemes for the IoT
applications mentioned in parallel to the TLS server certificates that
would be very helpful.

As for drafts, I’m not sure if you refer to problem statement or solution
proposal. For problem statement there is text in ACE and 6tisch WG drafts
(that of course could be more concisely presented). The message format in
focus here is that in development in the COSE WG.

As for solutions to short signatures there is only a short list of
candidates: A) old style Schnorr B) signatures with message recovery, and
now C) pairing based.

As a layman - please correct me if I’m wrong - I have the impression that
when it comes to maturity/“aegis" and feasibility for implementation in
the constrained setting in the near future (not only considering signature
size), A) is the main candidate in this list.

Göran

>>>> >> the final signature by using a method known as Schnorr's trick,
>>>>while
>>>> >> the
>>>> > others

---

From: Watson Ladd <[email-masked]>
Date: Thu, 20 Aug 2015 07:47:29 -0700

> size), A) is the main candidate in this list.

Then write a draft describing A if you think it's the only solution.
Solution B is detailed in ISO crypto standards or so I'm told. And
there is lots of analysis of solution C, and many papers on
implementations, but the pairing can be expensive. In solution C,
pairings are only used on verification, and are batchable. Signing
doesn't require a pairing computation.

---

From: Rene Struik <[email-masked]>
Date: Fri, 21 Aug 2015 17:10:29 -0400

Dear colleagues:

I think we should avoid Schnorr signatures with truncated hashes for now.

Having a signature format that is computationally friendly for batch 
computations may be useful esp. in settings with certificate chains and 
in some modi operandi of the draft TLS1.3 specification. A further 
benefit can be obtained if one would insist that such signatures do not 
hash the public key along. This would help, since then the public key is 
recoverable from the signature and, e.g., certificate chains can leave 
out public keys in all-but-one of the certs in the chain. This seems to 
be a useful feature for applications that do not care for batch 
operations, but do put special emphasis on concise encodings (as most 
"IoT"-focused people do). Leaving out the public key does not have a 
security impact (in the so-called multi-user setting). {BTW - this is 
not a foreign concept, since ECDSA is an example of such a scheme.}

There are signature schemes with low communication overhead, such as the 
ECPVS scheme (overhead at 128-bit security level is only 32 octets if 
the message to be signed has 16 octets of redundancy). I think this may 
be a scheme that could potentially be useful as well and has some 
provability results (e.g., in RSA-CT 2001). I do realize that this 
scheme has not been discussed within CFRG so far, but technically that 
should not matter that much. The scheme may have some IPR, but perhaps 
this could be considered if a friendly declaration is made.

Best regards, Rene

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 21 Aug 2015 14:27:15 -0700

+1

That said, I understand the IoT-related concerns here, and would suggest it
might make sense to specify a separate signature algorithm specifically for
the IoT use case where these sorts of security compromises can be made
without affecting the security of devices like Smartphones, Tablets, PCs,
and servers.

-- 
Tony Arcieri

---

From: Yoav Nir <[email-masked]>
Date: Tue, 25 Aug 2015 14:08:20 +0300

> On Aug 14, 2015, at 1:55 PM, Alexey Melnikov <[email-masked]> wrote:
> 
> Dear CFRG participants,
> 
> Of the various proposals, one ("hamburg", see <http://ed25519.cr.yp.to/cfrg/signatures.py>) takes the option of shortening the final signature by using a method known as Schnorr's trick, while the others do not. This means that the "hamburg" scheme enjoys shorter signatures (e.g. 48 bytes instead of 64 bytes at the 128-bit security level). But it removes the ability of the scheme to support fast batch verification of signatures. Some concerns about the security implications of the approach adopted in the "hamburg" scheme have also been voiced on list

A little late for the party. My excuse is that I was on vacation. I’m also against having shortened (“Hamburg” or “2”) signatures.

Regarding the IoT use cases, I realize that a signature enlarging the data so much that in exceeds a single packet is inconvenient. I’m wondering, though, what kinds or protocols are we talking about. (D)TLS and others all have signatures very rarely. Most packets (or records) don’t carry signatures - they carry tags or MACs based on relatively long-lived state. Is sending a signature once an hour or once a day that is 16 bytes longer still considered prohibitive?  Or are we talking about some protocol that signs every message?

Yoav

---

From: Göran Selander <[email-masked]>
Date: Wed, 26 Aug 2015 06:40:40 +0000

On 2015-08-25 13:08, "Yoav Nir" <[email-masked]> wrote:

>>have also been voiced on list
>
>A little late for the party. My excuse is that I was on vacation. I’m
>also against having shortened (“Hamburg” or “2”) signatures.
>
>Regarding the IoT use cases, I realize that a signature enlarging the
>data so much that in exceeds a single packet is inconvenient. I’m
>wondering, though, what kinds or protocols are we talking about. (D)TLS
>and others all have signatures very rarely. Most packets (or records)
>don’t carry signatures - they carry tags or MACs based on relatively
>long-lived state. Is sending a signature once an hour or once a day that
>is 16 bytes longer still considered prohibitive?  Or are we talking about
>some protocol that signs every message?

One example of type of application is given in
https://tools.ietf.org/html/draft-seitz-ace-core-authz-00#section-2.2

The candidate message format for the work in ACE is developed in the COSE
WG. Key establishment is TBD - the proposed architecture contains trusted
parties that e.g. could act KDC.

Hope that helps.

Göran

---

From: Alexey Melnikov <[email-masked]>
Date: Wed, 26 Aug 2015 13:50:43 +0100

> collectively wants to do. So this is not a poll on "hamburg" scheme 
To summarize results on this poll:

 From the mailing list discussion there is rough consensus not to 
recommend use of shorter signatures at this time.

But a significant minority would like to work on them, so chairs are 
happy to have a separate CFRG document on the topic at a later date. 
Chairs will talk to Michael Hamburg about that.

Best Regards,
Kenny and Alexey