[openpgp] Disadvantages of Salted Signatures

[Stephan Verbücheln <[e-mail]>]

Alternative title: Advantages of Deterministic Signatures

Hello everyone

Deterministic signatures have their own value. Especially with the
increasing popularity of ECC algorithms, because these are in
particular vulnerable to kleptographic attacks.

What is a kleptographic attack? The term kleptographic attack was
coined by Adam Young and Moti Yung more than 25 years ago for discrete-
logarithm-based signature schemes.[1]

A kleptographic attack can be summarized as follows:
1. A malicious blackbox implementation (e.g. PGP smartcard) can choose
the nonce in a way that allows the attacker to compute the secret key
from two signatures.
2. This is not news. Everyone here probably knows about nonce reuse and
related problems. However, the attacker can generate these two nonces
in a way that is provably impossible to detect (i.e., without breaking
the security of a cryptographically secure pseudorandom number
generator).
3. The attacker uses his own secret key which is required to detect
malicious nonces and compute the victim's secret key.
4. The core requirement for this attack is that the attacker beforehand
knows the Diffie-Hellman (DH) group parameters which are used for the
key and signatures. While with classic DSA, each PGP key basically has
its own DH group, elliptic-curve-based keys select one of a few
predefined curves. This makes the attack even more feasible.

Some years ago, I wrote down how the attack works on Bitcoin
transactions, which are basically ECDSA-signed messages.[2] The same
can be applied to signed PGP messages.

Deterministic signatures can be helpful to detect this kind of attacks.
For instance, if a PGP key is imported into multiple smartcards, then
they should give the same result when signing the same data.
In fact, the current version of GnuPG is doing exactly that when using
EdDSA (with the same timestamp).


In section 13.2. (Advantages of Salted Signatures) of the draft 
draft-ietf-openpgp-crypto-refresh-12, there are two motivations
mentioned for salted signatures.
The first is resistance to hash collision attacks with reference to
"SHA-1 Is A Shambles". This analysis seems to be plain wrong. I do not
see how the salt would make collision attacks any harder, let alone
raise the cost to second-preimage levels.
But even if they would, this is only relevant for almost broken hash
algorithms which should be avoided in the first place. SHA-1 was
reaching its end of life because 80 bits of attack complexity were not
unfeasible any more. The algorithm's additional weaknesses discovered
by some smart cryptographers made it crack a few years earlier, but it
would have been cracked soon anyway.
The second motivation is resilience to fault attacks. Here, the salt
looks to me like an effective countermeasure. However, this attack
appears to be quite exotic and requires the attacker to have some
access to the victim's vulnerable machine (e.g., shared cloud
hardware).
It further requires the victim to sign the same data over and over
again, which is not realistic in a practical scenario on the PGP layer
because the timestamp will be different for each signature. There is no
point in signing the same data with the same timestamp over and over
again because it will always have the same result. In the far-fetched
use case where the PGP user wants to sign over and over again with the
same timestamp but different results, he is free to add a salt to his
data.


As a conclusion, I would rather recommend against salted signatures.

Best regards
Stephan


[1]
https://www.researchgate.net/publication/221354983_The_Prevalence_of_Kleptographic_Attacks_on_Discrete-Log_Based_Cryptosystems

[2] https://arxiv.org/abs/1501.00447