Do low-entropy fingerprints actually make any sense?

Question

I'm thinking of ZRTP and OTR in particular here. From my understanding, after a Diffie-Hellman session is initiated, the shared secret is then hashed into a 4-digit number, which the two parties can then check out-of-band (or in ZRTP in-band, assuming that people can recognize each others' voices).

How is this possibly secure? The only articles I've read about the protocols say something like "there's only a 1/10000 chance that it's a man in the middle if the numbers match", but can't the man-in-the-middle pick his own private keys (by brute force) such that the numbers match? That is, with a setup like

Alice <- ss_am -> Mallory <- ss_mb -> Bob

could Mallory not use a brute-force search to find private keys such that ss_am and ss_mb hash to the same 4 numbers?

Or am I fundamentally misunderstanding something about ZRTP and OTR?

A related question would be the SSH public-key randomart thing. It has not a lot of bits of entropy, so couldn't an impersonator simply brute-force a private key such that the public key has the same randomart as the real public key?

This question probably also applies to ideas like generating gravatars from public keys so that impersonators look different, or the common practice of referring to PGP keys by their first few bits.

How can low-entropy fingerprints be useful?

Answer 1

Short key fingerprints are indeed vulnerable. But those are different from the short-authentication-string (SAS) used by ZRTP.

A simple SAS based protocol using one-time keys could look like this:

1. Alice sends a (collision resistant) hash of her public key to Bob.
2. Bob sends his public key to Alice
3. Alice sends her public key to Bob

The short authentication string is computed as hash of both public keys.

Bob can't deliberately influence the SAS because he doesn't know Alice's public key yet. Alice can't deliberately influence the SAS in Step 3, because she already committed to her public key, by publishing its hash in Step 1 before she learned about Bob's key.

Alice could abort the connection after step 2 or Bob after step 3, but that should display an error to the user and can't be pulled off too often.