Date: Thu, 14 Jul 2011 21:40:57 +0400 From: Solar Designer <solar@...nwall.com> To: crypt-dev@...ts.openwall.com Subject: Re: Some thoughts on hard to compute hashes Anthony, On Fri, Jul 01, 2011 at 06:36:11PM -0400, Anthony Ferrara wrote: > For i = 0 ... N - 1 > j <-- Integerify(x) mod N > If j > (N / B) > X <-- H(X xor V_j) > Elseif j > (N / 2B) > V_i <-- H(X xor V_j) > Elseif j > (N / 4B) > V_j <-- H(X xor V_i) > Else > X <-- H(X xor V_i) In your example, the branching may be avoided by turning the "j > (N / B)", etc. comparison results into all-zero and all-ones bitmasks (which is trivial to do without branching), then applying those in expressions on X, V_j, V_i variables. H() is then invoked from just one place, unconditionally. Its output is similarly put into the right variable or memory location using several expressions involving ANDs with the bitmasks. So all of X, V_i, and V_j are written to, but only one of those writes actually changes the value at the target location. Here's another example of a branching algorithm turned into non-branching: http://lists.randombit.net/pipermail/cryptography/2010-September/000184.html So it'll take some more effort to make branch-avoidance costly - e.g., you could use very different H() functions in different cases, so a branch-less implementation would have to compute each of them, whereas a branching one would compute just one needed for the current iteration. In that variation of your example, you'd achieve a 4x slowdown for a GPU that has to avoid branching. Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.