lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
 
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Mon, 27 Jan 2014 16:54:27 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Combining sliding window and bit-reversal

I did more testing of different DAG architectures while enhancing my
pebbling algorithm.  These benchmarks change as the code changes, but
here's an interesting data point.

I was comparing Catena-3 graphs to Alexander's power-of-two graphs,
and both did well in different areas.  Then I though, how about
combining them?  So, instead of picking random locations within the
sliding window, I pick bit-reversal based locations.  This results in
the hardest to pebble DAGs so far for my pebbling algorithm.

I'm thinking of using this without password dependent memory location
reads for the first 50%, and then for the last 50%, I'll use the
existing NoelKDF DAG, which will have a ton of edges back into the
sliding bit-reversal DAG.  Just to be specific about how this DAG is
generated, here is the function I wrote that creates edges from a
position in the graph to a prior position:

// Find the previous position using Alexander's sliding power-of-two
window, with Catena
// bit-reversal.
static uint32 findSlidingReversePos(uint32 pos) {
    // This is a sliding window which is the largest power of 2 < i.
    if(pos < 2) {
        return UINT32_MAX;
    }
    uint32 mask = 1;
    while(mask <= pos) {
        mask <<= 1;
    }
    mask = mask >> 1; // Mask is greatest power of 2 <= pos
    uint32 reversePos = bitReverse((pos) & (mask-1), mask);
    if(reversePos + 1 >= pos - mask) {
        return reversePos;
    }
    return reversePos + mask;
}

Bill

Powered by blists - more mailing lists