[messaging] Bounding hash 2d preimage bits (was Re:...Test Data)

[Trevor Perrin]

On Wed, Jul 23, 2014 at 8:52 AM, Joseph Bonneau <jbonneau at gmail.com> wrote:
[...]
>
> Another thought though is that instead of relying on brute-forcing
> fingerprints being slowed by public key generation being inherently slow,
> it's better to explicitly add itreated hashing to the fingerprint
> generation. One way to do this is to enforce that the hash of the public key
> starts with x consecutive zeros. This imposes no cost on verification and
> has the benefit that fingerprints are effectively shorter by x bits (with
> equivalent security) as the zeros don't need to be transmitted, stored or
> checked. I'd imagine in most cases we could afford x=20-30. The downside is
> that x must be set universally and can't be upgraded. That's why I'd suggest
> tying x to the public-key size so when key sizes are upgraded x can be as
> well.

That's a good idea, spending several extra seconds during key
generation may well be worth a fingerprint that's smaller by
20-something bits.

There's a few obvious twists on this:

1) Add a small nonce into the public-key format, so that it's easy for
the legitimate key-generator to search at high speed without the math
tricks being discussed.

2) Encode x into the fingerprint itself, e.g. use the first 4 bits to
encode the count of zero bytes, allowing for a "scaleable" security
level.

3) Instead of searching for a prefix of zero bytes, search for a
fingerprint with a high value in some useability metric.  E.g., my
"base32 pseudoword" format searches for a base32 fingerprint with high
vowel-consonant alternation, which I think makes compact but
pronounceable fingerprints, e.g.

Score=17:   byadep - mayo - eqcni - idah - logutu

Score=17:   hheute - ixej - urufe - unit - qefaiv

Score=18:   duconi - huho - baj5w - yejo - epevig

Score=18:   ezobiv - wxax - zugar - 2ube - adijuv

https://github.com/trevp/keyname
https://moderncrypto.org/mail-archive/messaging/2014/000050.html


Trevor