[messaging] "Pseudoword" base32 fingerprints

[Trevor Perrin]

On Wed, Feb 5, 2014 at 3:55 PM, Joseph Bonneau <jbonneau at gmail.com> wrote:
>> 1) You don't have free choice of strings (like a password generator).
>> Instead, you can only evaluate a "scoring function" on candidates
>> produced by SHA256(pubkey + 32-bit counter).
>
>
> I wasn't assuming you have free choice of any string you want, but that the
> world can choose (and agree) to a new hash function, which is really a hash
> function plus a function to turn the output into a human-readable string.
> This could be used in a new messaging protocol, for example, to represent
> public keys.
>
> Looks like your assumption is that the hash function is fixed though and
> therefore we have to search.
>
> Either is an interesting problem I think.

I see your point.  I think I prefer searching though, since it allows
a denser encoding while avoiding strings with low useability.  For
example, we can encode 5 bits of hash output per base32 character, to
achieve a 125-bit security level in 25 chars.

If you were to directly encode into, say, vowel-consonant pairs, there
are 105 such pairs: len("aeiou") * (26-len("aeiou")).  So you could
encode log2(105) ~= 6.7 bits per pair, or ~3.3 per character, meaning
you'd need ~50% more characters for the same security level.

People generate long-term keys rarely, so waiting several seconds for
a long-term useability advantage seems a plausible tradeoff.  And as
computers get more cores, GPUs, and specialized SHA256 ops, searching
speed will improve...


Trevor