[Cryptography] Two round secure hashing

[Bill Cox]

I'm not sure if anyone is interested in this sort of in-progress noodling
on fast file hashing by someone who doesn't really know what he's doing
(yet).  I'm having fun with this, and I don't want to ruin it just yet by
reading up on what really goes into modern hash function design.  I'll do
that later.  Just in case anyone else finds this stuff cool, here's some
fun I had.

I'm trying to determine how secure can we make 2-round hashing using large
numbers of message blocks in two chains, hashed in different orders.
 Apparently, given a file long enough, we can make it as secure as we like,
but "long enough" is exponential in terms of the number of rounds of
desired security against differential attacks.  However, substantial round
reductions for files a few KiB long appears doable, and least if we are
primarily concerned about collision attacks based on differential
characteristics (I'm not sure I used that term right).

Basically, the fun I've had lately has been building graphs corresponding
to two-chain hashing of message blocks in a way that guarantees there are
no loops smaller than some small constant K, insuring any differential
characteristic has to span K rounds to result in a collision.

Consider two hash chains of message blocks stored in an NxN matrix.  The
first chain hashes row by row, and the second hashes column by column.  Any
two adjacent message blocks in the first chain will be separated by N in
the second chain, meaning a simple two sequential message change that
cancel each other out on the first chain will explode into a mess on the
second.  The messages are in a matrix like this:

m11 m12 m13 ... m1N
m21 m22 m23 ... m2N
...
mN1 mN2 mN3 ... mNN

The row chain hashes messages in row order:

    m11 m12 m13 ... m1N m21 m22 m23 ... m2N ... mNN

The column chain hashes messages in column order:

    m11 m21 m31 ... mN1 m12 m22 m32 ... mN2 ... mNN

If an attacker finds a good "differential characteristic" for the round
function R, which has a reasonable chance of occurring for random message
blocks, then he can easily find collisions.  For example, if R(m^a) ==
R(m)^a  (where ^ means xor) with high probability (like > 1/sqrt(2^N) for
N-bit hashes) then an attacker can compute hashes for a random message M,
and a slightly modified version of M:

m11^a, m12^a, m13, m14 ...
m21^a, m22^a, m23, m24 ...
m31, m32, m33, m34 ...
...

The row-based sequence well see m11^a followed by m12^a, and will have a
chance of these two changes cancelling each other.  The same thing happens
in the next row with m21^a followed by m22^a.  Similarly, the column based
chain may see m11^a and m21^a cancel out, and m21^a cancel m22^a.  I call
this a "4-loop", since it is a message hashing loop involving 4 message
blocks.  With only a single chain, the differential characteristic would
only need to work out once, but here it has to work out in 4 places at the
same time, with probability being raised to the 4th power.  If the chance
of R(m^a) == R(m)^a is 1/4, then this 4-loop works out about 1 in 256 tries.

The more messages that have to be modified, and the further apart they are,
the lower the chance that the changes will cancel out.

The two chains can be represented by message indexes, and we can
draw bipartite graphs between the two message chains showing the relative
positions of the message blocks.  These graphs are hard to represent in
text, so I just write the message block numbers, where the first chain is
always 1 to N, and the second chain shows the position where each message
block has moved.  For example, a 6-block chain could look like:

chain a: 1 2 3 4 5 6
chain b: 1 3 5 2 4 6

A loop is written like: a1 => a2 => a3 -> b3 => b1 -> a1

This says we start in chain a at message m1, compute a round R(m1^a), and
hope we can still cancel out the change in m1 with a modification to m3.
 That fixes chain a, but chain b still needs work.  Moving from a3 -> b3
moves from the 3rd position in chain a to the second position in chain b.
 It doesn't call the round function R, it's just a free switch from chain a
to b.  In chain b, this loop shows an attacker is hoping that the changes
that cancel between a1 and a3 also cancel between b1 and b3.  To succeed in
cancelling changes in both chains, an attacker must complete the loop, or
else he will have a change with nothing to cancel it, exploding into a mess.

The round cost of this loop is only 3, because changes between chains are
free.  The round function is used to go from a1=>a2, a2=>a3, and b3=>b1.
 To be secure against differential collision attacks, I want to find
permutations of the message blocks for chain b that make it impossible for
an attacker to find short chains.  This is actually doable.

To make a chain that has a minimum loop size of 4, I can do this:

chain a: 1 2 | 3 4 | 5 6 | 7 8
chain b: 1 X | 3 X | 5 X | 7 X

Here, I've chosen the odd message numbers to remain in their original
positions, and I'm trying to find an assignment for all the even positions
that insure a loop size of no less than 4.  Regardless of this assignment,
4-loops for this pattern will exist, such as a1 => a2 => a3 -> b3 => bX =>
b1 -> a1.

A simple assignment that works for the X's is to just use x+4 mod N, where
x is the position, and there are N message blocks:

chain a: 1 2 | 3 4 | 5 6 | 7 8 ...
chain b: 1 6 | 3 8 | 5 10 | 7 12 ...

A simple proof that all loops will be 4 or more is to consider the 3
possible loop types, where they are differentiated by crossing vertically,
or diagonally.  Any loop with 2 vertical crossings between chains a and b
is clearly a 4-loop.  For example, if we cross vertically at position 3,
and again at position 5, we'll need to do 2 rounds in each chain to
complete the loop.  Similarly, and loop with two diagonal crossings is at
least a 4-loop.  The case of a vertical and diagonal is tricker.  if
instead of x+4, we use x+2 in the pattern, then we would have a 2 loop,
such as a3 => a4 -> b4 => b3 -> a3.  However, with x+4, all loops are
clearly >= 4, because each case where the vertical crosses the diagonal is
a 4-loop, and all loops where they do not cross are larger than 4.

To increase the minimum loop size from 4 to 6, we start with this pattern
and insert one more edge in every group (shown separated by | above):

chain a: 1 2 3 | 4  5 6 | 7  8 9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20
21 ...
chain b: 1 8 X | 4 11 X | 7 14 X | 10 17 X | 13 20 X | 16 23 X | 19 26 X ...

I just choose X to be x + c, where c is longer than the longest possible
span using 4 rounds.  In this case, the longest span of 4 rounds looks like:

    b8 -> a8 => a7 -> b7 => b14 -> a14 => a13 -> b13 => b20 -> a20

So, choose c == 18, so we span from the position after b8 all the way to
a21:

chain a: 1 2  3 | 4  5  6 | 7  8 9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20
21 ...
chain b: 1 8 21 | 4 11 24 | 7 14 27 | 10 17 30 | 13 20 33 | 16 23 36 | 19
26 39 ...

As before we can characterize minimum loops by crossing types.  Any loop
with 2 vertical edges between chains will be a 6-loop, such as a4 => a5 =>
a6 => a7 -> b7 => b24 => b11 => b4 -> a4.  Any loop with two of the same
type of diagonals (long or short), will similarly be at least a 6-loop, as
will the case as before of a vertical and a short diagonal.  The different
case is when we include one long diagonal.  The shortest loop we can make
will include the longest chain of 4 as above, plus 1 to get on the long
diagonal, + 1 to get off it, making it another 6-loop.

To make chains that have no loops smaller than 8, we just add another very
long edge type.  Again, we find the longest span possible with 6 calls to
R, and choose an edge length that makes an 8-loop out of it.  The longest
span looks like:

    b21 -> a21 => a22 -> b22 => b39 -> a39 => a40 -> b40 => b57 -> a57
=>a58 -> b58 => b75 -> a75

This uses 4 of the 18 long edges, and the other edges go forward or
backward 1, cancelling out progress, so the total span is 4*18 = 72, or 24
groups of 3.  We need to add another node to each group, so they'll be 4
long rather than 3, and add edges that span 24 groups of 4, or 96 long:

chain a: 1 2 3 4 | 5 6 7 8 | 9 10 11 12 ...
chain b: 1 10 99 28 | 5 14 103 32 | 9 18 107 36 ...

Note that the new long edge was inserted between two of the prior
diagonals.  This increase the cost to move forward on the new long edges
from 2 to 4, so that with 8, we can only span 2 of them for a length of 192
as the longest span of 8 rounds.

With a proof by induction based on what I said above, this has 8 round
security against collision attacks.   Any round security length is
achievable, given long enough message lengths, but the message lengths
required roughly doubles for each additional 2 rounds of strength.  The mod
N begins to be important with edge lengths of 96.  In particular, we'll
need at least 192 message blocks to insure that the mod N doesn't allow
loops shorter than 8 that span the whole ring.  We need two of these
chains, for a total of 384 message blocks.  If each is 512 bits in width,
that's 24,576 bytes, which still fits in a lot of L1 caches, but it's
beginning to bust out.

If L3 cache is fast enough, given other limiting factors such as DDR memory
speed, then we could grow this from 8 round security to maybe 22 without
busting out of 10-ish MiB of L3.  However, the algorithm becomes less
applicable to small files, limiting it's application.

If we want support for small files, 6 or 8 round security may be enough to
be interesting.  In particular, what if we take something like 2 rounds of
Blake2b's round function, and use it here as our round function with the 6
or 8 loop pattern?  In theory, that should give it 12 or 16 rounds of
strength against differential attacks, while running with the speed as if
only 4 rounds had been used.  That's a 3X-ish speed up.

To make this scheme even faster, I'm looking into adding a 3rd chain.  It
means that 3 rounds will be called, but I might be able to do 1 round of
Blake2b, for example, rather than 2 for the basic round function, for an
equivalent speed of 3-round Blake2b.  I'm not sure what the message access
pattern in the 3rd chain should be yet.  If I can design it so that any
loop in the first two chains results in a non-loop in the 3rd, that should
make the 3rd loop explode into a mess for any differential attack, I
think...

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140428/6b8500cc/attachment.html>