Subject: [Cfrg] Exposing the private key by signing "too many times"

From: "Paul Hoffman" <[email-masked]>
Date: Tue, 12 Apr 2016 18:31:41 -0700

Greetings again. I regularly hear from non-cryptographers that they once 
heard that you have to be careful not to sign "too many times" with the 
same public/private pair because doing so will expose the private key. 
I'm interested in the history of this belief. Are there any papers about 
the history of signature algorithms where this might have been true, or 
papers on the history of this belief?

--Paul Hoffman

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 12 Apr 2016 23:01:48 -0300

Probably some confused bunnies who have been told that if you reuse a
random secret in DSA, bad things happen

On Tue, Apr 12, 2016 at 10:31 PM, Paul Hoffman <[email-masked]> wrote:
> heard that you have to be careful not to sign "too many times" with the same
> public/private pair because doing so will expose the private key. I'm
> interested in the history of this belief. Are there any papers about the
> history of signature algorithms where this might have been true, or papers
> on the history of this belief?
>
> --Paul Hoffman
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Paul Grubbs <[email-masked]>
Date: Tue, 12 Apr 2016 22:05:22 -0400

This might not be what you mean, but historically some of the first
signature constructions were what are called 'one-time signatures', which
means basically what it says. Modern signature constructions are proved
secure relative to a definition that allows multiple signings with the same
key, though. In the realm of hash-based signatures this still comes up,
because some hash-based signatures bootstrap a one-time or 'few-time'
signature to a many-time signature. This is (I think) how XMSS and SPHINCS
work, though I am not an expert in this area.

On Tue, Apr 12, 2016 at 9:31 PM, Paul Hoffman <[email-masked]> wrote:

> same public/private pair because doing so will expose the private key. I'm

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 12 Apr 2016 23:07:15 -0300

Ah yes, look at Lamport hash sigs, can only use those once!

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 13 Apr 2016 04:54:47 +0000

Date: Tue, 12 Apr 2016 18:31:41 -0700
   From: "Paul Hoffman" <[email-masked]>

One of the patented post-quantum candidates, the NTRU signature
scheme, exhibits this property -- summary and references can be found
at the Wikipedia article:

https://en.wikipedia.org/wiki/NTRUSign

---

From: "Manger, James" <[email-masked]>
Date: Wed, 13 Apr 2016 15:06:01 +1000

Sign "too many times" and you might be the victim of an adaptive chosen-ciphertect attack, a la Bleichenbacher's million message attack. That doesn't expose the private RSA key, but it does expose a symmetric session key encrypted for that key. This might contribute to the belief you mention.

--
James Manger

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Paul Hoffman
Sent: Wednesday, 13 April 2016 11:32 AM
To: [email-masked]
Subject: [Cfrg] Exposing the private key by signing "too many times"

--Paul Hoffman

---

From: William Whyte <[email-masked]>
Date: Thu, 14 Apr 2016 06:32:04 -0400

I think the concern isn't a crypto concern but an implementation concern. There's folklore knowledge of side-channel attacks, and folklore belief that every time you use the key it's vulnerable to a software attack. Root CA keys are airgapped because every time they're brought online there's a risk they are used to sign something they shouldn't. So this isn't a threat that can be addressed by looking at details of particular algorithms, it's to do with key usage.

It does seem like common sense that the longer a key's life, the greater the risk that it gets compromised while active, so having some key rollover policy is probably good practice.

Cheers,

William

On April 13, 2016 at 1:06:15 AM, Manger, James ([email-masked]) wrote:

-- 
James Manger 

-----Original Message----- 
From: Cfrg [mailto:[email-masked]] On Behalf Of Paul Hoffman 
Sent: Wednesday, 13 April 2016 11:32 AM 
To: [email-masked] 
Subject: [Cfrg] Exposing the private key by signing "too many times" 

--Paul Hoffman

---

From: Aaron Zauner <[email-masked]>
Date: Thu, 14 Apr 2016 20:20:24 +0700

