Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Thu, 14 Jul 2011 15:45:32 -0400
From: Anthony Ferrara <>
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,


On Thu, Jul 14, 2011 at 1:40 PM, Solar Designer <> 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 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:
> 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.