<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Apr 25, 2014 at 12:16 AM, Joshua Marpet <span dir="ltr"><<a href="mailto:joshua.marpet@guardedrisk.com" target="_blank">joshua.marpet@guardedrisk.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>So the particular methodology you tried isn't working.  Next?</div>
</div></blockquote><div><br></div><div>Thanks for the encouragement.  It's nice to hear in crypto land.  It's a tough place for hobbyists and dabblers, which I think is a shame.  Internet security is in shambles, and it's not so much the expert's fault as the next level down, guys like me who don't get paid to do this, but who now and then get told to go implement some security widget (happens all the time).  I wish we were better about getting people in-the-loop, but instead we have a "just don't do it" approach that works about as well as our "just say no" commercials.  I think we should all be encouraged to write our own public-key cryptosystem, so long as no one uses them.  Here's mine:</div>
<div><div><br></div><div>    <a href="https://github.com/waywardgeek/bmat">https://github.com/waywardgeek/bmat</a><br></div></div><div><br></div><div>Two things next:  First, someone pointed me to Dmitry's Ph.D. thesis:</div>
<div><br></div><div>    <a href="https://cryptolux.org/images/b/b3/Thesis.pdf">https://cryptolux.org/images/b/b3/Thesis.pdf</a></div><div><br></div><div>I'll have some fun reading that.  Second, there seems to be significant security gain in hashing large super-blocks at once, rather than blocks no bigger than the hash state.  I want to explore this more.  Maybe I should read the thesis first, but what's the fun in that?  Reinventing the wheel is most of what everyone does now days, and they wind up wiser for it.  That provides people the gut-feel for a field that the original pioneers had.  I'll have to read it eventually, though...</div>
<div><br></div><div>I figured out yesterday that 3 states and 3 chains are required for obscure (to me) reasons.<br></div><div><br></div><div>Assume you want to create a collision with only 2 chains.  Assume you have a simple 1-bit flip that is preserved by R some percentage of the time, like 50%.  You can flip this bit, and also in the next message block, and the changes cancel with 50% probability in one chain.  The other chain, however, separates those bit flips by a long distance, so you have to do 2 more message bit-flips on the other chain to cancel them, and now our probability of succeeding is down to 1/8th (still very high).</div>
<div><br></div><div>Samuel was kind enough to email me an explanation of the more general tool called a "differential characteristic".  The idea is to find some input bit-flip pattern "a" that results in an output bit flip pattern "b" with high probability:</div>
<div><br></div><div>ROUND(state ^ a) = ROUND(state) ^ b<br></div><div><br></div><div>My simple 1-bit flip -> same bit flip is just a sub-set of this, but it works well enough for my purposes for now.</div><div><br></div>
<div>This is where my analysis before went wrong:  I assumed that if a single bit flip turned into two, and then six (it's up to 6 flips by the time we make our two corrections on the second chain), then it must explode exponentially.  Nope!  When 2 became 4, that was the only doubling that occurs.  After that, an attacker has two adjacent choices to make his correction, and the two correction paths bounce back and forth between chains until there are either too many for any chance of success relative to random guessing (meaning < 1/2^512 - so very many are needed!), or the chains converge with a useful probability of cancelling each other.  With the bit-reversal pattern, many of these two tracks meet up (become adjacent) after 2 bounces, and have a reasonable chance of canceling each other out, so two-chains using bit-reversal permutation is a dead end.</div>
<div><br></div><div>I worked a bit on message block permutations that guarantee that the tracks don't meet for as long as possible.  This turns out not to work out well.  Every node has to be highly unrelated to every other at the same time.  It can't be done with enough distance to be effective.</div>
<div><br></div><div>So, I have to add a 3rd state and message hashing chain.  With 3, every message bit-flip creates two changes in the other two chains, both of which have to be fixed locally.  This does explode exponentially, and has some potential, I think.</div>
<div><br></div><div>A reasonable way to think of this hashing approach is instead of multiple chains, it's just a bigger state (three times bigger).  The difference between this and normal block hash is that it hashes many input blocks at the same time, allowing each operation to cause an attacker more pain, by spreading the changes farther apart.  I think this can lead to much faster secure file hashing, though the algorithm would not be efficient for small block hashes, so it would not be general-purpose.  It's still very cool :-)</div>
<div><br></div><div>Bill</div></div></div></div>