[Cryptography] Two round secure hashing

[Bill Cox]

On Fri, Apr 25, 2014 at 12:16 AM, Joshua Marpet <
joshua.marpet at guardedrisk.com> wrote:

> So the particular methodology you tried isn't working.  Next?
>

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:

    https://github.com/waywardgeek/bmat

Two things next:  First, someone pointed me to Dmitry's Ph.D. thesis:

    https://cryptolux.org/images/b/b3/Thesis.pdf

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...

I figured out yesterday that 3 states and 3 chains are required for obscure
(to me) reasons.

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).

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:

ROUND(state ^ a) = ROUND(state) ^ b

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.

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.

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.

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.

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 :-)

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140425/2fdb22f9/attachment.html>