[messaging] "Pseudoword" base32 fingerprints

[Ximin Luo]

On 06/02/14 00:44, Robert Ransom wrote:
> On 2/5/14, Joseph Bonneau <jbonneau at gmail.com> wrote:
>> 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
> 
> 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.
> 

What's the difference between "securely computable" and "computable"?

Unique inverses are definitely nice to have - if I have the exact fingerprint written in front of me, I could compare it with the spoken version, but I could probably not reproduce the exact characters just from hearing the spoken version, because some sounds and combinations are ambiguous. (Without greatly reducing the speed of communication, anyway.)

But I'm not so sure it's essential - I can't remember ever having to reproduce the exact fingerprint from a written/spoken copy of it, even if that copy was most definitely non-friendly.

To guide us to the properties we want, we should consider some use-cases. For example, depending on which of the below you really want (that I mentioned previously), you might come up with wildly different strategies.

- given a maximum acceptable error rate, minimise the communication time
- given a maximum acceptable communication time, minimise the error rate

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 880 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140206/1f51c56c/attachment.sig>