[messaging] "Keybase Attack" on RSA signatures

[Max Krohn]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140909/0ee60a11/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140909/0ee60a11/attachment.sig>