phc-discussions - Re: [PHC] Dumb fast file digest idea...

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Wed, 23 Apr 2014 10:03:01 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Dumb fast file digest idea...

On Wed, Apr 23, 2014 at 9:31 AM, Dmitry Khovratovich <khovratovich@...il.com
> wrote:

> 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 see.  Blake2b should still be a decent candidate for the lower level
primitive, providing up to 256 bits of collision resistance?

> I do not understand what you're doing in the last two paragraphs. A
> pseudocode would help.
>
> Bets regards,
> Dmitry
>

The code, without parallel lanes or dealing with the last partial block, or
optimizing memory accesses, would look something like:

blockSize = 64*128*128 // 1 MiB buffer
uint512 block[128*128]
uint512 state = 0
while(block = readBlockFromFile(file)) {
    state = hashBlock(block, state)
}
output state // Digest of file

hashBlock(uint512 block[128*128], uint512 state) {
    uint512 buffer[128*128]
    for(i = 0; i < 128; i++) {
        for(j = 0; j < 128; j++) {
            state = Blake2B_ROUND(state, block[i*128+j])
            buffer[i + j*128] = state // Note that we multiply j, not i by
128
        }
    }
    for(i = 0; i < 128*128; i++) {
        state = Blake2B_ROUND(state, buffer[i])
    }
    return state
}

In this case, Blake2b_ROUND would be something like Lyra2's modified
Blake2b round, where the state and 512 bits of input are XORed together
before doing just the one round.  I incorrectly stated that Blake2b uses 8
rounds above.  It normally uses 12.  This version would use only 2.

By writing non-cryptographically strong single-round hashes separated by
long distances in memory, and then doing an outer hash of the memory,
adjacent memory locations should not be at all correlated.  Wont this allow
a cryptographically strong hash be derived from the buffer using only 1
round per 512-bit location in the buffer?  Of course, I'm very often
wrong...

Bill

Content of type "text/html" skipped