Discussion of secure messaging protocols ()

Tony Arcieri | 9 Sep 23:24 2014

"Keybase Attack" on RSA signatures

Keybase attempts to bind user identities on social media to their PGP keys by having users publish an RSA signature under an unknown key, which Keybase refers to as a "proof". The (allegedly) signed message contains a link to their Keybase identity, but contains no information about their public key fingerprint.

After clicking on the link in the message we're taken to the Keybase web site where their alleged public key is listed. We are then asked to verify this key is authentic by checking if the digital signature in the original message verifies.

However, is this actually secure? Or more specifically:

Can we produce an RSA keypair such that an existing digital signature will verify under it if we control both the private and public key?

For the purposes of this problem, let's say it doesn't even need to be a good / secure RSA key, just one that the "proof" signature verifies under.

I'd also note that, if someone does have a solution to this problem, it would probably be good to responsibly disclose to Keybase ;)

--
Tony Arcieri

_______________________________________________
Messaging mailing list
Messaging <at> moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

headers

Max Krohn | 9 Sep 23:52 2014

"Keybase Attack" on RSA signatures

On Sep 9, 2014, at 5:24 PM, Tony Arcieri <bascule <at> gmail.com> wrote:

Keybase attempts to bind user identities on social media to their PGP keys by having users publish an RSA signature under an unknown key, which Keybase refers to as a "proof". The (allegedly) signed message contains a link to their Keybase identity, but contains no information about their public key fingerprint.

Thanks for taking the time to check out keybase and to scrutinize how it works, we greatly appreciate it.

First, it’s worth mentioning that where possible (on github, reddit, hosted websites, etc), we ask that users to post full PGP signatures. Where space constrained (Twitter, DNS TXT entries), we ask them to post the hashes of these PGP signatures. We are assuming in the latter cases than an adversary can’t find another signature that hashes to the same hash (2nd preimage resistance of SHA-256).

After clicking on the link in the message we're taken to the Keybase web site where their alleged public key is listed. We are then asked to verify this key is authentic by checking if the digital signature in the original message verifies.

However, is this actually secure? Or more specifically:

Can we produce an RSA keypair such that an existing digital signature will verify under it if we control both the private and public key?

A Keybase “proofs” is a signatures of JSON object that includes: (1) the username on keybase; (2) the username on github (or twitter or whatever); (3) the user’s PGP fingerprint; (4) a hash of the previous signed message. So the adversary would have to come up with a hash collision in addition to generating the correct signature. Granted, it’s only a SHA1 hash collision since we’re using RFC4880-style PGP fingerprints.

Here’s an example of such a proof and the JSON object signed: https://gist.github.com/maxtaco/8847250

I'd also note that, if someone does have a solution to this problem, it would probably be good to responsibly disclose to Keybase ;)

Thanks! Please do let us know of any vulnerabilities you might find, obviously Keybase is worse than useless if the crypto is broken.

_______________________________________________
Messaging mailing list
Messaging <at> moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

headers

Tony Arcieri | 10 Sep 00:07 2014

Re: "Keybase Attack" on RSA signatures

On Tue, Sep 9, 2014 at 2:52 PM, Max Krohn <themax <at> gmail.com> wrote:

A Keybase “proofs” is a signatures of JSON object that includes: [...] (3) the user’s PGP fingerprint

Sorry, I must've glossed over this. It would seem to provide an immediate defense to forging a keypair under which the signature would validate, however it seems in conjunction with a SHA1 collision that allows the replacement of the fingerprint in the original message, this could be potentially problematic.

--
Tony Arcieri

_______________________________________________
Messaging mailing list
Messaging <at> moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

headers

Dennis E. Hamilton | 10 Sep 05:43 2014

Re: [messaging] "Keybase Attack" on RSA signatures

Comment below.

Original Message

----------------

From: cryptography [mailto:cryptography-bounces+dennis.hamilton=acm.org <at> metzdowd.com] On Behalf Of Tony Arcieri
Sent: Tuesday, September 9, 2014 15:07
To: Max Krohn
Cc: messaging; Crypto
Subject: Re: [Cryptography] [messaging] "Keybase Attack" on RSA signatures

On Tue, Sep 9, 2014 at 2:52 PM, Max Krohn <themax <at> gmail.com> wrote:

A Keybase “proofs” is a signatures of JSON object that includes: [...] (3) the user’s PGP fingerprint

--
Tony Arcieri

I am not certain how this can work.

The fact that there is a fingerprint included in the message that keybase.io has be signed with my private key does not mean that determines the public key certificate that is used for verification of the signed message. If someone else finds one of my claims, they should use my keybase.io ID to fetch the key to use in verifying the signed message for themselves. I.e., if they want to check the message at http://orcmid.com/keybase.txt, they should go to keybase.io/orcmid to get my public-key certificate if they don’t have it already.

