[Cryptography] Two round secure hashing

[John Bailer]

Has anyone seen this?
A New Internet Explorer Security Flaw Leaves One Quarter Of Web Browsers Vulnerable 

 
   A New Internet Explorer Security Flaw Leaves One Q...
More bad news in the world of online security. Update: Adobe has released a security patch.  
View on www.buzzfeed.com Preview by Yahoo  
 

Thanks

John 


John Bailer
  CEOT. 0171 409-0814 • The Stock Market Engine •http://stockmarketengine 
On Monday, April 28, 2014 6:45 PM, Bill Cox <waywardgeek at gmail.com> wrote:
 
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

_______________________________________________
The cryptography mailing list
cryptography at metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140428/0feb732a/attachment.html>