# How can we authenticate a public key with limited secure side channel?

I'm looking for a method for 2 peers verifying the authenticity of each other's public key that was transfered over an insecure channel and where the needed secure side channel can only transfer short values (significanlty shorter than the length of a cryptographic hash) but in both directions. Are there standard methods for this?

Otherwise, the most naive approach would probably be only comparing a small part of each others public key, e.g. the first few bytes, or alternatively the first few bytes of a cryptographic hash of the keys. In this question it is already mentioned that this is not a good method when the prefix gets too small, but couldn't this be somewhat compensated by also exchanging randomized starting positions (instead of starting the comparison at the beginning or any other fixed position) over the secure channel to minimize the probability that a man-in-the-middle attack works?

• Can you be concrete about the data-rate of the secure channel? Why can't it transfer 256-bit? How much can it (sanely) transfer? – SEJPM Jan 7 '18 at 20:25
• Well, in my use case that would be verbal communication and the understandable unwillingness of users to read each other very long numbers ;) I was wondering if there is a method to make it reasonably unlikely for an attack to succeed when it is limited to let's say 8 decimal or hex digits each peer has to give the other, or something like that. – zse Jan 8 '18 at 8:02

PGP supports a so-called fingerprint of the public key, which really is a 20-byte hash expressed in hexadecimal as 10 groups of 4 characters. The recommendation is to read it over the phone. That's doable, but seldom done.

In the context, we only need second-preimage resistance, thus 20 bytes are a bit overkill. With a slow password hash (scrypt, argon2) we can safely get this down to 5 groups of 5 characters in a 25-character alphabet 0123456789CFGHJKMPRTVWXZ+, for $5\cdot5\log_2(25)>116$ bit.
Note: that alphabet is likely to produce reasonably safe-to-spell-at-work codes, and is easily keyable if the software remaps Sto 5, Bto 8, ODQto 0, IJLto 1, UYto V, and so on)

With a challenge-response we can reduce this further. We can use a slow password hash using the (hash of) the public key as password and the challenge as salt.

• please enter CK9Z 5H7C what do you get ?
• got 01W8 RR4G

A substitution has probability $<2^{-37.1}$ (one in 150 thousand millions) of going undetected, which is perfectly fine in practice.

• You can also pick a (safe-for-work!) word list of a nice round size and use that, as an effectively much larger but more memorable alphabet. (Expurgating words that participate in multi-word double-entendres left as an exercise for the reader.) – Squeamish Ossifrage Mar 14 '18 at 20:32
• Sounds reasonable, though as I'm no expert I'd prefer a more off-the-shelve solution than coding that up myself. SRP seems to provide that for me – zse Mar 17 '18 at 15:05
• @zse: SRP will require the verbal exchange to A) be done with confidentiality, when the solution used by PGP and variants that I propose only require integrity, which is much easier to get. B) as an aside, occur before some sizable exchange of information (thru a channel protected using SRP). – fgrieu Mar 17 '18 at 17:27

It seems SRP (resp. TLS-SRP) is what I'm looking for, where a short shared one time password from the secure side channel is used only once for the authenticated secure exchange of the public keys.

• I have no idea why this was voted down; it sounds like a perfectly reasonable approach... – poncho Mar 14 '18 at 17:12
• @poncho: SRP requires too much bandwidth, I guess. – fgrieu Mar 14 '18 at 17:57
• @fgrieu: I didn't see any tight bound on the bandwidth used over the insecure link. Yes, the problem states a tight bound on the secure link; however that's just an exchanged shared password that SRP will authenticate with – poncho Mar 14 '18 at 18:09
• I do not see at all how SRP would be used here. The stated goal is "verifying the authenticity of each other's public key that was transferred over an insecure channel" and the (other, later) "needed secure side channel can only transfer short values" and "would be verbal communication". Thus we have two problems: 1) that secure side channel can reasonably be assumed to have integrity, but not confidentiality. 2) We do not seem to be in a position to re-establish a better-than-low-bandwidth channel. – fgrieu Mar 14 '18 at 20:06
• I guess I haven't explained it very well: The idea is to use the secure (verbal) side channel for exchanging a short one-time password. This is used for a single SRP connection that is then an authenticated communication medium where the public keys can be transferred again / verified. And I assumed confidentiality for the secure side channnel. – zse Mar 17 '18 at 14:50