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

[David Leon Gil]

Joe, Trevor: These strategies are less advantageous than it seems against
most attackers. (The NSA possibly excepted.)

In this sort of attack, you're strongly bounded by memory throughput; you
can execute many hashes on an ASIC or FPGA in the time it takes to access
memory. The sort of fixed condition you're considering can be checked on
the ASIC without a memory request.

(Some of djb's papers on brute-force touch on this.)

A much much better way to spend the time is choosing, e.g., a larger/longer
instance of scrypt. (Or whatever PHC selects.)

Robert: If your host name and IP address change frequently, just use your
name, or your zip code, or a short, very easy-to-remember nonce. The
requirement is not that it be as strong as a password; just something to
de-genericize the attack. (You get rid of most of that 2^27 advantage with
only 2^16 unique hostnames...)

De-genericizing attacks using 'nonces' in this way does not allow
avoiding memory accesses, with their huge latency.

On Wednesday, July 23, 2014, Trevor Perrin <trevp at trevp.net> wrote:

> On Wed, Jul 23, 2014 at 8:52 AM, Joseph Bonneau <jbonneau at gmail.com
> <javascript:;>> 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
> Messaging at moderncrypto.org <javascript:;>
> https://moderncrypto.org/mailman/listinfo/messaging
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140723/e134ab32/attachment.html>