On Wed, Jul 23, 2014 at 8:52 AM, Joseph Bonneau <[email protected]> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
