Если вы программист, то пользуетесь хэш-функциями каждый день. Они применяются в базах данных для оптимизации запросов, в структурах данных для ускорения работы, в безопасности для защиты данных. Почти каждое ваше взаимодействие с технологией тем или иным образом включает в себя хэш-функции.
Хэш-функции фундаментальны и используются повсюду.
Но что же такое хэш-функции и как они работают?
В этом посте я собираюсь развенчать мифы вокруг этих функций. Мы начнём с простой хэш-функции, узнаем, как проверить, хороша ли хэш-функция, а затем рассмотрим реальный пример применения хэш-функции: хэш-таблицу.
В оригинале статьи многие иллюстрации интерактивны
Что такое хэш-функция?
Хэш-функции — это функции, получающие на входе данные, обычно строку, и возвращающие число. При многократном вызове хэш-функции с одинаковыми входными данными она всегда будет возвращать одно и то же число, и возвращаемое число всегда будет находиться в гарантированном интервале. Этот интервал зависит от хэш-функции: в некоторых используются 32-битные целочисленные значения (то есть от 0 до 4 миллиардов), в других интервалы гораздо больше.
Если бы мы захотели написать на JavaScript имитацию хэш-функции, то она могла бы выглядеть так:
function hash(input) {
return 0;
}Даже не зная, как используются хэш-функции, мы бы могли понять, что эта функция бесполезна. Давайте узнаем, как определить качественность хэш-функции, а чуть позже мы поговорим о том, как они используются в хэш-таблицах.
Какая хэш-функция может считаться хорошей?
Так как
input может быть любой строкой, а возвращаемое число находится в каком-то гарантированном интервале, может случиться так, что при двух разных входных строках будет возвращено одно и то же число. Это называется «коллизией»; хорошие хэш-функции стремятся к минимизации создаваемых ими коллизий.Однако полностью избавиться от коллизий невозможно. Если бы мы написали хэш-функцию, возвращающую число в интервале от 0 до 7, и передали бы ей 9 уникальных входных значений, то гарантированно получили бы как минимум 1 коллизию.
Выходные значения хорошо известной хэш-функции modulo 8 (деление на 8 с остатком). Какие бы 9 значений мы ни передали, есть всего 8 уникальных чисел, поэтому коллизии неизбежны. Цель заключается в том, чтобы их было как можно меньше.
Для визуализации коллизий я использую сетку. Каждый квадрат в сетке будет обозначать число, возвращаемое хэш-функцией. Вот пример сетки 8x2.
В дальнейшем при каждом хэшировании значения мы будем делать соответствующий ему квадрат в сетке чуть темнее. Смысл в том, чтобы наглядно показать, насколько хорошо хэш-функция избегает коллизий. Мы стремимся получить хорошее равномерное распределение. Будет понятно, что функция плоха, если у нас получатся скопления или паттерны из тёмных квадратов.
Вы сказали, что когда хэш-функция возвращает одинаковое значение для двух входных данных, это называется коллизией. Но если у нас будет хэш-функция, которая возвращает значения в большом интервале, а мы накладываем их на маленькую сетку, то не создадим ли мы множество коллизий, которые на самом деле не будут коллизиями? В нашей сетке 8x2 и 1, и 17 соответствуют второму квадрату.
Отличное замечание. Ты совершенно права, в нашей сетке будут возникать «псевдоколлизии». Но это приемлемо, потому что если хэш-функция хороша, то мы всё равно увидим равномерное распределение. Инкремент каждого квадрата на 100 — это столь же хорошее распределение, как и инкремент каждого квадрата на 1. Если мы получим хэш-функцию с большой степенью коллизий, то это всё равно будет бросаться в глаза. Вскоре мы сами в этом убедимся.
Давайте возьмём сетку побольше и хэшируем 1000 случайно сгенерированных строк. Анимация сетки показывает, как каждое входное значение хэшируется и помещается в сетку.
Значения распределяются равномерно, потому что мы используем хорошо изученную хэш-функцию под названием
murmur3. Эта функция широко используется в реальных приложениях благодаря своему отличному распределению, а также очень высокой скорости работы.Как бы выглядела наша сетка, если бы мы использовали плохую хэш-функцию?
function hash(input) {
let hash = 0;
for (let c of input) {
hash += c.charCodeAt(0);
}
return hash % 1000000;
}Эта хэш-функция циклически обходит всю переданную ей строку и суммирует числовые значения каждого символа. Затем она делает так, чтобы значение находилось в интервале от 0 до 1000000 при помощи оператора деления с остатком (
%). Назовём эту хэш-функцию stringSum.Вот как она выглядит в сетке. Напомню, что это 1000 случайно сгенерированных строк, которые мы хэшируем.
Не сильно отличается от
murmur3. В чём же дело?Проблема в том, что передаваемые на хэширование строки случайны. Давайте посмотрим, как ведёт себя каждая функция, когда входные данные не случайны: это будут числа от 1 до 1000, преобразованные в строки.
Теперь проблема стала очевиднее. Когда входные данные не случайны, выходные данные
stringSum образуют паттерн. А сетка murmur3 выглядит так же, как и при случайных значениях.А вот что получится, если мы хэшируем 1000 самых распространённых слов на английском:
Разница менее заметна, но мы всё равно видим паттерн в сетке
stringSum. Функция murmur3 снова выглядит, как обычно.В этом и состоит сила хорошей хэш-функции: какими бы ни были входные данные, выходные данные всегда распределены равномерно. Давайте поговорим о ещё одном способе визуализации этого, а затем расскажем, почему это важно.
▍ Лавинный эффект
Ещё один способ проверки хэш-функций — это так называемый «лавинный эффект». Это показатель того, какое количество битов меняется в выходном значении при изменении всего одного бита во входном значении. Чтобы можно было сказать, что хэш-функция имеет хороший лавинный эффект, смена одного бита во входном значении должна приводить в среднем к смене 50% битов в выходном значении.
Именно это свойство помогает хэш-функциям не создавать паттерны в сетке. Если небольшое изменение во входных данных приводит к небольшим изменениям в выходных, то возникнут паттерны. Паттерны — это показатели плохого распределения и повышенного уровня коллизий.
Ниже мы показали лавинный эффект на примере двух 8-битных двоичных чисел. Верхнее число — это входное значение, а нижнее — выходное значение
murmur3. Каждый раз во входном значении меняется один бит. Изменившиеся в выходном значении биты будут выделены зелёным, а неизменившиеся биты — оранжевым.murmur3 проявляет себя хорошо, несмотря на то, что иногда меняется меньше 50% битов, а иногда больше. И это нормально, если в среднем получается 50%.Давайте посмотрим, как ведёт себя
stringSum.А вот это уже отвратительно. Выходные данные равны входным, поэтому каждый раз меняется только один бит. И это логично, ведь
stringSum просто суммирует числовое значение каждого символа в строке. Этот пример хэширует эквивалент одного символа, то есть выходное значение всегда будет таким же, как входное.Почему всё это важно
Мы поговорили о нескольких способах определения качественности хэш-функций, но не обсудили, почему это важно. Давайте исправим это, рассмотрев хэш-таблицы (hash map).
Чтобы понять хэш-таблицы, нужно сначала понять, что такое map. Map — это структура данных, позволяющая хранить пары «ключ-значение». Вот пример на JavaScript:
let map = new Map();
map.set("hello", "world");
console.log(map.get("hello"));Здесь мы берём пару «ключ-значение» (
"hello" → "world") и сохраняем её в map. Затем мы выводим значение, связанное с ключом "hello", то есть "world".Более интересным примером реального использования стал бы поиск анаграмм. Анаграмма — это когда два разных слова состоят из одинаковых букв, например, «апельсин» и «спаниель» или «кабан» и «банка». Если у вас есть список слов, и вы хотите найти все анаграммы, то можно отсортировать буквы в каждом слове по алфавиту и использовать эту строку как ключ структуры map.
let words = [
"antlers",
"rentals",
"sternal",
"article",
"recital",
"flamboyant",
]
let map = new Map();
for (let word of words) {
let key = word
.split('')
.sort()
.join('');
if (!map.has(key)) {
map.set(key, []);
}
map.get(key).push(word);
}В результате выполнения этого кода мы получаем map со следующей структурой:
{
"aelnrst": [
"antlers",
"rentals",
"sternal"
],
"aceilrt": [
"article",
"recital"
],
"aabflmnoty": [
"flamboyant"
]
}▍ Реализация собственной простой хэш-таблицы
Хэш-таблицы — одна из множества реализаций map; также существует множество способов реализации хэш-таблиц. Простейший способ, который мы и покажем — это список списков. Внутренние списки в реальном мире часто называют «bucket», поэтому так мы их и будем называть. Хэш-функция применяется к ключу для определения того, в каком bucket должна храниться пара «ключ-значение», после чего эта пара «ключ-значение» добавляется в bucket.
Давайте рассмотрим простую реализацию хэш-таблицы на JavaScript. Мы изучим её снизу вверх, то есть сначала рассмотрим вспомогательные методы, а затем перейдём к реализациям
set и get.class HashMap {
constructor() {
this.bs = [[], [], []];
}
}Мы начнём с создания класса
HashMap с конструктором, настраивающим три bucket. Мы используем три bucket и короткое имя переменной bs, чтобы этот код удобно было просматривать на устройствах с маленькими экранами. В реальном коде можно создавать любое количество bucket (и придумать более осмысленные имена переменных).class HashMap {
// ...
bucket(key) {
let h = murmur3(key);
return this.bs[
h % this.bs.length
];
}
}В методе
bucket к переданному key применяется murmur3, чтобы найти bucket, который нужно использовать. Это единственное место в нашем коде хэш-таблицы, где используется хэш-функция.class HashMap {
// ...
entry(bucket, key) {
for (let e of bucket) {
if (e.key === key) {
return e;
}
}
return null;
}
}Метод
entry получает bucket и key и сканирует bucket, пока не найдёт элемент с указанным ключом. Если элемент не найден, возвращается null.class HashMap {
// ...
set(key, value) {
let b = this.bucket(key);
let e = this.entry(b, key);
if (e) {
e.value = value;
return;
}
b.push({ key, value });
}
}Метод
set мы первым узнаём из предыдущих примеров Map на JavaScript. Он получает пару «ключ-значение» и сохраняет её в хэш-таблицу. Он делает это при помощи созданных ранее методов bucket и entry. Если элемент найден, то значение перезаписывается. Если элемент не найден, то пара «ключ-значение» добавляется в map. В JavaScript { key, value } — это более компактная запись { key: key, value: value }.class HashMap {
// ...
get(key) {
let b = this.bucket(key);
let e = this.entry(b, key);
if (e) {
return e.value;
}
return null;
}
}Метод
get очень похож на set. Он использует bucket и entry для поиска элемента, связанного с переданным key, точно так же, как это делает set. Если элемент найден, возвращается его value. Если он не найден, то возвращается null.Объём кода получился довольно большим. Главное, что нужно из него понять: наша хэш-таблица — это список списков, а хэш-функция используется для того, чтобы понять, в каком из списков хранить ключ и откуда его извлекать.
Вот визуальное представление этой хэш-таблицы. При помощи
set добавляется новая пара «ключ-значение». Чтобы не усложнять визуализацию, если bucket должен «переполниться», то все bucket очищаются.Так как мы используем в качестве хэш-функции
murmur3, то распределение между bucket оказывается хорошим. Можно ожидать частичный дисбаланс, но обычно распределение достаточно равномерное.Чтобы получить значение из хэш-таблицы, мы сначала хэшируем ключ, чтобы понять, в каком из bucket будет находиться значение. Затем нам нужно сравнить ключ, который мы ищем, со всеми ключами в bucket.
Именно этот этап поиска мы минимизируем при помощи хэширования, и именно благодаря ему
murmur3 оптимизирована по скорости. Чем быстрее хэш-функция, тем быстрее мы отыскиваем нужный bucket для поиска, и тем быстрее наша хэш-таблица в целом.Кроме того, из-за этого так важно снижение количества коллизий. Если бы мы решили использовать имитацию хэш-функции из начала статьи, постоянно возвращающую 0, то поместили бы все пары «ключ-значение» в первый bucket. Для поиска любого элемента нам пришлось бы проверить все значения в хэш-таблице. При хорошей хэш-функции с хорошим распределением мы снижаем количество необходимых операций поиска до 1/N, где N — это количество bucket.
Давайте посмотрим, как проявляет себя здесь
stringSum.Любопытно: кажется,
stringSum распределяет достаточно неплохо. Мы замечаем паттерн, но в целом распределение выглядит хорошим.Наконец-то! Победа
stringSum! Я знала, что она когда-нибудь пригодится.
Не торопись, Хаски. Нам нужно обсудить серьёзную проблему. Распределение выглядит приемлемым при этих последовательных числах, однако мы видели, что у
stringSum плохой лавинный эффект. Всё это не кончится ничем хорошим.Коллизии в реальном мире
Давайте рассмотрим два массива данных из реального мира: IP-адреса и английские слова. Я возьму 100 000 000 случайных IP-адресов и 466 550 английских слов, хэширую их
murmur3 и stringSum, а потом посмотрю, сколько коллизий мы получим.IP-адреса
murmur3 |
stringSum |
|
| Коллизии | 1 156 959 | 99 999 566 |
| 1,157% | 99,999% |
Английские слова
murmur3 |
stringSum |
|
| Коллизии | 25 | 464 220 |
| 0,005% | 99,5% |
Когда мы используем хэш-таблицы в реальности, то обычно не храним в них случайные значения. В качестве примера можно представить подсчёт количества запросов, в которых встречался IP-адрес, в коде вычисления ограничения частоты доступа к серверу. Или код, подсчитывающий количество вхождений слов в книгах на протяжении веков для отслеживания их происхождения и популярности. В этих областях применения
stringSum ужасна из-за своей чрезвычайно высокой частоты коллизий.Синтетические коллизии
А теперь настало время плохих новостей для
murmur3. Нам стоит учитывать не только коллизии, вызванные схожестью входных данных. Взгляните:Что здесь происходит? Почему все эти бессмысленные строки хэшируются в одинаковое число?
Я хэшировал 141 триллион случайных строк, чтобы найти значения, при использовании
murmur3 хэшируемые в число 1228476406. Хэш-функции всегда должны возвращать одинаковый результат для конкретного входного значения, поэтому можно найти коллизии простым перебором.Простите, 141 триллион? Это… 141 и 12 нулей?
Да, и это заняло у меня всего 25 минут. Компьютеры очень быстры.
Наличие у злоумышленников лёгкого доступа к коллизиям может иметь катастрофические последствия, если ваше ПО создаёт хэш-таблицы из пользовательского ввода. Возьмём для примера HTTP-заголовки. HTTP-запрос выглядит так:
GET / HTTP/1.1
Accept: */*
Accept-Encoding: gzip, deflate
Connection: keep-alive
Host: google.comВам необязательно понимать все слова, достаточно знать, что первая строка — это запрашиваемый путь, а все остальные строки — это заголовки. Заголовки — это пары
Key: Value, поэтому HTTP-серверы обычно хранят их в таблицах. Ничто не мешает нам отправить любые нужные заголовки, поэтому мы можем быть очень жестокими и передать заголовки, которые, как нам известно, вызовут коллизии. Это может существенно замедлить сервер.И это не теоретические рассуждения. Если вы поищите «HashDoS», то сможете найти ещё множество примеров этого. В середине 2000-х это была очень серьёзная проблема.
Есть несколько способов решения этой проблемы конкретно для HTTP-серверов: например, игнорирование бессмысленных ключей заголовков и ограничение количества хранимых заголовков. Однако современные хэш-функции наподобие
murmur3 предоставляют более общее решение: рандомизацию.Выше в этом посте мы показали несколько примеров реализаций хэш-функций. Эти реализации получают единственный аргумент:
input. Многие из современных хэш-функций получают второй параметр: порождающее значение (seed) (иногда называемое «солью» (salt)). В случае murmur3 этим seed является число.Пока мы использовали в качестве seed значение 0. Давайте посмотрим, что произойдёт с собранными мной коллизиями при использовании seed, равного 1.
Именно так: простой заменой 0 на 1 мы избавились от всех коллизий. В этом и заключается предназначение seed: он непредсказуемым образом рандомизирует выходные данные хэш-функции. То, как он этого достигает, не относится к теме нашей статьи, каждая хэш-функция делает это по-своему.
Хэш-функция по-прежнему возвращает одинаковые выходные данные для одинаковых входных данных, только теперь входные данные — это сочетание
input и seed. Те значения, у которых возникают коллизии при одном seed, не приводят к коллизиям при использовании другого. Языки программирования в начале процесса часто генерируют случайное число для использования в качестве seed, чтобы каждый раз при запуске программы seed различался. Если я злоумышленник, не знающий seed, то больше не могу стабильно наносить ущерб.Если внимательно присмотреться к двум предыдущим визуализациям, то можно заметить, что в них хэшируются одинаковые значения, но они создают разные значения хэша. Из этого следует, что если вы хэшируете значение с одним seed, и хотите в будущем выполнять сравнения с ним, то необходимо использовать одинаковый seed.
Использование разных значений для разных seed не влияет на применение хэш-таблиц, потому что хэш-таблицы существуют только во время выполнения программы. При условии, что на протяжении всего срока работы программы вы используете один seed, ваши хэш-таблицы будут без проблем работать. Если вам нужно сохранить значения хэша вне своей программы, например, в файл, то обязательно знать, какой seed использовался.
Песочница
По традиции я создал песочницу, в которой вы можете писать собственные хэш-функции и визуализировать их в сетках, как в этой статье. Поэкспериментировать с песочницей можно здесь.
Заключение
Мы поговорили о том, что такое хэш-функции, рассказали о некоторых способах оценки их качества, объяснили, что происходит, когда они плохие; также мы узнали о нескольких способах, которыми их могут взломать злоумышленники.
Вселенная хэш-функций велика, и в этом посте мы рассказали о ней лишь поверхностно. Мы не говорили о криптографическом и некриптографическом хэшировании, коснулись лишь одного из тысяч способов применения хэш-функций и вообще не обсудили способ работы современных хэш-функций.
Если вам интересна эта тема, то рекомендую изучить следующие материалы:
- https://github.com/rurban/smhasher: этот репозиторий — золотой стандарт тестирования качества хэш-функций. Он проводит кучу тестов, выполняя сравнение с большим количеством хэш-функций, и представляет результаты в виде большой таблицы. Может быть сложно понять, для чего нужны все эти тесты, но это самая современная система для тестирования хэш-функций.
- https://djhworld.github.io/hyperloglog/ — это интерактивная статья о структуре данных под названием HyperLogLog. Она используется для эффективного подсчёта уникальных элементов в огромных массивах данных. Для этого она очень хитро применяет хэширование.
- https://www.gnu.org/software/gperf/ — это ПО, которому можно передать ожидаемое множество элементов, которые нужно хэшировать, и оно автоматически сгенерирует «идеальную» хэш-функцию.
Благодарности
Благодарю всех, кто читал ранние черновики статьи и давал бесценные отзывы.
И всех, кто помог мне найти хэш-коллизии
murmur3:Telegram-канал с розыгрышами призов, новостями IT и постами о ретроиграх ????️
Комментарии (43)
Daddy_Cool
10.07.2023 13:22Все понятно кроме одного момента ).
Зачем это всё надо? Да, я читал, что хэш-функции используются на каждом шагу, но всё таки? Нужен пример где практически важная задача решается с использованием хэша.
karavan_750
10.07.2023 13:22+2Например, безопасное хранение аутентификационных данных клиента на сервере.
nronnie
10.07.2023 13:22Hash-функции, которые используются в структурах данных и индексах и криптографические hash-функции (md5, sha*) это достаточно разные вещи.
karavan_750
10.07.2023 13:22+2Вы обратили внимание на разницу в алгоритмах, но это никак не делает разным смысл хэша.
IvanPetrof
10.07.2023 13:22+11Торренты. Чтобы быстро понять что у разных людей на руках один и тот же файл, достаточно сравнить из хэши, вместо того, чтобы каждый раз сравнивать все гигабайты файла. (так же можно искать дубликаты файлов на диске, например).
Электронная подпись. Алгоритмом подписи подписывается обычно хэш сообщения, а не само сообщение.
Вообще, хэш это такая "контрольная сумма" на максималках. Его можно использовать (и используют) для проверки целостности данных. К примеру при передаче файлов по сети, можно так же передать его хэш, чтобы принимающая сторона могла понять были ли ошибки передачи. Так же можно контролировать целостность хранения файлов на диске, в архивах и т.п.
PrinceKorwin
10.07.2023 13:22+1Также хэш функции используются в БД для контроля целостности отдельных записей в таблицах. Хорошо помогало поймать момент когда диск начался сыпаться и спасти данные.
fireSparrow
10.07.2023 13:22И раз уж зашла речь про БД, то в них есть индексы на основе хэша.
Ivan22
10.07.2023 13:22ладно индексы.... джоины самые продвинутые - это HASH JOIN который как раз и работает на основе хэширования и раскладывания по бакетам в памяти одной таблицы (желательно которая меньше) и потом перебор каждой строки второй таблицы, хэширование ключа соединения, и быстрый поиск в памяти нужного бакета первой таблицы.
Ivan22
10.07.2023 13:22.... и еще же группировака - тоже делается на основе хэш таблицы. Бакеты это как раз группы
vadimr
10.07.2023 13:22Вообще, хеш-функция и контрольная сумма – это разные вещи, хоть они и делают похожую работу. Главный критерий качества хеш-функции – это уменьшить количество коллизий на всей области применения, а главный критерий качества контрольной суммы – давать различные значения результата при наиболее вероятных искажениях аргумента.
IvanPetrof
10.07.2023 13:22-1Вы правы. Но думаю стоить заметить, что такой критерий для контрольной суммы вытекает из её ограничений (малая разрядность (вплоть до одного бита - "бит чётности") и простота алгоритма рассчёта (чтобы если что, без проблем реализовать аппаратно)).
Бывают ещё "корректирующие коды", которые позволяют исправить некоторые ошибки.
mayorovp
10.07.2023 13:22Нет, такой критерий для контрольной суммы вытекает из её применения.
IvanPetrof
10.07.2023 13:22Если контрольной сумме дать больше битности (128 или 256 как в хэшфункциях), то необходимость "затачивать" их под определённого рода ошибки (переставление двух соседних символов, как в алгоритме Луна, или порча нескольких бит подряд) сильно уменьшится. Но если мы начинаем функцию "душить" по битности, то тут придётся выкручиваться и решать какие ошибки мы хотим "ловить", а какие маловероятны.
Если абстрагироваться, то хэш функция, это специального рода контрольная сумма, ориентированная на устойчивость к определённому роду ошибок (коллизии. Случайные или специальные)
Opaspap
10.07.2023 13:22Сплит тесты конечно же. Остаток от hash(userId+expirementName) дает номер бакета в заданном интервале.
Perlovich
10.07.2023 13:22+6Так прям в статье же дан пример использования: хэш-мапа. Одна из самых часто используемых структур данных. Без неё в программировании никуда.
kinh
10.07.2023 13:22Для ускорения поиска по большим ключам. Допустим, у нас есть таблица, где ключом является текстовая строка. Если начала этих строк одинаковы, то сравнение с искомым ключом "в лоб" займёт много времени. Пример таких имён:
VeryLongNameOfSomethingObject1
VeryLongNameOfSomethingObject2
...
Однако если заранее вычислить хэши этих строк, и хранить вместе со строками, то мы можем сначала сравнить хэши, и в большинстве случаев сразу выяснить, отличаются ли строки. Только если хэши совпадают, мы уже сравниваем сами длинные строки, чтобы окончательно убедиться, что нашли нужную запись.
Также, если у нас много памяти, то хэши могут использоваться для ускорения вставок в разреженную таблицу. В этом случае хэш используется как индекс элемента в таблице. Вместо того, чтобы выполнять долгую процедуру поиска по дереву, куда нам вставить новый элемент таблицы - мы вычисляем хэш фиксированной длины, и сразу пытаемся вставить туда. Если место занято, то используем какой-нибудь алгоритм разрешения коллизий, вроде линейного поиска от первоначального места вставки, пока не найдём свободное место. Преимущество такого подхода: не нужно хранить деревья ключей, которые для больших баз данных могут занимать много места.
maximw
10.07.2023 13:22В некоторых языках (PHP, Java и кажись Python тоже) есть типы данных - мапы. Внутри они примерно так устроены, как описано в статье.
thevlad
10.07.2023 13:22Описанные в статье хэш функции используются в основном в реализации структуры данных hash map/hash set, а так же bloom filter.
Данные хэш функции не являются криптографически стойкими, поэтому использовать их для аутентификации и прочих действиях связанных с безопасностью не лучшая идея(как предлагалось выше). https://en.wikipedia.org/wiki/Cryptographic_hash_function
Fourgotten
10.07.2023 13:22-1Самое банальное — пароли к ЛК на сайте, например. Если их хранить в базе в чистом виде, то при утечке данных, злоумышленник получит все пароли ваших пользователей. Поэтому хранится только хэш пароля, а когда юзер авторизуется, введенный им пароль снова хэшируется и сравнивается с хэшем из базы данных. Если хэши совпали, значит пароль верный
Daddy_Cool
10.07.2023 13:22Ага. Спасибо! Меня всегда смущало, что можно подобрать ДРУГИЕ входные данные, чтобы был такой же хэш, т.е. те самые коллизии.
Интересно, а есть какие-нибудь оценки трудоёмкости такой операции в зависимости от длины исходных данных для конкретной хэш-функции, для того же murmur3?thevlad
10.07.2023 13:22+3Обычные хэш функции никогда не используются для данных целей, по крайней мере адекватными людьми - они не являются криптостойкими. Для криптостойких хэш функций, сложность, как и обычно для всего в крипте - переборная.
PS: про коллизии и реальный криптоанализ обычных хэш функций http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/
zuek
10.07.2023 13:221С, как минимум, 7.7, хранит в таблице пару "Логин"-"md5(пароль)", и да, при прямом доступе к таблице пользователей, пароли гуглятся на 1-2-3...
Мои, самые первые, реализации различных веб-интерфейсов, хранили "md5(login)"-"md5(password)", правда, это было прям реально давно - где-то до середины нулевых, сейчас я не программист, а если надо что-то "по-быстрому набросать на коленке с авторизацией", лезу освежать в памяти, как готовить "password_hash" (напомню - за PHP в частности, и за программирование вообще, я берусь крайне редко), так как на практике слишком много раз встречал неудачное хранение хэшей паролей.
IvaYan
10.07.2023 13:22+1Хеш-функции разные бывают. Те, которые еще называют чексуммами или контрольными суммами, возвращают число 32 или 64 бита и предназначены не для паролей, а для контроля того что данные не испорчены. Некоторые еще позволяют какие-то оишбки исправить. Сюда относятся CRC, Adler-32, MurmurHash и более современный xxhash. Пример применения -- записать в файл архива хеш исходных данных и после распаковки проверить, что распаковали правильно или записать в заголовок пакета, передаваемого по сети, чтобы получатель мог проверить, что данные доехали. Для защиты паролей не имеют смысла. Этими функциями занимаются математика и теория информации.
А есть криптографичесике хеш-функции. Сюда относятся md5 (устарела), sha-1 (устарела), sha-2 (пока не устарела, но осталось недолго), sha-3 (замена sha-2 и пока почти нигде не поддерживается). Их задача обнаружить изменение исходных данных, даже самое минимальное, и при этом минимизировать вероятность коллизии, особенно, умышленной. Их можно (но не нужно) использовать для защиты паролей. Можно использовать для электронной подписи. Считаем такой хеш и подписываем его ассиммитричной криптой. Если хеш не сошелся, значит документ был изменён. Еще их может использовать файловое хранилище для дедупликации. Посчитав такой хеш для файла и проверив по базе, можно понять, есть файл в хранилище или нет, и если есть, то не загружать. Благодаря тому что эти функции специально нацелены на минимизацию коллизий, в целом, вероятностью коллизии можно пренебречь при определенных условиях. Но поскольку мы сжимаем много данных (в случае файлового хранилища файлы могут был размером в гигабайты) в маленькое количество данных (256 бит для sha-256) коллизии все равно возможны. Но благодаря этому мы получаем еще одно свойство -- по хешу невозможно даже примерно получить представление об исходных данных, поэтому, например, практически невозможно понять, как поменять данные, чтобы получить заданных хеш. Еще одно требование к ним -- лавинный эффект, то есть при минимальном изменении исходных данных, хеш должен меняться до неузнаваемости (нельзя, чтобы менялась только часть хеша). Этими функциями занимается криптограция.
Теперь о паролях. Проблема в том, что хеш-функция для одних и тех же данных дает один и тот же хеш. Поэтому если у двух пользователей одинаковый пароль, в базе для них будут записаны одинаковые хеши, что плохо, так как упрощает атаку (можно атаковать одного пользователя и получить пароли от нескольких). Здесь сейчас приняты разные хитрые схемы, например, можно посчитать для кажого пользователя случайный массив байт и объединить его с паролем и хешировать уже результат такого объединения. Здесь можно посмотреть bcrypt.
Есть еще хеш-функции в хеш-таблицах (они же мапы, они же словари, они же ассоциативные массивы, много названий для одного и того же). У них чуть иные требования. Контроль целостности как таковой не нужен. Нужно для одних и тех же данных гарантированного давать один и тот же результат, время расчета должно быть минимальным и при этом разборс значений должен быть довольно велик. Используются для поиска того, в какой бакет (сегмент) ассоциативного массива положить данные или где их искать. Считаться быстро нужно чтобы этот поиск работал моментально, разброс значений нужен чтобы все данные не попали в один сегмент.
nronnie
10.07.2023 13:22+3Здесь сейчас приняты разные хитрые схемы, например, можно посчитать для кажого пользователя случайный массив байт и объединить его с паролем и хешировать уже результат такого объединения.
Что ж тут хитрого - обычный 'salt', который уже сто лет как применяется.
maximw
10.07.2023 13:22Есть еще практический пример атаки коллизиями. Во мнгоих языках десериализация json использует хеш-мапы. И отсылка на API-эндпоинт специально сформированного json, где все значения идут в один бакет, может сильно затормозить сервер. Относительно протой DoS.
WASD1
10.07.2023 13:22-1Используйте нормальные библиотеки хэшмап (или языки, где хэшмап из коробки нормальный). И атака не состоится.
Нормальные - это те, где бакеты организованы в виде деревьев.mayorovp
10.07.2023 13:22+1Чтобы бакет сделать деревом — нужен компаратор для элементов. А элементы в общем случае сравнить можно только по хеш-коду.
Правильная защита от этой атаки — рандомизация хеш-функции. Впрочем, её тоже в общем случае на классических языках не сделать.
WASD1
10.07.2023 13:22-1Чтобы бакет сделать деревом — нужен компаратор для элементов. А элементы в общем случае сравнить можно только по хеш-коду.
Это же прямо ложно. Всё из чего можно сделать хороший хэш (и/или взять Eq) - можно сравнить побайтно лексикографически, что для наших целей вполне подходит.
Не говоря уже о том - что для сравнения можно использовать более сильные хэш ф-ии (SHA2 вроде не подвержено атаке искусственными коллизиями).
В общем это типичный пример когда "в теории" всё сложно, но если вам надо не шашечки, а ехать - то всё решаемо.mayorovp
10.07.2023 13:22Это вы вообще про какой язык написали, что у вас есть бесплатный доступ к побайтовому сравнению любых данных?
Самое близкое что я могу вспомнить — это С++, но даже там будет проблема при наличии std::string как части ключа (а это одновременно и основной источник возможных атак!).
SHA2 да, атаке не подвержено. Но она сама по себе небыстрая, использовать её для хеш-таблиц — что из пушки по воробьям.
WASD1
10.07.2023 13:22-1> Чтобы бакет сделать деревом — нужен компаратор для элементов. А элементы в общем случае сравнить можно только по хеш-коду.
> для чего можно взять hash можно и сравнить побайтно
Это вы вообще про какой язык написали, что у вас есть бесплатный доступ к побайтовому сравнению любых данных?
Вы меняете тезис в процессе обсуждения. Не надо так ;)
> Не говоря уже о том - что для сравнения можно использовать более сильные хэш ф-ии
SHA2 да, атаке не подвержено. Но она сама по себе небыстрая, использовать её для хеш-таблиц — что из пушки по воробьям.
А где вы видели использования для хэш-таблиц? Использование только для компарации по дереву внутри бакета (ну и да бакет становится деревом, есил элементов в нём больше, чем N, в java ЕМНИП=4). Т.е. исключительно редко или если нас начали DOS-ить.
mayorovp
10.07.2023 13:22Это не я меняю тезис, это вы приводите странные алгоритмы которых я вообще ни в одном языке не видел.
Что же до Java — там дерево строится по хеш-коду если ключи оказались не Comparable. А реализацию Comparable по умолчанию не генерирует ни Lombok, ни Java records.
WASD1
10.07.2023 13:22-2Вы сказали фактически неверную вещь: "А элементы в общем случае сравнить можно только по хеш-коду".
Будучи пойманным за руку применили 2 очень некрасивые попытки выкрутиться:
1. Смена тезиса
2. "Это не я меняю тезис это вы (не важно что тут идёт, т.к. тезис был сменён)"
Если это ваша позиция - то разговор нужно завершать. Конструктив при такой позиции не просматривается.mayorovp
10.07.2023 13:22А где вы меня поймали-то?
Общий случай — это когда у нас в классе нет случайной реализации особых интерфейсов вроде Comparable, которые обычно для ключей никто не реализует.
WASD1
10.07.2023 13:22-2"можно организовать только через Х" и "через Х организовать проще всего, а ICmparable добавлять муторно" - разные утверждения.
Я уже молчу что от пользователя мы получаем +/- строки (строки \ xml-json \ кортежи SELECT из базы).
На момент прошлого коммента не понимал: выкручивание будучи пойманным за руку - принципиальная позиция или стечение обстоятельств, когда неудобно признаться в неправоте.
Сейчас понятно. DIXI.mayorovp
10.07.2023 13:22"Можно организовать только через Х" и "можно организовать только через Х в общем случае" — это разные утверждения, и у меня с самого начала было написано второе.
А вы сначала невнимательно прочитали, а теперь вместо того чтобы признать ошибку — выкручиваетесь через обвинение оппонента. Не надо так делать.
kekoz
10.07.2023 13:22+1В этом посте я собираюсь развенчать мифы вокруг этих функций.
Полезная статья для тех, кому хэш-функция — магия. Очень жаль только, что так и не удалось заслушать
начальника транспортного цехани одного мифа. Оно и не удивительно, ведь у автора слово ”миф” в статье встречается ровно 0 раз :)Но чтобы перевод сам не становился источником мифов о якобы невозможности полного избавления от коллизий, надо бы рассказать об “Идеальном хэше” (perfect hash). Чтобы не превращать комментарий в довольно объёмный текст, просто рекомендую интересующимся прочитать соответствующую статью в англоязычной википедии (в русской её нет).
vilgeforce
" получающие на входе данные, обычно строку " - вообще, массив байтов. Аналогично и на выходе - массив байтов
vanxant
...а главное то, что на входе массив байт произвольной длины, а вот длина выхода фиксирована. Соответственно, если вход длиннее выхода, коллизии неизбежны (иначе мы бы создали универсальный упаковщик всего в длина_выхода байт).
vilgeforce
Чертовски логично!
Dotarev
Думаю, автор имел в виду именно строку как самый распространенный (в реальных применениях) тип данных, для которого используется хеширование.
WQS100
Внимание, анекдот!
Sild
Там была ещё одна, про парня, у которого была лабораторная по архиваторам - и он единственный из группы кто ее сдал, написав копирование файла