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_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?