Joe, Trevor: These strategies are less advantageous than it seems against most attackers. (The NSA possibly excepted.)<div><br></div><div>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.</div>
<div><br></div><div>(Some of djb's papers on brute-force touch on this.)</div><div><br></div><div>A much much better way to spend the time is choosing, e.g., a larger/longer instance of scrypt. (Or whatever PHC selects.)<br>
</div><div><div><br></div><div>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...)</div>
<div><br></div>De-genericizing attacks using 'nonces' in this way does not allow avoiding memory accesses, with their huge latency.<br><div><div><br>On Wednesday, July 23, 2014, Trevor Perrin <<a href="mailto:trevp@trevp.net">trevp@trevp.net</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Wed, Jul 23, 2014 at 8:52 AM, Joseph Bonneau <<a href="javascript:;" onclick="_e(event, 'cvml', 'jbonneau@gmail.com')">jbonneau@gmail.com</a>> wrote:<br>

[...]<br>
><br>
> Another thought though is that instead of relying on brute-forcing<br>
> fingerprints being slowed by public key generation being inherently slow,<br>
> it's better to explicitly add itreated hashing to the fingerprint<br>
> generation. One way to do this is to enforce that the hash of the public key<br>
> starts with x consecutive zeros. This imposes no cost on verification and<br>
> has the benefit that fingerprints are effectively shorter by x bits (with<br>
> equivalent security) as the zeros don't need to be transmitted, stored or<br>
> checked. I'd imagine in most cases we could afford x=20-30. The downside is<br>
> that x must be set universally and can't be upgraded. That's why I'd suggest<br>
> tying x to the public-key size so when key sizes are upgraded x can be as<br>
> well.<br>
<br>
That's a good idea, spending several extra seconds during key<br>
generation may well be worth a fingerprint that's smaller by<br>
20-something bits.<br>
<br>
There's a few obvious twists on this:<br>
<br>
1) Add a small nonce into the public-key format, so that it's easy for<br>
the legitimate key-generator to search at high speed without the math<br>
tricks being discussed.<br>
<br>
2) Encode x into the fingerprint itself, e.g. use the first 4 bits to<br>
encode the count of zero bytes, allowing for a "scaleable" security<br>
level.<br>
<br>
3) Instead of searching for a prefix of zero bytes, search for a<br>
fingerprint with a high value in some useability metric.  E.g., my<br>
"base32 pseudoword" format searches for a base32 fingerprint with high<br>
vowel-consonant alternation, which I think makes compact but<br>
pronounceable fingerprints, e.g.<br>
<br>
Score=17:   byadep - mayo - eqcni - idah - logutu<br>
<br>
Score=17:   hheute - ixej - urufe - unit - qefaiv<br>
<br>
Score=18:   duconi - huho - baj5w - yejo - epevig<br>
<br>
Score=18:   ezobiv - wxax - zugar - 2ube - adijuv<br>
<br>
<a href="https://github.com/trevp/keyname" target="_blank">https://github.com/trevp/keyname</a><br>
<a href="https://moderncrypto.org/mail-archive/messaging/2014/000050.html" target="_blank">https://moderncrypto.org/mail-archive/messaging/2014/000050.html</a><br>
<br>
<br>
Trevor<br>
_______________________________________________<br>
Messaging mailing list<br>
<a href="javascript:;" onclick="_e(event, 'cvml', 'Messaging@moderncrypto.org')">Messaging@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/messaging" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br>
</blockquote></div></div></div>