Создание алгоритма хеширования RuHash в черновиках Из песочницы

Привет, Хабр! Недавно у меня возникла идея создать собственный алгоритм хеширования, на вход которого можно бы было подать информацию любой длины и получить хеш определенного размера. Особенность всех алгоритмов хеширование — в их необратимости. Но существует и другой, не менее важный момент — однозначность.

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

1 Идеи

1.1 Однозначность

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

Возьмем несколько кусков информации, которые после операции хеширования получают одинаковый результат. В некоторых случаях это может оказаться некритично. А что если это система авторизации? На большинстве сайтов проверка осуществляется md5 хешем, и поэтому такая неоднозначность в формировании хеша может ускорить брутфорс пароля.

Однозначность можно повысить добавлением спецсимволов (вида #,$,%,^,&) в хеш, но его удобство несколько понизится. Хотя если использовать большую длину хеша и спецсимволы можно значительно повысить стойкость алгоритма.

1.2 Необратимость

Обеспечить необратимость можно довольно простыми способами. Операциями сложения, умножения, деления и вычитания кодов символов, а также различные специализированные операции. В отличии от неоднозначности, создать необратимый алгоритм вполне возможно. Необратимость алгоритма широко используется для хранения различной чувствительной информации (например паролей).

2 Создание алгоритма

Реализовать алгоритм я решил на C++.

2.1 Функция number() или отбеливание (whitening)

Первым делом нужно написать функцию, которая будет принимать определенное число на вход и выдавать ANSI код символа 0-9, a-z, A-Z. Выбор символа будет зависеть именно от входного числа.

int number(int x) { // вспомогательная функция отбеливания
    x+=256;
    while (!(((x <= 57) && (x >= 48)) || ((x <= 90) && (x >= 65)) || ((x <= 122) && (x >= 97)))) {
        if (x < 48) {x+=24;} else {x-=47;}
    }
    return x;
}

Цикл будет выполняться пока не подберется код символа, соответствующий 0-9 или a-z или A-Z. Это будет ключевая функция необратимости, так как подобрать символ в обратную сторону довольно проблематично.

2.2 Ввод данных

Хранить входную строку будет std::vector, а для ввода-вывода мы будем использовать консоль.

int main() {
    std::vector<char> v;
    char s;
    while (std::cin>>s) {
        if (s == ';') break;
        v.push_back(s);
    }
    std::cout<<"Hash: "<<ruhash(v)<<std::endl;
    return 0; 
}

Объявляем последовательность и заполняем ее данными. Для остановки ввода я выбрал символ ';'. Его можно легко изменить на любой другой. Функция ruhash() будем возвращать строку с нашим хешем.

2.3 Написание функции ruhash()

Функцию хеширования ruhash() и функцию отбеливания number() я решил вынести в заголовочный файл ruhash.h. Далее займемся продумыванием и написанием основного функционала.

Выходной хеш у нас должен быть всегда равен 32 символам (a-z, A-Z, 0-9). На вход должна подаваться последовательность любой длины. В процессе создания алгоритма мы будем использовать функцию отбеливания number(), которая была описана выше.

Первым делом нужно дополнить входной блок до такого количества символов, чтобы возведя 2 в n степень можно бы было его получить. В добавок к этому количество дополняемых символов должно быть больше 64. Это нужно, чтобы улучшить показатель однозначности. Рассмотрим это на примере. На вход поступило 300 символов, значит ближайший блок будет 512. Если же поступит 500 символов на вход, то он дополнится до 1024 символов.

std::string ruhash(std::vector<char> v) { // алгоритм хеширования
    int len = v.size(); // определяем длину входного блока
    int min = 64; // минимальный блок
    while (min < len) min*=2; // блок должен быть 64, 128, 256, 512 бит и т.д.
    if ((min - len) < 64) min*=2; // если количество информации, которое требуется дописать меньше 64, то будем дописывать еще
    int add = min-len; // количество информации, которую нужно добавить
    ...

Так, теперь у нас количество символов, которые нужно дописать. Дальше нужно сгенерировать соль и дописать данные. Соль будем генерировать на основе суммы кодов всех символов, отнимем от этого числа длину исходной последовательности символов и прогоним ее через отбеливание. При дописывании информации будем добавлять к соли элементы исходной и добавляемой последовательности, а также счетчик.

    ...
    int salt = 0; // соль на основе суммы кодов всех символов и длины
    for (int i = 0; i < v.size(); ++i) salt+=v[i]; // собираем из кодов всех символов соль
    salt = number(salt-len); // добавляем в соль длину
    for (int i = 1; i <= add; ++i) v.push_back(number(i*salt*v[i])); // дописываем информацию на основе соли, счетчика и входной строки, отбеливаем ее
    ...

Теперь у нас есть целый блок размером 128, 256, 512… символов. Пришло время применить операцию сворачивания этого блока в блок размером 32 символа. Перед реализацией его на C++ я немного продемонстрирую принцип работы этой техники в упрощенном варианте.

Допустим, что дана последовательность из 8 символов. Мы ее свернем в 4 символов по схеме ниже.


На этой картинке вполне наглядно выглядит операция сворачивания. Таким образом повторяя несколько раз эту операцию можно свернуть даже 512 символов в 32.

    ...
    std::vector<int> prev; // выходной вектор
    for (int i = 0; i < v.size(); ++i) prev.push_back(v[i]); // переписываем коды символов в выходной вектор
    std::vector<int> now; // промежуточный вектор
    
    while (prev.size() != 32) { // пока размер вектора не станет 32, будем его сокращать
        for (int j = 0; j < prev.size(); j+=2) {
            int t = prev[j] + prev[j+1]; // складываем пары чисел в одно, тем самым уменьшая размер последовательности в 2 раза
            now.push_back(t);
        }
        prev = now; // промежуточный блок переписываем в выходной вектор
        now.clear();
    }
    ...

На данный момент у нас есть 32-битный блок, состоящий из чисел. На последнем этапе мы прогоним их через функцию number(), то есть отбелим и посимвольно перепишем все содержимое конечного вектора в строку и затем вернем результат работы всего алгоритма.

    ...
    std::vector<char> f; // конечный хеш
    for (int i = 0; i < prev.size(); ++i) {
        f.push_back(number(prev[i]+i*i)); // отбеливаем полученный вектор
    }
    
    std::string hash; // строка для результата
    for (int i = 0; i < f.size(); ++i) {
        hash+=f[i];
    }
    return hash;
}

3 Итоги

Мы написали вполне хорошую функцию хеширования на C++ и рассмотрели некоторые приемы получения необратимого алгоритма. Вообще, сравнивая современные алгоритмы хеширования, лучше всего использовать 256-битные алгоритмы хеширования для более точного сравнения информации больших объемов. Для коротких 20-30 битных паролей вполне подойдет md5.

4 Взлом

Хотите попробовать взломать свежеиспеченный алгоритм RuHash? Жители Хабра могут попробовать взломать вот такой хеш, то есть получить исходную строку.

MqsvgafTwEVaGoVaziEMpkdztMNfUaLU

Исходники: https://github.com/ilyadev/RuHash