
Date: Thu, 14 Jul 2011 15:45:32 0400 From: Anthony Ferrara <ircmaxell@...il.com> To: cryptdev@...ts.openwall.com Subject: Re: Some thoughts on hard to compute hashes That's quite fair. I was just using that as a demonstration of the concept. But that was a very interesting read. It makes perfect sense and is intuitive, but it's still quite interesting. Thanks for the input, Anthony On Thu, Jul 14, 2011 at 1:40 PM, Solar Designer <solar@...nwall.com> wrote: > 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 allzero and allones 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 nonbranching: > > http://lists.randombit.net/pipermail/cryptography/2010September/000184.html > > So it'll take some more effort to make branchavoidance costly  e.g., > you could use very different H() functions in different cases, so a > branchless 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.