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

From: Alexey Melnikov <[email-masked]>
Date: Sun, 03 May 2015 12:14:53 +0100

CFRG chairs are starting discussion of the next topic.

The consensus view of the mailing list was that NIST compliance of our 
selected
signature scheme is not necessary, opening up the opportunity for us to
consider a rich class of signature schemes beyond ECDSA.

Most if not all signature schemes defined over elliptic curves can be
de-randomised by generating the "random" value used during signing in a
pseudorandom manner from the message to be signed. This ameliorates some
catastrophic failure modes for these schemes. The generation could involve
using a PRF such as HMAC with a key designed solely for this purpose
(resulting in an augmented private (signing) key). An alternative could be
to hash a string consisting of a concatenation of the private (signing)
key with the message to be signed. There are other possibilities too.
Several methods are described in detail in RFC 6979
(http://tools.ietf.org/html/rfc6979).

To determine the way forward, we are going to conduct a poll to determine
how we should tackle the question of de-randomisation. Please pick one 
of the
options specified below:

1. CFRG should stick to randomised signature schemes only.

2. CFRG should adopt deterministic signature scheme only.

3. De-randomisation should be an optional feature for implementers to
decide upon (i.e. both choices 1 and 2 allowed).

Please address only this specific topic of de-randomisation at this time.
Further topics will follow.

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 03 May 2015 13:19:33 +0100

> 2. CFRG should adopt deterministic signature scheme only.

That one please. My reasons are that the catastrophic failures
have happened and must be avoided and I don't like having
unnecessary choices.

If there were evidence of some weakness resulting from 2 then
I would be willing to think again about 3 but I've not seen
that. (Nor have I looked though;-) I would be very much against
option 3 if there is no specific and convincing benefit that
accrues from allowing that choice.

Cheers,
S.

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 3 May 2015 12:28:17 +0000

> That one please. My reasons are that the catastrophic failures have
> happened and must be avoided and I don't like having unnecessary choices.

What Stephen said. Further, we're not going to go back and make existing formats and their uses illegal, so if you want DSA you know where to find it.

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 3 May 2015 07:39:46 -0700

> decide upon (i.e. both choices 1 and 2 allowed).

#2. Others have done #1 sufficiently. If someone wants to later do #3 on what comes out of #2, they can do that work on their own and CFRG can review it.

--Paul Hoffman

---

From: Andy Lutomirski <[email-masked]>
Date: Sun, 3 May 2015 08:13:41 -0700

selected
> how we should tackle the question of de-randomisation. Please pick one of
the
> decide upon (i.e. both choices 1 and 2 allowed).

You left out 4: schemes that are secure without random input but that
nonetheless accept random input.  These could work like derandomized
schemes but with an extra input to the hash.

My preference order would be 2, 4, 3, 1.  Some people want random
signatures for what I consider to be strange reasons.  4 should satisfy
them, and test vectors could verify that they aren't omitting the hash.

--Andy

---

From: David Jacobson <[email-masked]>
Date: Sun, 03 May 2015 09:24:18 -0700

On 5/3/15 4:14 AM, Alexey Melnikov wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

If everyone did encrypt then sign (the recommended procedure), or sign 
then encrypt, identical plaintext would still be different in what was 
sent (assuming an nonce-like IV is supplied to the encryption).  If 
someone was foolish enough to do encrypt and sign, then there would be a 
need to make identical plaintext not have identical signatures.  If 
anyone feels that we need to accommodate this, then it would be good to 
allow an optional random input  (#4 as suggested by Andy Lutomirski in 
his response).

A counter argument is that if you want to do something like that, you 
should just have your application include an application-level nonce in 
the plaintext, and not burden the signature standard with making 
identical plaintext have different signatures.

So, amongst those listed I choose #2, but perhaps Andy's #4 should be 
considered.

   --David Jacobson

---

From: Watson Ladd <[email-masked]>
Date: Sun, 3 May 2015 09:47:40 -0700

On Sun, May 3, 2015 at 9:24 AM, David Jacobson <[email-masked]> wrote:
> If everyone did encrypt then sign (the recommended procedure), or sign then
> encrypt, identical plaintext would still be different in what was sent
> (assuming an nonce-like IV is supplied to the encryption).  If someone was
> foolish enough to do encrypt and sign, then there would be a need to make
> identical plaintext not have identical signatures.  If anyone feels that we
> need to accommodate this, then it would be good to allow an optional random
> input  (#4 as suggested by Andy Lutomirski in his response).

Is encrypt then sign really what is recommended? Remember that
public-key encryption is CCA2 secure, and that signatures are about
non-repudiability, not simply authentication The correct picture is
much more complicated: see
http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.html for a
partial analysis. The correct constructions depend on the exact
security requirements.

Unlinkability of different signatures for the same messages is not
part of the standard security definition for signatures. It's not
enough to demand randomization: RSA signatures are trivially linkable,
even when randomized, and so are ECDSA signatures. The property you
claim is important isn't provided by today's signatures: either its
not important, or all sorts of things are broken.

Sincerely,
Watson Ladd

>
> A counter argument is that if you want to do something like that, you should
> just have your application include an application-level nonce in the
> plaintext, and not burden the signature standard with making identical
> plaintext have different signatures.
>

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

---

From: Tony Arcieri <[email-masked]>
Date: Sun, 3 May 2015 10:07:13 -0700

>  2. CFRG should adopt deterministic signature scheme only.

#2. Entropy failures with randomized schemes have lead to many problems in
practice.

-- 
Tony Arcieri

---

From: Alyssa Rowan <[email-masked]>
Date: Sun, 03 May 2015 18:27:32 +0100

> 2. CFRG should adopt deterministic signature scheme only.

#2, deterministic required.

It's the obvious, dramatically better right answer:

• We don't need a secure CSPRNG to sign things, only to generate keys.
• We have test vectors for signatures.

- -- 
/akr

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 3 May 2015 10:39:06 -0700

3.  Implementations SHOULD use whatever specific deterministic construction CFRG decides on.  But using a randomized construction for technical reasons (side channel protection, threshold signatures, low-latency coupons or whatever) should not be forbidden by the spec, especially since the other party can’t tell how you signed it.

PS Sorry Alexey, I accidentally replied only to you before.

> On May 3, 2015, at 4:14 AM, Alexey Melnikov <[email-masked]> wrote:
> 
> The consensus view of the mailing list was that NIST compliance of our selected
> (http://tools.ietf.org/html/rfc6979 <http://tools.ietf.org/html/rfc6979>).
> 
> how we should tackle the question of de-randomisation. Please pick one of the
> options specified below:
>

---

From: Yoav Nir <[email-masked]>
Date: Sun, 3 May 2015 20:54:27 +0300

> On May 3, 2015, at 2:14 PM, Alexey Melnikov <[email-masked]> wrote:
> 

#2.

Random number generation is one of the weak spots of a lot of cryptographic libraries. Either they get the PRNG/DRBG wrong, or even when they get it right, they rely on a problematic source for seeding. 

Things might work fine on regular servers, then lose their entropy when running in a virtualized environment. Very often the entropy comes from a source that is outside the control of the cryptographic library and may or may not be reliable depending on the running environment. 

Deterministic works for everybody. Randomized works not for everybody. Better go with #2.

Of course de-randomizing doesn’t buy you much if you use the signature as part of a protocol such as TLS that requires random bytes, but removing one thing that relies on the RNG is better than not doing it.

Yoav

---

From: James Cloos <[email-masked]>
Date: Sun, 03 May 2015 14:18:52 -0400

AM> 2. CFRG should adopt deterministic signature scheme only.

Andy's #4 is interesting, as is David's reply.

But even if something like that comes later, cfrg should work on a
deterministic signature scheme.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: David Jacobson <[email-masked]>
Date: Sun, 03 May 2015 14:00:30 -0700

On 5/3/15 9:50 AM, Mihir Bellare wrote:
>
>      If someone was foolish enough to do encrypt and sign, then there
>     would be a need to make identical plaintext not have identical
>     signatures.  If anyone feels that we need to accommodate this,
>     then it would be good to allow an optional random
>
>
> The usual goal is that one wants IND-CPA privacy. The attack one is 
> trying to prevent here is loss of IND-CPA due to the ability to detect 
> repeats, meaning an adversary knowing messages M1,M2 and their 
> ciphertexts C2,C2 can test whether or not M1=M2. Signature 
> randomization does not help prevent this, because signatures are 
> verifiable given the public key and this can be used to detect repeats 
> even with randomization. So this would not appear to be a good reason 
> to keep randomization in the signature.
>
> Mihir
>
>
>
>

Mihir is right.

In addition, I have a suspicion based on information theory that if a 
signature allows randomization, the size of size of the signature will 
need to be larger.  Here is an intuitive argument.  Suppose that the 
size of the signature is 256 bits.  Somehow the message and the private 
key map somewhat uniformly onto those 256 bits.  For any given message 
and key, only one signature value is correct.  Now, I we add 256 bits of 
randomness, and them mix in in the obvious way. Now for a fraction of 
about (1-1/e) of the signature space, there is a value of the input 
randomness that could have generated it.  That means that the verifier 
can't reject most signature values.  To avoid this, we have to have a 
larger signature, so valid values (for a given message and key) are 
sparse.  Consider that ECDSA with P-256 has 512 bit signatures.

For this reason, I think allowing optional randomness as in proposal #4 
is not just not helpful, but forces larger signatures.  For many uses, 
small signature are desirable.  So I retract my original support for 
#4.  Now I'm only supporting #2.

   --David Jacobson

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 3 May 2015 15:09:51 -0700

> On May 3, 2015, at 2:00 PM, David Jacobson <[email-masked]> wrote:
> 
>>  If someone was foolish enough to do encrypt and sign, then there would be a need to make identical plaintext not have identical signatures.  If anyone feels that we need to accommodate this, then it would be good to allow an optional random
>> 
>> The usual goal is that one wants IND-CPA privacy. The attack one is trying to prevent here is loss of IND-CPA due to the ability to detect repeats, meaning an adversary knowing messages M1,M2 and their ciphertexts C2,C2 can test whether or not M1=M2. Signature randomization does not help prevent this, because signatures are verifiable given the public key and this can be used to detect repeats even with randomization. So this would not appear to be a good reason to keep randomization in the signature. 
>> 
>> Mihir
>> 
>> 
>> 
>> 
> 
> Mihir is right.  
> 
> In addition, I have a suspicion based on information theory that if a signature allows randomization, the size of size of the signature will need to be larger.  Here is an intuitive argument.  Suppose that the size of the signature is 256 bits.  Somehow the message and the private key map somewhat uniformly onto those 256 bits.  For any given message and key, only one signature value is correct.  Now, I we add 256 bits of randomness, and them mix in in the obvious way.  Now for a fraction of about (1-1/e) of the signature space, there is a value of the input randomness that could have generated it.  That means that the verifier can't reject most signature values.  To avoid this, we have to have a larger signature, so valid values (for a given message and key) are sparse.  Consider that ECDSA with P-256 has 512 bit signatures.
> 
> For this reason, I think allowing optional randomness as in proposal #4 is not just not helpful, but forces larger signatures.  For many uses, small signature are desirable.  So I retract my original support for #4.  Now I'm only supporting #2.
> 
>   --David Jacobson

Do you actually have a 2*WF ECC signature scheme in mind?  The only ones I know of use pairings, and the 3*WF and 4*WF ones I know of are all randomized (but can and should be derandomized).

— Mike Hamburg

---

From: Nico Williams <[email-masked]>
Date: Sun, 3 May 2015 17:18:06 -0500

> accrues from allowing that choice.

+1

---

From: Damien Miller <[email-masked]>
Date: Mon, 4 May 2015 17:03:49 +1000 (AEST)

> 1. CFRG should stick to randomised signature schemes only.

no

> 2. CFRG should adopt deterministic signature scheme only.

Yes. Dependencies on runtime randomness cause catastrophic security
failures when said randomness isn't. Deterministic schemes are much
easier to test too - one doesn't need to add extra parameters to
sign/verify functions (making the API more complex and easy to get
wrong) or "deterministic PRNG" hooks (which are like leaving the poison
next to the toothpaste) to support test vectors.

> decide upon (i.e. both choices 1 and 2 allowed).

No

-d

---

From: David Jacobson <[email-masked]>
Date: Mon, 04 May 2015 07:15:08 -0700

On 5/3/15 3:09 PM, Michael Hamburg wrote:
>
>> On May 3, 2015, at 2:00 PM, David Jacobson <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>>>      If someone was foolish enough to do encrypt and sign, then
>>>     there would be a need to make identical plaintext not have
>>>     identical signatures.  If anyone feels that we need to
>>>     accommodate this, then it would be good to allow an optional random
>>>
>>>
>>> trying to prevent here is loss of IND-CPA due to the ability to 
>>> detect repeats, meaning an adversary knowing messages M1,M2 and 
>>> their ciphertexts C2,C2 can test whether or not M1=M2. Signature 
>>> verifiable given the public key and this can be used to detect 
>>> repeats even with randomization. So this would not appear to be a 
>>> good reason to keep randomization in the signature.
>>>
>>> Mihir
>>>
>>>
>>>
>>>
>>
>> Mihir is right.
>>
>> signature allows randomization, the size of size of the signature 
>> will need to be larger.  Here is an intuitive argument.  Suppose that 
>> the size of the signature is 256 bits.  Somehow the message and the 
>> private key map somewhat uniformly onto those 256 bits. For any given 
>> message and key, only one signature value is correct.  Now, I we add 
>> 256 bits of randomness, and them mix in in the obvious way.  Now for 
>> a fraction of about (1-1/e) of the signature space, there is a value 
>> of the input randomness that could have generated it.  That means 
>> that the verifier can't reject most signature values.  To avoid this, 
>> we have to have a larger signature, so valid values (for a given 
>> message and key) are sparse.  Consider that ECDSA with P-256 has 512 
>> bit signatures.
>>
>> For this reason, I think allowing optional randomness as in proposal 
>> #4 is not just not helpful, but forces larger signatures.  For many 
>> uses, small signature are desirable.  So I retract my original 
>> support for #4.  Now I'm only supporting #2.
>>
>>   --David Jacobson
>
> Do you actually have a 2*WF ECC signature scheme in mind?  The only 
> ones I know of use pairings, and the 3*WF and 4*WF ones I know of are 
> all randomized (but can and should be derandomized).
>
> — Mike Hamburg
No, I have no scheme in mind.  This was just an intuitive argument that 
allowing an entropy input requires that the minimum signature size be 
larger.  After I wrote that, I got to thinking about formalizing my 
argument, probably involving an oracle that transforms messages and 
public-private keypairs to a set of possible signatures, one of which is 
selected by the supplied randomness. But I've not got anything to post.

    --David

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 4 May 2015 09:16:45 -0700

> On May 4, 2015, at 7:15 AM, David Jacobson <[email-masked]> wrote:
> 
>>> On May 3, 2015, at 2:00 PM, David Jacobson <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
> No, I have no scheme in mind.  This was just an intuitive argument that allowing an entropy input requires that the minimum signature size be larger.  After I wrote that, I got to thinking about formalizing my argument, probably involving an oracle that transforms messages and public-private keypairs to a set of possible signatures, one of which is selected by the supplied randomness.  But I've not got anything to post.
> 
>    —David

I agree that a randomized signatures have to be bigger than WF bits, and the same is not obviously true for deterministic ones.  But ECC signatures are usually based on zero-knowledge proofs, which are intrinsically randomized but can be derandomized.  In some sense, they’re already derandomized once to make  NIZK: the step c = hash(g^k,message) in Schnorr sigs is in place of a random challenge, which is why the hash is usually modeled as a random oracle.

I also agree that CFRG should specify a derandomized signature algorithm.  But since it does not harm interoperability (or security if done right), we should not absolutely require the nonce to be computed in the way we specify.  We should allow a different PRF to be substituted, because for example HMAC-SHA2 is a nightmare to blind against DPA.  We should allow the use of random nonces: if not in TLS, then in low-latency environments like v2v where pregenerated signature coupons could be a big win.

— Mike

---

From: Adam Langley <[email-masked]>
Date: Mon, 4 May 2015 09:28:49 -0700

> decide upon (i.e. both choices 1 and 2 allowed).

I would favour a deterministic signature scheme for robustness
reasons. I'm sure that, should certain applications wish to have
precomputed signatures, then an RFC won't stop them, but it will guide
most people towards the solution that is generally the best choice.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 04 May 2015 13:37:01 -0400

> decide upon (i.e. both choices 1 and 2 allowed).

I prefer 2, for reasons of robustness and simplicity.  I don't expect
this to rule out CFRG review of a non-deterministic signature scheme in
the future, should one come up, but for the present process, we should
stick to deterministic signature schemes.  Let's give implementers fewer
ways to trip up.

   --dkg

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 4 May 2015 21:08:04 +0300

On Mon, May 04, 2015 at 09:16:45AM -0700, Michael Hamburg wrote:
> 
> I also agree that CFRG should specify a derandomized signature algorithm.
> But since it does not harm interoperability (or security if done right),
> we should not absolutely require the nonce to be computed in the way we
> specify.  We should allow a different PRF to be substituted, because for
> example HMAC-SHA2 is a nightmare to blind against DPA.  We should allow
> the use of random nonces: if not in TLS, then in low-latency
> environments like v2v where pregenerated signature coupons could be
> a big win.

Regarding coupon generation: Derandomization can be used to turn
the "nonce" with extreme randomness requirements into true nonce.
It may still be random, but needs only be random enough to be
unique, not to be quasi-perfectly random.

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Mon, 4 May 2015 19:28:41 +0000

> -----Original Message-----
> From: Alexey Melnikov
> 

I prefer #3, but with more specific nuance:

CFRG should recommend that signers make signature ephemerals depend on
the message being signed.

Abstractly: signer has some secret s and computes ephemeral as k =
F(s,m) for some secure function F (able to avoid any bias), whose 
details are to be determined.

The secret s SHOULD be new, but MAY be old.  It MUST be secret, and
MUST be guarded to the same degree as the static signing key.  It
SHOULD be erased after use (i.e., instead of guarded for eternity).

Only ever deviate from this if ephemeral public (kG) needs to
pre-computed for low-latency signing.  (Is this what some call a
coupon?)  In this case, the message value SHOULD be replaced by a
nonce (e.g. date). 

Reasons (and some counter-reasons in #5)
=======================================

The reasons are many, so I've added headings.

1. Actual cause of catastrophic failures
----------------------------------------

The main relevant catastrophic failure I've heard of is due to re-use
of signature ephemerals across different messages.  I don't know the
details of why these happened (even what specifications the
implementers were using), but plausible explanations of why this
failure happened is:

1a. Unclear specifications and a general lack of education.

1b. Implementers trying to save a scalar multiplication.

Perhaps others know another third reason 1c.  

Note well: point 1a is somewhat self-critical in that I've
edited/commented on a few ECDSA standards, as well as written papers
on ECDSA.

Reason 1a can be fixed by clarifying standards and publicizing
potential pitfalls.  If the implementers in question had been properly
informed, they would have adhered to the specifications by using
proper randomization, thereby avoiding this catastrophic failure.

Altering technique does not address reason 1a: if the new technique is
poorly enough explained, an implementer may sidestep it too.  In other
words, no crypto can be foolproof.  See topic #3 below.

Reason 1b is not fixed by making the ephemeral key a deterministic
function of the message: the implementer still has an incentive to
re-use the ephemeral.

2. Hindsight patching
---------------------

De-randomization is a hindsight patch, even assuming we've determined
a correct cause.  Although it looks like a clear fix, we should also
take care and apply foresight to fix similar problems.  I try to do so
in the next section.

3. De-randomization is an overcorrection
----------------------------------------

De-randomization might introduce new pitfalls for an implementer to
trip into:

3a.... More side channels?

Suppose attacker asks a target to repeatedly re-use an ephemeral by
repeatedly asking for signature on the same message.  If the signer
does not cache the scalar multiplication result, and the attacks has
some kind of side channel acces, does the repeated exposure ampifly
the risk, as in a differential side channel attack?

3b... Re-use keys more often, why not always?

A naive implementer updating an existing secure signature
implementation from randomized to de-randomization might observe that
the de-randomized version re-uses ephemeral keys more often.  They
might reason that the CFRG says this is an improvement, then maybe
even more re-use is better.  Why not re-use all keys.

Sure, we will try to explain not to such a thing!  But we could also
add an equivalent explanation for randomized signatures.  In other
words, it's not the technical differences that's more foolproof, but
rather the level of instruction.

3c....  De-randomized signing key?

If the CFRG recommendation is unclear to the implementers under
consideration, the implementer may reason as follows: if randomization
is bad for signatures, maybe I should make the long-term signing key
deterministic too.  Randomization is bad for signatures, right?
Again, a well-intentioned, but misinformed, implementer may swing the
pendulum too far in the other direction.

3d.... Increased failure to erase ephemerals?

Given a deteministic signature specification, an implementer might
reason that the ephemerals are derived from the long-term secret using
a one-way function, and therefore (!) that is no (or less) need to
erase them, or keep them within some security boundary.

3e.... Replay attacks on encryption?

We want to minimize re-use ephemeral keys (and nonces) for producing
ciphertexts.  De-randomization of signatures (for equal messages)
seems to suggest that re-use of ephemerals improves security.  If the
implementers carry this logic from signatures to key exchange or
encryption, then they might compromise semantic security because
repeated plaintexts could be rendered detectable as repeated
ciphertexts.

3f.... Loss of forward secrecy?

In ECDH, we want to maintain forward secrecy by not deriving from
ephemerals from the static secrets.  If an implementer carries over
the ephemeral generation from a deterministic signing implementation,
then forward secrecy will be undermined.

3g.... Decreased Schnorr message-hiding ability?

Some protocols may rely on non-advertised properties of signatures.

For example, consider the following definition of a message-hiding
property of signatures: the only way that a signature and a public key
can be used to learn anything about a message signed is to test the
message under the verification algorithm.

ECDSA lacks this message-hiding property: given a sequence of
signatures under a public key, one can detect repeated messages, even
if the repeated message are secret and unguessable, and therefore
impossible to verify.

Randomized Schnorr signatures seem to have better message-hiding
capability: unless I am missing something. But de-randomized Schnorr
signatures lose this non-standard property of signatures.

This issue is similar to how we now expect collision-resistant hash
functions to be like random oracles, which far exceeds their original
purpose.

3h.... Provable security: more assumptions to prove unforgeability

What is the effect of de-randomization on the security proofs of
unforgeability? 

For example, the recent work of Koblitz and Menezes

http://eprint.iacr.org/2015/140

in Section 7.2, touches upon this issue.  In particular, they treat
the case of ECDSA, and describe two de-randomized variants ECDSA* and
ECDSA**, which differ in that ECDSA** does not use the static signing
key to derive the ephemeral, but rather a separate indpendent
alternative key.

Curiously, they argue ECDSA** is at least as good as ECDSA, but they
find an obstacle to making a similar argument for ECDSA*.

My worry with their ECDSA**, however, is that not quite foolproof: an
implementer who is likely to reuse an ephemeral may be just as likely
to choose the alternative key poorly.

Coron has some results about the limitations of provably security in
"unique" signatures.  I need to review to the details to see whether
making DL signature schemes deterministic renders them "unique", or it
Coron's result, or later generalizations, already extend to most
DL-based signature schemes.   

For what little it's worth, I can think of many silly but very weak
ways to deteministically derive ephemerals, which merely shows that
the some basic assumptions must be made for the mechanism.  Do the
current proposals even have proofs?

Intuitively, we know from lattice attacks on the signatures that
rather slighly biases in epehemerals are risky.  Furthermore, even
correlations between ephemerals are risky.  So, we need to be sure
that a determinstically-derived ephemerals does not grant the
adversary a means to induce this bias by choice of message.  If you
review the Kobtliz--Menezes proof for ECDSA**, then prove this using a
PRF.

In my limited understanding, this requires deterministic signature to
rely on a stronger assumption: a PRF.  By contrast, traditionally
signatures only needed a very mild form of PRG, which seems like less
harsh threat model than PRF because it does not permit the adversary
to query any message.

What about collisions?  If the attacker can cause the a collision in
the deterministic algorithm for generating ephemerals, then the game
is over for the signer.  Of this function has a key, so it is harder
to find collisions than in SHA1.  But if one goes to the trouble of
avoiding dependence on collision-resistant hash functions like SHA1,
then one may want some kind of argument that things do not rely on
collision resistance.  (This critique is subsumed by the earlier PRF
critique: an adversary who can find a collision in a PRF wins, so it
can be viewed as a more concrete example of the PRF issue.)

Of course, we may well already need PRFs for privacy, but I wouldn't
want to some fault in a PRF, e.g. AES, carry over into authentication.

4. What about verification?
---------------------------

Signers may ignore the CFRG recommendation, but such ignorance can be
detected (and tested for) if the signer generates distinct signatures
on the same message.

If a verifier sees two different signatures of the same method, then
the verifier can deduce CFRG non-compliance.  Should the verifier go a
step further and reject the signatures, on the grounds of
non-compliance?

The only wrinkle here is that the issue of secure key generation is
not very visible to other parties: it is a non-interop issue; it is
purely a security issue.

5. Maybe deterministic signatures help in other ways
----------------------------------------------------

In addition to the heavily advertised property of reducing the risk of
the implementaiton fault of an ephemeral re-used across different
messages, deterministic signatures may help in other ways, as listed
below.

Note well, these arguments favor of deterministic signatures, but I do
not feel they outweigh the arguments against.

5a.... Information-theoretically each signature, being derived from
the private key, potentially leaks some information about the
long-term static key.  In deterministic signatures, the amount of
leakage is potentially reduced, because no new information is
available to the attacker.

5b.... As I now recall, some of the provable security arguments
[Advances in ECC, Chapter 2] that I found for the security of ECDSA
did require a presumption that the signature was a deterministic
function of the message.

---

From: "Parkinson, Sean" <[email-masked]>
Date: Mon, 4 May 2015 18:51:10 -0400

+1

Sean :-)
--
Sean Parkinson | Consultant Software Engineer | RSA, The Security Division of EMC
Office +61 7 3032 5232 | Fax +61 7 3032 5299
www.rsa.com

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Adam Langley
Sent: Tuesday, 5 May 2015 2:29 AM
To: Alexey Melnikov
Cc: [email-masked]
Subject: Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

> decide upon (i.e. both choices 1 and 2 allowed).

I would favour a deterministic signature scheme for robustness reasons. I'm sure that, should certain applications wish to have precomputed signatures, then an RFC won't stop them, but it will guide most people towards the solution that is generally the best choice.

Cheers

AGL

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 05 May 2015 16:22:13 +0200

> 1. CFRG should stick to randomised signature schemes only.

No.

> 2. CFRG should adopt deterministic signature scheme only.

At this time, yes.

There are situations where you need non-determinism in a public-key
signature scheme to achieve certain properties.

I believe it will eventually be useful for the CFRG to recommend a
non-deterministic signature scheme that is better than RSA/DSA/ECDSA.

As Andy said, you can have a scheme that is secure in a deterministic
setting but still accept ranndomness to achieve a non-deterministic
signature, for wider applicability.

However the majority of applications under consideration today (e.g.,
PKIX, TLS, S/MIME, OpenPGP) would directly benefit from having a good
and easy to implement deterministic signature scheme, like EdDSA.

So I believe this should be the focus for the current agenda.

> decide upon (i.e. both choices 1 and 2 allowed).

No.

/Simon

---

From: "D. J. Bernstein" <[email-masked]>
Date: 5 May 2015 15:22:58 -0000

Dan Brown writes:
> a correct cause.

Let's go back to the videotape.

1991: NIST proposes DSA. Later, after a CPSR lawsuit, NIST admits NSA
authorship of DSA: https://epic.org/crypto/dss/new_nist_nsa_revelations.html

1992: Rivest criticizes several aspects of DSA, including DSA's use of
randomness generation during signing: "Signing with DSS requires the
generation and use of random numbers (the k values). ... The poor user
is given enough rope with which to hang himself---something a standard
should not do." https://people.csail.mit.edu/rivest/pubs/RHAL92.pdf

1994: NIST standardizes DSA.

1997: Barwood echoes the randomness criticism and, as a solution,
proposes deterministic generation of k: "The normal (i.e. IEEE P1363)
way of implementing digital signatures using an elliptic curve seems to
call (at least implicitly) for the generation of true random integers.
Generating true random integers is difficult to do in a safe portable
way, so I propose a method that does not require any true random input.
... What I suggest is that a prng is used to generate k, keyed with d
(the private key), and seeded with e (the message digest)."
https://groups.google.com/forum/#!original/sci.crypt/SalLSLBBTe4/xtYNGDe6irIJ

1997: Wigley independently proposes the same solution in more
generality: "I was thinking last night about an implementation of
digital signatures - re: the requirement for a truly random number in
DSA / NR / most other algo's. Why not derive the random number from the
message to be signed therefore removing the need for a hardware rng
(smartcards) or a complex and potentially fallible software attempt."
https://groups.google.com/forum/#!original/sci.crypt/3g8DnnEkv5A/iZqTyLxF2qYJ

1997: Naccache, M'Raihi, and Levy-dit-Vehel independently file a patent
application on the same idea. (They abandon the application in 2003.)

1998: M'Raihi, Naccache, Pointcheval, and Vaudenay manage to stretch the
idea into an entire SAC paper: "In this paper, we present a simple
method for generating random-based signatures when random number
generators are either unavailable or of suspected quality (malicious or
accidental). ... Suffice it to say that one should replace each
session's random number by a digest of the keys (secret and public) and
the signed message."
https://www.di.ens.fr/users/pointche/Documents/Papers/1998_sac.pdf

2010: Bushing, Marcan, Segher, and Sven ("failOverflow") announce that
they have recovered the Sony PlayStation 3 signing key, thanks to Sony's
reuse of a single k for many signatures.
https://www.youtube.com/watch?v=PR9tFXz4Quc

Of course, the 1997 proposals from Barwood, Wigley, Naccache, M'Raihi,
Levy-dit-Vehel, Pointcheval, and Vaudenay would have stopped this 2010
attack. Can you please explain why you call this "hindsight patching"?

> The secret s SHOULD be new, but MAY be old.

With your proposal, the "poor user is given enough rope with which to
hang himself---something a standard should not do". What stops the user
from choosing a constant s, producing a predictable k and revealing the
signing key?

It's not enough to _tell_ people that k has security consequences---
something that has been said again and again since the original ElGamal
paper in 1985. What actually works is having standard _test vectors_
that eliminate the bad implementations. By agreeing on a deterministic
way to generate k, with no additional inputs, we allow every common
mistake in k generation to be caught by test vectors.

I don't mean to suggest that _every_ k-generation function is safe. On
the contrary: generating a constant k, as Sony did, is of course very
bad; generating k biased mod the group order is bad; etc. The designer
needs to specify a k-generation function that's secure _and_ that
actually ends up being tested in implementations. Failure to do this is
tantamount to allowing _every_ function that implementors come up with;
instead of having _one_ function to carefully review for security
problems, we're faced with a neverending list of implementation-specific
functions.

The same principles apply to "entropy pools". Having each library make
up its own mechanism to combine multiple entropy sources is a recipe for
disaster. What we need is a specified, security-reviewed, deterministic,
tested mechanism to combine multiple entropy sources---centralized in
the operating system (even better, the hypervisor, when there is one) to
maximize the chance that good entropy sources are actually used and to
minimize the number of lines of code to review.

Obviously the system does ultimately rely on having some good entropy
source, and testing entropy sources is a quite different problem with a
long history of failures, even in cryptographic products "certified" by
the U.S., Canadian, and German governments:

   http://smartfacts.cr.yp.to

But the fact that there's a hard problem in one corner of the crypto
ecosystem doesn't mean that we should give up on solving the problem.
Our best chance of solving this problem starts by isolating it---
eliminating it from every other part of the ecosystem.

> 3a.... More side channels?

No. Unprotected implementations of standard _randomized_ DSA are well
known to be broken by side-channel attacks. It's important to protect
all secrets---including k, which is used for scalar multiplication, and
the long-term secret, which is used for arithmetic mod the group order.
Standard defenses include blinding of each secret bit (splitting b into
r and r+b), blinding mod the group order (replacing k with k+rp), etc.;
these defenses work for deterministic signing systems too.

The bigger picture is that crypto is constantly mixing secret data with
public data. Side-channel defenses take responsibility for protecting
this. We know how to defend, e.g., computing an authenticator of a
potentially forged message---even if the same message is repeated any
number of times. This is also what we're doing in computing k.

A carefully managed internal PRNG _can_ be cheaper to protect than this
computation, but this cost improvement is quite small compared to the
overall cost of a signature unit. An implementor desperate to take this
approach will find that the resulting signatures, despite violating the
deterministic standard (and failing standard signing tests), are fully
interoperable---CFRG is not proposing that _verifiers_ track signatures
of the same message and enforce repetition constraints.

> 3f.... Loss of forward secrecy?

Here you're speculating that an implementor might draw dumb conclusions
from the k definition and, as a result, misimplement something else.

Sure, anything is possible, but intelligent risk management requires
sensibly evaluating the _likelihood_ and _impact_ of bad events. The
chance of an implementor reusing k as Sony did, or generating k that's
slightly too short, is obviously much higher than the chance of all of
the scenarios that you postulate, and the impact---forgery of arbitrary
messages under this public key---is no less disastrous than the impact
of any of your scenarios.

> given a sequence of signatures under a public key, one can detect
> repeated messages, even if the repeated message are secret and
> unguessable, and therefore impossible to verify.

Sure. Standard signature caching (e.g., DNSSEC saves signatures) also
has this effect. Many RSA signature systems are also deterministic. You
speculate that there are some protocols that need non-deterministic
signatures for some vague reason; those protocols will already have to
be quite careful in their selection of signature systems.

This is obviously far less important than the disastrous consequences of
poor k generation for typical real-world applications of signatures.

> What is the effect of de-randomization on the security proofs of

First of all, to give proper credit, this purely theoretical issue was
adequately analyzed by Olson in 1997:

   https://groups.google.com/forum/#!original/sci.crypt/3g8DnnEkv5A/TXTyOg9jgvUJ

The solution to all of the theoretical problems, as mentioned by Olson,
is to have one discrete-log key and one message-hash key. Ed25519 uses a
KDF (normally SHA-512) to derive these two separate keys from a master
signing key.

You say that "an implementer who is likely to reuse an ephemeral may be
just as likely to choose the alternative key poorly". But these objects
have totally different levels of fragility from a security perspective.
Choosing a slightly biased k is a disaster; choosing a slightly biased
message-hash key (or discrete-log key) is irrelevant. Repeating k is a
disaster; I have no idea what "poor" choice of message-hash key you
think would be analogous to this. Sure, a _guessable_ message-hash key
is as disastrous as a guessable k, but the equal problems in this
extreme case don't imply equal problems in other cases.

> want to some fault in a PRF, e.g. AES, carry over into authentication.

The modern trend is to rely on the security of ciphers, notably AES, not
just for _encrypting_ every message but also for _authenticating_ every
message. Do you think this is a problem?

The community has been subjecting ciphers to massive scrutiny for many
years. The security standard is very high: we imagine that the attackers
can freely choose all inputs and see all outputs, and that the attackers
automatically win if they can find _any_ pattern, even though this isn't
enough to break typical applications. The best possible security, within
various real-world performance constraints, is systematically analyzed.
Worrisome cipher structures are identified and avoided.

Is it still possible that an attacker will find some shocking break of
AES? Yes, it's possible. Is it conceivable that generating k's with a
modern cipher will produce k's so biased as to allow forged signatures?
Yes, it's conceivable. But is it reasonable to say that this wildly
speculative horror story has the same probability as another equally
disastrous Sony-style implementation screwup? No, it isn't.

---Dan

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 5 May 2015 22:40:31 +0300

> decide upon (i.e. both choices 1 and 2 allowed).

2. Deterministic only.

Basically, ECC signatures explode if one so much as looks at it wrong.
Thus, proper testing is really important, and that is only possible
for fully deterministic algorithms.

Some notes:
- Adding external tweak input does not break determinism.
- For "coupon" generation, derandomization can be used to provode nonce
  input instead of cryptoglycerin input.

-Ilari

---

From: Paul Lambert <[email-masked]>
Date: Tue, 5 May 2015 12:43:23 -0700

On 5/5/15, 12:40 PM, "Ilari Liusvaara" <[email-masked]> wrote:

>>of

+1

No cryptoglycerin :-)

Paul

---

From: Olafur Gudmundsson <[email-masked]>
Date: Tue, 5 May 2015 18:48:46 -0400

+1  I could not have put my arguments any better than Simon did. 
#2 is the only reasonable choice at this point. 

Olafur

> On May 5, 2015, at 10:22 AM, Simon Josefsson <[email-masked]> wrote:
>

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 06 May 2015 01:35:11 -0700

On 05/03/2015 10:39 AM, Michael Hamburg wrote:
> 3.  Implementations SHOULD use whatever specific deterministic
> construction CFRG decides on.  But using a randomized construction for
> technical reasons (side channel protection, threshold signatures,
> low-latency coupons or whatever) should not be forbidden by the spec,
> especially since the other party can’t tell how you signed it.

+1 to the above #3.

If I see it correctly, the value of #2 is viewed in the following context:

* we trust the system to correctly generate a long-term secret, and 
possibly a dedicated long-term seed

* the signature standard will specify a DRBG and how to seed it to 
generate bytes, e.g. for the r in ECDSA

* we rely on audit or a vendor assurance that the implementation indeed 
uses the standard-mandated DRBG and the seed(s) correctly; note that 
using random bytes instead of said DRBG is undetectable by verifiers

I second the problem with #2 that it's not cryptographically enforceable 
and it limits some performance optimizations. Therefore, SHOULD is fine, 
but prohibiting random bytes instead of specific DRBG is overkill. 
TLS1.2 currently requires access to plenty of random/pseudorandom bytes, 
for example.

>> On May 3, 2015, at 4:14 AM, Alexey Melnikov <[email-masked]
>> <mailto:[email-masked]>> wrote:
>>
>> [email-masked] <mailto:[email-masked]>

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 6 May 2015 12:32:04 +0300

On Wed, May 06, 2015 at 01:35:11AM -0700, Andrey Jivsov wrote:
> 
> I second the problem with #2 that it's not cryptographically enforceable and
> it limits some performance optimizations. Therefore, SHOULD is fine, but
> prohibiting random bytes instead of specific DRBG is overkill. TLS1.2
> currently requires access to plenty of random/pseudorandom bytes, for
> example.

Except there are random numbers and there are random numbers.

What happens in practice if you feed slightly bad random numbers
into...
a) TLS nonces?
b) TLS DHE private keys?
c) TLS Encrypted premaster secrets?
d) TLS RSA signatures?
e) TLS non-RSA deterministic signature tweaks?
f) TLS non-RSA signture random r's?

