[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Thu, 14 Jul 2011 15:45:32 -0400
From: Anthony Ferrara <ircmaxell@...il.com>
To: crypt-dev@...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 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.