> On 13 Apr 2016, at 08:31, Paul Hoffman <[email-masked]> wrote:
> 
> Greetings again. I regularly hear from non-cryptographers that they once heard that you have to be careful not to sign "too many times" with the same public/private pair because doing so will expose the private key. I'm interested in the history of this belief. Are there any papers about the history of signature algorithms where this might have been true, or papers on the history of this belief?

Could this be confusion with small DH subgroups and the `SSL_OP_SINGLE_DH_USE` option in OpenSSL? See CVE-2016-0701 for more details on the matter: https://www.openssl.org/news/secadv/20160128.txt

Aaron

---

From: Dan Brown <[email-masked]>
Date: Thu, 14 Apr 2016 14:44:43 +0000

Long ago DSA allowed biased ephemeral secrets, which Bleichenbacher exploited to extract the private key.

Not aware of history or survey papers on topic, sorry.

Some security proofs may have dependency on number of signatures, but that seems unlikely to lead to a regular belief among 'non-cryptographers'.

Intuitively, such a belief could arise naturally: info-theoretically each signature might leak some new small amount of info about the private key.

Not related to signatures, but there's also Gallant's attack against static DH :)

Is it CFRG's job to educate in such matters?

  Original Message
From: Paul Hoffman
Sent: Tuesday, April 12, 2016 9:32 PM
To: [email-masked]
Subject: [Cfrg] Exposing the private key by signing "too many times"

--Paul Hoffman

---

From: Thomas Pornin <[email-masked]>
Date: Thu, 14 Apr 2016 19:05:27 +0200

> Not aware of history or survey papers on topic, sorry.

The attack is described in this report from Serge Vaudenay (section 5):

   http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1002_reportDSA.pdf

Serge says that the attack was announced in February 2001; apparently,
according to that CHES 2013 article:

   http://www.iacr.org/archive/ches2013/80860105/80860105.pdf

the attack was also presented and discussed at an IEEE P1363 WG meeting
on November 15th, 2000.

To my knowledge it was never formally published.

Conceptually, this is a generalization of the dreaded "secret value
reuse". If you reuse the same k value in two distinct signatures (with
the same private key) then the private key is revealed. Bleichenbacher's
attack generalizes that result into leveraging a selection bias; plain
reuse just being an awfully large selection bias.

	--Thomas Pornin

---

From: David Jacobson <[email-masked]>
Date: Thu, 14 Apr 2016 10:40:51 -0700

Yes, CFRG should educate.

Standards often have informational sections.  We should include 
references to security proofs in an informational section.   The 
references should point out critical assumptions in each referenced proof.

In addition standards often contain a section on security 
considerations, which gives information on precautions the implementer 
must take to have the actual implementation be secure.   But we could go 
further and cite papers about the vulnerability.  We could also cite 
papers about vulnerabilities for systems similar  to but different from 
the standard, and mention how the standard avoids the vulnerability.

In addition, if things like side channel attacks are relevant, this 
should be mentioned, and the conditions under which the side channel 
attack is relevant should by mentioned.  (For example, timing attacks to 
signing are important if the device is a set-top box in the possession 
of a potential adversary, but would not be relevant to signing code or a 
certificate in an air-gapped secure signing room.)

   --David Jacobson

---

From: [email-masked]
Date: Thu, 14 Apr 2016 12:03:03 -0700 (PDT)

There are also several so-called "lattice attacks", mostly based on work done
on modular polynomial factorization by Dan Coppersmith.

AFAIK all of these attacks assume that either some bits of the ephemeral are
leaked (e.g., by a timing attack), or that there's some way to control the
value of some bits of the ephemeral key (e.g., so-called glitch attacks). In
such circumstances the results of some number (sometimes quite small) of
signature operations are used to extract the private key.

See for example:

	http://www.hpl.hp.com/techreports/1999/HPL-1999-90.pdf

				Ned