I'm working on a solution where an iPad should connect to a server software running on a laptop using TLS with a self-signed certificate that was automatically generated on the laptop during the installation of the software there. I need to make sure there is no man-in-the-middle attack, so the obvious solution would be to take a hash of the cert with a function that is second preimage resistant and show the hash on the laptop and iPad.

The problem is that carefully comparing all the digits of a SHA-256 hash, for example, takes a while so I'd rather have a method that is (almost) as secure and works by comparing only 10 digits or so.

In principle that must be possible because the numeric comparison protocol of Bluetooth works like that. Details see on page 13 of this document: http://u.cs.biu.ac.il/~lindell/PAPERS/BT-numeric.pdf

Is there an easy method or protocol to shorten the string of digits that has to be compared but without too much overhead? Re-implementing the way this is solved for Bluetooth seems like a lot of work.

  • $\begingroup$ Note: this is a task that is not solved in a satisfying way yet. Signal and WhatsApp face a similar problem and they use 40-digit codes and / or QR-codes for this. $\endgroup$ – SEJPM Jun 21 '16 at 18:11
  • $\begingroup$ I think the messenger apps need to solve a different (harder) problem because there's no direct communication between the two phones when the users compare their fingerprints $\endgroup$ – flo von der uni Jun 21 '16 at 18:51

TL;DR: Using words instead of strings / images may be a good solution for short, easy-to-verify codes and using locality / time dependent verification codes strengthens short hashes as would using password-hashes.

Additionally to the improvements to comparability of the hash proposed by A. Toumantsev, I will propose three extra measures which I believe may be more unconventional than his solution but will adapt to your situation in a better way.

The challenge you're facing

You need to reduce the output size so much that a user won't get tired comparing two outputs, making the comparison short and / or interesting is the obvious solution.
At the same time you need to ensure that the output is not too short, or an attacker will be able to brute-force keys with the same output and thus will be able to fool the user and accept a man-in-the-middle attack.

Improvement 1: Don't use images or QR-codes, use words!

Images tend to be difficult to compare properly and chances are that the user screws up the comparing process as much he can do with long number strings, in fact if the image is high-resolution it may actually prove more difficult to do a proper comparison.
Randomly selecting a word in the user's native language for each byte (or maybe two bytes) and showing the user a "sentence" consisting of 16-32 such words may actually be feasible for full comparison. This would then benefit from the Stapled Horse batteries effect and be easier to remember / check, much like passphrases are easier to remember than passwords.
Of course this only a suggestion and actual tests are required in order to find the most effective solution.

Improvement 2: Buy yourself strength by imposing time limitations

You are in the lucky situation that the parties wanting to verify each other's public key can communicate. This way you can randomize the verification process, because if an attacker found a key that passes your 64-bit test, he will probably fail your randomized test, so just let both devices exchange a random nonce and display the properly encoded $\operatorname{HMAC-SHA256}_{\text{Nonce}}(\text{PublicKey})$ for verification to the user. If you let this HMAC expire after an hour or so, you effectively only give an attacker that time amount for finding an appropriate second-preimage.

This trick with a 128-bit nonce would allow you to reduce the shown value's size to somewhere around 64-128 bit (less would slowly become dangerous again) while still maintaining strong security.
You may also want to give the user an option to mark a certificate / key as "verified" for this method.

Improvement 3: Password hashes

You can combine the above three methods with a password-hash that takes a few hundred milliseconds on your devices (using the nonce as the salt and the key as the password). This way an attacker has to spend a considerable amount of effort for each key generation, slowing down any brute-force attack attempts. With this method you can probably gain 10-20 "bits" of security without any problems, allowing you to shorten the displayed value even more.

  • $\begingroup$ Hmm, I like the idea of a time-limited key check value. Good one :) $\endgroup$ – Maarten Bodewes Jun 21 '16 at 19:37

I'm not commenting on the security side of the solution, there are real experts here who can help with this (or turn your idea right down ;) ).

However, assuming your solution (with SHA256) is acceptable and secure, your main problem seems to be that "carefully comparing all the digits of a SHA-256 hash .. takes a while".

Indeed, comparing a string of 64 hex digits is not an easy task for a human, so - why not think in the direction of presenting the same information in some human-friendly form?

Off the top of my head - let's have a dictionary of words (or images). Let each hex byte (00-FF) be used as an index to that dictionary. As a result we have a list of 32 words (or images) on the screen...

I'm sure you've got the idea...

Idea #2: Conversion (of some sort) from Hex digits into Latin alphabet letters (maybe plus decimals, maybe plus punctuation marks as well) - still much more readable than hex.

I have been reliably informed that the idea is perfectly on-topic on Cryptography.SE

  • $\begingroup$ Au contrare, human interaction with cryptographic protocols is an active topic in my opinion. I think PGP uses a similar scheme for key fingerprinting. $\endgroup$ – Maarten Bodewes Jun 21 '16 at 14:29
  • $\begingroup$ @MaartenBodewes Even better, then. I'll edit my answer accordingly. To show off a bit ;): I genuinely coined this idea on my way from a smoking break to the office but, while I was typing it, I thought that this field just must be well-developed because it has so many applications in our modern life.... Thanks for upvoting. $\endgroup$ – tum_ Jun 21 '16 at 14:38
  • $\begingroup$ Idea #2 basically would come down to performing base 32 or 64 encoding (or similar) instead of encoding to hexadecimals. I'm not sure it would bring down the number of characters enough to be worth while. Using just the 16 leftmost bytes of the hash on the other hand could be a good balance between security and practical communication of the hash. $\endgroup$ – Maarten Bodewes Jun 21 '16 at 15:18
  • $\begingroup$ @MaartenBodewes "Using just the 16 leftmost bytes of the hash" was the idea #0 ;) (or rightmost, or every odd, etc.) but - now we come to the need of assessing the security strength, which is the field I deliberately avoid leaving it to experts. $\endgroup$ – tum_ Jun 21 '16 at 15:57
  • $\begingroup$ I just mentioned it here because it can obviously be combined with option #1 and #2. $\endgroup$ – Maarten Bodewes Jun 21 '16 at 15:57

I think I have come up with an idea that should be secure but would like to hear an expert's opinion on it:

First step: use a protocol between the two parties A and B to come up with a random number R that none of the parties can force to be a given value.

Second step: calculate a secure hash of R concatenated with the self-signed certificate and use a prefix of the result with the desired length, e.g. the first 10 characters as the string that has to be shown and compared.

The first step could be implemented as follows:

  • A and B each use a secure RNG to come up with 256 random bits, rA and rB. Then each party calculates the SHA-256 of that value, let's call those H(rA) and H(rB).

  • A connects to B over the TLS link and saves the certificate that is used. All subsequent connections to B only succeed if the cert stays the same (pinning).

  • A sends H(rA) to B and B replies with H(rB).

  • A sends rA to B and B replies with rB.

  • A and B both verify that the other party's value and hash match. Abort with warning if mismatch.

  • Both parties calculate R = H(rA | rB).

  • $\begingroup$ Depending on how much your TLS library exposes, you can use some value derived from your current connection for this. (Channel ID, master key,...) $\endgroup$ – SEJPM Jun 22 '16 at 13:31
  • $\begingroup$ Thanks for the tip, SEJPM. The TLS libs don't expose those values. Do you think that the method I described is secure? $\endgroup$ – flo von der uni Jun 22 '16 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.