Can signing too much compromise a private key?

Question

Can a collection of many messages signed with the same private key be abused to either forge signatures so some (but not all possible) messages, or even worse to reconstruct that private key with less effort than from the public key?

Answer 1

If the signature algorithm is any good (and used properly with large enough keys which were generated in a correct and suitably random way), then, in practice, the answer is no: having access to many existing signatures does not allow the attacker to forge new ones, let alone recompute the private key.

From a theoretical point of view: most (actually all) signature scheme begin by hashing the message to be signed, and the signature is actually computed over the hash value. Therefore, if the attacker has an existing signature S for message M, which hashes to h(M), and finds a message M' such that h(M) = h(M'), then S is also a valid signature for M' ("valid signature" means "a signature that will be accepted by verifiers"). Therefore one possible attack way is to try many variants of a phony message M' until one is found which hashes to the same h(M) than an existing signature, at which point the attacker has forged a new signature (more precisely, has successfully recycled an existing signature for a new message).

This is a second-preimage attack on the hash function. Having many existing signatures gives more targets for the attacker, which makes that attack easier. But easier is not easy. A "normal" signature algorithm will use hash functions which are strong enough and with a wide enough output that second-preimage attacks are not feasible, for any practical number of targets. To put some figures under it: with a 160-bit hash function (e.g. SHA-1), the cost of a second-preimage attack with one target is about 2¹⁶⁰; if the attacker can gather one million existing signatures, cost drops to about 2¹⁴⁰: that's one million times easier, but still way too hard (e.g. see there).

---

Note the fine print, though: I insist on the algorithm being used properly. For instance, consider DSA (or its elliptic-curve variant ECDSA). When computing a signature, you need to generate a random value k chosen uniformly in the [1..q-1] range for a given prime integer q (a new random k is needed for each signature). If the choice is biased in some way, this might be exploited for a key recovery attack. An extreme case is the Sony-PS3 debacle, where they used a fixed value of k, always the same regardless of the message to be signed. This is very wrong: two known signatures suffice to rebuild the private key. More generally, Bleichenbacher has shown (a dozen years ago) that if k is chosen by taking a random string of bits of the same size than q, then reducing modulo q, then the slight bias is sufficient to rebuild the private key from about 2⁶³ known signatures (for a 160-bit q).

Of course, in that situation, the problem is not allowing the attacker to see many signatures, but using the algorithm improperly. Implementation of cryptographic algorithms is hard (kids, don't do it at home !).

Answer 2

No, at least not for modern signature schemes. The attack/concern you describe is similar to the common attacks considered when doing a security proof. In particular the adaptive chosen-message attack is most related to what you describe.

In this attack the attacker submits a message to the signer, who returns the signature of the message. The attack then chooses another message (based on information gained from the first signature) and the signer signs that message. They continue this a long as the attacker desires.

Once the attacker is done, they are required to forge a signature for a message that was not queried during the first process. Modern signature schemes have been proven secure against this type of attack (for example RSA-PSS).

Modern ciphers have also been proven secure against attacks where an attacker might use information gained from signatures to get the private key.

Answer 3

It can, potentially, e.g. if the data is video frames, and the mode of operation is ECB or there is no random IV, by predicting what what is changing on the source data, it's possible to recover the key. This is the case for some satellite encryption for example.