2
$\begingroup$

I know about PBKDF2, bcrypt, scrypt, etc. and while I'm not a crypt professional, I think I understand why are they better than just "hash(pass+salt)".

But a colleague of mine surprised me with the following password hash function which he claims to be good, because

  1. It is slow on CPU (takes about 2-3 seconds in i5)
  2. It will be slower on GPU because needs random access to a lot of memory (why? GPUs have lots of gigabytes)
  3. It cannot be timed, any time-based attack will fail even if underlying hash-function will be vulnerable (aren't hash calculation time a constant, for SHA512 at least?).
  4. It cannot be cracked by audio attack because of fake operations (what's that?)

So while I do not like bicycles in cryptography in general, arguments sound reasonable and I just want to know the truth fro myself, in the first place and to argue for rewriting of this code to something standard.

EDIT

So here are some specific questions, as suggested in comment by @B-Con:

  1. Why this (needing a lot of memory) hash will be slow of GPU?
  2. Isn't SHA512 and RIPEMD160 calculation time a constant?
  3. Does a fake data processing in parallel of real data really help against audio attack whatever it is?

    private static readonly RNGCryptoServiceProvider _random = new RNGCryptoServiceProvider();
    private const int BlockCount = 1024;
    private const int IterationCount = 65536;
    
    private static byte[] GetHashInternal(byte[] data, byte[] salt)
    {
        var sha512 = new SHA512Managed();
        var ripemd = new RIPEMD160Managed();
        var hashLength = (sha512.HashSize / 8) + (ripemd.HashSize / 8);
        var realHash = new byte[BlockCount * hashLength];
        var fakeHash = new byte[BlockCount * hashLength];
        var realData = new byte[hashLength];
        var realSalt = new byte[hashLength];
        var fakeData = new byte[hashLength];
        var fakeSalt = new byte[hashLength];
    
        for (var index = 0; index < data.Length; index++)
        {
            realData[index % (hashLength - 1)] ^= data[index];
        }
    
        for (var index = 0; index < salt.Length; index++)
        {
            realSalt[index % (hashLength - 1)] ^= salt[index];
        }
    
        _random.GetBytes(fakeData);
        _random.GetBytes(fakeSalt);
    
        var length1 = sha512.HashSize / 8;
        var length2 = ripemd.HashSize / 8;
        var offset = 0;
    
        for (var step = 0; step < IterationCount; step++)
        {
            for (var index = 0; index < hashLength; index++)
            {
                realHash[(offset + index) % realHash.Length] ^= realData[index];
            }
    
            for (var index = 0; index < hashLength; index++)
            {
                fakeHash[(offset + index) % realHash.Length] ^= fakeData[index];
            }
    
            Array.Copy(sha512.ComputeHash(realHash, offset, hashLength), 0, realHash, (offset + (hashLength / 2)) % (realHash.Length - length1), length1);
            Array.Copy(sha512.ComputeHash(fakeHash, offset, hashLength), 0, fakeHash, (offset + (hashLength / 2)) % (fakeHash.Length - length1), length1);
            Array.Copy(ripemd.ComputeHash(realHash, offset, hashLength), 0, realHash, (offset + length1 + (hashLength / 2)) % (realHash.Length - length2), length2);
            Array.Copy(ripemd.ComputeHash(fakeHash, offset, hashLength), 0, fakeHash, (offset + length1 + (hashLength / 2)) % (fakeHash.Length - length2), length2);
    
            for (var index = 0; index < hashLength; index++)
            {
                realHash[(offset + index) % realHash.Length] ^= realSalt[index];
            }
    
            for (var index = 0; index < hashLength; index++)
            {
                fakeHash[(offset + index) % realHash.Length] ^= fakeSalt[index];
            }
    
            Array.Copy(ripemd.ComputeHash(realHash, offset, hashLength), 0, realHash, (offset + length1 + (hashLength / 2)) % (realHash.Length - length2), length2);
            Array.Copy(ripemd.ComputeHash(fakeHash, offset, hashLength), 0, fakeHash, (offset + length1 + (hashLength / 2)) % (fakeHash.Length - length2), length2);
            Array.Copy(sha512.ComputeHash(realHash, offset, hashLength), 0, realHash, (offset + (hashLength / 2)) % (realHash.Length - length1), length1);
            Array.Copy(sha512.ComputeHash(fakeHash, offset, hashLength), 0, fakeHash, (offset + (hashLength / 2)) % (fakeHash.Length - length1), length1);
    
            offset = (offset + 13) % (realHash.Length - hashLength);
        }
    
        return sha512.ComputeHash(realHash);
    }
    
$\endgroup$
6
  • 2
    $\begingroup$ Hi there. Crypto.SE discourages custom algorithm analysis, which is really the essence of this question. You may receive better information by sifting your question down to a set of specific questions about achieving certain cryptographic properties. As it stands, the question is possibly in danger of being removed. $\endgroup$
    – B-Con
    Feb 25, 2014 at 6:15
  • 1
    $\begingroup$ All the properties you enumerate are supposed to be achieved by scrypt. Scrypt has a paper behind it and it is used by many people out there. Even if that's true many people would consider you an early user if you use scrypt (because it's been there for not so many years). So, do you think your colleague's algorithm is worth the risk? Has he exposed it? Is anyone else using it? $\endgroup$
    – xxxxxxxxx
    Feb 25, 2014 at 7:45
  • $\begingroup$ Audio attack: en.wikipedia.org/wiki/Acoustic_cryptanalysis $\endgroup$
    – xxxxxxxxx
    Feb 25, 2014 at 7:46
  • $\begingroup$ The technique for avoiding timing attacks doesn't work. So if the salt is known, it's just as vulnerable to side channel attacks as scrypt with known salt. At a glance this looks like a badly done variant of scrypt. $\endgroup$ Feb 25, 2014 at 9:57

1 Answer 1

6
$\begingroup$

The threat model of password storage is that of server compromision, where the attacker gain access to the database and server code. The attacker can then run the code to test password candidates, possibly making modifications, porting to faster platform, etc.

The attacker will not bother computing the fake hash and fake salt. So this scheme is twice as slow for the real server than for the attacker.

for (var index = 0; index < data.Length; index++)
{
    realData[index % (hashLength - 1)] ^= data[index];
}

That part is quite interesting and breaks a lot of things that the designers of one-way hash functions painstainkingly crafted into their babies.

The realData array is initialized with zeroes and if data length is less than hashLength, not all of it will be filled with actual data at the end of the loop. Any pair of inputs that differ only in the number of trailing zeroes will hash to the same thing. (Granted, it might not be possible to input \x00 as a valid password character, but still).

Then, I think there is a one-off error, it should simply be realData[index % hashLength]. As is, realData[hashlength - 1] will never be set.

In addition, there will be collisions with longer strings, it suffice to find pairs of bytes that XOR to the same thing. For the simplest example, a string of 2 * hashLength of the same repeated character will hash to the same thing as any other string of 2 * hashLength of another repeated character. When the index loops over, the character will be XORed with itself, yielding 0. There are many other way to find collisions even before looking at the internal loops.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.