[messaging] On Signed-Only Mails

[Trevor Perrin]

On Wed, Dec 7, 2016 at 11:36 AM, Bjarni Runar Einarsson
<bre at pagekite.net> wrote:
>
> Signatures don't just prove that the content is authentic, in
> practice they also work in the other direction - associating
> content and online identity with the signing key.

Like I mentioned earlier, that's an incorrect use of signatures [1].

The standard model for signature security is EUF-CMA ("Existential
Unforgeability under Chosen Message Attack").  This means that an
attacker given a public key and signing oracle can't output a valid
(message, signature) pair unless the message was submitted to the
signing oracle.  This is what all popular signature algorithms are
designed to achieve.

You're relying on a different property:  An attacker given (public
key, message, signature) can't output a *different* key pair with a
public key that also verifies the message.

This is much less-studied, but generally referred to as "Duplicate
Signature Key Selection", and it's known that some signature
algorithms don't resist this [2].

For example, consider PGP's use of DSA signatures.  According to RFC
4880, the public key contains integers (p,q,g,y).  Section 4.4 of [2]
describes how an attacker can take an existing message and signature
from public key (p,q,g,y) and create a new key pair with public key
(p,q,g',y') that also verifies the message.

A complicating factor is that PGP signature packets include a 64-bit
key ID which is a hash of the public key.  However, that just requires
the attacker to randomize the attack and try around 2^64 calculations
until he finds a matching key ID, which might be feasible for a
state-level attacker.

This might play out differently for different signature algorithms
(e.g. Ed25519 wouldn't give the attacker the same freedom to change
the "g" or "y" values; the RSA analysis is different).  Also, it's
possible that various complications might prevent or mitigate the
attack:
 * extra verification checks in software might reject "weird-looking"
public keys
 * the 64-bit key ID reduces attacker freedom and increases cost
 * verifying multiple signatures might prevent the attack
 * users might manually verify the fingerprint after retrieving the key

But this is still a confused and risky use of signatures, IMO.

Trevor

[1] https://moderncrypto.org/mail-archive/messaging/2016/002287.html
[2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.1051