# Familiar key signing over video call

Say that a friend of mine and I have both generated new PGP keys, and we want to use a video call to verify each other's new keys because we live on opposite sides of the planet. While we could both somehow share our public key and then read back the fingerprint, reading a fingerprint is a bit cumbersome, especially given that we both have to do it.

After I came across this "problem", a potential solution dawned on me, but I wanted to check here whether it will actually securely verify the new keys.

1. I download what purports to be my friend's new key from somewhere.
2. I encrypt and sign a message containing two random English words using my friend's alleged new key.
3. We start the video call, and I tell my friend the first word in the email.
4. My friend decrypts the message and checks that the word was indeed the first word.
5. My friend then tells me the second word in the email (which I can verify since I sent the email).

I believe that if we both get our words "right" according to what was in my original mail, I can now trust that the key I have is my friend's new key. Furthermore, my friend can now trust that the key that signed that email is my new key.

While this may seem like a very roundabout way of achieving this, it is actually very simple to do if you're on a UNIX box:

shuf -n2 /usr/share/dict/words | tee /dev/stderr | gpg -sear <friends-key> | mail -s "Key verification keywords" <friends-email>


My question (finally) is now whether this scheme truly does verify our new keys, or whether there is some gaping hole I've missed?

Update 1: Come to think of it, the signature here can easily be forged as an attacker can just re-sign the encrypted blob with their own key. However, if the fingerprint is also included inside the encrypted part of the message, I believe it would still be secure.. The new command would be:

(shuf -n2 /usr/share/dict/words; gpg --fingerprint <my-key>) | tee /dev/stderr | gpg -sear <friends-key> | mail -s "Key verification keywords" <friends-email>


The friend would then check that the signing key has the same fingerprint as the one contained in the message before trusting it.

EDIT: I only say video call because it would be easier for someone to pretend they're my friend if all I had to go on was the voice.

-
Are you really sure this is faster and/or easier at all than just reading out loud the fingerprints / key ids? ;) –  Jens Erat Jun 8 at 23:19
Possibly not, but it's still fun to come up with new schemes and try to determine if they are secure or not. –  Jonhoo Jun 8 at 23:22
It is a fun exercise but we don't really deal with the command line here; we're more on the theoretic side. You already figured out your scheme is susceptible to a man-in-the-middle attack and to mitigate that would make the scheme unnecessarily complicated. Just use some phonetic alphabet and read out the fingerprints over the call. Much easier, much faster. Related fact: This verification problem is the reason why the PGP web of trust was invented, but you have the advantage of a face-to-face (or at least a close approximation). –  rath Jun 9 at 0:00
The question wass about the scheme itself though, not the commands. They were just there to illustrate how it could be done in practice. –  Jonhoo Jun 9 at 8:34

So your protocol goes like this:

• Alice generates a key pair $(a_{priv}, a_{pub})$ and sends $a_{pub}$ to Bob.
• Bob generates a key pair $(b_{priv}, b_{pub})$ and sends $b_{pub}$ to Alice.
• Alice generates a message $m$ and sends $Enc(Sign(m, a_{priv}), b_{pub})$ (or $Sign(Enc(m, b_{pub}), a_{priv})$, I'm not sure which of both is usually used by PGP) to Bob.
• Bob decrypts and checks the signature to get a message $m'$.
• By a video call both verify that $m' = m$.

Your key verification scheme is based on two ideas:

• If Bob did succeed to decrypt some message encrypted by Alice using $b_{pub}$, then Bob must be in possession of the corresponding private key $b_{priv}$.
• If Alice knows the content of a signed message which could be verified using $a_{pub}$, then Alice must have been the signer and be in possession of $a_{priv}$.

But this doesn't work in presence of a man-in-the-middle attack for the previous key exchange and the exchanged message.

Assume Eve is able to intercept all messages between Alice and Bob.

Then the attack goes this:

• A → E: $a_{pub}$
• Eve generates a new key pair $(a'_{priv}, a'_{pub})$.
• E → B: $a'_{pub}$
• B → E: $b_{pub}$
• Eve generates a new key pair $(b'_{priv}, b'_{pub})$.
• E → A: $b'_{pub}$
• A → E: $Enc(Sign(m, a_{priv}), b'_{pub})$
• Eve decrypts the message, strips the signature and re-signs and re-encrypts.
• E → B: $Enc(Sign(m, a'_{priv}), b_{pub})$
• Bob checks signature and decrypts, and gets the same $m$ as sent by Alice.
• Video call verification shows that "everything is okay".

If the message also contains parts of the key to be used, that would have to be changed by Eve as well, of course.

So no, you can't get around checking the actual finger print of the keys (or something derived from it).

-
I believe you've mixed up the keys used for encryption in A → E and E → B, but apart from that the attack seems reasonable. Oh well, reading fingerprints it is then. –  Jonhoo Jun 9 at 19:07
@Jonhoo thanks for the note, I fixed them. –  Paŭlo Ebermann Jun 9 at 19:37