# Negotiate a secure connection without certificates?

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 singing 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?).

• I think the standard way to do is to hash the DH secret with a specific label and then stretch + convert that to numbers. – SEJPM Jul 17 '17 at 17:56
• @SEJPM I'm assuming you're referring to a Diffie–Hellman key exchange. As far as I can tell - that assumes there is no Man-In-The-Middle there. If there were - you might think you're sharing a secret with the "receiver" but both you and the receiver are sharing a (different) secret with the MITM. Am I correct? – ispiro Jul 17 '17 at 18:06
• Maybe you can use password authenticated key agreement schemes. There exists a lot of different variants, like EKE, PAKE, SPEKE, and especially PACE which is now used in electronic passports. – user27950 Jul 17 '17 at 19:25
• @Cryptostasis Thanks. But that would require the user to type in a password/number. I would like to avoid that if possible. – ispiro Jul 17 '17 at 19:33
• @fgrieu if they match means - if the numbers on both computers' screens are the same. The computer can't know that the number on the other computer is the same - for all it knows - it created a hash from its own key || the MITM's key, and the other computer might be showing a hash of its key || the MITM's key. – ispiro Jul 17 '17 at 20:52

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.

• Thank you for your detailed answer. I have some questions regarding it, though. a) You are, of course, correct in that a collision resistant hash is required. But why do you say that I implied only a preimage resistant one? Is it because of the length? Is 100 bits considered safe for preimage resistance but not for collision resistance? I meant using only 96 bits of a longer hash such as SHA-256. Would that be fine? b) Why do you require Alice and Bob to read back the hash? Is it just a precaution in case they heard wrong? – ispiro Jul 18 '17 at 11:42
• c) I don't understand the last paragraph. Did you mean that until that point you assumed that Alice and Bob might cheat each other, and that if that is not the case then they can use 96 bits as in my suggestion? (My case, according to this is indeed fair game.) – ispiro Jul 18 '17 at 11:42
• @ispiro: I hopefully clarified my last paragraph. As explained in my second bullet, even if the genuine parties are honest, the shceme of the question is not secure with 96-bit hash if the honest parties public keys have (both) been prepared in advance and made public, and the attacker is active. – fgrieu Jul 18 '17 at 11:56

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 handshake1 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.

• Thanks. I would, indeed, be authenticating devices (of which the signing keys will persist) so - the second case. Though I'll reiterate the point that though the attacker will be expected to need ~$2^{96}$ "keys" - those keys don't have to be prime-based, since the attacker doesn't care about their security, and therefore the attacker could create them much quicker than creating real key pairs. – ispiro Jul 17 '17 at 20:10
• @ispiro while they don't have to be prime-based, it isn't even feasible to count to $2^{96}$ which is even easier than generating keys. – SEJPM Jul 17 '17 at 20:11
• Yes. I didn't mean to contradict you. I just meant that that has to be kept in mind (if I want to lower the number of digits shown to the user). – ispiro Jul 17 '17 at 20:12
• This method ... allows users to post their public key hashes to social media or similar...` - I don't understand this part. Since the created hash is a hash of a pair of keys - one of each device - this hash won't help anyone but those two to communicate. – ispiro Jul 17 '17 at 20:42
• @ispiro well, this statement relates to the variation on your scheme which is to hash and present each key alone and not as a pair ;) – SEJPM Jul 17 '17 at 20:44

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.

• Thanks. But the only side channel is the user's memory. And if possible, I would like to avoid the user having to type in a password. – ispiro Jul 17 '17 at 19:35
• If the user can compare a number on both sides then comparing a short hash of the DH key will work well. If it's two users without a shared secret certificates or a side channel, I do not believe this is possible. Because any protocol could be done also by the MITM twice once with each side. You have to have something the MITM can't do. – Meir Maor Jul 18 '17 at 3:38