Subject: Re: [Cfrg] EC signature: next steps

From: Simon Josefsson <[email-masked]>
Date: Tue, 01 Sep 2015 09:04:22 +0200

Ilari Liusvaara <[email-masked]> writes:

> On Mon, Aug 31, 2015 at 03:06:43PM +0200, Simon Josefsson wrote:
>> Alexey Melnikov <[email-masked]> writes:
>> 
>> > - are there errors of fact or omission that need to be corrected?
>> 
>> 1) I don't understand by this part of Ilari's writeup: 'dictated by
>> ???'.
>
> I earlier tought that the prehash comes from the key, but then
> read comment by DJB stating that this is not the case.

Do you have a reference?  I believe the
http://ed25519.cr.yp.to/eddsa-20150704.pdf paper is clear on this.
Simply explained, the prehash is a parameter of the signature system.

> As for personalization, the problem is that protocols A and B (or
> even just different versions of the same protocol!) can interpret the
> same message in rather different ways.

Do you have a concrete example?  I would consider that a protocol flaw.

>> 3) What is NPOT?
>
> (Order) Near Power Of Two. The difference of order and nearest power
> of two is on order of sqrt(l).
>
> Such orders produce even distributions of x mod l, where x is n bits
> long with smaller n than usual.
>
> Both Curve25519 and Curve448 are NPOT. 

How is this relevant to the chose of signature scheme?

/Simon

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 1 Sep 2015 18:41:09 +0300

> Simply explained, the prehash is a parameter of the signature system.

So it is denoted in the key (since signature system parameters need to
be fixed by the key) after all?

> Do you have a concrete example?  I would consider that a protocol flaw.

The problem is that each protocol or version might be reasonable alone,
but still interact badly.

The worst are "challenge signing" protocols. One could argue that is a
design flaw, but that kind of construct is used because it is simple.
 
> How is this relevant to the chose of signature scheme?

It isn't really relevant.

-Ilari

---

From: "D. J. Bernstein" <[email-masked]>
Date: 1 Sep 2015 15:51:35 -0000

> Do you have a concrete example?  I would consider that a protocol flaw.

It's certainly a protocol flaw---but sometimes designers of multiple
protocols, or multiple protocol components, don't talk to each other:

   * Protocol A: There are two messages, "Put the troops through a
     surprise drill" and "Don't put the troops through a surprise
     drill". For efficiency these messages are compressed to "1" and
     "0" respectively. For security, make sure to check that the
     compressed message is signed with the General's PGP key.

   * Protocol B: There are two messages, "Launch the missiles" and
     "Don't launch the missiles". For efficiency these messages are
     compressed to "1" and "0". For security, make sure to check that
     the compressed message is signed with the General's PGP key.

Each protocol is safe by itself, but the two protocols together allow
forgeries. Here's a fairly recent example of this type of bug in TLS:

   https://www.cosic.esat.kuleuven.be/publications/article-2216.pdf

The standard fix for this type of problem is to encode more information
into the signed messages so that they can't be taken out of context. Of
course, to figure out how much information is enough, you have to work
at the protocol layer, understanding all the different contexts in all
of the high-level protocols that might sign messages under the same
key---and the protocol designers need to talk to each other! Any
encoding, no matter how verbose, can be ruined by another protocol
assigning new meanings to some of the encoded messages.

Ilari and Mike have both suggested a different approach, feeding extra
side inputs into signatures, where these inputs vary from one protocol
to another. I have the same questions about these side inputs that I had
about William's suggestion to include certificates:

   * Are cryptographic libraries supposed to change their signature APIs
     to allow an extra side input?

   * What exactly are the format and semantics of this input? For
     example, how exactly would this side input be used to stop the TLS
     bug mentioned above?

   * What happens when someone wants to use more of these inputs?

   * How should libraries handle all of the signature standards that
     don't support this input?

   * More to the point, how is this supposed to be better than having
     the application sign a more informative message, using the
     traditional concept of a signature system?

As I wrote before: The standard signature concept has been stable for
decades. It's shared by theoretical papers, signature specifications,
attack papers, and software. From this perspective, having a side input
to a signature algorithm per se---rather than having it be part of how
the higher-level application decides to use signatures---is a severe
layering violation. I've seen cases where there's real justification for
rethinking the layers in cryptography, but "this application always
needs to verify X,Y,Z so signature systems should have X,Y,Z as separate
inputs" is obviously a bad argument.

---Dan

---

From: Natanael <[email-masked]>
Date: Tue, 1 Sep 2015 19:16:45 +0200

> protocols, or multiple protocol components, don't talk to each other:

[...]

> assigning new meanings to some of the encoded messages.

[...]

>      example, how exactly would this side input be used to stop the TLS

I've got one suggestion. It may be impractical to implement or maybe even
impossible in some circumstances, but I believe it would work when designed
for from the start;

Every signature in every context needs a unique deterministic nonce.

The nonce is derived from at least the following: the signing public key,
the message *and the code path of invocation* (as how the spec defines
it!), and probably a standard cryptographic nonce/counter.

