Замедление хеширования паролей. Зачем?

Доброго времени суток, хабрапараноик! Сегодня мы поговорим о немного необычном способе повышения безопасности, а именно замедлении хеширования паролей. Казалось бы, когда всё вокруг стараются оптимизировать, зачем что то замедлять?
Хотя бы затем, что даже в самой супер-пупер защищенной системе самым слабым звеном остается человек. А именно, его пароль.

Вы пытались когда нибудь взломать зашифрованный rar архив? И сколько паролей в секунду оно перебирало? 50-100-200? Даже на хорошем GPU, при использовании небезызвестного cRARk, скорость перебора всего около 2400 вариантов/сек. И это-то по сравнению с десятками (сотнями) миллионов паролей/сек для zip/md5/SHA1.

Под катом моя вольная интерпретация этого процесса.


Смысл всего действа сводится к следующему:

• Ключом шифрования важной является не пароль, а (медленный) хэш от него
• Юзеру ничего не стоит подождать секунду\пол секунды пока пароль прохешируется
• А вот homo brutforsus придется запастись терпением

Да, чуть не забыл про всеми любимые rainbow tables, которые довольно успешно генерятся даже для систем, использующих сахар соль. Их генерация тоже станет если не бесполезной, то очень трудозатратной.

Я не говорю, что системы с солью плохие, просто их можно еще усилить.

И так, есть соль, есть пароль. Что дальше?

А дальше все довольно просто:

1. Конкатенируем соль и пароль
2. Хэшируем, запоминаем результат
3. while (много много раз) do{
4. сгенерировать раундовую соль
5. Сконкатенировать её и хэш
6. Прохэшировать, запомнить результат}

В Winrar (спасибо ему, кстати, за вдохновение), если мне не изменяет память, раундовой солью является номер итерации. Я же пошел немножко дальше.

Итак, код. Всё написано на java с использованием библиотеки BouncyCastle, но вдумчивому хабрапараноику не составит сложности перенести это (и может быть добавить своё) на любой язык программирования, полный по тьюрингу. К тому же BouncyCastle есть и для C#.

1. Я использую 2 алгоритма хеширования (SHA-256 и SHA-512), поэтому для начала небольшой интерфейсик, который поможет нам всё это дело более-менее универсализировать.

public interface IDigest
{
    public byte[] process(byte[] data);
    
    public int getSize();
}

2. Пример реализации этого интерфейса для алгоритма SHA-256 (используется класс SHA256Digest из библиотеки BouncyCastle):

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. Самая вкуснятина. Её я объясню подробно.

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));
    }
}

Людям не знакомым с java скажу сразу, что не стоит пугаться многочисленных вставок & 0xFF. Это всего лишь конвертация signed byte в unsigned путем преобразования его в int и применения такой вот битовой маски. А всё потому, что в java нет unsigned типов! Совсем! Ну да ладно, это не смертельно.

Вся красивость тут заключается в формировании раундовой соли, поэтому основное внимание будет уделяться ей.

Немного о переменных:

• res — массив из 32 байт для SHA-256 или 64 байт для SHA-512. В нем хранится результат хеширования
• roundSaltSize — размер раундовой соли. 4 байта для SHA-256 и 8 байт для SHA-512
• temp — массив из элементов размера массива res плюс размер раундовой соли roundSaltSize
• s_primeIndices — массив индексов элементов в массиве res, начиная с которых мы будем вычислять соответствующий байт раундовой соли. То есть, начинать вычисления первого байта раундовой соли для SHA-256 мы будем с res[7], второго с res[11] и т.д. Для SHA-512 будут задействованы все индексы
• btemp — байт, который после серии хитрых преобразований станет на своё место в раундовой соли

Еще одна ремарка прежде чем мы перейдем к разъяснениям формирования алгоритма раундовой соли. Весь алгоритм не является результатом каких либо научных исследований и тестов. Он создан для формирования значения, которое было бы зависимо от некоторых байтов результирующего хэша и помогло бы его замедлить и усложнить. Ну а теперь описание:

1. В начале в массив toHash собираются основная соль и пароль
2. Массив toHash хешируется и результат запоминается в массиве res. Всё, про основную соль и пароль забыли
3. Запускаем длинный цикл в 0x50000 итераций
4. Далее работаем с массивом temp, в который копируем массив res. В конце массива temp еще остается 4 или 8 байт для соли. Нам предстоит их заполнить
5. Для каждого из байтов раундовой соли:
6. Запоминаем в btmp элемент, который находится по одному из индексов (7, 11, 17… ) в зависимости от номера текущего байта (j)
7. Затем 7(k) раз делаем следующее:
8. Берем остаток от деления btmp, у которого биты сдвинуты вправо на k позиций, на длину массива res
9. предыдущее число используем как индекс для массива res, вытаскиваем число по этому индексу
10. btmp присваиваем это число, сложенное с btmp по модулю 256 и прокрученное вправо на 8-k бит
11. Помещаем btmp на своё место после хэша в массиве temp
12. Хэшируем temp

Вызов этого метода выглядит следующим образом:

byte[] salt = new byte[16];
new SecureRandom().nextBytes(salt); // generate random 16byte salt
byte[] hashedPassword = new SlowHasher().calculateSlowHash(new SHA256(), password, salt);

В результате получится хэш(хэш(хэш+ранудовая соль)+раундовая соль)… который можно использовать как 256 битный ключ шифрования важной информации для AES-256, например.

На моей машине (C2D 2.6) на генерацию одного хэша приходится около 0.25 секунды, что я считаю приемлемым для использования. в своих проектах. Можно увеличить число раундов и тогда время соответственно вырастет.

Если уважаемой публике будет интересно, то я могу рассказать и о других прикладных аспектах работы с библиотекой BouncyCastle как то симметричное\ассиметричное шифрование, генерация сертификатов и т.д.

UPD:
В комментах указали ссылку на доку, в которой такого рода схема принимает еще больший размах