Date: Thu, 6 Feb 2014 21:48:59 -0600 (CST)
From: Steve Thomas <steve@...tu.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Re: NoelKDF ready for submission

> On February 4, 2014 at 5:03 PM Bill Cox <waywardgeek@...il.com> wrote:
>
> On Tue, Feb 4, 2014 at 2:01 PM, Steve Thomas <steve@...tu.com> wrote:
> > I found two bugs in your reference code:
> >
> > NoelKDF() Line 102:
> > + numblocks <<= startGarlic;
> > for(i = startGarlic; i <= stopGarlic; i++) {
> >
> > NoelKDF() Line 107:
> > - value += mem[2 * p * numblocks * blocklen + blocklen - 1];
> > + value += mem[(2 * p + 1) * (uint64) numblocks * blocklen - 1];
> > I'm assuming this is a bug since the original is using the last int in the
> > first
> > block. Which is known early on.
>
> Thanks for finding these! I'm using your suggested fix for the 1st
> one, and thinking of just initializing the second loop with value == 1
> like the first. Do you think that would be OK?

Yes, but only because when value is one the first fromAddr is the last block.


> > xorIntoHash() needs to be replaced preferably with a cryptographic hash that
> > uses more than the last hash's size bytes of data. You can reverse a 256 bit
> > non-parallel hash to on average 3 bits of the state in "mem" 7 steps prior
> > through hashBlocks()'s "fromAddr". Also 6 bits from 6 prior, 9 bits from 5
> > prior, 12 bits from 4 prior, ..., 21 bits from 1 prior, and 256 bits from
> > the
> > last block.
>
> Did you notice that wordHash is initialized as the PBKDF2-SHA256 of
> the password and salt?

Yes.


> If I simply XOR-ed the results of the memory
> hashing together, that would be a problem, but since wordHash starts
> out life as indistinguishable from true random data, XOR-ing lower
> quality memory hashes into it cannot damage it's quality.

The quality of random is not in question here.


> I may be unfamiliar with the attack you are referring to, but I don't
> think there is an issue here.

hash = PBKDF2_SHA256(password, salt, 1, hashSize)
...
return hash ^ lastHashSizeBytesOfMem
Make a guess and xor "PBKDF2_SHA256(password, salt, 1, hashSize)" to the hash
you are trying to crack. You now have the assumed last bytes of mem.

Let's say the hash is 256 bits that's 8, 32 bit numbers. We can reverse this
data modulo 4 to 7, 2 bit numbers from "mem[fromAddr+j]":

memHash[i+1] % 4 = (memHash[i] * (mem[prevAddr+blockSize-8+i] | 3) +
mem[fromAddr+blockSize-8+i]) % 4
memHash[i+1] % 4 = (memHash[i] * 3 + mem[fromAddr+blockSize-8+i]) % 4
mem[fromAddr+blockSize-8+i] % 4 = (memHash[i+1] - memHash[i] * 3) % 4

mem[fromAddr+blockSize-8] % 4 = (memHash[1] - memHash[0] * 3) % 4
mem[fromAddr+blockSize-7] % 4 = (memHash[2] - memHash[1] * 3) % 4
mem[fromAddr+blockSize-6] % 4 = (memHash[3] - memHash[2] * 3) % 4
mem[fromAddr+blockSize-5] % 4 = (memHash[4] - memHash[3] * 3) % 4
mem[fromAddr+blockSize-4] % 4 = (memHash[5] - memHash[4] * 3) % 4
mem[fromAddr+blockSize-3] % 4 = (memHash[6] - memHash[5] * 3) % 4
mem[fromAddr+blockSize-2] % 4 = (memHash[7] - memHash[6] * 3) % 4

mem[fromAddr2+blockSize-8] % 4 = (mem[fromAddr+blockSize-7] -
mem[fromAddr+blockSize-8] * 3) % 4
mem[fromAddr2+blockSize-7] % 4 = (mem[fromAddr+blockSize-6] -
mem[fromAddr+blockSize-7] * 3) % 4
mem[fromAddr2+blockSize-6] % 4 = (mem[fromAddr+blockSize-5] -
mem[fromAddr+blockSize-6] * 3) % 4
mem[fromAddr2+blockSize-5] % 4 = (mem[fromAddr+blockSize-4] -
mem[fromAddr+blockSize-5] * 3) % 4
mem[fromAddr2+blockSize-4] % 4 = (mem[fromAddr+blockSize-3] -
mem[fromAddr+blockSize-4] * 3) % 4
mem[fromAddr2+blockSize-3] % 4 = (mem[fromAddr+blockSize-2] -
mem[fromAddr+blockSize-3] * 3) % 4
...

Now do the first half in modulo 4. 1/16 memory plus the extra 31% to 25% memory
reduction and this removes the multiplication. You can do this in AVX2 and get
128 different password guesses running at a time.

Vectorized version of modulo 4 of value = value*3 + mem[fromAddr + i]:
tmp = ((value & 0x5555...) << 1) ^ value
value = (tmp ^ mem[fromAddr + i]) ^ ((tmp & mem[fromAddr + i] & 0x5555...) << 1)

Now that we have the first half we just check if we can find this in the first
half:
mem[fromAddr7+blockSize-8] % 4

mem[fromAddr6+blockSize-8] % 4
mem[fromAddr6+blockSize-7] % 4

mem[fromAddr5+blockSize-8] % 4
mem[fromAddr5+blockSize-7] % 4
mem[fromAddr5+blockSize-6] % 4

Keep in mind I'm not sure what the probability of false negatives or false
positive or the optimal number of reversed fromAddr's to check. So this may be
a non-issue.

Also I said you could on average reverse 3 bits, but that's only on the first
reversal. Basically if the least significant bit is 0 then you can get 3 bits
from "mem[fromAddr+j]" if the least significant 2 bits are 00 then 4 bits.
Anyway once you are down to 2 bits you can't get more bits when reversing.
Content of type "text/html" skipped

Powered by blists - more mailing lists