Date: Wed, 23 Apr 2014 15:31:21 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Dumb fast file digest idea...

Hi Bill,

If you alternate AES rounds with message injection on the full state,
collisions can be found instantly.

It is a non-trivial task to make a secure AES-based hash function, and
there have been many attempts during the SHA-3 competition. All of them are
not that fast.  One of problems is that the 128-bit state can provide only
64-bit security against collision attacks, which is certainly not
recommended.

I do not understand what you're doing in the last two paragraphs. A
pseudocode would help.

Bets regards,
Dmitry




On Wed, Apr 23, 2014 at 3:11 PM, Bill Cox <waywardgeek@...il.com> wrote:

> Sorry about going slightly off-topic for this list, but certainly there
> are experts here who will see the flaws in this idea.  Basically, I'm
> wondering if we can use a memory buffer to considerably speed up
> computation of secure file hashes using reducing rounds, without giving up
> any security.
>
> I was trying last night use the new AESENC instruction to compute file
> hashes very rapidly.  There are probably more problems with AESENC, but a
> major one is that a single round (one AESENC instruction) is by itself not
> cryptographically secure.  It normally requires 10 rounds to produce a 128
> bit encrypted result, plus a lot of mucking with round keys and such.  When
> I use AESENC to encrypt a "state" using sequential 16-byte blocks of the
> message as the key, I don't think the resulting hash is secure.  Being a
> speed freak, I love it's speed!  I am able to compute a digest of a random
> 512MiB file in 68 milliseconds!  The file was already cached, of course.
>  Being secure would be a plus in this situation...
>
> To find a collision, an attacker only has to figure out how to modify two
> adjacent blocks of 16 bytes of the file in such a way that it results in
> the same encrypted state 2 AESENC instructions later.  While that is likely
> difficult, it is nowhere near the effort of doing that if we had performed
> the full AES algorithm each 16 byte block.
>
> What if we do a simple post-process on the sequence of states generated?
>  Just fill a memory buffer with the computed 16-byte state values,
> incrementing by say 128*16 every time, so that we have to make 128 passes
> over the memory to fill it.  This insures that state blocks which are near
> each other in memory are vastly separated computationally, by very many
> rounds of AESENC.  Once the block of memory is full, feed it into the
> original simple AESENC loop, using sequential blocks of 16-bytes from the
> buffer as the key.
>
> This takes 2 AESENC instructions per 16 bytes of output, and probably
> busts into L2 cache, but I bet it's still very fast.  As with EARWORM,
> running 4 parallel tracks of AESENC speed things up considerably.  I've
> probably messed up a number of details, but can such an algorithm provide
> the same security of other 128-bit cryptographic hashes, while running much
> faster?  The same scheme could be (and maybe I'll write this) used with
> Blake2b, doing 1 round of Blake2b rather than 8, filling memory as above,
> and doing a 1 round hashes of the buffer when full.  The last partial
> buffer could be processed in the usual way, with full rounds.  I think it
> would run amazingly fast.  We'd be doing an average of 2 rounds rather than
> 8 per 32-byte block.  Would it be secure?
>
> Bill
>



-- 
Best regards,
Dmitry Khovratovich

Content of type "text/html" skipped

Powered by blists - more mailing lists