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
[<prev] [next>] [day] [month] [year] [list]
```Date: Thu, 19 Feb 2015 14:38:03 +0800
From: Ben Harris <mail@...rr.is>
To: discussions@...sword-hashing.net
Subject: Replacement index function for data-independent schemes (Catena)

Building on the analysis of Catena and Lyra2 by Alex and Dimitry (
http://orbilu.uni.lu/handle/10993/20043), I'd like to suggest a replacement
to bit-reversal hashing (BRH) that, unlike the double-butterfly, maintains
most of the advantages of BRH.

The function is a combination of bit-reversal (to promote low-order bits
higher) and a grey-code-like xor (to permute the weight/population count).
The function is:

phi(i) = reverse(i) ^ (reverse(i) >> ceil(n / 2))

Where reverse is a bit reversal, ceil is the ceiling function, n is the
number of bits (garlic).

Using this function 0 is a fixed point - later I will cover a small change
to move the fixed point to the last index instead.

To permit an in place algorithm like Catena's BRH, the above function can
be modified to a constant time function including the round number.

phi_round(i, round) {
var ret = i;
var shift = (garlic + 1) >> 1; // ceil(n / 2)
var mask = (1 << (garlic >> 1)) - 1;
if ((round + 1) % 6 >= 4) ret ^= i & (mask << shift);
if ((round + 4) % 6 < 4) ret ^= i >>> shift;

if ((round + 5) % 6 < 4) ret ^= i << shift;
if ((round + 2) % 6 >= 4) ret ^= i & mask;

ret &= (1 << garlic) - 1;

if (i & 1 == 1) ret = reverse(ret);

return ret;
}

The function is 6-cyclic instead of 2 like bit reversal. It also permutes
the population count which is a stronger permutation than just reordering
the bits. On rounds 0, 2 and 4 the reversal is cancelled out, the index
values are as follows for each round (4 bit example)

0    1234

1    4343 xor
12

2    1212 xor
34

3    2143

4    3434 xor
12

5    2121 xor
43

6    1234

The lower order bits are spread around, ensuring that nodes are separated
for up to 6 rounds. The final change is to move the stationary point to the
final point with a bit inversion:

phi(i) = reverse(i) ^ ( ~reverse(i) >> ceil(n / 2) )

phi_round(i, round) {
var ret = i;
var shift = (garlic + 1) >> 1; // ceil(n / 2)
var mask = (1 << (garlic >> 1)) - 1;
if ((round + 1) % 6 >= 4) ret ^= i & (mask << shift);
if ((round + 4) % 6 < 4) ret ^= i >>> shift;

if ((round + 5) % 6 < 4) ret ^= i << shift;
if ((round + 2) % 6 >= 4) ret ^= i & mask;

if ((round + 5) % 6 < 2) ret ^= mask << shift;
if ((round + 2) % 6 < 2) ret ^= mask;

ret &= (1 << garlic) - 1;

if (i & 1 == 1) ret = reverse(ret);

return ret;
}

An illustration is available at http://bharr.is/d3-catena/

Content of type "text/html" skipped
```