On Tuesday, Sep 9, 2014 at 5:24 PM, Tony Arcieri <[email protected]>, 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
[email protected]
https://moderncrypto.org/mailman/listinfo/messaging
