[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20110714174057.GA30965@openwall.com>
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.