A signature to be generated by signing function X which was called by
function A takes a unique constant from A and from X and hash them together
with the above mentioned data, pre-sorted in a specific way. Let's say we
have a revocation signature feature and a command message signing feature -
the feature who's function calls the signing function has its own constant
come first before hashing to create the nonce. The hashing function may be
a MAC, or some other function resistant to extension attacks.

If some implementation does things internally in a non-standard order it
must track the official order of doing things, as well as be careful to not
itself create ambiguity. The nonce creation behavior should be replicated
exactly.

I don't personally care how this context nonce is included. It might be
easier to just sign it with the rest of the message.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 1 Sep 2015 20:36:19 +0200

Den Tue, 1 Sep 2015 18:41:09 +0300
skrev Re: EC signature: next steps:

> > >> 1) I don't understand by this part of Ilari's writeup: 'dictated
> > >> by ???'.
> > >

I don't understand what you mean by "denoted in the key"?  The encoding
of the public key does not contain the prehash OID or anything similar,
if that is what you refer to.

The prehash is a parameter of the signature system, similar to many
other parameters (curve, base point, encodings, etc).  A key is only
valid for a particular signature system, unless some other (likely
higher level) protocol or mechanism specify how it could safely be used
with another signature system.

> > > even just different versions of the same protocol!) can interpret
> > > the same message in rather different ways.
> > 
> The problem is that each protocol or version might be reasonable
> alone, but still interact badly.
> 

Are there any IETF protocols like that?  I'm not sure if this is an
imaginary or real problem.  The traditional solution is to use one key
per protocol anyway.

> > >> 3) What is NPOT?
> > >
> > > (Order) Near Power Of Two. The difference of order and nearest
> > > power of two is on order of sqrt(l).
> > >
> > > Such orders produce even distributions of x mod l, where x is n
> > > bits long with smaller n than usual.
> > >

Then I suggest either that it is dropped from the comparison, or that
its meaning/relevance is clarified.

/Simon

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 1 Sep 2015 12:01:17 -0700

> On Sep 1, 2015, at 10:16 AM, Natanael <[email-masked]> wrote:
> 
> 
> Den 1 sep 2015 17:51 skrev "D. J. Bernstein" <[email-masked] <mailto:[email-masked]>>:
> >
> > Simon Josefsson writes:
> I've got one suggestion. It may be impractical to implement or maybe even impossible in some circumstances, but I believe it would work when designed for from the start;
> 
> The nonce is derived from at least the following: the signing public key, the message *and the code path of invocation* (as how the spec defines it!), and probably a standard cryptographic nonce/counter.
> 
> A signature to be generated by signing function X which was called by function A takes a unique constant from A and from X and hash them together with the above mentioned data, pre-sorted in a specific way. Let's say we have a revocation signature feature and a command message signing feature - the feature who's function calls the signing function has its own constant come first before hashing to create the nonce. The hashing function may be a MAC, or some other function resistant to extension attacks.
> 
> If some implementation does things internally in a non-standard order it must track the official order of doing things, as well as be careful to not itself create ambiguity. The nonce creation behavior should be replicated exactly.
> 
> I don't personally care how this context nonce is included. It might be easier to just sign it with the rest of the message. 

Not that it matters much for CFRG, but STROBE lite is going to do something like this.

The idea is that you have a sponge object which can accumulate state either from a protocol, or from a symmetric primitive.  The state starts with an arbitrary protocol/cryptosystem description string, and gets tagged data objects accumulated into it.  Since it’s a duplex construction, it can be used for encryption and decryption.  The output at any point is a hash (suitable for random oracle usage) of everything which has gone into it, with a certain parseable encoding scheme.  The tags may be protocol- or cryptosystem-specific, but there’s a generic pool of them for convenience purposes.  In general they include what the data means to the protocol, who sent or received a message (if it’s a protocol and not a static cryptosystem) and a length field (which is redundant but helps prevent certain mistakes).

Instead of signing a message, you sign a session object which has a protocol description and possibly context tags in addition to your message.  So you have a sponge object with your session state, and you want to sign.  The process will be something like

st <-> (TAG_SIG_SYSTEM, sig and curve description) // could be optional in principle if it’s obvious from context?

st2 = copy of st
st2 <-> (TAG_SIG_SECRET, secret key = x)
st2 <-> (TAG_SIG_GEN_NONCE, [squeeze n bytes]) -> k
erase st2
// or choose k at random, or by some other pseudorandom method; the above technique may be weak to DPA
// because it mixes a secret key directly with a pseudorandom state.

st <-> (TAG_SIG_EPH, g^k)
st <-> (TAG_SIG_CHALLENGE, [squeeze n bytes]) -> c
st <-> (TAG_SIG_RESPONSE, cx+k) -> encryption of cx+k

The signature is (g^k, encryption of cx+k).  The value cx+k is encrypted because it proves knowledge of the key when used in a keyed protocol; otherwise if you could somehow convince someone that your public key was the identity, then the signature (identity,0) would not prove knowledge of the key.

Of course, this method is vulnerable to internal collision attacks if they exist.

Cheers,
— Mike

---

From: Rene Struik <[email-masked]>
Date: Fri, 4 Sep 2015 09:24:12 -0400

Dear colleagues:

I think the signature scheme should facilitate the following:
a) signature generation.
Ideally, signing should be possible without requiring the signer to 
access its public key (obviously, it does require the private key). For 
Schnorr and ECDSA type schemes, one does not need to include the public 
key in the signing process, since security in the multi-user setting is 
roughly the same as in the single-user setting (see [1], [2]).
b) signature verification.
If the public key of the signer is not included with signing, it is also 
generally not required with verification (if the signature includes the 
ephemeral signing key), since then the public key of the signer can be 
reconstructed from the signature itself (with Schnorr signature (R,s) 
over message m, one has Q=(1/h)(R-sG), where h=H(R,m)). This may have 
advantages in settings with certificate chains and with single 
signatures (where one can reduce overhead to identify the public key of 
the signer).
c) reuse of same signing key with IUF/non-IUF schemes.
Ideally, one should be able to use the same signing key, no matter 
whether one uses the signature scheme in the so-called IUF setting or in 
the non-IUF setting. If I understand correctly, consensus is to only 
specify an IUF-scheme, but even then, the design should be so that it 
can support both flavors. This should *not* be left to applications to 
specify (and can also easily be done).
d) same signature scheme for Weierstrass curves, (twisted) Edwards 
curves, and Montgomery curves.
The signature scheme should work for all these three schemes and not 
just for (twisted) Edwards curves. Ideally, it should also work for Huff 
curves, Jacobian curves, etc., without requiring any changes outside the 
scalar multiplication routine.

Best regards, Rene

Ref:
[1] A. Menezes, N.P. Smart, "Security of Signature Schemes in A 
Multi-User Setting", CACR-Corr-2001-063.
[2] J. Malone Lee, S. Galbraith, N. P. Smart, "Public Key Signatures in 
the Multi-User Setting", Inform.Proc.Letters, 2002.

On 8/31/2015 5:53 AM, Alexey Melnikov wrote:
> Dear CFRG participants,
>
> Many thanks to Ilari for posting this updated summary of where things
> currently stand. Kenny and I would now like to run a short discussion
> focusing on this summary, with our intention being to flush out any last
> issues or additional points of comparison between the different schemes
> that everyone should be aware of.
>
> Once everyone has kicked the tires, so to speak, we plan to move to a
> poll to decide which scheme CFRG should focus on writing up and formally
> recommending. We, as chairs, are hoping these steps will get us to the
> finishing line.
>
> So:
>
> - are there important characteristics or points of comparison that
> Ilari's summary does not cover?
>
> - anything else?
> We'll let this discussion run for exactly one week, but we might extend
> the time if the discussion is still going strong and new arguments or
> points of comparison are brought up. After that, if no major new
> information is brought up, we will start the Quaker poll for selecting a
> single CFRG-recommended signature scheme.
>
>
> Best Regards,
> Kenny and Alexey
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://mail.ietf.org/mailman/listinfo/cfrg

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

---

From: David Jacobson <[email-masked]>
Date: Fri, 4 Sep 2015 09:06:56 -0700

Why do you advocate that signing should be possible without requiring 
the signer to access its public key?  In RSA signataures the public key 
is (m, e) and the private key is d.  But the signer needs m.   This does 
not seem to be a problem.

I don't get how you can do verification without a public key that you 
believe is the public key for the party you believe to be the sender.  
There has to be some connection to something trusted.

    --David

On 9/4/15 6:24 AM, Rene Struik wrote:
> access its public key (obviously, it does require the private key). 
> For Schnorr and ECDSA type schemes, one does not need to include the 
> public key in the signing process, since security in the multi-user 
> setting is roughly the same as in the single-user setting (see [1], [2]).
> If the public key of the signer is not included with signing, it is 
> also generally not required with verification (if the signature 
> includes the ephemeral signing key), since then the public key of the 
> signer can be reconstructed from the signature itself (with Schnorr 
> signature (R,s) over message m, one has Q=(1/h)(R-sG), where 
> h=H(R,m)). This may have advantages in settings with certificate 
> chains and with single signatures (where one can reduce overhead to 
> identify the public key of the signer).
> whether one uses the signature scheme in the so-called IUF setting or 
> in the non-IUF setting. If I understand correctly, consensus is to 
> only specify an IUF-scheme, but even then, the design should be so 
> that it can support both flavors. This should *not* be left to 
> applications to specify (and can also easily be done).
> just for (twisted) Edwards curves. Ideally, it should also work for 
> Huff curves, Jacobian curves, etc., without requiring any changes 
> outside the scalar multiplication routine.
>
> Best regards, Rene
>
> Ref:
> [2] J. Malone Lee, S. Galbraith, N. P. Smart, "Public Key Signatures 
> in the Multi-User Setting", Inform.Proc.Letters, 2002.
>
>
>
>

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 4 Sep 2015 10:31:26 -0700

I agree with Rene. Having to hold the public key along with the private key can be annoying, and there is little gain to it in light of the papers he cited. More below. 

Sent from my phone.  Please excuse brevity and typos.

> On Sep 4, 2015, at 09:06, David Jacobson <[email-masked]> wrote:
> 
> Why do you advocate that signing should be possible without requiring the signer to access its public key?  In RSA signataures the public key is (m, e) and the private key is d.  But the signer needs m.   This does not seem to be a problem.

