<span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">On current GPUs, that's "a lot", not "slightly".  GPUs currently deliver </span><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">CPU-like speeds for bcrypt, but a lot higher speeds for PBKDF2-HMAC-SHA*</span> <div>
<br></div><div>Yeah, I realized that was a bit unfair. I guess I was thinking mostly in relation to scrypt -- bcrypt is certainly not inexpensive.</div><div><br></div><div>> The limit is actually at 72 chars.  55 was an error in the paper.</div>
<div><br></div><div>Oh, interesting. Then it seems like less of an issue.</div><div><br></div><div>Thanks for the clarification!</div><div><br><div class="gmail_quote">On Thu, Aug 16, 2012 at 4:27 AM, Solar Designer <span dir="ltr"><<a href="mailto:solar@openwall.com" target="_blank">solar@openwall.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Thu, Aug 16, 2012 at 02:25:34AM +0200, Patrick Mylund Nielsen wrote:<br>
> PBKDF2 is certainly decent, and often the easiest choice if you intend to<br>
> comply with e.g. FIPS 140-2/ISO 27001, but the biggest argument against it<br>
> is that it _isn't_ difficult to parallelize, since it is just e.g.<br>
> HMAC-SHA256. Each guess might require sequential iteration, but you can<br>
> still compute many guesses simultaneously.<br>
<br>
</div>Exactly.<br>
<div class="im"><br>
> bcrypt is slightly more computationally expensive<br>
<br>
</div>On current GPUs, that's "a lot", not "slightly".  GPUs currently deliver<br>
CPU-like speeds for bcrypt, but a lot higher speeds for PBKDF2-HMAC-SHA*.<br>
<br>
(I expect that we'll get faster attacks on bcrypt using general-purpose<br>
hardware with AVX2 and Intel MIC, though.)<br>
<div class="im"><br>
> (although its 55-byte input limit is often ignored,)<br>
<br>
</div>The limit is actually at 72 chars.  55 was an error in the paper.<br>
<div class="im"><br>
> > PBKDF2-HMAC-SHA1 significantly weaker than PBKDF2-HMAC-SHA512?<br>
><br>
> SHA-1 is still safe in an HMAC construction, however there's no convincing<br>
> reason not to use at least PBKDF2-HMAC-SHA256 that I can think of. You<br>
> don't need it to be fast. Going beyond that won't really give you much<br>
> security compared to using a memory-hard function.<br>
<br>
</div>There's a lot of difference between SHA-1 and SHA-512 in terms of<br>
friendliness to current GPUs.  SHA-512 is a lot less GPU-friendly.<br>
<br>
SHA-256 is inbetween.  This is related to SHA-512 making more complete<br>
use of 64-bit CPUs.  If you use more of the available resources and do<br>
so wisely, then the attacker will similarly have to use more resources.<br>
This alone accounts for a 2x difference between SHA-256 and SHA-512 when<br>
we consider attackers' GPU implementations.  Further difference comes<br>
from SHA-512's increased register pressure (on GPU's 32-bit registers).<br>
<br>
Overall, SHA-256 is 2-3 times slower than SHA-1, and SHA-512 is a<br>
further 4-14 times slower than SHA-256 on current GPUs with currently<br>
available implementations.  SHA-512 is 10 to 30 times slower than SHA-1<br>
on current GPUs with currently available implementations.<br>
<br>
Still PBKDF2-HMAC-SHA-512 is a lot more susceptible to attacks with<br>
current GPUs than bcrypt, let alone scrypt.<br>
<br>
Alexander<br>
</blockquote></div><br></div>