lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Thu, 6 Feb 2014 21:48:59 0600 (CST)
From: Steve Thomas <steve@...tu.com>
To: discussions@...swordhashing.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
> > nonparallel 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 PBKDF2SHA256 of
> the password and salt?
Yes.
> If I simply XORed the results of the memory
> hashing together, that would be a problem, but since wordHash starts
> out life as indistinguishable from true random data, XORing 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+blockSize8+i]  3) +
mem[fromAddr+blockSize8+i]) % 4
memHash[i+1] % 4 = (memHash[i] * 3 + mem[fromAddr+blockSize8+i]) % 4
mem[fromAddr+blockSize8+i] % 4 = (memHash[i+1]  memHash[i] * 3) % 4
mem[fromAddr+blockSize8] % 4 = (memHash[1]  memHash[0] * 3) % 4
mem[fromAddr+blockSize7] % 4 = (memHash[2]  memHash[1] * 3) % 4
mem[fromAddr+blockSize6] % 4 = (memHash[3]  memHash[2] * 3) % 4
mem[fromAddr+blockSize5] % 4 = (memHash[4]  memHash[3] * 3) % 4
mem[fromAddr+blockSize4] % 4 = (memHash[5]  memHash[4] * 3) % 4
mem[fromAddr+blockSize3] % 4 = (memHash[6]  memHash[5] * 3) % 4
mem[fromAddr+blockSize2] % 4 = (memHash[7]  memHash[6] * 3) % 4
mem[fromAddr2+blockSize8] % 4 = (mem[fromAddr+blockSize7] 
mem[fromAddr+blockSize8] * 3) % 4
mem[fromAddr2+blockSize7] % 4 = (mem[fromAddr+blockSize6] 
mem[fromAddr+blockSize7] * 3) % 4
mem[fromAddr2+blockSize6] % 4 = (mem[fromAddr+blockSize5] 
mem[fromAddr+blockSize6] * 3) % 4
mem[fromAddr2+blockSize5] % 4 = (mem[fromAddr+blockSize4] 
mem[fromAddr+blockSize5] * 3) % 4
mem[fromAddr2+blockSize4] % 4 = (mem[fromAddr+blockSize3] 
mem[fromAddr+blockSize4] * 3) % 4
mem[fromAddr2+blockSize3] % 4 = (mem[fromAddr+blockSize2] 
mem[fromAddr+blockSize3] * 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+blockSize8] % 4
mem[fromAddr6+blockSize8] % 4
mem[fromAddr6+blockSize7] % 4
mem[fromAddr5+blockSize8] % 4
mem[fromAddr5+blockSize7] % 4
mem[fromAddr5+blockSize6] % 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 nonissue.
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