This is useful in cases where the private key is derived pseudo randomly from something like a PUF.  This way the signer can just sign the message instead of deriving the public key first, which would make the operation twice as expensive. 

This use case is not practical with RSA. 

> I don't get how you can do verification without a public key that you believe is the public key for the party you believe to be the sender.  There has to be some connection to something trusted.

By verifying the signature, you recover the public key. Then you can decide whether you trust it, eg by following a cert chain or checking a list of trusted keys or hashes. This avoids sending the public key, which isn't usually a big deal but it can matter for constrained devices.  It's also more elegant in some systems. 

>  --David

Cheers,
-- Mike
>> Ideally, signing should be possible without requiring the signer to access its public key (obviously, it does require the private key). For Schnorr and ECDSA type schemes, one does not need to include the public key in the signing process, since security in the multi-user setting is roughly the same as in the single-user setting (see [1], [2]).
>> If the public key of the signer is not included with signing, it is also generally not required with verification (if the signature includes the ephemeral signing key), since then the public key of the signer can be reconstructed from the signature itself (with Schnorr signature (R,s) over message m, one has Q=(1/h)(R-sG), where h=H(R,m)). This may have advantages in settings with certificate chains and with single signatures (where one can reduce overhead to identify the public key of the signer).
>> Ideally, one should be able to use the same signing key, no matter whether one uses the signature scheme in the so-called IUF setting or in the non-IUF setting. If I understand correctly, consensus is to only specify an IUF-scheme, but even then, the design should be so that it can support both flavors. This should *not* be left to applications to specify (and can also easily be done).
>> d) same signature scheme for Weierstrass curves, (twisted) Edwards curves, and Montgomery curves.
>> The signature scheme should work for all these three schemes and not just for (twisted) Edwards curves. Ideally, it should also work for Huff curves, Jacobian curves, etc., without requiring any changes outside the scalar multiplication routine.
>> 
>> Best regards, Rene
>> 
>> Ref:
>> [1] A. Menezes, N.P. Smart, "Security of Signature Schemes in A Multi-User Setting", CACR-Corr-2001-063.
>> [2] J. Malone Lee, S. Galbraith, N. P. Smart, "Public Key Signatures in the Multi-User Setting", Inform.Proc.Letters, 2002.
>> 
>> 
>> 
>>

---

From: William Whyte <[email-masked]>
Date: Fri, 4 Sep 2015 13:00:39 -0500

I also like the idea of being able to sign and verify without providing
the public key as part of the hash input.

Cheers,

William

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Rene Struik
Sent: Friday, September 04, 2015 8:24 AM
To: Alexey Melnikov; [email-masked]
Subject: Re: [Cfrg] EC signature: next steps

Dear colleagues:

Best regards, Rene

Ref:

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 4 Sep 2015 21:18:01 +0100

If the cost of supporting any of the things Rene mentions is *any*
delay, I'm against.

S.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 4 Sep 2015 20:26:28 +0000

It took us all a while to get here. If it takes a bit longer to get it
right, so be it.

There’s ECDSA and EC-KCDSA for those who can’t wait any longer. :-)  Not
to mention [F]HMQV. :-)
-- 
Regards,
Uri Blumenthal

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 4 Sep 2015 23:35:03 +0300

> There’s ECDSA and EC-KCDSA for those who can’t wait any longer. :-)  Not

Also, Ed25519 (it is starting to pop up in various places)...

-Ilari

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 4 Sep 2015 21:38:53 +0100

> There’s ECDSA and EC-KCDSA for those who can’t wait any longer. :-)  Not

Being any slower here IMO risks implementations for a number of
protocols shipping with Ed25519, causing confusion and possible
interop issues. The issue is simply whether or not CFRG's work
will be overtaken by events. I hope that won't happen and have
been asking folks within IETF WGs to please hold off. But they
won't forever, and a number of folks have expressed frustration
at how long this is taking. Taking longer certainly increases
the liklihood of this work being OBE.

S.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 17 Sep 2015 22:47:29 -0000

This message continues the security analysis of inserting the public key
A into the hash in Schnorr's signature system: e.g., H(R,A,M) instead of
Schnorr's classic H(R,M). The 'brown' and 'ladd' proposals omit the key
from the hash but the other proposals include it.

The Ed25519 paper says that including the key is an inexpensive way "to
alleviate concerns that several public keys could be attacked
simultaneously". Here's the background regarding these concerns:

   * Most of the literature on signature-system security focuses on the
     problem of forging messages under _one_ public key.

   * The real-world attacker actually sees _many_ public keys, and is
     probably happy if he solves the problem of forging messages under
     any one of those keys. (For example, he simply wants to take over
     _somebody's_ account to gain computer power, relay more attacks,
     etc.) This isn't the same problem.

   * The concern is that switching to the multi-key problem could give
     the attacker an advantage, compared to the original problem. There
     _is_ an analogous advantage in attacking secret-key protocols---
     which is why I recommend 256-bit secret keys.

   * It's easy to prove, for any signature system, that attacking a
     billion keys at once can't give the attacker an advantage of more
     than a factor of a billion. But, yikes, a billion is a big number!

