[messaging] "Pseudoword" base32 fingerprints

[Robert Ransom]

On 2/5/14, Joseph Bonneau <jbonneau at gmail.com> wrote:
> Good project idea Trevor. There are a lot of related tools which aim to
> make random pronounceable passwords. Two for Linux are:
>
> pwgen: zae7IiB7 phoosu1U Hu5meed8 aeY4eeGu oht6ax9M aD4taur4 Ohpai5sh
> sheiGah8
> apg: odripAbag6 (o-drip-Ab-ag-SIX) AzMykUpt3opo (Az-Myk-Upt-THREE-op-o)

These work by sampling from a distribution which ensures
‘friendliness’, for some (boolean) definition of “friendly”.

keyname works by searching for a string whose hash, when represented
using a simple alphabet-based coder which can easily be implemented in
constant time, maximizes some (non-boolean) measurement of how
‘friendly’ a string is.


> In general, I think it would nice to have a library for turning random bits
> into "human-friendly form". This might include a tradeoff for
> length/painlessness, but we would also surely get different results if we
> optimize for:
> a) easy for humans to spot differences
> b) easy for humans to pronounce/hear/type
> c) easy for humans to remember
>
> We would also probably end up with a different algorithm for different
> language populations...
>
> There's a really a lot here. It might be worthwhile as a first step just to
> enumerate the possible design constraints.

There are several possible meanings of ‘turning random bits into
‘human-friendly form’’, independent of what “friendly” means in a
particular application or to a particular set of users:

1.  Modify s so that E(H(s)) is ‘friendly’, where H is a
    second-preimage-resistant function and E (a) chops a bitstring
    into pieces, then (b) applies a bitstring-to-text-string function
    to each piece which can be securely computed and has an inverse
    which can be securely computed, then (c) concatenates the
    resulting text strings.

2.  1, except that the bitstring-to-text-string functions used by E
    need not have a securely computable inverse.

3.  1, except that E may be any injective bitstring-to-text-string
    function (e.g. Markov chain driven by Huffman or arithmetic
    decoder).

4.  Construct a securely computable function E: Bits(k) -> Text with
    securely computable inverse, such that when h is sampled uniformly
    at random from the set of k-bit bitstrings, E(h) is ‘friendly’
    with high probability.

5.  4, except that E need not have a securely computable inverse.

6.  5, except that E need not be securely computable.

7.  4, except that E need not have a computable inverse.

8.  7, except that E need not be injective.


Trevor implemented 1.  You appear to be talking about one of 4 through
8.

I do not believe that approaches 4 through 8 are good in any
application.  I'm not interested in using approaches 1 through 3, but
(a) they don't inherently muck up every implementation of a protocol,
and (b) they will be done whether I write code to support them or not.


Robert Ransom