Now, if you could forge a message such that it verifies with an existing affixed signature, and the message is even intelligible, that would be a remarkable action against public-key technology. It would mean a lot more than there being a defect in keybase.io protocols for association of identifiers with an entity having authority over a private key. Not only would you have found an SHA1 collision, let’s say, but you are able to have the modified message still look like a JSON plaintext and be unnoticeable as a crafted collision. There’s just no place to do that in these plaintext claim documents.

Since the readable plaintext in those posted claims is not the actual signed message, but a statement about what the signed message is, it is possible to be misleading. But if the signed message block that is on that page is altered, keybase.io will detect that on periodic verification of the file at that URL.

_______________________________________________
The cryptography mailing list
cryptography <at> metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

headers

Tony Arcieri | 10 Sep 06:15 2014

Re: [messaging] "Keybase Attack" on RSA signatures

On Tue, Sep 9, 2014 at 8:43 PM, Dennis E. Hamilton <dennis.hamilton <at> acm.org> wrote:

Now, if you could forge a message such that it verifies with an existing affixed signature, and the message is even intelligible, that would be a remarkable action against public-key technology.

The strength of the signature comes from the key. In the case of Keybase, we don't know we have the right key, and are trying to use the signature to determine that.

As I've discovered from this thread, the dual-share key-share attack is able to produce a keypair such that an existing digital signature will verify under it. If we can confuse the victim into verifying a signature under an attacker-controlled key, the signature will appear valid even though it was produced under a different key.

This is necessary but not sufficient for an attack against Keybase however, since the message being signed contains the key fingerprint, which I wasn't aware of at the time I started this thread.

--
Tony Arcieri

_______________________________________________
The cryptography mailing list
cryptography <at> metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

headers

David Leon Gil | 10 Sep 02:43 2014

Re: "Keybase Attack" on RSA signatures

On Tuesday, Sep 9, 2014 at 5:24 PM, Tony Arcieri <bascule <at> gmail.com>, wrote:

Keybase attempts to bind user identities on social media to their PGP keys by having users publish an RSA signature under an unknown key, which Keybase refers to as a "proof". The (allegedly) signed message contains a link to their Keybase identity, but contains no information about their public key fingerprint.

After clicking on the link in the message we're taken to the Keybase web site where their alleged public key is listed. We are then asked to verify this key is authentic by checking if the digital signature in the original message verifies.

However, is this actually secure? Or more specifically:

As you've noted, what keybase.io is doing appears to be fine; they include a lot of information about the public key in their proofs. It would be preferable to include the public key itself, or a strong hash of it.

Can we produce an RSA keypair such that an existing digital signature will verify under it if we control both the private and public key?

Yes; this is a dual-share key-share attack. It works only if you allow users to choose arbitrary public exponents. You just create a smooth enough modulus that you can solve the discrete log problem on its component primes; this isn't incompatible with the modulus being difficult to factor.

(This can also be done, in theory, for ECDSA, but no implementations that I know of have made the mistake of permitting users to specify arbitrary base points.)

For the purposes of this problem, let's say it doesn't even need to be a good / secure RSA key, just one that the "proof" signature verifies under.

Indeed; as best I can tell, keybase.io's OpenPGP implementation is not checking any of the RSA cryptosystem's validity conditions. (Neither does Google's E2E. GnuPGP and PGP check some, but not all.) What RSA public key consumers should check, in rough order of importance:

gcd(n, e) == 1

n mod 2 == 1

1 < e <= 2^16+1

is_prime(e)

(Note that the last two are more restrictive than the sufficient conditions for validity. There is no particular reason to be more lenient, however. It is also nice to check that n can't be factored by trial division or random ECM instances for rho, lambda, and p-1, but this is impractical for JS implementations.)

_______________________________________________
Messaging mailing list
Messaging <at> moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

headers

Maxwell Krohn | 10 Sep 14:26 2014

Re: "Keybase Attack" on RSA signatures


> Indeed; as best I can tell, keybase.io's OpenPGP implementation is not checking any of the RSA
cryptosystem's validity conditions. (Neither does Google's E2E. GnuPGP and PGP check some, but not
all.) What RSA public key consumers should check, in rough order of importance:
> 
> gcd(n, e) == 1
> n mod 2 == 1
> 1 < e <= 2^16+1
> is_prime(e)
> 
> (Note that the last two are more restrictive than the sufficient conditions for validity. There is no
particular reason to be more lenient, however. It is also nice to check that n can't be factored by trial
division or random ECM instances for rho, lambda, and p-1, but this is impractical for JS implementations.)

Thank you for these suggestions, I’ll incorporate them into the Web client. The command-line client
shells out to GnuPG so should be partially covered.

Are there analagous checks recommended for DSA and ECDSA keys?

_______________________________________________
Messaging mailing list
Messaging <at> moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging