Negotiate a secure connection without certificates?

Question

I would like to have a simple experience for a user for setting up a secure connection between two computers against a MITM attack. Something like the following:

A number (possibly base64) appears on both screens, the user verifies that the number is identical and clicks OK.

Is there a standard algorithm for this?

If not - would the following be secure?

1. Each computer sends the other its public signing key. And then on each computer:
2. The keys are concatenated.
3. Then hashed with PBKDF2 (or the like).
4. The user is then shown that hash on both computers, and clicks OK on both if they match.

Since an attacker can create signing keys quickly (since the attacker doesn't care that they be prime-based) trying for keys that will create the same hash as the one shown, the hash shown to the user would need to be relatively long (~100 bits?).

Answer 1

Yes, the procedure outlined insures that the public keys are genuine on both sides, assuming both computers are trusted, have generated the public/private key pairs, kept the private key secret, ensured that their own public key is in the data entering the hash, and that's wide enough. But notice:

• The order in which the public keys is concatenated must be agreed upon; lexicographic order of participants (or of their public key) will do.
• A collision-resistant hash is required (not only a preimage-resistant one as implicit in the question's "~100 bits"), because an active adversary can know the public key $A$ and $B$ of both parties, and is then content finding $A'$ and $B'$ (for which s/he knows the corresponding private key) with $H(A\|B')=H(A'\|B)$; thus the hash could be SHA-256 (50 characters among an alphabet of 35, or 43 characters in Base64) for 128-bit security.
• An entropy-stretching hash like PBKDF2 allows to reduce the hash size by $2\log_2(n)$-bit for $n$ iterations, say by 40.6-bit for 1300000 iterations, to 215.4-bit (42 characters among an alphabet of 35, or 36 characters in Base64).
• Limiting the amount of time between key generation and acceptance of the keys allow to further reduce the hash size.

---

A standard procedure in PGP/GPG is that each party `

• Have generated their public/private key pairs (that can be a while ago);
• Sends the public key (self-certified) to the other party, by any channel no matter how untrusted (e.g. a public key server);
• Import the other side's alleged public key;
• Have PGP/GPG compute the "fingerprints" of the keys, which essentially are hashes of the public keys (one's fingerprint can be pre-computed at key generation).
• By phone or other channel trusted for integrity, insure the fingerprints match; dialog could go:
  • hi Bob, this is Alice, I'll read you the fingerprint of my key, please cross-check: 39 4D 6F 33 9A 37 83 A0 C3 D3 33 4D AD A4 A9 C7
  • hi Alice, this is Bob, I checked your fingerprint 39 4D 6F 33 9A 37 83 A0 C3 D3 33 4D AD A4 A9 C7, I'll read you mine, please cross-check: 534E 287A 7D98 B1F7 0323 6F5F BE83 6B66 BBDD FC14
  • hi Bob, this is Alice, I checked your fingerprint 534E 287A 7D98 B1F7 0323 6F5F BE83 6B66 BBDD FC14, we are all set.

Yes there are two different formats of fingerprint around (128-bit and 160-bit); yes this is not entirely immune to social engineering or sophisticated attacks on the audio channel; yes many users only really read/check some of the beginning and a little of the end of fingerprints, and skip reading back, making said attacks less unlikely.

Notice that if the parties play fair game, the hashes used for PGP/GPG fingerprint only need (second) preimage-resistance, thus having two fingerprints does not increase the amount of data to verify compared to the system in the question. Update: by play fair game I mean that none of the parties exchanging their public keys will purposely generate two public/private key pairs with the same fingerprint, then try to repudiate a signature on the ground that their public key is not what the other party pretends.

Answer 2

There are two possible standard ways to handle this, depending on whether you just want to verify this connection or whether you want to verify another device.

First note that all MITM-attacks (by name) work in the way that there is an adversary in the middle of the two legitimate clients. This trivially implies that both clients will see different Diffie-Hellman secrets (if DH is used) because the attacker has to re-encrypt between the connections. It also means that if the handshake¹ completes without an error, both parties see the attacker's public key as their peer's key.

First let's consider the connection-based method. For this I'll assume that DH is at the core of the handshake. Example applications include ad-hoc pairing with a bluetooth device with a small screen or encrypted voice comms with a small screen. So to verify the connection, verifying that a (stretched) hash of the shared secret is the same suffices, however don't forget to do this in a way such that it doesn't expose the actual secret key. For this to be secure, obviously, it needs to be hard to find $X$ such that $H(X^a)=H(X^b)$, which has expected complexity of about $2^n$ with $n$ being the number of bits that have to agree in a fixed subset of the output of $H$. So if you want this to be reasonably secure, you want to about $n=80$, so for the work-factor-increase $p$ (iteration-count) $p\cdot 2^m\geq2^n$ should hold with $m$ being the amount of bits displayed to the user. So if you display 16 base64 characters to the user, you encode $16 \cdot 6=96$ bits of information and thus an attacker would have to try about $2^{96}$ keys which is infeasible. Note that because you authenticate the DH secret, only the connection is authenticated.

The alternative standard way is to display a hash of your own public key and the received public key (the valid key from the handshake). In this case you authenticate the other device in the sense that if the signing keys don't change across multiple connections all of these connections are authenticated with one comparison. Much of the above analysis applies as well here, with the difference that you need to find a 2nd-preimage with the hash of the legitimate peer's public key, ie find a public key $pk_e$, such that $H(pk_e)=H(pk_b)$. So if you display 16 base64 characters of the hash, an attacker needs to try $2^{96}$ keys which is infeasible. This method is advantageous to your solution in that it allows users to post their public key hashes to social media or similar decentral out-of-band channels.

The method you proposed is a hybrid of the first above one and the second one. The analysis of the first one applies and the benefits of the device-authentication of the second one are inherited, so if it reflects your usage scenario well, it will work.

---

^{1: I mean a handshake here that uses long-term signing keys to establish a shared secret in a secure manner if said keys are correct.}

Answer 3

If you have a side channel where you can verify a string is identical you can simply do a Diffi Hellman key exchange and then verify both sides have the same resulting key. If the side channnel is secure from evesdroppers you can directly compare the key. But you would probably prefer to compare a hash of the key. This also allows comparing something much shorter then the actual key. For example I have seen systems for voice communication which after setting up the key the parties are expected to read out a verification number, but this simply assumes the mitm can not take the place of both parties and read out a different number to each. With nothing pre shared preventing man in the middle is tricky. If you have a mitm resistant side channel which is public and very low bandwidth the above solution works. If it is high ebough bandwidth simply do DH key exchange over it.

Edit: to ensure the user can compare a short hash we should add a large random nounce before hashing the key. So a mitm won't be able to make keys which will collide with a truncated hash.