I hope it's clear that the word "concern" does _not_ mean that there are
any known multi-key attacks better than single-key attacks on any of the
signature schemes under consideration. What it means is that one can
reasonably be worried about the _possibility_ of multi-key attacks, and
about the lack of study of this possibility.

I'm happy to announce that there's now a theorem guaranteeing that key
insertion completely eliminates this concern:

   probability of breaking any 1 of N signature keys using H(R,A,M)
   <= probability of breaking a targeted signature key using H(R,M).

In other words, if you believe that the classic H(R,M) system in the
single-key case is secure, then you have to believe that the H(R,A,M)
system is secure for any number of keys. The proof is a simple reduction
that takes any attack against multi-key H(R,A,M) and converts it into a
single-key attack against H(R,M); the single-key attack has practically
identical performance and success probability to the multi-key attack.  

The proof relies critically on the insertion of the public key A into
the hash. There's a huge obstacle to proving a similar theorem without 
the public key, as I'll explain below. The best theorem we know without
hashing A is the generic

   probability of breaking any 1 of N signature keys using H(R,M)
   <= N*probability of breaking a targeted signature key using H(R,M)

which still leaves the concern unaddressed. To summarize:

   * Inserting the public key eliminates the multi-key concerns.
   * Omitting the public key doesn't.

I should emphasize that the theorem is for a quite traditional form of
Schnorr's system, and hasn't yet been combined with modern features such
as derandomization, key derivation, cofactors, etc.; many of these
features obviously complicate the "provable security" picture. However,
even with its limited scope, the theorem---together with the inability
to prove the same theorem with the key omitted---justifies the idea that
inserting the key into the hash is the conservative thing to do.

The proof idea appeared many years ago, but unfortunately with a serious
mistake, leading to various incorrect conclusions, both by the original
authors and by subsequent readers. This week I've conferred with and
heard back from various people, including two of the original authors,
and everyone seems to agree with what I'm saying. The rest of this
message discusses the history, the mistake, and the proof details.

Rene Struik writes:
> one does not need to include the public key in the signing process,
> since security in the multi-user setting is roughly the same as in the
> single-user setting (see [1], [2]).

Reference #1 doesn't quantify security levels, and doesn't have any
proof techniques relevant to the concerns under discussion.

Reference #2 _does_ quantify security levels, and specifically claims to
have proven that "security does not decrease with the number of users"
for Schnorr signatures. This claim will have to be retracted. The proof
is wrong, and there's no hope of proving the claimed theorem.

