Slowing password hashing. What for?

    Good day, habraparanoik! Today we’ll talk about a slightly unusual way to increase security, namely slowing down password hashing . It would seem that when everyone around is trying to optimize, why slow down something?
    At least then, that even in the most super-duper protected system, the weakest link remains a person. Namely, his password.

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

    Under the cut, my free interpretation of this process.


    The meaning of the whole action is as follows:
    • The encryption key is important not the password, but the (slow) hash from it
    • It costs the user nothing 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 everyone’s favorite rainbow tables , which are quite successfully generated even for systems using sugar and salt . Their generation will also become, if not useless, then very labor-intensive.

    I'm not saying that salt systems are bad, they just can be 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. Concatenate it and hash
    6. Cache, remember the result}

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

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

    1. I use 2 hashing algorithms (SHA-256 and SHA-512), so for starters there is a small interface that will help us to more or less universalize this 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 yummy. 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 will say right away that you should not be afraid of numerous inserts & 0xFF. This is just a conversion of signed byte to unsigned by converting it to int and applying such a bitmask. And all because in java there are no unsigned types! Absolutely! Well, okay, this is not fatal.

    All the beauty here is the formation of round salt, so the main attention will be paid to 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 - the size of the round salt. 4 bytes for SHA-256 and 8 bytes for SHA-512
    • temp - array of res array size elements plus round salt size roundSaltSize
    • s_primeIndices - 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 computing the first byte of the round salt for SHA-256 with res [7], the second with res [11], etc. For SHA-512 all indexes will be involved
    • btemp - a byte that after a series of tricky conversions will fall into place in the round salt

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

    1. In 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 basic salt and password forgot
    3. We start a long cycle in 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 store in btmp an element that is located at one of the indices (7, 11, 17 ...) depending on the number of the current byte (j)
    7. Then do the following 7 (k) times:
    8. We take the remainder from the division of btmp, in which the bits are shifted to the right by k positions, by the length of the array res
    9. we use the previous number as an index for the res array, we pull out the number at this index
    10. btmp assign this number, added to btmp modulo 256 and scrolled to the right by 8-k bits
    11. Put 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 + ranud salt) + round salt) ... which can be used as a 256-bit encryption key for important information for AES-256, for example.

    On my machine (C2D 2.6), it takes about 0.25 seconds to generate one hash, which I think is acceptable for use. in their projects. You can increase the number of rounds and then time will increase accordingly.

    If it is interesting to a respected public, I can tell you about other applied aspects of working with the BouncyCastle library, such as symmetric / asymmetric encryption, certificate generation, etc.

    UPD:
    The comments indicated a link to the dock, in which this kind of scheme takes on even greater scope

    Also popular now: