<html><body><div style="color:#000; background-color:#fff; font-family:Courier New, courier, monaco, monospace, sans-serif;font-size:10pt"><div id="yiv5294724278"><div><div style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-family: 'Courier New', courier, monaco, monospace, sans-serif; font-size: 10pt;"><div class="yiv5294724278" id="yiv5294724278" style=""><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210545" style=""><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210544" style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-family: 'Courier New', courier, monaco, monospace, sans-serif; font-size: 10pt;"><div class="yiv5294724278" id="yiv5294724278" style=""><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201705" style=""><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201704" style="color: rgb(0, 0, 0); background-color:
rgb(255, 255, 255); font-family: 'Courier New', courier, monaco, monospace, sans-serif; font-size: 10pt;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_9" style=""><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_15" style="">Has anyone seen this?</span></div><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_9" style="background-color:transparent;"><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_18" style=""><a rel="nofollow" shape="rect" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_195926" target="_blank" href="http://www.buzzfeed.com/charliewarzel/a-new-internet-explorer-security-flaw-leaves-one-quarter-of" style="">A New Internet Explorer Security Flaw Leaves One Quarter Of Web Browsers Vulnerable</a> <br clear="none" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_195923" style=""></span></div><div
class="yiv5294724278" id="yiv5294724278enhancrCard_3" style="width: 450px; font-family: Georgia, Times, 'Times New Roman', serif;"><table class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201791" cellspacing="0" cellpadding="0" style="width:450px;height:170px;display:block;"><tbody class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201790" style=""><tr class="yiv5294724278" style=""><td colspan="6" rowspan="1" class="yiv5294724278" style="height:1px;background-color:#e5e5e5;"><div class="yiv5294724278" style="height:1px;background-color:#e5e5e5;"></div></td></tr><tr class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201789" style=""><td colspan="1" rowspan="2" class="yiv5294724278" style="width:1px;background-color:#e5e5e5;"><div class="yiv5294724278" style="width:1px;background-color:#e5e5e5;"></div></td><td colspan="1" rowspan="2" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201808"
style="vertical-align:middle;width:168px;height:168px;background-color:#000000;"><div align="center" class="yiv5294724278" style="width:168px;"><a rel="nofollow" shape="rect" class="yiv5294724278" target="_blank" href="http://www.buzzfeed.com/charliewarzel/a-new-internet-explorer-security-flaw-leaves-one-quarter-of" style="text-decoration:none;color:#000000;"><img class="yiv5294724278" alt="image" src="http://s3-ak.buzzfeed.com/static/2014-04/campaign_images/webdr03/28/15/a-new-internet-explorer-security-flaw-leaves-one--2-804-1398712809-6_dblbig.jpg" width="168" height="112" style="display:block;margin:auto;"></a></div></td><td colspan="1" rowspan="2" class="yiv5294724278" style="width:1px;background-color:#e5e5e5;"><div class="yiv5294724278" style="width:1px;background-color:#e5e5e5;"></div></td><td colspan="2" rowspan="1" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201788" style="width: 100%; vertical-align: middle; font-family:
Georgia, Times, 'Times New Roman', serif;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201787" style="line-height:16.5px;background-color:#ffffff;height:130px;width:279px;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210548" style="word-wrap:break-word;padding:7px 20px 0px 14px;"><span class="yiv5294724278" style=""></span><span class="yiv5294724278" style=""></span><a rel="nofollow" shape="rect" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210547" target="_blank" href="http://www.buzzfeed.com/charliewarzel/a-new-internet-explorer-security-flaw-leaves-one-quarter-of" style="text-decoration:none;color:#000000;"><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210546" style="margin:0;font-weight:normal;font-size:18px;line-height:21px;max-height:43px;color:#000000;overflow:hidden;display:inline-block;">A New Internet Explorer Security Flaw Leaves One
Q...</span></a><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210549" style="font-size: 13px; line-height: 20px; color: rgb(153, 153, 153); max-height: 81px; font-family: Georgia, Times, 'Times New Roman', serif; overflow: hidden;">More bad news in the world of online security. Update:
Adobe has released a security patch.</div></div></div></td><td colspan="1" rowspan="2" class="yiv5294724278" style="width:1px;background-color:#e5e5e5;"><div class="yiv5294724278" style="width:1px;background-color:#e5e5e5;"></div></td></tr><tr class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201794" style=""><td colspan="1" rowspan="1" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201797" style="width: 100%; vertical-align: middle; font-family: Arial, 'Helvetica Neue', Helvetica, sans-serif;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201796" style="font-size:0pt;padding:7px 20px 9px 15px;"><a rel="nofollow" shape="rect" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210551" target="_blank" href="http://www.buzzfeed.com/charliewarzel/a-new-internet-explorer-security-flaw-leaves-one-quarter-of" style="color:black;text-decoration:none;cursor:pointer;"><span
class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201749" style="display:inline-block;line-height:11px;max-width:179px;min-width:119px;overflow:hidden;max-height:13px;"><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210550" style="vertical-align:middle;font-size:9px;line-height:11px;color:#999999;">View on <span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210595" style="font-weight:bold;">www.buzzfeed.com</span></span></span></a></div></td><td colspan="1" rowspan="1" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201793" style="vertical-align: middle; width: 100px; font-family: Arial, 'Helvetica Neue', Helvetica, sans-serif;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201792" style="padding:9px 20px 12px 0px;max-width:100px;min-width:80px;overflow:hidden;text-align:right;line-height:11px;max-height:13px;font-size:0pt;"><span
class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201795" style="vertical-align:middle;font-size:9px;line-height:11px;color:#999999;">Preview by
Yahoo</span></div></td></tr><tr class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201800" style=""><td colspan="6" rowspan="1" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201799" style="height:1px;background-color:#e5e5e5;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201798" style="height:1px;background-color:#e5e5e5;"></div></td></tr></tbody></table></div><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_9" style=""> </div><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_9" style="background-color:transparent;"><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_28_1398434973795_13" style=""><br clear="none" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_201735" style=""></span></div><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_9" style="background-color:transparent;"><div
class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208507" style="background-color:transparent;">Thanks</div><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208506" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208505" style="background-color:transparent;">John </div><br clear="none" class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""><div class="yiv5294724278" id="yiv5294724278WISESTAMP_SIG_866" style=""><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208488" style="font-family: Verdana, Arial, Helvetica, sans-serif;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208493" style="margin:0px 0px 8px;"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208503" style="font-family: sans-serif; font-size: 12px; width: 440px;"><img
class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208504" src="https://s3.amazonaws.com/uploads.wisestamp.com/f4825a1402c068b38b09067a18b9a112/1367525497.png?chaching=none" alt="logo" style="border-width:0px;height:31px;width:200px;"></div><table class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208492" border="0" style="font-family: sans-serif; font-size: 12px; width: 440px;"><tbody class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208496" style="width:440px;border-spacing:2px;border:0px none rgb(128, 128, 128);"><tr valign="top" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208495" style="width:440px;border-spacing:2px;border:0px none rgb(128, 128, 128);"><td colspan="1" rowspan="1" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210590" style="font-family: Impact, Charcoal; font-size: 17px; font-weight: bold; letter-spacing: 1px; text-transform: capitalize;
vertical-align: top; color: rgb(32, 32, 32); border-width: 0px 1px 0px 0px; border-style: none solid none none; border-color: rgb(32, 32, 32) rgb(0, 161, 230) rgb(32, 32, 32) rgb(32, 32, 32); padding: 1px 8px 1px 1px; width: 63px; outline: rgb(32, 32, 32) none 0px;"><span class="yiv5294724278" style="font-family: Arial; color: rgb(0, 161, 230); outline: rgb(0, 161, 230) none 0px; border-spacing: 2px; border: 0px none rgb(0, 161, 230);">John Bailer</span><div class="yiv5294724278" style="font-family: sans-serif; width: 63px; outline: rgb(32, 32, 32) none 0px; border-spacing: 2px; border: 0px none rgb(32, 32, 32);"> </div></td><td colspan="1" rowspan="1" class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208494" style="font-family: 'Arial Narrow', Arial; font-size: 13px; letter-spacing: 1px; vertical-align: top; color: rgb(80, 80, 80); padding: 1px 1px 1px 6px; width: 354px; outline: rgb(80, 80, 80) none 0px; border: 0px none rgb(80,
80, 80);"><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208502" style="font-family: sans-serif; font-size: 17px; text-transform: capitalize; margin: 0px 0px 7px; width: 354px; outline: rgb(80, 80, 80) none 0px; border-spacing: 2px; border: 0px none rgb(80, 80, 80);">CEO</div><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210594" style="font-family: sans-serif; outline: rgb(80, 80, 80) none 0px; border-spacing: 2px; border: 0px none rgb(80, 80, 80);">T. 0<span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210593" style="outline:rgb(80, 80, 80) none 0px;border-spacing:2px;border:0px none rgb(80, 80, 80);">171 409-0814</span> </span><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210592" style="font-family: sans-serif; outline: rgb(80, 80, 80) none 0px; border-spacing: 2px; border: 0px none rgb(80, 80, 80);"><span class="yiv5294724278"
style="font-weight:700;color:rgb(0, 161, 230);outline:rgb(0, 161, 230) none 0px;border-spacing:2px;border:0px none rgb(0, 161, 230);">•</span> <span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_210591" style="outline:rgb(80, 80, 80) none 0px;border-spacing:2px;border:0px none rgb(80, 80, 80);">The Stock Market Engine</span> </span><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208501" style="font-family: sans-serif; outline: rgb(80, 80, 80) none 0px; border-spacing: 2px; border: 0px none rgb(80, 80, 80);"><span class="yiv5294724278" style="font-weight:700;color:rgb(0, 161, 230);outline:rgb(0, 161, 230) none 0px;border-spacing:2px;border:0px none rgb(0, 161, 230);">•</span><span class="yiv5294724278" id="yiv5294724278yui_3_13_0_1_1398434973795_208500" style="outline:rgb(80, 80, 80) none 0px;border-spacing:2px;border:0px none rgb(80, 80, 80);"><a rel="nofollow" shape="rect" class="yiv5294724278"
id="yiv5294724278yui_3_13_0_1_1398434973795_210563" target="_blank" href="http://stockmarketengine/" style="">http://stockmarketengine</a></span></span></td></tr></tbody></table></div></div></div></div><div class="yiv5294724278" id="yiv5294724278yui_3_13_0_26_1398434973795_11" style="display:none;"> <div class="yiv5294724278" style="font-family: 'Courier New', courier, monaco, monospace, sans-serif; font-size: 10pt;"> <div class="yiv5294724278" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 12pt;"> <div class="yiv5294724278" id="yiv5294724278yqt47163" style=""><div class="yiv5294724278" id="yiv5294724278yqt38685" style=""><div class="yiv5294724278yqt2543837843" id="yiv5294724278yqt98011"><div class="yiv5294724278" dir="ltr" style=""> <font class="yiv5294724278" size="2" face="Arial" style=""> On Monday, April 28, 2014 6:45 PM, Bill Cox <waywardgeek@gmail.com> wrote:<br clear="none"
class="yiv5294724278" style=""> </font> </div> <div class="yiv5294724278" style=""><div class="yiv5294724278" id="yiv5294724278" style=""><div class="yiv5294724278" style=""><div class="yiv5294724278" dir="ltr" style=""><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div>
<div class="yiv5294724278" style="">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).</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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:</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">m11 m12 m13 ... m1N</div><div class="yiv5294724278" style="">m21 m22 m23 ... m2N</div><div class="yiv5294724278" style="">...</div><div class="yiv5294724278" style="">mN1 mN2 mN3 ... mNN</div><div class="yiv5294724278" style="">
<br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">The row chain hashes messages in row order:</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style=""> m11 m12 m13 ... m1N m21 m22 m23 ... m2N ... mNN</div><div class="yiv5294724278" style="">
<br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">The column chain hashes messages in column order:</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style=""> m11 m21 m31 ... mN1 m12 m22 m32 ... mN2 ... mNN</div><div class="yiv5294724278" style="">
<br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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:</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">m11^a, m12^a, m13, m14 ...</div><div class="yiv5294724278" style="">m21^a, m22^a, m23, m24 ...</div><div class="yiv5294724278" style="">m31, m32, m33, m34 ...</div><div class="yiv5294724278" style="">
...</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">The more messages that have to be modified, and the further apart they are, the lower the chance that the changes will cancel out.</div><div class="yiv5294724278" style="">
<br clear="none" class="yiv5294724278" style=""></div>
<div class="yiv5294724278" style="">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:</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">chain a: 1 2 3 4 5 6</div><div class="yiv5294724278" style="">chain b: 1 3 5 2 4 6</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">A loop is written like: a1 => a2 => a3 -> b3 => b1 -> a1</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">To make a chain that has a minimum loop size of 4, I can do this:</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">chain a: 1 2 | 3 4 | 5 6 | 7 8</div>
<div class="yiv5294724278" style="">chain b: 1 X | 3 X | 5 X | 7 X</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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:</div><div class="yiv5294724278" style="">
<br clear="none" class="yiv5294724278" style="">
</div><div class="yiv5294724278" style=""><div class="yiv5294724278" style="">chain a: 1 2 | 3 4 | 5 6 | 7 8 ...</div><div class="yiv5294724278" style="">chain b: 1 6 | 3 8 | 5 10 | 7 12 ...</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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):</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style=""><div class="yiv5294724278" style="">chain a: 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20 21 ...</div>
<div class="yiv5294724278" style="">chain b: 1 8 X | 4 11 X | 7 14 X | 10 17 X | 13 20 X | 16 23 X | 19 26 X ...</div></div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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:</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style=""> b8 -> a8 => a7 -> b7 => b14 -> a14 => a13 -> b13 => b20 -> a20</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">So, choose c == 18, so we span from the position after b8 all the way to a21:</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style=""><div class="yiv5294724278" style=""><div class="yiv5294724278" style="">chain a: 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20 21 ...</div>
<div class="yiv5294724278" style="">chain b: 1 8 21 | 4 11 24 | 7 14 27 | 10 17 30 | 13 20 33 | 16 23 36 | 19 26 39 ...</div></div></div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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:</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style=""> b21 -> a21 => a22 -> b22 => b39 -> a39 => a40 -> b40 => b57 -> a57 =>a58 -> b58 => b75 -> a75</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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:</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">chain a: 1 2 3 4 | 5 6 7 8 | 9 10 11 12 ...</div><div class="yiv5294724278" style="">chain b: 1 10 99 28 | 5 14 103 32 | 9 18 107 36 ...</div><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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.</div>
<div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">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...</div>
<div class="yiv5294724278" id="yiv5294724278yqtfd57553" style=""><div class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div><div class="yiv5294724278" style="">Bill</div>
</div></div></div></div></div><br clear="none" class="yiv5294724278" style=""><div class="yiv5294724278" id="yiv5294724278yqtfd31435" style="">_______________________________________________<br clear="none" class="yiv5294724278" style="">The cryptography mailing list<br clear="none" class="yiv5294724278" style=""><a rel="nofollow" shape="rect" class="yiv5294724278" ymailto="mailto:cryptography@metzdowd.com" target="_blank" href="mailto:cryptography@metzdowd.com" style="">cryptography@metzdowd.com</a><br clear="none" class="yiv5294724278" style=""><a rel="nofollow" shape="rect" class="yiv5294724278" target="_blank" href="http://www.metzdowd.com/mailman/listinfo/cryptography" style="">http://www.metzdowd.com/mailman/listinfo/cryptography</a></div><br clear="none" class="yiv5294724278" style=""><br clear="none" class="yiv5294724278" style=""></div></div></div></div> </div> </div> </div>
</div></div></div></div></div></div></div></div></div></div></body></html>