Answers:
a) Nothing.
b) Nothing.
c) Nothing.
d) Nothing.
e) Nothing.
f) Signature key compromised pretty quickly, all active security
   lost.

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Wed, 6 May 2015 15:39:51 +0000

Professor Bernstein, 

Thank you for the informative comments of this tricky topic: persuasive per usual. 

Accordingly, I now amend my proposal to 
k = F(m,a,t) 
where 
F is some to-be-specified cryptographically strong deterministic function,
m is the message, 
a is the actual long-term (signing) key, and 
t is a temporal value (tweak/nonce), preferably secret and unpredictable, or at least non-repeating, optionally fixed (including empty: reducing the signature scheme to an outright deterministic signature scheme), and not under any influence from an adversary.  

When k is used in signatures, this approach could be called tweakably deterministic signatures, although I would prefer to call it message-dispersed signatures (to avoid the silly pitfall I mentioned of over-generalizing the value of determinism in key generation).

The changes my previous proposal have brought my current proposal closer to deterministic signatures than to purely randomized signatures. The tweak value t helps to address some of the potential pitfalls of purely deterministic signatures that I listed in my previous email.  Please let me know if you think the cost of tweaking outweighs the gains I described.

So, I'm not intending to be critical of deterministic signatures, or to support/defend past pure PRNG-based or underspecified randomized signatures, but rather to be in support something slightly securer than either, by combining the good features of both randomized and deterministic signatures.  Yet more reasons and responses in-line below.  So, please take them with a grain of salt, and read them in the light of trying make things securer.

