Is this a safe way to verify public keys?

Question

I want to verify a public key like this:

1. Alice generates a public/private key pair for encryption
2. Alice generates a public/private key pair for signing
3. Alice signs a random 4-letter word + the public encryption key using her private signing key
4. Alice sends her public keys (both) and the signature to Bob
5. Alice sends the 4-letter word to Bob using a secure and trusted way
6. Bob verifies the public encryption key of Alice by verifying that the signature is created with the 4-letter word in the way described above.

This is what I am not sure about:

1. Is a 4 letter word enough?
2. Does verifying the signature verify that the public key is the original key and has not been altered by a "man in the middle", when the original message is the secret?

Background: I want to archive save exchange of public keys between too parties. But there is no trusted third party authority I could rely on.

But instead the two parties will meet in person at the beginning. At that moment they trust each other completely. One party can give the other a secret (for example on a sheet of paper).

Of course in theory the other party could give something back. But for reasons of user-friendliness I want to avoid this.

Of course the fingerprint of the public key could be the secret. But again, to make it user friendly, I want to make the secret as short as possible.

Answer 1

1. Is a 4 letter word enough?

It doesnt matter how long the word is as long as it can be considered unique and is kept secret. An attacker signing his public key with a lot of random sequences of 4 letters where one of them contains the correct sequence is unlikely to suceed as the amount of random combinations make the attack rather obvious.

2. Does verifying the signature verify that the public key is the original key and has not been altered by a "man in the middle", when the original message is the secret?

If the signature is valid, you definitly know that the owner of the (signature pairs) private key who also knows the secret 4 letter sequence gives you a public key, nothing else. It doesnt check if the key inside is a valid certificate, if the 4 letter sequence is correct or that this is the correct public key (the owner of the signing key pair can sign whatever he wants).

Now lets imagine you have a Man-in-the-Middle (MITM) at step 4, when Alice transfers the public keys and the signed 4 letter word to Bob. As there is no CA and we assume that Bob can not distinguish the certificate of Alice from the certificate of the MITM, the MITM could simply replace the public keys with his own, read the 4 letter word and sign the same word with his own key too. A signed word is easily accessible, so at the moment you sent it the MITM can simply read it and use it to replace all future data and be authenticated by Bob. Therefore, this is not a safe way to verify public keys.

Possible Solutions

• Exchange a hash (sha1 f.e.) of the fingerprint at step 5. It can still be considered safe enough if Bob only remembers the beginning and ending couple letters of the hash as it would be impossible for a MITM to create a certificate whose fingerprint's hash starts and ends exactly with the same couple letters.
• Use symmetrical encryption. Put your public certificate in a password protected (zip f.e.) archive and exchange this password.

By the way, you dont need two key pairs, you can sign & encrypt with the same keys.