Slow password hashing. What for?

Good day, habraraparanik! Today we will talk about a slightly unusual way to increase security, namely, slowing down password hashing . It would seem that when everyone is trying to optimize everything, why should we slow down something?

At least then, that even in the super-duper itself, the protected system remains the weakest link. Namely, his password.



Have you ever tried to hack an encrypted rar archive? And how many passwords per second did it go through? 50-100-200? Even on a good GPU, using the notorious cRARk, the search speed is only about 2400 options / sec. And this is in comparison with tens (hundreds) of millions of passwords / sec for zip / md5 / SHA1.



Under the cut is my free interpretation of this process.



')

The meaning of the whole action is as follows:

• The encryption key is not the password, but the (slow) hash of it.
• The user does not cost anything to wait a second / half a second while the password is cached
• But homo brutforsus will have to be patient

Yes, I almost forgot about all your favorite rainbow tables , which are quite successfully generated even for systems that use sugar and salt . Their generation will also become if not useless, then very labor-intensive.



I'm not saying that the systems with salt are bad, they just can be further strengthened.



And so, there is salt, there is a password. What's next?



And then everything is pretty simple:

1. Concatenate salt and password
2. Hash, remember the result
3. while (many many times) do {
4. generate round salt
5. Combine it and hash
6. Cache, remember the result}

In Winrar (thanks to him, by the way, for inspiration), if my memory serves me, the round salt is the iteration number. I went a little further.



So the code. Everything is written in java using the BouncyCastle library, but for the thoughtful habrandaranik, it will not be difficult to transfer this (and maybe add your own) to any programming language that is full of turing. In addition, BouncyCastle is for C #.



1. I use 2 hash algorithms (SHA-256 and SHA-512), so for starters, a small interface that will help us more or less universalize the whole thing.

public interface IDigest

{

public byte [] process ( byte [] data);



public int getSize ();

}

2. An example of the implementation of this interface for the SHA-256 algorithm (using the SHA256Digest class from the BouncyCastle library):

public class SHA256 implements IDigest

{



private SHA256Digest m_SHA256 = new SHA256Digest ();



@Override

public byte [] process ( byte [] data)

{

m_SHA256.reset ();

m_SHA256.update (data, 0, data.length);

byte [] result = new byte [m_SHA256.getDigestSize ()];

m_SHA256.doFinal (result, 0);

return result;

}



@Override

public int getSize ()

{

return m_SHA256.getDigestSize ();

}

}

3. The most delicious. I will explain it in detail.

public class SlowHasher

{

private final static int BITS_IN_BYTE = 8;



private static final int [] s_primeIndices = new int [] {7, 11, 17, 23, 31, 41, 47, 53, 61};



/ **

* this method hashes password 0x50000 times adding round salt each round

*

* param digest

* param password

* return

* /

public byte [] calculateSlowHash (IDigest digest, String password, byte [] salt)

{

int roundSaltSize = digest.getSize () / BITS_IN_BYTE;

byte [] bPasswd = password.getBytes ();

byte [] toHash = new byte [bPasswd.length + salt.length];



/ *

* composing array of bytes that will be hashed

* /

System.arraycopy (salt, 0, toHash, 0, salt.length);

System.arraycopy (bPasswd, 0, toHash, salt.length, bPasswd.length);



byte [] res = digest.process (toHash);

byte [] temp = new byte [res.length + roundSaltSize];



for ( int i = 0; i <0x50000; i ++)

{

System.arraycopy (res, 0, temp, 0, res.length);



/ ***

* calculating salt

* /

for ( int j = 0; j <roundSaltSize; j ++)

{

int btmp = res [s_primeIndices [j]] & 0xFF;

for ( int k = 1; k <BITS_IN_BYTE; k ++)

{

btmp = ror ((btmp + (res [ror (btmp, k)% res.length] & 0xFF))% 256, BITS_IN_BYTE-k);

}

temp [res.length + j] = ( byte ) btmp;

}

res = digest.process (temp);

}

return res;

}



/ **

* rotate bits right treating input as byte

* param value 0 <= value <= 255

* param n number of bits to shift

* return

* /

public static int ror ( int value , int n)

{

return (( value >> (n% BITS_IN_BYTE)) | (( value << (8 - (n% BITS_IN_BYTE))) & 0xFF));

}

}



People who are not familiar with java I will say right away that you should not be afraid of the many inserts & 0xFF . This is just converting signed byte to unsigned by converting it to an int and applying such a bitmask. And all because there are no unsigned types in java! Totally! Well, okay, this is not deadly.



All the beauty here is the formation of round salt, so the focus will be on it.



A little bit about variables:

• res is an array of 32 bytes for SHA-256 or 64 bytes for SHA-512. It stores the hash result.
• roundSaltSize is the size of the round salt. 4 bytes for SHA-256 and 8 bytes for SHA-512
• temp is an array of res array size elements plus the size of the round salt roundSaltSize
• s_primeIndices is an array of indices of elements in the res array, starting from which we will calculate the corresponding byte of the round salt. That is, we will start the computation of the first byte of the round salt for SHA-256 with res [7], the second with res [11], etc. All indexes will be used for SHA-512
• btemp - byte, which after a series of clever transformations will take its place in the round salt

Another remark before we proceed to the explanation of the formation of the algorithm of the round salt. The whole algorithm is not the result of any scientific research and tests. It was created to generate a value that would be dependent on some bytes of the resulting hash and would help to slow down and complicate it. Well, now the description:

1. At the beginning, the main salt and password are collected in the toHash array.
2. The toHash array is hashed and the result is stored in the res array. Everything, about the main salt and password forgot
3. Run a long loop at 0x50000 iterations
4. Next we work with the temp array, into which we copy the res array. At the end of the temp array, there are still 4 or 8 bytes for salt. We have to fill them
5. For each of the round salt bytes:
6. We remember in btmp an element that is located in one of the indices (7, 11, 17 ...) depending on the number of the current byte (j)
7. Then 7 (k) times we do the following:
8. Take the remainder of the btmp division, in which the bits are shifted to the right by k positions, by the length of the res array
9. the previous number is used as an index for the array res, we pull out the number at this index
10. btmp assign this number folded with btmp modulo 256 and scrolled to the right by 8-k bits
11. We place btmp in its place after the hash in the temp array
12. Hash temp

The call to this method is as follows:

byte [] salt = new byte [16];

new SecureRandom (). nextBytes (salt); // generate random 16byte salt

byte [] hashedPassword = new SlowHasher (). calculateSlowHash ( new SHA256 (), password, salt);

The result is a hash (hash (hash + ranoid salt) + round salt) ... which can be used as a 256-bit key to encrypt important information for AES-256, for example.



On my machine (C2D 2.6) the generation of one hash accounts for about 0.25 seconds, which I consider acceptable for use. in their projects. You can increase the number of rounds and then the time will grow accordingly.



If it’s interesting for a respected public, I can tell you about other applied aspects of working with the BouncyCastle library like symmetric / asymmetric encryption, certificate generation, etc.



UPD:

In the comments indicated a link to the dock, in which this kind of scheme takes even greater scope