Best regards,

Dan

> From: Cfrg [mailto:[email-masked]] On Behalf Of D. J. Bernstein
> 
> Dan Brown writes:
> > 2. Hindsight patching
> > ---------------------

I am vaguely familiar with this history, but thanks for the detailed reminder.  I'll add some hazy recollections of my own to the history.

> generation and use of random numbers (the k values). ... The poor user is given
> enough rope with which to hang himself---something a standard should not
> do." https://people.csail.mit.edu/rivest/pubs/RHAL92.pdf
> 
> 1997: Barwood echoes the randomness criticism and, as a solution, proposes
> deterministic generation of k: "The normal (i.e. IEEE P1363) way of
> implementing digital signatures using an elliptic curve seems to call (at least
> implicitly) for the generation of true random integers.
> Generating true random integers is difficult to do in a safe portable way, so I
> propose a method that does not require any true random input.
> ... What I suggest is that a prng is used to generate k, keyed with d (the private
> key), and seeded with e (the message digest)."
> generality: "I was thinking last night about an implementation of digital
> signatures - re: the requirement for a truly random number in DSA / NR / most
> other algo's. Why not derive the random number from the message to be
> signed therefore removing the need for a hardware rng
> idea into an entire SAC paper: "In this paper, we present a simple method for
> generating random-based signatures when random number generators are
> either unavailable or of suspected quality (malicious or accidental). ... Suffice it
> to say that one should replace each session's random number by a digest of
> the keys (secret and public) and the signed message."

