[messaging] "Keybase Attack" on RSA signatures

[David Leon Gil]

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.)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140909/d45951d1/attachment.html>