The overall proof idea in reference #2 is good, _except_ that the proof
skips past a critical step (namely, proving that the alleged forgery is
on a message that wasn't legitimately signed); the huge obstacle sinks
the proof at exactly this point. Inserting the public key into the hash
dodges the obstacle, and makes the whole proof idea work, producing the
new theorem, which _does_ eliminate the concern for multi-key H(R,A,M).

End of summaries. I'll now dive into the proof details, with the goal of
allowing public verification of what I said above.

"Classic scheme", parametrized by a standard group and a standard base
point B: The signer, given a message M, produces as signature a uniform
random R, independent of everything else, and the unique S satisfying
SB = R+H(R,M)A, where A is the public key.

Let's consider single-key attacks against the classic scheme. An attack
receives as input

   * a key A and
   * an oracle that, given M, produces a uniform random R, independent
     of everything else, and the unique S satisfying SB = R + H(R,M)A.

An attack produces as output a message M and an alleged signature (R,S).
Success means that

   * SB = R+H(R,M)A, i.e., (R,S) is a signature of M under A; and
   * M was not an oracle query, i.e., key A did not legitimately sign
     message M.

The starting assumption is that such attacks have been adequately
studied, and that the classic scheme is (for appropriate distributions
of A) secure against these attacks: i.e., any attack with a feasible
cost has a negligible probability of success.

"Generalized scheme", parametrized by a standard group, a standard base
point B, and a standard function "tag": The signer, given M, produces as
signature a uniform random R, independent of everything else, and the
unique S satisfying SB = R+H(R,tag(A),M)A, where A is the public key.
I'm implicitly assuming that R and tag(A) are both self-delimiting, so
we can recover R and tag(A) and M from the concatenation (R,tag(A),M).

If tag(A) is defined as the empty string then the generalized scheme is
the same as the classic scheme. If tag(A) is defined as A then the
generalized scheme includes the whole public key in the hash.

Let's consider N-key attacks against the generalized scheme. An attack
receives as input

   * keys A_1,A_2,...,A_N and
   * an oracle that, given a key T in {A_1,A_2,...,A_N} and a message M,
     produces a uniform random R, independent of everything else, and
     the unique S satisfying SB = R+H(R,tag(T),M)T.

An attack produces as output a public key T, a message M, and an alleged
signature (R,S). Success means that

   * T is in {A_1,A_2,...,A_N}, i.e., T is one of the specified keys;
   * SB = R+H(R,tag(T),M)T, i.e., (R,S) is a signature of M under T; and
   * (T,M) was not an oracle query, i.e., key T did not legitimately
     sign message M.

What I'll do is convert any N-key attack X against the generalized
scheme into a single-key attack ReRandomize(X) against the classic
scheme. The goal is to ensure that ReRandomize(X) and X have practically
identical costs and the same identical success probabilities. We'll see
that this works if the tag function is injective. We'll also see what
the obstacle is if multiple keys collide under the tag function, for
example if tag(A) = empty.

Here's what ReRandomize(X) does.

Generate uniform random r_1,r_2,...,r_N, and convert the input key A
into N independent uniform random keys A+r_1 B, A+r_2 B, ..., A+r_N B.
Run X on these N keys. Whenever X asks for a signature of M under T:

   * Look up T in the list of A+r_1 B, A+r_2 B, ..., A+r_N B to find an
     i such that T = A+r_i B; if none exists, reject the query.

   * Relay the concatenation (tag(T),M) to the input oracle. By
     hypothesis the input oracle produces a uniform random R,
     independent of everything else, and the unique S satisfying
     SB = R + H(R,tag(T),M)A.

   * Compute S' = S+r_i H(R,tag(T),M). Then S'B = R + H(R,tag(T),M)T;
     i.e., (R,S') is a signature of M under T in the generalized scheme.

   * Return (R,S') to X. Notice that this is exactly the behavior of a
     normal signer who knows the secret key for T in the generalized
     scheme: namely, returning a uniform random R, independent of
     everything else, and a solution to the right equation.

This is exactly a run of X against N independent uniform random keys and
an appropriate oracle for those keys. Eventually X produces as output
T,M,R,S. As above find i such that T = A+r_i B (aborting if there is no
such i), and compute S' = S - r_i H(R,tag(T),M). Output the
concatenation (tag(T),M) and the pair (R,S').

_If_ tag is injective, and X is successful against the generalized
scheme, then this algorithm ReRandomize(X) is successful against the
classic scheme. Indeed, recall the definition of success for X:

   * First, T is in {A_1,A_2,...,A_N}. This means that there _will_ be an
     i such that T = A+r_i B.

   * Second, SB = R+H(R,tag(T),M)T. This implies S'B = R+H(R,tag(T),M)A;
     i.e., (R,S') is a signature of (tag(T),M) under A.

   * Third, (T,M) wasn't an oracle query from X. What I want to conclude
     at this point is that (tag(T),M) wasn't legitimately signed by A,
     i.e., wasn't an oracle query from ReRandomize(X). This is where the
     injectivity of tag(T) matters.

     The queries from ReRandomize(X) are exactly (tag(T'),M') for the
     queries (T',M') from X such that T' is in {A+r_1 B,...,A+R_N B}.
     I'm using the notation T',M' here to avoid confusion with the T,M
     output by X.

     Suppose the output (tag(T),M) was a query from ReRandomize(X). Then
     (tag(T),M) = (tag(T'),M') for some query (T',M') from X. Now tag is
     self-delimiting, so tag(T) = tag(T') and M = M'; tag is injective,
     so T = T'; so (T,M) = (T',M'); so (T,M) _was_ a query from X,
     contradiction. Hence (tag(T),M) wasn't a query from ReRandomize(X).

That's the end of the proof.

What happens if we drop the injectivity requirement for the tag
function? The argument still works if the tag function is injective _on
the generated keys_. If the tag length is, say, 160 bits, and there are
2^60 keys, then it's reasonable to conjecture that the collision chance
is around 2^-40, which is acceptable as an attack probability. Maybe one
could even prove something about the collision chance of 160-bit tags
for 256-bit curves. But this approach obviously breaks down for short
tag lengths, and in particular for empty tags.

(I don't think there's a real reason to consider any intermediate tag
lengths between empty tags and complete tags. There's negligible impact
on hashing cost. The extreme "I need to minimize secret-key storage and
can't afford to recompute the public key on demand" argument is an
argument for an empty tag, not an argument for a short tag.)

Even worse, if tags collide, the conclusion that we're trying to prove
is simply wrong. As an extreme example, take empty tags, and consider a
very slow 2-user attack X that

   * asks the first key for a signature of the message "yes",

   * applies any ECDLP algorithm (however long this takes) to compute
     the discrete logarithm of the second key, and

   * applies the normal signing procedure to forge a signature of the
     message "yes" under the second key.

This attack X has success probability almost exactly 1: the only way it
fails is in the extremely rare case that the two keys happen to be
identical. However, the attack ReRandomize(X) has success probability
exactly 0: it outputs a signature of "yes", but that's not a forgery,
since earlier it asked for a signature of "yes".

Could ReRandomize be modified somehow to work for empty tags? The
obstacles are formidable:

   * The signature scheme hashes messages, and I can't imagine how the
     reduction could modify hash inputs, so the reduction will have to
     produce a forgery on the same message "yes" forged by X.

   * For this to be a forgery, the reduction has to retroactively avoid
     asking for a signature on "yes". How can the reduction predict that
     "yes" will be the message to be forged?

   * Even if the reduction does somehow predict this, how will it answer
     X's signing query for "yes" from the first user? The reduction
     can't simply skip that query---maybe X actually does some
     interesting computation on the signature result, influencing its
     final output.

The original paper doesn't try to address any of these obstacles. It
writes down ReRandomize(X) for the case of empty tags (minor difference:
it takes r_1=0, assuming that A is uniformly distributed), and correctly
observes that success in X implies that the output of ReRandomize(X) is
a valid signature. It then leaps to the conclusion that the output is a
"valid forgery", without checking whether the message was signed before.

---Dan

---

From: Dan Brown <[email-masked]>
Date: Thu, 17 Sep 2015 23:46:32 +0000

Seems correct! Clever catch.

I think this justifies a MUST (or SHOULD for ECDSA) for inclusion of the public key in the message of the classic signature.

Aside: does this proof work for H(A,R,M)‎ too? If not, then what does that mean?

  Original Message
From: D. J. Bernstein
Sent: Thursday, September 17, 2015 6:47 PM
To: [email-masked]
Subject: [Cfrg] key as message prefix => multi-key security

   * a key A and

---Dan

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Sep 2015 01:49:07 -0000

Dan Brown writes:
> Aside: does this proof work for H(A,R,M) too?

As doctors say: First, do no HARM. :-)

In all seriousness: The proof applies, but relative to a new hash
function H' that's just like H but swaps the first and second chunks of
input. Nobody would expect this to matter for Schnorr in the typical
case that the block size of H is big enough for both chunks.

---Dan

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 18 Sep 2015 08:48:00 +0000

Dan,

Thanks, this is a very valuable contribution and provides a strong
argument in favour of including the public key in the hash, as in the
EdDSA proposal (while the other proposals can be adapted to add this
feature).

If anyone wishes to change their existing vote in the on-going poll in the
light of this new information, please feel free to do so (I maybe have
missed some messages, but I believe that there's only one "+1" at the
moment for any proposal other than EdDSA).

Cheers,

Kenny

---

From: Sven Schäge <[email-masked]>
Date: Fri, 18 Sep 2015 14:31:25 +0200

The proof seems good. I am all for the additional hashing of the full
public key.

Some comments:

1) The reduction ReRandomize seems to preserve even strong security, i.e.
the message that the adversary produces as part of the forgery can even be
among those queried to the oracle before - as long as the corresponding
signature is new.

2) The security notion is more realistic than to consider a single public
key. However, it lacks the even more realistic modelling of an attacker
that may also corrupt public keys: formally one would consider an
additional corruption oracle that given a public key outputs the
corresponding secret key. The above reduction could not simulate such an
oracle as all secret keys are unknown to the simulator. One can show that,
for classical DH secret/public key pairs if the attacker is able to make t
queries to such a corruption oracle, the security loss degrades with t.

- Sven

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 18 Sep 2015 13:55:41 +0000

+1 for EdDSA.

P.S. Other proposals should be changed to include pub key in the hash.
-- 
Regards,
Uri Blumenthal

---

From: William Whyte <[email-masked]>
Date: Sun, 20 Sep 2015 23:31:48 -0400

Hi Dan -- this is a nice result. If I understand right, the property it
depends on is that the tag uniquely determines the key? So it seems this
proof would also hold in the case where the tag was all the information
necessary to derive the public key from an implicit certificate?

As I've said before, I'd like it if the signature scheme had the
flexibility to support implicit certificates without requiring a receiver
to first derive the public key, then verify. This result seems to indicate
that such a construction is possible while having multi-key security.

However, in the case of implicit certs, the tag has to be both the implicit
certificate itself and the CA public key, as the derived end-entity public
key isn't unique without the CA public key; and the CA public key may in
turn be derived from its own implicit cert and is only uniquely defined
given the public key for its own CA. So defining the tag contents and
encoding correctly for the implicit cert setting seems like it'll take some
time and should probably be done as a separate project from the
standardization of a baseline signature algorithm.

Cheers,

William

---

From: Bill Cox <[email-masked]>
Date: Tue, 22 Sep 2015 16:14:30 -0700

Please excuse my arm-chair cryptanalysis below.  My experience so far tells
me my conclusions are generally either a) wrong, b) already well known, or
c) both, which is most often the case.  Often this is because I read to
much on Wikipedia :)

The proof convinces me that using H(R, tag(A), M), we get single-key
security for the multi-key situation when tag(A) is injective, which is the
new theorem.  Very cool!  The analysis following the proof states:

> since earlier it asked for a signature of "yes".

The oracle has seen "yes" as the message before from ReRandomize, which
uses A to sign everything, which is why the attack fails.  However, this
oracle chooses a random R, independent of M and A.  If we're not talking
Ed25519, but some random signature scheme which requires R to be random for
each signature, and signs H(R, M), can't we say that so long as R is
securely randomly generated, that they are secure in the multi-key
situation?  In the multi-key secure case, the oracle signs H(R || A || M),
while in the regular case, it signs H(R || M).  Also assuming H is
collision resistant and R is truly random and long enough, each of these
values is effectively a random number.  Signing one or the other wont
change any security properties, will it?  Of course, relying on R to be
truly random is a poor choice for security, so adding in A seems like a
good idea, especially if other schemes are likely to copy this precident.

In Ed25519, I read conflicting descriptions of how R is derived.  Wikipedia
says it is generated from M and A, while some random web site says it's
derived from some one-time generated random nonce z and M, but not A.  I
don't know which is correct, but  I guess it makes more sense to put A in
H(R, A, M) than into R.  Obviously, I would prefer not to do both at the
same time.

So, the above proof is awesome, but I think we can also say some schemes
which don't hash in A but do hash in a true random number are also
multi-key secure, assuming a good random number source and hash function.
Is this right?  I prefer the Ed25519 scheme in any case to those that
require true randomness for every signature.

Thanks,
Bill

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 27 Sep 2015 11:37:51 -0700

> inserting the key into the hash is the conservative thing to do.
...

The above is a quote from 
http://www.ietf.org/mail-archive/web/cfrg/current/msg07335.html [1]

Because CFRG requires a deterministic signature method, "classic" scheme 
in [1] doesn't look like a good model for any current signature proposal.

I refer to an assumption of a uniform random R, independent of 
everything else in H(R,M), in the "classic" scheme in [1].

Let's use EdDSA as an example.

Denote:
   M1 = H(M) -- for IUF

Then:
   r = H(H(k),M1)
   R = rB

Therefore:
   H(R,M1) = H(H(H(k),M1)B,M1) = H(H(H(ECDLP(A)),M1)B,M1)

Classic scheme [1] wouldn't even directly apply to EdDSA, because 
H(R,M1) *is* bound to a signer's private key. ( EdDSA uses H(R,A,M1) 
instead. )

(A few H above should be viewed as yet different H, but this doesn't 
change my comment.)

---

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Sep 2015 22:56:22 -0000

Andrey Jivsov writes:
> Because CFRG requires a deterministic signature method, "classic"
> scheme in [1] doesn't look like a good model for any current signature
> proposal.

The whole point of this type of security analysis is to understand the
potential gaps in difficulty between _different_ problems facing the
attacker: e.g., between the problem of breaking signature system X and
the problem of breaking signature system Y.

The gold standard in this area is proving that a new problem is at least
as hard to solve as a classic problem. This doesn't say that the two
problems are good models of each other: maybe the new problem is even
_harder_ to break! But that's not relevant to the logic. Here's the
standard argument: the classic problem has survived scrutiny; this means
(hopefully) that the classic problem is hard to solve; this in turn
implies that the new problem is hard to solve. (Of course, all of this
breaks down if the classic problem is actually easy to solve---maybe
everybody missed an important attack strategy against that problem.)

Consider, for example, the following chain of problems:

   * Problem 1: Forge signatures from a single signer in the classic
     Schnorr signature scheme.

     This has been around long enough, and studied long enough, that one
     can reasonably hope that it's hard to break. However, even if we
     _assume_ that it's hard to break, we still need to figure out what
     this means for other problems facing the attacker.

   * Problem 2: Forge signatures from any 1 of N signers in a modified
     signature scheme that uses the public key as a prefix of a message.

     It's conceivable that Problem 2 is _harder_ to solve than Problem
     1. Maybe an attack against Problem 1 requires particular message
     prefixes that can't be adjusted to match the public key. (One can
     manufacture artifically dumb hash functions that allow attacks
     against Problem 1 without obviously breaking Problem 2; on the
     other hand, this doesn't say anything about real hash functions.)

     Earlier I was explaining in detail a proof that Problem 2 can't be
     _easier_ to solve than Problem 1: any attack against Problem 2 can
     be converted into an attack against Problem 1 with the same success
     probability and practically identical speed.
     
   * Problem 3: Same as Problem 2, except with "signature caching" by
     all of the legitimate signers. This means that, once a message has
     been signed, the signer will always return that signature for that
     message, rather than generating new signatures for that message.

     It's conceivable that Problem 3 is _harder_ to solve than Problem
     2. Maybe having multiple signatures on the same message leaks
     information somehow, and signature caching stops this (as in, e.g.,
     http://cr.yp.to/papers.html#rwtight).

     Problem 3 can't be _easier_ to solve than Problem 2. Any attack
     against Problem 3 can be converted (by caching!) into an attack
     against Problem 2 with the same success probability and practically
     identical speed.

   * Problem 4: Same as Problem 3, except that now the legitimate
     signers deterministically generate each one-time scalar as a keyed
     hash of the message to be signed, where the key is a long-term
     signer secret, independent of everything else.

     If the keyed hash is indistinguishable from uniform---this is a
     standard "PRF" assumption---then Problem 4 is indistinguishable
     from Problem 3, and thus can't be easier or harder to solve than
     Problem 3.

The main conclusion is that _if_ classic Schnorr for a single signer is
hard to break, _and_ the PRF assumption holds, _then_ the deterministic
key-prefixed system for N signers is hard to break. This provides the
following guidance to someone looking for attacks against the
deterministic key-prefixed system:

   * find a single-key attack against classic Schnorr, or
   * find an attack against the PRF assumption, or
   * find an error in the logic, or
   * find an attack outside the attack model.

The bigger picture is that this is still only part of a comprehensive
security analysis. Earlier I mentioned several complications in the
"provable security" picture; derandomization was only one of the items,
certainly not the most difficult item.

---Dan