For what little it's worth, I do vaguely recall discussions about adding message-determinism and/or message-dependency in the ANS X9F or IEEE P1363 committee, and even the IPR issues.  At one point, there was discussion of mandating feeding the message to be signed into the DRBG before signing, but that did not materialize.  

> 2010: Bushing, Marcan, Segher, and Sven ("failOverflow") announce that they
> have recovered the Sony PlayStation 3 signing key, thanks to Sony's reuse of a
> single k for many signatures.

My words "hindsight patching" are, in hindsight, an unclear summary of my technical reasoning. Sorry. I'll still try to explain.

You conclude "Of course ... would have stopped this 2010 attack."  How do you know that the scalar multiplication step would not have been skipped just because of deterministic k?  I've watched that video before, hoping to find some info on the root cause of the 2010 attack, but unless I missed something, they only report on the re-use of k across different messages without explaining how that occurred.  But maybe you know more, e.g. have some insider information.

Consider ECDSA as specified X9.62-2005.  I don't know if it was the specification being used in the 2010 attack, but let's say it is for argument's sake.  

Section 7.2 , signature generation, requires the signer to use Annex A.4, key generation, which requires one to use Annex D, random number generation, which requires one to use the HMAC-DRBG, (or some other future NIST/ANSI-approved RNG pending their approval) together range refitting.  Full pseudocode for HMAC-DRBG is given in Annex D.  

Annex L.4 gives test vectors but, alas, does not use the HMAC-DRBG, instead only specifying k.

Perhaps (a) the 2010 attack followed from there being too many layers of indirection, 7.2->A.4->D... i.e. the implementers stopped reading before they saw the HMAC_DRBG pseudocode.  Perhaps (b) the 2010 attack followed because the HMAC_DRBG was used but for some reason was instantiated just once and re-used.  Perhaps (c) the 2010 attack followed because of the inconsistency of the test vectors with the rest of the specification.  

Now replace the HMAC_DRBG with some deterministic scheme: why would the outcome be any different? Are you saying it's (b)?  

Who knows: maybe the implementers involved 2010 attack had read one of the papers you cited, but misunderstood the value of determinism and overcorrected to make the signatures deterministic across messages (can I say explosion here? Others have.).

The citations you mentioned did show "foresight", especially if they accurately describe the cause of the 2010 attack.  I think you too modestly omitted the fact that your also proposed deterministic signatures before the 2010 attack, right?  What I want to emphasize is CFRG should apply similar foresight in considering other likely failure modes, not just the one whose likelihood is made evident by an attack.  It's usually better to fix things before an attack, right?  

Anyway, what the CFRG is now doing, applying a security fix after an attack is often called a "patch", right?  Also, the _reasons_ many in CFRG are offering for adopting deterministic signatures, i.e. the evaluation of the merit of the deterministic signatures, now is based on the hindsight in view the 2010 attack.

As I mentioned earlier, I think some of these deterministic signature papers were cited before 2010 in some standards committee.   I'm not sure, but I believe they were dismissed as something that would never happen, or as something beyond the scope of the standard's responsibility.  If the 2010 attack were indeed caused entirely by randomizations (which I question!), then these standards lacked foresight.  In this case, I'm arguing CFRG should show more "foresight" than these past committees, by trying to thwart other possible failures before they happen. 

To that end, I've tried to think up possible failures, which I listed as 3a...3h.  Maybe CFRG can think of other possible risks.  At least now, we can assess the possibilities.  If you can rule them out as too improbable, then fine, all the better, right?  So, thank you, again, for at least considering them.

> With your proposal, the "poor user is given enough rope with which to hang
> himself---something a standard should not do". What stops the user from
> choosing a constant s, producing a predictable k and revealing the signing key?

What stops the user: the part I said about s being secret, guarded the same as the signing key.  

Quibble: setting s to be the signing key gives a constant but secret s, my original proposal to deterministic signatures, so it is not the constancy of s that is the problem. But I get your point, which is why I amended my proposal, despite my questioning of the actual cause of the 2010 attack.

As I said above, I've amended my proposal to 
k = F(m,a,t) 
where 
m is the message, 
a is the actual long-term signing key, and 
t is a temporal value (tweak/nonce), preferably secret and unpredictable, or at least non-repeating, and optionally fixed (reducing the signature scheme to a deterministic signature scheme).  

This aims to be a middle-ground between randomized and fully deterministic signatures, an effort to combine the best of both methods.

I'm theoretically wary of mixing in a, but yes, if F is sufficiently one-way etc., then it's totally intuitively fine.

A general strategy here is defense-in-depth: to avoid k reuse across messages and to avoid predictable k, we've got three defenses: m, a and t.  Furthermore, I see t as a low-cost protection against the scenarios I labeled 3a...3h, at least if t is an independent secret from s and unpredictable.  

Do you foresee that a signer getting into trouble from the tweak t?  Intuitively, if we assume a is unguessable, and that the signer controls t, the attacker can win by finding m and m' such that F(m,a,t) = F(m',a,t') which seems unlikely, because it is a collision in the a-keyed function, etc.

> 
> It's not enough to _tell_ people that k has security consequences--- something
> that has been said again and again since the original ElGamal paper in 1985.

At least some old standards do more than warn about security: they specify steps to generate k, HMAC_DRBG.  Yes, this requires entropy to be secure, but so does the long-term key.

> What actually works is having standard _test vectors_ that eliminate the bad
> implementations. By agreeing on a deterministic way to generate k, with no
> additional inputs, we allow every common mistake in k generation to be
> caught by test vectors.

My (amended) proposal would also admit test vectors, if F is fully specified, by setting:
m = "test message"
a = "test signing key - never use this ever"
t = "test nonce - never use this ever"
k = F(m,a,t) ="..."

Do test vectors mean it will prevent another 2010 attack?

I suspect that HMAC_DRBG has test vectors somewhere, if only ANSI X9.62-2005 had incorporated them with the ECDSA test vectors!  Should I dig up these, to be sure?

> 
> I don't mean to suggest that _every_ k-generation function is safe. On the
> contrary: generating a constant k, as Sony did, is of course very bad;
> generating k biased mod the group order is bad; etc. The designer needs to
> specify a k-generation function that's secure _and_ that actually ends up being
> tested in implementations. Failure to do this is tantamount to allowing _every_
> function that implementors come up with; instead of having _one_ function to
> carefully review for security problems, we're faced with a neverending list of
> implementation-specific functions.
> 
> The same principles apply to "entropy pools". Having each library make up its
> own mechanism to combine multiple entropy sources is a recipe for disaster.
> What we need is a specified, security-reviewed, deterministic, tested
> mechanism to combine multiple entropy sources---centralized in the operating
> system (even better, the hypervisor, when there is one) to maximize the
> chance that good entropy sources are actually used and to minimize the
> number of lines of code to review.
> 

Well, seems to me like you're straying a bit off-topic (entropy) in the paragraph above.  Anyway, I agree, and if there was such a centralized key/entropy source, then randomized signatures would be a cinch.  I am not sure how best to enforce each library to use some centralized key/entropy source.

ASIDE: I'm very interested in entropy and so on, and wrote a paper on assessing entropy, and the various means to harness it etc.  I've even mentioned some of these ideas to standards bodies, with little traction. What do you think of the 800-90A/B/C effort?  On the flip side, does centralizing (entropy) key generation also make it easier for a corrupt OS to compromise keys?  Would it be slightly safer if a process could obtain direct access to say, a camera, to derive its own keys.  Now I'm straying way off topic, sorry.

> source, and testing entropy sources is a quite different problem with a long
> history of failures, even in cryptographic products "certified" by the U.S.,
> Canadian, and German governments:
> 
> But the fact that there's a hard problem in one corner of the crypto ecosystem
> doesn't mean that we should give up on solving the problem.
> Our best chance of solving this problem starts by isolating it--- eliminating it
> from every other part of the ecosystem.
> 
> known to be broken by side-channel attacks. It's important to protect all
> secrets---including k, which is used for scalar multiplication, and the long-term
> secret, which is used for arithmetic mod the group order.
> Standard defenses include blinding of each secret bit (splitting b into r and r+b),
> blinding mod the group order (replacing k with k+rp), etc.; these defenses work
> for deterministic signing systems too.
> 

Um, surely you're not saying unprotected implementations of _deterministic_ (EC)DSA or Schnorr are not broken by side-channel attacks?  Are these not independent issues?  

So, what I was getting at: A good implementation might work really hard to protect against say simple power analysis, e.g. Montgomery ladder and the blinding techniques.  Great, but what if differential power/timing analysis is able average out the blinding effect, and detect the very minute remaining signal from the Montgomery ladder?  Are you saying such iterative side channel attacks are fully preventable? If so, then great, else doesn't changing k every time seems to help reduce this threat?  In other words, wouldn't this provide "defense-in-depth" or "multi-factor side-channel-protection", etc.  The way I see it, randomized signatures, or the tweaked deterministic signatures I'm proposing, seem to theoretically require less side-protection than fully deterministic signatures.

> The bigger picture is that crypto is constantly mixing secret data with public
> data. Side-channel defenses take responsibility for protecting this. We know
> how to defend, e.g., computing an authenticator of a potentially forged
> message---even if the same message is repeated any number of times. This is
> also what we're doing in computing k.
> 
> computation, but this cost improvement is quite small compared to the overall
> cost of a signature unit. An implementor desperate to take this approach will
> find that the resulting signatures, despite violating the deterministic standard
> (and failing standard signing tests), are fully interoperable---CFRG is not
> proposing that _verifiers_ track signatures of the same message and enforce
> repetition constraints.
> 

You say "speculating"; I'd say "worrying".  

In some of the cases 3b...3g, it would not require a transfer of a mistake from one piece of code to another. An implementer might have a common key generation unit: shared between the ephemeral and static keys, shared between signatures and key exchange, per some kind of centralization strategy.  In such cases, the fault might arise without any transfer of a code.

Anyway, so you think that you think 3b...3f are too unlikely to address, right?

> 
> Sure, anything is possible, but intelligent risk management requires sensibly
> evaluating the _likelihood_ and _impact_ of bad events. The chance of an
> implementor reusing k as Sony did, or generating k that's slightly too short, is
> obviously much higher than the chance of all of the scenarios that you
> postulate, and the impact---forgery of arbitrary messages under this public
> key---is no less disastrous than the impact of any of your scenarios.
> 
I agree about the principles of risk management likelihood and impact.  

Where I seem to disagree is on the likelihood.   Somebody implementing from scratch might build a common key generation unit, shared between signatures and key exchange, that bundles the scalar multiplication step with job of the selection of k.  Maybe that's a bad idea, but aren't we trying to foolproof things?

In "sensibly evaluating likelihood", we should consider things like conditional probability.  Randomized signatures are more widely deployed, so they have a higher incidence of failure.  But do they have a higher rate of failure?    

Do we have two specifications that are nearly identical except for one being deterministic and one being randomized, so that we can isolate the effect of deterministic or randomized?  Alas, probably not, so we have to act somewhat by intuition.
 
> Sure. Standard signature caching (e.g., DNSSEC saves signatures) also has this
> effect. Many RSA signature systems are also deterministic. You speculate that
> there are some protocols that need non-deterministic signatures for some
> vague reason; those protocols will already have to be quite careful in their
> selection of signature systems.
> 
> This is obviously far less important than the disastrous consequences of poor k
> generation for typical real-world applications of signatures.
> 
> First of all, to give proper credit, this purely theoretical issue was adequately
> analyzed by Olson in 1997:
> 
> 
Thanks for the link. 

Olson concludes: "Using the same key, there's
still the possibility of unfortunate interaction between the
hash and the exponential, which is the sort of thing that
rarely exists, but is hard to disprove."  

In the context of provability of stuff, which is the realm of my comment 3h, saying something is "hard to disprove" is not usually considered "adequately analyzed", let alone any sort of proof.  So, I don't see how this answers my question about the effects on security proofs.  That said, I fully agree on the intuition.  I'm not against trusting intuition, but I am for verifying intuition, which means trying to prove stuff.

If you are trying to dismiss comment 3h as theoretical, then why not just say so, otherwise I'm just confused.

Anyway, Olson's general argument seems to align with the Koblitz--Menezes paper: using a distinct alternative key for deriving signature k value deterministically is easy to prove to be as good as random signatures, but using the actual signing key for this task is mysteriously hard to prove.  

I don't think you're proposing to follow Olson literally by using an alternative key instead of the signing key, because you pointed out the risk in my proposal that the alternative key might be predictable, and that you have not specified EdDSA in this way (as I recall).  So, I'm wondering what you're getting at here. 

> The solution to all of the theoretical problems, as mentioned by Olson, is to
> have one discrete-log key and one message-hash key. Ed25519 uses a KDF
> (normally SHA-512) to derive these two separate keys from a master signing
> key.
> 
> You say that "an implementer who is likely to reuse an ephemeral may be just
> as likely to choose the alternative key poorly". But these objects have totally
> different levels of fragility from a security perspective.
> Choosing a slightly biased k is a disaster; choosing a slightly biased message-
> hash key (or discrete-log key) is irrelevant. Repeating k is a disaster; I have no
> idea what "poor" choice of message-hash key you think would be analogous to
> this. Sure, a _guessable_ message-hash key is as disastrous as a guessable k,
> but the equal problems in this extreme case don't imply equal problems in
> other cases.
> 
> The modern trend is to rely on the security of ciphers, notably AES, not just for
> _encrypting_ every message but also for _authenticating_ every message. Do
> you think this is a problem?
> 
As to the modern trend, on the theory side, I think it is moving away from relying on PRF properties, even for encryption.  For example, using AES in counter mode seems to be a way of relying on its PRG properties instead of its PRP/PRF properties.  To me, the PRG property of AES-CTR seems far more certain than a PRF, because a PRG attacker does not get to control the inputs blocks fed into the block cipher.  I'd be wrong if it is true that any PRF attack, however slight, on AES translates into an attack on AES-CTR.  So, the modern trend seems to be moving away from PRF assumptions, towards milder assumptions, as in the move from AES-CBC to AES-CTR, which seems good to me: even lower chance of anything going wrong.  Of course, maybe the actual cause for the trend ECB -> CBC -> CTR is based on the better understanding of encryption modes (and their proper usage), but the theoretical side effect seems to relying on more plausible assumptions.

Ignoring the PRF/PRP/PRG distinctions, yes, the reliance of authentication upon ciphers in general is a problem, but just a _theoretical_ problem.

Going out on limb: AES is not used for authenticating certificates, at least in hierarchical PKI, where signatures are used.  I'm less familiar with distributed PKI, but I don't think it relies cipher-based authentication.  So, in the initial stages of authentication, whether Alice knows if she still start talking Bob or Eve, typically does not seem to rely on AES or any other cipher.  Usually, Alice relies on a signature of a CA, plus Bob's signature or some authenticated key agreement, or perhaps a pre-shared key with Bob (where may ciphers are used?).   

But this authentication step is intermediate to Alice's final goals, so I'll try to be more specific. After authenticated key exchange with Bob, she can send a secret message to Bob.   Let's call the assurance she needs before doing contact Bob, "outgoing authentication", to distinguish it from "incoming authentication" of messages Alice receives from Bob.  Ok, so outgoing authentication is not really a standard definition, and is really just an intermediate pre-requisite to the end-goal of privacy.    But by isolating this sub-goal, we distinguish between different reliances.  For example, a super-theoretical risk is if there is a secret attack on AES or SHA1/2: in this disaster, Bob's (or a CA's) old deterministic signatures (if they, say mandate, AES for a PRF) might somehow expose the signing key.  Now alternative cipher/hash users (e.g. ChaCha/Salsa users) would lose some protection: Alice might worry about a MITM attack against Bob.  Maybe, they're using alternative algorithms because of speed, but a little extra security cushion is okay if it is cheap.

> years. The security standard is very high: we imagine that the attackers can
> freely choose all inputs and see all outputs, and that the attackers
> automatically win if they can find _any_ pattern, even though this isn't enough
> to break typical applications. The best possible security, within various real-
> world performance constraints, is systematically analyzed.

Yes, I am well aware that AES is widely believed to be a good PRF, as you describe.

The point 3h was about provability.  We do not have some proofs that AES is a good PRF, or do we?

I don't think you want to dismiss provability, en masse, right? It's quite fair to discuss the plausibility of various assumptions used in the proofs. So, I take your position to be that PRF assumptions to be perfectly reasonable to use in security proofs, and that my goal to avoid relying on a PRF assumption, and aiming for a milder PRG assumption, is frivolous?  Is that accurate?

Anyway, are we going to use AES, SHA256, or what, for deterministic signatures?  That question is for future CFRG discussion, I suppose. Out of order, sorry.

On the 3h topic of proofs, do the proposals for deterministic signature already have security proofs?  Since they involve the static signing key, the existence of such proofs seems to contradict the position of Koblitz and Menezes.    

Anyway, I hope there's never attack on AES, but if there is, then I can imagine it being only be some kind of obscure theoretical PRF attack, where the attacker is allowed to freely choose the plaintext blocks in some clever way, thereby inducing a minute amount of bias in the ciphertext blocks.  In this situation, AES might still be perfectly good to use in a PRG, as in AES-CTR encryption, and for running CTR-DRBG, because the PRF attacker lacks control of the plaintext blocks needed to induce the bias. Such a mixed situation would be similar to how SHA1 is deemed okay for some uses despite collision attacks, etc., and SHA2 is still okay despite key-extension attacks, and so on.

Although I am impressed by the work done on AES, maybe I don't have as much confidence in it as you, first, because I have not directly worked in the area, and second, RC4 is widely used, yet has problems meeting the much milder PRG goals.  

To bring this PRF discussion back to signatures: suppose we use a deterministic signature based on AES, and the attacker has some strange plaintext block pattern that causes a minute bias in the ciphertext blocks, i.e. PRF attack.   As above, perhaps this would have no impact on AES-CTR, because the attacker never controls the counter plaintext blocks.  But small biases are risky for DL signatures, because the lattice attacks make them sensitive to this.  In this unlikely situation, generating signature k values generated with something more like AES-CTR, i.e. a traditional CSPRNG/DRBG, rather than more like AES-ECB, i.e. a deterministic signature mechanism, might be better.  

Intuitively, adding a tweak, as in my second proposal, seems to both list of threats.

> 
> Is it still possible that an attacker will find some shocking break of AES? Yes, it's
> possible. Is it conceivable that generating k's with a modern cipher will produce
> k's so biased as to allow forged signatures?
> Yes, it's conceivable. But is it reasonable to say that this wildly speculative
> horror story has the same probability as another equally disastrous Sony-style
> implementation screwup? No, it isn't.
> 

I don't recall saying that 3h scenario had the same probability as the 2010 attack.  The 3h scenario is only theoretical.  It considers a very low probability attack, unless we model some kind of malice in the selection of whatever PRF is being used, e.g. if we use SHA256.

Just to be clear, I think I implied that the event of one of the scenarios 3a...3g happens has comparable probability to a _repeat_ of the 2010 attack: warranting some kind of countermeasure, e.g. the tweaks in my new proposal.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 6 May 2015 21:37:51 -0700

> t is a temporal value (tweak/nonce), preferably secret and unpredictable, or at least non-repeating, optionally fixed (including empty: reducing the signature scheme to an outright deterministic si…

I think that if we worry about kleptography, t should not be used.

> So, I'm not intending to be critical of deterministic signatures, or to support/defend past pure PRNG-based or underspecified randomized signatures, but rather to be in support something slightly s…

How is this proposal more secure, i.e. what properties does it have,
that protocols rely on, that EdDSA doesn't?

> You conclude "Of course ... would have stopped this 2010 attack."  How do you know that the scalar multiplication step would not have been skipped just because of deterministic k?  I've watched tha…

Let me see if I have this correct. You're arguing that an implementor,
told to compute k=F(m, x), and go through some more steps, will skip
that step. Fine: they evidently skipped the random number generation
step. But at that point we might as well specify an implementor who
skips over comparison steps in signature verification.

What DJB is arguing is that the implementor missed the *per-message*
random generation, a much more subtle issue then failing to compute a
different random number each time. Why, just yesterday I had a student
tell me the odds of rolling a 6 with two dice should be 1/6, not 5/36.

> To that end, I've tried to think up possible failures, which I listed as 3a...3h.  Maybe CFRG can think of other possible risks.  At least now, we can assess the possibilities.  If you can rule the…

But you've offered no assessment of why we should analyze these
failures. Why are these the most likely? By contrast we know
kleptography is a real issue.

> I'm theoretically wary of mixing in a, but yes, if F is sufficiently one-way etc., then it's totally intuitively fine.

In the EdDSA scheme, the signing key consists of x a discrete
logarithm of the public key, and z, a key for the PRF. It's a trivial
exercise to show that using k=H(z,m) is secure if H is a PRF from
{0,1}*->bit strings of the correct length, and the length is long
enough for the group being used.

> At least some old standards do more than warn about security: they specify steps to generate k, HMAC_DRBG.  Yes, this requires entropy to be secure, but so does the long-term key.

It's easy to have standards that specify secure ways of doing things.
Oddly enough, I still have a job breaking systems. Test vectors are
far more likely to be run then extensive audits. I have seen systems
(and once written one!) that don't use long enough k for modular
reduction, that don't ensure adequate seeding of the random number
generator, etc, etc, etc. Many implementations of cryptography aren't
written by experts. They are occasionally written from Wikipedia
articles.

> I suspect that HMAC_DRBG has test vectors somewhere, if only ANSI X9.62-2005 had incorporated them with the ECDSA test vectors!  Should I dig up these, to be sure?

I don't have access to ANSI X9.62-2005. But let's consider the impact
of the Debian bug, or the FreeBSD-CURRENT bug. Even if the authors of
the ECDSA module had taken care to carefully seed the approved random
number generator, they would have generated an extremely limited
number of possible k. How does including HMAC_DRBG test vectors fix
this problem? We know the causes of these failures: where do they fit
in your analysis?

Deterministic functions are much easier to test. We can pick vectors
to stress common issues, automate comparison testing, etc. I don't
know how to do the same for nondeterministic functions.

> So, what I was getting at: A good implementation might work really hard to protect against say simple power analysis, e.g. Montgomery ladder and the blinding techniques.  Great, but what if differe…

One of the standard countermeasures against side channels is to
compute [k]P as [k+r]P-[r]P for a random r the same size as k. Of
course, an attacker attacking an implementation using this method
knows slightly more than if we compute a different [r]P every time:
they know each set of traces sum to the same number. I don't see how
this helps much. (Mike Hamburg would know better).
> In some of the cases 3b...3g, it would not require a transfer of a mistake from one piece of code to another. An implementer might have a common key generation unit: shared between the ephemeral an…

How is this risk mitigated by your approach? If we assume that they
make a "common key generator", then your specification of F(m,a,t) was
entirely ignored, as was DJB's proposed k=F(m, z). However, in testing
with selected test vectors the deviation from your proposal can't be
detected, while from DJB's it's easy.

> If you are trying to dismiss comment 3h as theoretical, then why not just say so, otherwise I'm just confused.

See my upthread note about the trivial argument. Down below you
reproduce this argument. So what exactly makes you think 3h is a
problem, given the obvious work-around?

> I don't think you're proposing to follow Olson literally by using an alternative key instead of the signing key, because you pointed out the risk in my proposal that the alternative key might be pr…

In ECDSA, k, the key, is fed to SHA-512 to produce l and r, each 32
bytes. l is then hashed with the message to produce the commitment
value, and r is the discrete log of the public key. Obviously this
introduces an annoying dependence on the distinguishability of SHA-512
outputs from 64 byte random strings, but granting that assumption this
is exactly Olson's solution.

> But this authentication step is intermediate to Alice's final goals, so I'll try to be more specific. After authenticated key exchange with Bob, she can send a secret message to Bob.   Let's call the assurance she needs before doing contact Bob, "outgoing authentication", to distinguish it from "incoming authentication" of messages Alice receives from Bob.  Ok, so outgoing authentication is not really a standard definition, and is really just an intermediate pre-requisite to the end-goal of privacy.    But by isolating this sub-goal, we distinguish between different reliances.  For example, a super-theoretical risk is if there is a secret attack on AES or SHA1/2: in this disaster, Bob's (or a CA's) old deterministic signatures (if they, say mandate, AES for a PRF) might somehow expose the signing key.  Now alternative cipher/hash users (e.g. ChaCha/Salsa users) would lose some protection: Alice might worry about a MITM attack against Bob.  Maybe, they're using alternative algorithms
>  because of speed, but a little extra security cushion is okay if it is cheap.
>

You've never explained what assumption you want to make on F, so it's
entirely unclear if you actually are relying on a weaker assumption.
In fact, as I argue down below, for most hash functions you actually
aren't.

> To bring this PRF discussion back to signatures: suppose we use a deterministic signature based on AES, and the attacker has some strange plaintext block pattern that causes a minute bias in the ci…

Nobody other than you has actually proposed using AES for a PRF in
this application. (There are several efficiency reasons not to). But
let's consider what failure of of the compression function of an
Merkel-Damgård hash function like SHA2 to be a PRF in the message
argument means for one-wayness and collision attacks.

Your hypothetical attack involves a set S of blocks b such that C(k,b)
has some easily recognizable property for a higher proportion of k
then expected for a random function. My attacker computes a large
number of k_i, and then calculates all C(k_i, b). Since these C(k_i,
b) are not uniformly distributed, the probability of collision
increases above that expected for a random function. So we are relying
on PRF assumptions when signing with SHA2.

(A PRF distinguisher for H(k,m) gives a PRF distinguisher for C.
What's harder is to work out the exact constants in the above).

---

From: Dan Brown <[email-masked]>
Date: Thu, 7 May 2015 15:45:24 +0000

> From: Watson Ladd [mailto:[email-masked]]
> 
> > Accordingly, I now amend my proposal to k = F(m,a,t) where F is some
> > to-be-specified cryptographically strong deterministic function, m is
> > the message, a is the actual long-term (signing) key, and t is a
> > temporal value (tweak/nonce), preferably secret and unpredictable, or at
> least non-repeating, optionally fixed (including empty: reducing the signature
> scheme to an outright deterministic signature scheme), and not under any
> influence from an adversary.
> 

[DB] Good catch.  So, that cost should be weighed against the gains from using t.

Just to expand: is your concern about the following kleptographic malware? The malware lets multiple t values be generated (honestly), say t_1, t_2, ... t_n, and then search the corresponding k_1, ..., k_n for a value k_i that suffers from bias needed to make a lattice attack work? The kleptographic malware then lets k=k_i through to per a normal signature.

> 
> >
> > When k is used in signatures, this approach could be called tweakably
> deterministic signatures, although I would prefer to call it message-dispersed
> signatures (to avoid the silly pitfall I mentioned of over-generalizing the value
> of determinism in key generation).
> >
> > The changes my previous proposal have brought my current proposal closer
> to deterministic signatures than to purely randomized signatures. The tweak
> value t helps to address some of the potential pitfalls of purely deterministic
> signatures that I listed in my previous email.  Please let me know if you think
> the cost of tweaking outweighs the gains I described.
> >
> > So, I'm not intending to be critical of deterministic signatures, or to
> support/defend past pure PRNG-based or underspecified randomized
> signatures, but rather to be in support something slightly securer than either,
> by combining the good features of both randomized and deterministic
> signatures.  Yet more reasons and responses in-line below.  So, please take
> them with a grain of salt, and read them in the light of trying make things
> securer.
> 
> How is this proposal more secure, i.e. what properties does it have, that
> protocols rely on, that EdDSA doesn't?
> 
[DB] Maybe I was unclear above: the tweak tries to address the issues I labelled 3a..3h in the first email I sent.  If you have time to spare, then please consider these issues.  I think you know that Bernstein responded to 3a...3h already, so I would fully understand if you didn't want to waste any time.

> 
> Let me see if I have this correct. You're arguing that an implementor, told to
> compute k=F(m, x), and go through some more steps, will skip that step. Fine:
> they evidently skipped the random number generation step. But at that point
> we might as well specify an implementor who skips over comparison steps in
> signature verification.

[DB] Wasn't there were real world examples (goto fail???) of signature verification steps being accidentally skipped?  I'm trying to see if the point of your paragraph is to compare realisms of two failure modes, or to just give up on protecting against attack X because we cannot protect against attack Y. ASIDE: implicit certificates, e.g. SEC4 (includes IPR), can _sometimes_ address this failure to verify a cert, because of instead of a verification step to miss it absorbs the authentication right into the use of the public key.

I think I originally described the examples 3a...3h in sufficient detail, with at least a paragraph each.

> different random number each time. Why, just yesterday I had a student tell
> me the odds of rolling a 6 with two dice should be 1/6, not 5/36.
> 

[DB]  I didn't hear Bernstein's argument that way.  I know well that math works by the subtlety of k being re-used across different messages, but as far as I know, in the 2010 attack, the implementer use just one k for every single signature?  Or maybe I'm wrong: perhaps the implementer did some kind of subtle mistake of using the same k_1 for the first signature of each message, and then another k_2 for every the second signature of each message?  Are you saying that kind of subtle mistake is more likely than some kind of larger bungle?

> 
> But you've offered no assessment of why we should analyze these failures.
> Why are these the most likely? By contrast we know kleptography is a real
> issue.

[DB] I provided my assessment in one paragraph for each of the points 3a..3h.

> >
> > This aims to be a middle-ground between randomized and fully deterministic
> signatures, an effort to combine the best of both methods.
> >
> In the EdDSA scheme, the signing key consists of x a discrete logarithm of the
> public key, and z, a key for the PRF. It's a trivial exercise to show that using
> k=H(z,m) is secure if H is a PRF from {0,1}*->bit strings of the correct length,
> and the length is long enough for the group being used.
> 

[DB] I guess I misremembered EdDSA: I thought it used k =H(x,m).  Are z and x are truly independent?  Then why Bernstein object to my original proposal k = F(s,m) where s is a secret by saying that s might be constant, and then predictable?  Maybe there's a connection between z and x in EdDSA?  Is x = H(z,z) or something?

> paper in 1985.
> > At least some old standards do more than warn about security: they specify
> steps to generate k, HMAC_DRBG.  Yes, this requires entropy to be secure, but
> so does the long-term key.
> 
> Oddly enough, I still have a job breaking systems. Test vectors are far more
> likely to be run then extensive audits. I have seen systems (and once written
> one!) that don't use long enough k for modular reduction, that don't ensure
> adequate seeding of the random number generator, etc, etc, etc. Many
> implementations of cryptography aren't written by experts. They are
> occasionally written from Wikipedia articles.
> 

[DB] Ok, how do your "test vectors" work, given that the signer has a secret signing key?  Do you substitute in test key for the signing key?  Why cannot that be done for a seeded PRNG implementation: just feed in a test seed?

> 
> I don't have access to ANSI X9.62-2005. But let's consider the impact of the
> Debian bug, or the FreeBSD-CURRENT bug. Even if the authors of the ECDSA
> module had taken care to carefully seed the approved random number
> generator, they would have generated an extremely limited number of
> possible k. How does including HMAC_DRBG test vectors fix this problem? We
> know the causes of these failures: where do they fit in your analysis?
> 
[DB] Entropy deficiency is an orthogonal issue, but if a has enough entropy, then k = F(m,a,t) should be fine, just like the deterministic k=F(m,a) should be good. If t does not enough entropy, then k = F(m,a,t) reduces to k = F(m,a). 

So, the way to use HMAC_DRBG, or any DRBG, is not instantiate it anew for each secret or key needed.  That would be a mis-use of any DRBG. I don't think that's what happened in the 2010 attack.  If a DL-based signature with a DRBG in the intended way, i.e. as a deterministic DL-based signature is used in the intended way, then all is dandy, provide the initial seeds are good.

> Deterministic functions are much easier to test. We can pick vectors to stress
> common issues, automate comparison testing, etc. I don't know how to do the
> same for nondeterministic functions.
> 
[DB] Sure, that's why X9.62 includes test-able algorithms for key-generation.

> >
> > So, what I was getting at: A good implementation might work really hard to
> protect against say simple power analysis, e.g. Montgomery ladder and the
> blinding techniques.  Great, but what if differential power/timing analysis is
> able average out the blinding effect, and detect the very minute remaining
> signal from the Montgomery ladder?  Are you saying such iterative side
> channel attacks are fully preventable? If so, then great, else doesn't changing k
> every time seems to help reduce this threat?  In other words, wouldn't this
> provide "defense-in-depth" or "multi-factor side-channel-protection", etc.  The
> way I see it, randomized signatures, or the tweaked deterministic signatures
> I'm proposing, seem to theoretically require less side-protection than fully
> deterministic signatures.
> 
> One of the standard countermeasures against side channels is to compute [k]P
> as [k+r]P-[r]P for a random r the same size as k. Of course, an attacker
> attacking an implementation using this method knows slightly more than if we
> compute a different [r]P every time:
> they know each set of traces sum to the same number. I don't see how this
> helps much. (Mike Hamburg would know better).

[DB] Again, blinding is a good method.  It needs a good random r, so it does not save much on that account compred to random k.  If k is used, say, a thousand times, can the relative traces of [k+r]P and [r]P, which are related by k, leak out some info about k?  Maybe nobody thinks so now, but if the k were different, then we needn't worry so much about it.

> > In some of the cases 3b...3g, it would not require a transfer of a mistake from
> one piece of code to another. An implementer might have a common key
> generation unit: shared between the ephemeral and static keys, shared
> between signatures and key exchange, per some kind of centralization
> strategy.  In such cases, the fault might arise without any transfer of a code.
> 
> How is this risk mitigated by your approach? If we assume that they make a
> "common key generator", then your specification of F(m,a,t) was entirely
> ignored, as was DJB's proposed k=F(m, z). 

[DB] The common key generator would have an optional input: like the SP 800-90 and /dev/random (you can write to it).  The convention in my scenario would be that callers to the key generator write to the optional input before calling it: much like deterministic obtain a secret by making it depend on the message.

So, I'm not saying that DJB or you would implement things in this way, just that somebody else might.

> However, in testing with selected
> test vectors the deviation from your proposal can't be detected, while from
> DJB's it's easy.
> 
[DB] Oh: t should be specified in my proposal to generated using a DRBG, per the traditional state-of-the-art ECDSA implementations.  

These can be test vectored easily by supplying all the seed inputs, and corresponding outputs.

If an implementers fails by generating t with the wrong deterministic algorithm, then the test vectors will catch it.  If an implementer fails by not supply adequate seeds for t, but adequate seeds for a, then all is fine.

> See my upthread note about the trivial argument. Down below you reproduce
> this argument. So what exactly makes you think 3h is a problem, given the
> obvious work-around?
> 

[DB] I'm not sure what your "upthread argument" is.  

> >
> > I don't think you're proposing to follow Olson literally by using an alternative
> key instead of the signing key, because you pointed out the risk in my proposal
> that the alternative key might be predictable, and that you have not specified
> EdDSA in this way (as I recall).  So, I'm wondering what you're getting at here.
> 
> In ECDSA, k, the key, is fed to SHA-512 to produce l and r, each 32 bytes. l is
> then hashed with the message to produce the commitment value, and r is the
> discrete log of the public key. Obviously this introduces an annoying
> dependence on the distinguishability of SHA-512 outputs from 64 byte random
> strings, but granting that assumption this is exactly Olson's solution.
> 

[DB] Ok.

> In fact, as I argue down below, for most hash functions you actually aren't.
> 

[DB] 

> >
> > Anyway, are we going to use AES, SHA256, or what, for deterministic
> signatures?  That question is for future CFRG discussion, I suppose. Out of
> order, sorry.
> >
> > On the 3h topic of proofs, do the proposals for deterministic signature
> already have security proofs?  Since they involve the static signing key, the
> existence of such proofs seems to contradict the position of Koblitz and
> Menezes.
> >
> > Anyway, I hope there's never attack on AES, but if there is, then I can imagine
> it being only be some kind of obscure theoretical PRF attack, where the
> attacker is allowed to freely choose the plaintext blocks in some clever way,
> thereby inducing a minute amount of bias in the ciphertext blocks.  In this
> situation, AES might still be perfectly good to use in a PRG, as in AES-CTR
> encryption, and for running CTR-DRBG, because the PRF attacker lacks control
> of the plaintext blocks needed to induce the bias. Such a mixed situation would
> be similar to how SHA1 is deemed okay for some uses despite collision attacks,
> etc., and SHA2 is still okay despite key-extension attacks, and so on.
> >
> > Although I am impressed by the work done on AES, maybe I don't have as
> much confidence in it as you, first, because I have not directly worked in the
> area, and second, RC4 is widely used, yet has problems meeting the much
> milder PRG goals.
> >
> > To bring this PRF discussion back to signatures: suppose we use a
> deterministic signature based on AES, and the attacker has some strange
> plaintext block pattern that causes a minute bias in the ciphertext blocks, i.e.
> PRF attack.   As above, perhaps this would have no impact on AES-CTR,
> because the attacker never controls the counter plaintext blocks.  But small
> biases are risky for DL signatures, because the lattice attacks make them
> sensitive to this.  In this unlikely situation, generating signature k values
> generated with something more like AES-CTR, i.e. a traditional CSPRNG/DRBG,
> rather than more like AES-ECB, i.e. a deterministic signature mechanism, might
> be better.
> 
> Nobody other than you has actually proposed using AES for a PRF in this
> application. (There are several efficiency reasons not to). But let's consider

 [DB] Well, one can use NIST SP 800-90A CTR-DRBG with FIPS 186-4 version of ECDSA.

> what failure of of the compression function of an Merkel-Damgård hash
> function like SHA2 to be a PRF in the message argument means for one-
> wayness and collision attacks.
> 
> Your hypothetical attack involves a set S of blocks b such that C(k,b) has some
> easily recognizable property for a higher proportion of k then expected for a
> random function. My attacker computes a large number of k_i, and then
> calculates all C(k_i, b). Since these C(k_i,
> b) are not uniformly distributed, the probability of collision increases above
> that expected for a random function. So we are relying on PRF assumptions
> when signing with SHA2.
> 

[DB] Let's crunch the numbers a little here.  

Suppose C is SHA-1, and that my hypothetical attacker knows a secret set S of 2^20 blocks b such that C(k_i,b) has first bit 0 for all k_i.  My hypothetical attacker could probably exploit this to extract a deterministic signer's key with about 2^20 messages, probability near to one, and rather little computation.  Your collision-finder has a minutely increased chance of finding a collision in SHA1, which won't help to find the private key.  Just ball-parking the probs here: 2^40/2^160=2^-120 versus 2^40/2^159=2^-119.

You're quite right.

---

From: Russ Housley <[email-masked]>
Date: Fri, 8 May 2015 08:18:58 -0400

+1

---

From: Watson Ladd <[email-masked]>
Date: Fri, 8 May 2015 06:14:40 -0700

> Just to expand: is your concern about the following kleptographic malware? The malware lets multiple t values be generated (honestly), say t_1, t_2, ... t_n, and then search the corresponding k_1,…

Exactly.

> [DB] Maybe I was unclear above: the tweak tries to address the issues I labelled 3a..3h in the first email I sent.  If you have time to spare, then please consider these issues.  I think you know t…

As far as I can tell, only 3a and 3h involves anything that actually
can be analyzed. And the results in 3h, knowing that ROM=>PRF and we
need ROM (or generic group model) for Schnorr security, are not good
for your position. (I don't know if generic group implies PRF exists,
and my earlier comment on PRF->collision was completely bogus, when
looking at multiple queries) 3a is actually a reasonable argument, but
there are quite a few cases where power analysis doesn't matter.

> [DB] Wasn't there were real world examples (goto fail???) of signature verification steps being accidentally skipped?  I'm trying to see if the point of your paragraph is to compare realisms of two…

No, it's to point out that once you assume the implementor isn't
reading the spec, there is nothing you can do. I don't see how your
proposal makes this better. In fact it makes it worse in a number of
ways, and makes implementations more complicated.

First, you are proposing that the "implementation" include a DRGB,
that gets instantiated once, and called multiple times. That's
incompatible with threads in C, unless the library author forces
applications to call per-thread initialization functions, etc, etc. Of
course, encryption libraries essentially need to do this, but there's
a workaround: open /dev/urandom once, and use the fact that read is a
threadsafe system call. Some operating systems have a systemwide
random number generator that is a single, nonfailing, call. Libraries
that require randomness can use it. But that's not all operating
systems. Some CPUs have an instruction that can be used to generate
random data. But that isn't universal.

Once we decide to make a DRGB, with the possibility of injecting
seeds, applications have to remember not to do this, but to seed the
DRGB correctly before using. But now we have a Big Red Button, which
if pushed utterly destroys security. Libraries that require strong
randomness should use standard system provided means to obtain it, and
should not offer alternatives with no security. Fork security, and VM
restarts are good reasons not to do this. (Passing in a secret key for
testing does not have this problem: it's exactly the same interface as
used when using the code not in testing).

With your amended proposal, signatures remain secure even with bad
randomness (unless we have kleptographic bugs, induced by our good
friends at Fort Mead). So what exactly is the point of having all this
extra code lying around, and dependencies on randomness?

Of course, you've stated that implementors should be permitted to make
deterministic signatures instead, but we should warn people that this
is less secure and not recommended. Instead we should recommend design
decisions which weaken, not strengthen, security, increase the volume
of code to be written, and make certain design decisions impossible.

Sincerely,
Watson Ladd

---

From: Nico Williams <[email-masked]>
Date: Fri, 8 May 2015 22:32:40 -0500

> t is a temporal value (tweak/nonce), preferably secret and unpredictable, or at least non-repeating, optionally fixed (including empty: reducing the signature scheme to an outright deterministic si…

The signature scheme just must be deterministic as to all inputs, and it
must be state-less.  I suppose one could have OPTIONAL inputs like t
above, or cached pre-computations (a cache is not the same as state),
but those warrant extreme caution (see Watson Ladd's response).

The issue here is partly about what the API looks like.  The signature
API has to be an interface to a deterministic function with no hidden
inputs nor hidden state: so it can be tested.

It's also about state: some (most!) systems can't keep it; the scheme
simply must be state-less.  Certainly we need a state-less signature
scheme.  An explicit-state scheme might later prove useful, but first we
urgently need a state-less one.

Given a deterministic, state-less function, implementations can be
tested via test vectors.  This should be a priority.  Batch verification
is also quite desirable, but can be had anyways (EdDSA has it).

An API with explicit state (e.g., a bag of one-time-use nonces, a
counter-based nonce generator) might be a nice optimizations for some
cases, but the price to pay is extreme difficulty keeping the required
state.

Nico
--

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 10 May 2015 23:33:18 -0700

> f) Signature key compromised pretty quickly, all active security

I agree that signing algorithms like ECDSA are sensitive to the leaking 
of a few bits of nonces per signature. However, a secure DRBG/KDF used 
throughout is considered mandatory nowadays. Nonces, long-term key 
generation, IVs, session keys, etc, should be obtained via good DRBG/PRF 
anyway.

Your list got me thinking regarding the issue of fault attacks on 
deterministic signatures.

I will use the EdDSA as an example. Consider an EdDSA signing on a 
smartcard.

EdDSA algorithm, in its canonical version, includes a message M in the 
calculation of the hash twice: once to calculate the ephemeral private 
value r for R=r*G, and second, to calculate a multiple of the long-term 
private signing key 'a' during the calculation of S. {R,S} is the 
signature. Assume that a smartcard signature implementation requires 
transfer of the M to the smartcard twice, due to limited memory on the 
smartcard and that the EdDSA cryptographically enforces that the two 
hashing operations are performed sequentially. As a result, the signing 
operation provides a reliable method to affect the second hashing, but 
not the first. A user (or malware) can change the M to M' at the 
appropriate moment, affecting the second hashing, which should be a 
realistic task with a sufficiently large message.

The second hashing in the EdDSA algorithm is done over data that the 
user knows, specifically, H'=Hash(R, A, M'). It can be observed that one 
valid signature and one invalid, generated as described above, will 
recover the private key 'a'. Hint: the deterministic r remains the same 
and is canceled out by subtraction.

This attack is similar to RSA CRT fault attacks on PKCS#1.5 
deterministic signatures. A random 'r' could have helped to "blind" the 
private key from the above exposure.

As I voted earlier, I don't think it's the the best to _prohibit_ a 
random 'r' for all applications, as opposed to _discourage_. A 
closed-source implementations may still use random values for 'r' 
despite the prohibition in the spec.

---

From: Brian Smith <[email-masked]>
Date: Sun, 10 May 2015 21:36:55 -1000

> extra code lying around, and dependencies on randomness?

As far as I understand Dan Brown's argument, he is saying that nobody
should be *required to depend* on randomness (i.e. purely deterministic
signatures should be allowed), but any implementation *should be allowed*
to use randomness if the use of randomness helps prevent side channel
attacks.

(Quoted out of order):

> 3a is actually a reasonable argument, but

The question is whether it is reasonable to assume that there are *no*
cases where power analysis, EMI, or other side channel attacks matter, that
are relevant to this decision.

I've read in this thread some suggestions that such side channel attacks do
not matter for TLS. I don't think that that assertion has been shown to be
conclusively true, considering that we have to assume that the server doing
the signing is co-located physically centimeters away from, or even on the
same system as, systems that may be attacking them.

Timing side channels and the *idea* of developing constant time signing
implementations to guard against them, are well understood. Yet, even when
people go out of their way to develop constant-time implementations, they
frequently get it wrong. In particular, it is pretty common to see
implementations making wrong assumptions about which C language constructs
will result in constant-time execution. (This should be unsurprising, since
C doesn't make any such guarantees.) Therefore, even if timing side
channels are the only side channels that we are concerned with, it might
*still* be useful to use randomization on top of a deterministic scheme as
a defense-in-depth mechanism (as BoringSSL does, for example).

After all, if we're designing under the assumption that implementers cannot
follow even the most obvious and clear instructions regarding randomizing k
in ECDSA, then it seems prudent to also assume that they cannot write
constant-time code that is correct, considering that even incredibly
well-informed implementers have had difficulties in doing so. (It is not
hard to find code in major implementations claiming to be constant time
that isn't actually constant time.)

> these defenses work for deterministic signing systems too.

I'm not disagreeing with DJB. However, I think it is worth spending time,
at least, verifying whether this assertion that all relevant side channel
attacks can be reasonably prevented for purely deterministic signature
schemes is true. If so, then only a purely deterministic scheme should be
specified. Otherwise, randomization should be permitted but not required.

Cheers,
Brian

---

From: Sean Turner <[email-masked]>
Date: Mon, 11 May 2015 13:51:36 +0200

On May 04, 2015, at 19:37, Daniel Kahn Gillmor <[email-masked]> wrote:

>   —dkg

+1

spt

---

From: Watson Ladd <[email-masked]>
Date: Mon, 11 May 2015 06:42:14 -0700

On Mon, May 11, 2015 at 12:36 AM, Brian Smith <[email-masked]> wrote:
> As far as I understand Dan Brown's argument, he is saying that nobody should
> be *required to depend* on randomness (i.e. purely deterministic signatures
> should be allowed), but any implementation *should be allowed* to use
> randomness if the use of randomness helps prevent side channel attacks.

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

> The question is whether it is reasonable to assume that there are *no* cases
> where power analysis, EMI, or other side channel attacks matter, that are
> relevant to this decision.
>
> C doesn't make any such guarantees.) Therefore, even if timing side channels
> are the only side channels that we are concerned with, it might *still* be
> useful to use randomization on top of a deterministic scheme as a
> defense-in-depth mechanism (as BoringSSL does, for example).
>
> hard to find code in major implementations claiming to be constant time that
> isn't actually constant time.)

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

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

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

> I'm not disagreeing with DJB. However, I think it is worth spending time, at
> least, verifying whether this assertion that all relevant side channel

---

From: Nico Williams <[email-masked]>
Date: Mon, 11 May 2015 10:23:15 -0500

On Sun, May 10, 2015 at 11:33:18PM -0700, Andrey Jivsov wrote:
> I agree that signing algorithms like ECDSA are sensitive to the
> leaking of a few bits of nonces per signature. However, a secure
> DRBG/KDF used throughout is considered mandatory nowadays. Nonces,
> long-term key generation, IVs, session keys, etc, should be obtained
> via good DRBG/PRF anyway.

"Sure, and I want a pony too."

Statefulness is difficult to implement.

Consider OpenSSL.  Till now OpenSSL has thankfully not needed to use
file locking.  If it had to...  The thought of OpenSSL using POSIX file
locking makes me shudder with fear.  As it is one really does not need
to worry too much about N copies of OpenSSL in one process (besides some
of those N being out of date) for N>1 -- just make sure that the right
version is loaded and linked at run-time for each dependent.

Or consider any other software implementation.  To make it work reliably
one would really need an IPC mechanism to talk to a daemon so it does
all the signing because then it can have a single lock around the
signing state.

Even accepting that complication, compare the result to a deterministic,
state-less signature function!

(This is not even considering the difficulty in synchronously updating
persistent state, or arranging to be able to survive occasional failures
to do so.)

Test vectors go out the window, unless we specify every detail of state
keeping so that the state can be made explicit... further complicating
implementations _and_ applications.

> EdDSA algorithm, in its canonical version, includes a message M in
> the calculation of the hash twice: once to calculate the ephemeral
> private value r for R=r*G, and second, to calculate a multiple of
> the long-term private signing key 'a' during the calculation of S.
> {R,S} is the signature. Assume that a smartcard signature
> implementation requires transfer of the M to the smartcard twice,
> due to limited memory on the smartcard and that the EdDSA
> cryptographically enforces that the two hashing operations are
> performed sequentially. As a result, the signing operation provides
> a reliable method to affect the second hashing, but not the first. A
> user (or malware) can change the M to M' at the appropriate moment,
> affecting the second hashing, which should be a realistic task with
> a sufficiently large message.
> 
> user knows, specifically, H'=Hash(R, A, M'). It can be observed that
> one valid signature and one invalid, generated as described above,
> will recover the private key 'a'. Hint: the deterministic r remains
> the same and is canceled out by subtraction.

This can be fixed by replacing M with H(M) in the second hash, since
H(M) will be of fixed size and the smartcard can compute it as it
computes the first hash.

Perhaps we should add 'online' to the list of required attributes (which
so far should be: deterministic, and state-less).

Nico
--

---

From: "D. J. Bernstein" <[email-masked]>
Date: 11 May 2015 20:02:13 -0000

Nico Williams writes:
> replacing M with H(M) in the second hash

This makes the signature scheme vulnerable to collisions in H. This
_shouldn't_ be a problem, since the community puts a lot of effort into
designing hash functions for which finding collisions seems to be
extremely difficult; but it's safer to build collision-resilient
signature systems, using collisions as an early-warning mechanism.

Of course, it's up to the user what to sign with a collision-resilient
signature system. In particular, instead of signing m, the user is free
to sign H(m). This throws away collision-resilience, but it can improve
cost in some applications: specifically, if H is one-pass while the
signature system isn't, then the whole procedure of signing H(m) is
one-pass, and this saves time when m doesn't fit into fast RAM. But this
combination clearly shouldn't be the default: security is job #1, and
the number of passes is irrelevant to most applications.

Similarly, the user is free to use a deterministic signature system to
sign (r,m), where r is chosen randomly for each message. This type of
randomization can in some situations reduce the cost of protecting
against, e.g., EM attacks. But again this shouldn't be the default: it
makes testing harder for everybody, raises kleptographic questions, etc.

Here's a related excerpt from http://blog.cr.yp.to/20140323-ecdsa.html:

   _Maximum security_. Ed25519 actually generates k by hashing the
   secret key together with the entire message. Very fast "PRFs" used to
   authenticate messages, such as VMAC, are safe here, but Ed25519
   simply uses SHA-512 since it's quite rare for this to be a noticeable
   bottleneck. Using an RNG wouldn't break interoperability, but the
   safest option is the default. Using Ed25519 to sign H(m), rather than
   m, would mean hashing m only once (at the expense of collision
   resilience), but again the safest option is the default.

---Dan

---

From: Nico Williams <[email-masked]>
Date: Mon, 11 May 2015 15:26:06 -0500

> signature systems, using collisions as an early-warning mechanism.

Right.  Fot the record, I'd prefer to not replace M with H(M) in the
derivation of k.  Instead I'd rather not have hardware like Andrey
posited.

It is clear that some users have a use for randomized k's, and that will
interop with a deterministic, stateless signature scheme that derives k
from the secret key and the message.  There's no way to prevent that,
so/and we shouldn't try, but the signature scheme that CFRG settles on
should be deterministic and stateless as specified.

Nico
--

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 11 May 2015 17:18:02 -0700

> derivation of k.  Instead I'd rather not have hardware like Andrey

This is a somewhat separate question about the hashing twice 
(https://www.ietf.org/proceedings/92/minutes/minutes-92-cfrg search for 
"twice"), but I view that the related concerns supports the idea of a 
random k esp. with protocols that deal with messages of unlimited size.

Nico: you are against the interpretation of EdDSA as done in 
https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-00#section-5. 
If you are against, consider what the code like "cat InFile | gpg 
--clearsign" suppose to do then? (I assume that this piping is what 
influenced this particular interpretation of EdDSA.)

Because pipes are unidirectional, M (v.s. H(H)) protocol forces the code 
to buffer the message into a temporary file. Creating a temporary file 
amplifies the concern in 
http://www.ietf.org/mail-archive/web/cfrg/current/msg06759.html (e.g. 
consider some setup with different privileges): there is a good chance 
that an implementation will do the second hashing on the temp file, but 
not the first (because the first hashing can be performed on the piped 
in content).

> should be deterministic and stateless as specified.

I generally agree with this. Just don't criminalize / recognize the 
benefit of random 'k' (with the security caveats).

---

From: Nico Williams <[email-masked]>
Date: Mon, 11 May 2015 19:44:37 -0500

On Mon, May 11, 2015 at 05:18:02PM -0700, Andrey Jivsov wrote:
> (https://www.ietf.org/proceedings/92/minutes/minutes-92-cfrg search
> for "twice"), but I view that the related concerns supports the idea
> of a random k esp. with protocols that deal with messages of
> unlimited size.
> 
> Nico: you are against the interpretation of EdDSA as done in https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-00#section-5.

If we need online signing for some applications, then we can have it,
either because those applications hash the message first, then sign, or
because we have two signature functions, one online one not.

> benefit of random 'k' (with the security caveats).

There's no IETF police.

Nico
--

---

From: David Leon Gil <[email-masked]>
Date: Wed, 13 May 2015 23:53:21 +0000

4, 2

--

I'm not sure I understand David's argument about 4. See Koblitz and
Meneze's rather dull recent paper for the details of how to do this:
http://eprint.iacr.org/2015/140

(And, indeed, OpenSSL and Go use similar constructions, both of which
predate the KM paper.)

--

Also, there is a need for encrypt-and-sign under some circumstances:
Suppose that (as for encrypted email in some cases) you want a mail server
to verify that mail is signed under an authorized public key, but not be
able to decrypt the mail.

In this case, it is easy to ensure unlinkability by an adversary who does
not know the public key by encrypting the message under the signature.
(Robert Ransom is credited for the observation that this should be
blindingly obvious in Bernstein's Elligator paper.)

In fact, one can achieve a slightly stronger goal with, e.g.:

h = hash(publickey || message || r)
p = hash(publickey || message)

sig' = (r || s) ^ p

where `hash` is an indifferentiable hash function with sufficient output
length, and `r` is the public nonce. (A slightly different construction is
needed for PRFs.)

In this case, an adversary must know *both* the public key and the message
to decrypt the signature.[*]

And the cost of achieving unlinkability is a single XOR.

--

Many thanks to Payman Mohassel and Juan Garay for very helpful
conversations on this and some related constructions.

Prior cites appreciated.

- David

[*] Note, however, that a construction like:

p = mac(publickey, hash(message))
h = mac(r, s)

does not achieve as strong as a goal. (This should be clear if you consider
the first construction as an AONT of the public key and message with the
signature.)
On Sun, May 3, 2015 at 2:00 PM David Jacobson <[email-masked]>
wrote:

>   If someone was foolish enough to do encrypt and sign, then there would
>> be a need to make identical plaintext not have identical signatures.  If
>> allow an optional random
> repeats, meaning an adversary knowing messages M1,M2 and their ciphertexts
> C2,C2 can test whether or not M1=M2. Signature randomization does not help
> prevent this, because signatures are verifiable given the public key and
> this can be used to detect repeats even with randomization. So this would
> not appear to be a good reason to keep randomization in the signature.
>
>  Mihir
>
>
>
>
>
> Mihir is right.
>
> signature allows randomization, the size of size of the signature will need
> to be larger.  Here is an intuitive argument.  Suppose that the size of the
> signature is 256 bits.  Somehow the message and the private key map
> somewhat uniformly onto those 256 bits.  For any given message and key,
> only one signature value is correct.  Now, I we add 256 bits of randomness,
> and them mix in in the obvious way.  Now for a fraction of about (1-1/e) of
> the signature space, there is a value of the input randomness that could
> have generated it.  That means that the verifier can't reject most
> signature values.  To avoid this, we have to have a larger signature, so
> valid values (for a given message and key) are sparse.  Consider that ECDSA
> with P-256 has 512 bit signatures.
>
> For this reason, I think allowing optional randomness as in proposal #4 is
> not just not helpful, but forces larger signatures.  For many uses, small
> signature are desirable.  So I retract my original support for #4.  Now I'm
> only supporting #2.
>
>
>   --David Jacobson
>
>
>
>
>

---

From: Alexey Melnikov <[email-masked]>
Date: Mon, 18 May 2015 19:16:53 +0100

> decide upon (i.e. both choices 1 and 2 allowed).
While some people were supportive of doing #3 (and some suggested that 
this might be a future topic after the main recommendation to the TLS WG 
is done), the vast majority of people preferred option #2. Nobody 
support the option #1.