Comments 49
" получающие на входе данные, обычно строку " - вообще, массив байтов. Аналогично и на выходе - массив байтов
...а главное то, что на входе массив байт произвольной длины, а вот длина выхода фиксирована. Соответственно, если вход длиннее выхода, коллизии неизбежны (иначе мы бы создали универсальный упаковщик всего в длина_выхода байт).
Чертовски логично!
Думаю, автор имел в виду именно строку как самый распространенный (в реальных применениях) тип данных, для которого используется хеширование.
(иначе мы бы создали универсальный упаковщик всего в длина_выхода байт).
Внимание, анекдот!
- Слушай, вчера написал новый архиватор. Любой файл сжимает в 5 байт.
- Ну просто рулез!..
- Ага. Сейчас работаю над разархиватором.
иначе мы бы создали универсальный упаковщик всего в длина_выхода байт
Просто надо найти самое большое число, куда точно все поместится и упаковывать в него
Все понятно кроме одного момента ).
Зачем это всё надо? Да, я читал, что хэш-функции используются на каждом шагу, но всё таки? Нужен пример где практически важная задача решается с использованием хэша.
Например, безопасное хранение аутентификационных данных клиента на сервере.
Торренты. Чтобы быстро понять что у разных людей на руках один и тот же файл, достаточно сравнить из хэши, вместо того, чтобы каждый раз сравнивать все гигабайты файла. (так же можно искать дубликаты файлов на диске, например).
Электронная подпись. Алгоритмом подписи подписывается обычно хэш сообщения, а не само сообщение.
Вообще, хэш это такая "контрольная сумма" на максималках. Его можно использовать (и используют) для проверки целостности данных. К примеру при передаче файлов по сети, можно так же передать его хэш, чтобы принимающая сторона могла понять были ли ошибки передачи. Так же можно контролировать целостность хранения файлов на диске, в архивах и т.п.
Также хэш функции используются в БД для контроля целостности отдельных записей в таблицах. Хорошо помогало поймать момент когда диск начался сыпаться и спасти данные.
И раз уж зашла речь про БД, то в них есть индексы на основе хэша.
ладно индексы.... джоины самые продвинутые - это HASH JOIN который как раз и работает на основе хэширования и раскладывания по бакетам в памяти одной таблицы (желательно которая меньше) и потом перебор каждой строки второй таблицы, хэширование ключа соединения, и быстрый поиск в памяти нужного бакета первой таблицы.
.... и еще же группировака - тоже делается на основе хэш таблицы. Бакеты это как раз группы
Вообще, хеш-функция и контрольная сумма – это разные вещи, хоть они и делают похожую работу. Главный критерий качества хеш-функции – это уменьшить количество коллизий на всей области применения, а главный критерий качества контрольной суммы – давать различные значения результата при наиболее вероятных искажениях аргумента.
Вы правы. Но думаю стоить заметить, что такой критерий для контрольной суммы вытекает из её ограничений (малая разрядность (вплоть до одного бита - "бит чётности") и простота алгоритма рассчёта (чтобы если что, без проблем реализовать аппаратно)).
Бывают ещё "корректирующие коды", которые позволяют исправить некоторые ошибки.
Нет, такой критерий для контрольной суммы вытекает из её применения.
Если контрольной сумме дать больше битности (128 или 256 как в хэшфункциях), то необходимость "затачивать" их под определённого рода ошибки (переставление двух соседних символов, как в алгоритме Луна, или порча нескольких бит подряд) сильно уменьшится. Но если мы начинаем функцию "душить" по битности, то тут придётся выкручиваться и решать какие ошибки мы хотим "ловить", а какие маловероятны.
Если абстрагироваться, то хэш функция, это специального рода контрольная сумма, ориентированная на устойчивость к определённому роду ошибок (коллизии. Случайные или специальные)
Любую контрольную сумму можно рассматривать как разновидность хеш-функции.
Для контроля целостности передачи данных по радиоканалу (контрольная сумма) нужно максимизировать вероятность обнаружения ошибки при заданной модели помехи.
Для криптографических целей (например, хеширование данных перед формированием ЭЦП) - по сути то же самое, но помехи могут вноситься интеллектуальным злоумышленником. Формально там требования описываются строже, но суть именно такая.
Для БД рассматривают не модель помехи а статистические свойства данных и оптимизируют равномерность их размазывания по выходным значениям.
И как ни странно, во всех этих приложениях критично важна скорость вычисления хеша.
Сплит тесты конечно же. Остаток от hash(userId+expirementName) дает номер бакета в заданном интервале.
Так прям в статье же дан пример использования: хэш-мапа. Одна из самых часто используемых структур данных. Без неё в программировании никуда.
Для ускорения поиска по большим ключам. Допустим, у нас есть таблица, где ключом является текстовая строка. Если начала этих строк одинаковы, то сравнение с искомым ключом "в лоб" займёт много времени. Пример таких имён:
VeryLongNameOfSomethingObject1
VeryLongNameOfSomethingObject2
...
Однако если заранее вычислить хэши этих строк, и хранить вместе со строками, то мы можем сначала сравнить хэши, и в большинстве случаев сразу выяснить, отличаются ли строки. Только если хэши совпадают, мы уже сравниваем сами длинные строки, чтобы окончательно убедиться, что нашли нужную запись.
Также, если у нас много памяти, то хэши могут использоваться для ускорения вставок в разреженную таблицу. В этом случае хэш используется как индекс элемента в таблице. Вместо того, чтобы выполнять долгую процедуру поиска по дереву, куда нам вставить новый элемент таблицы - мы вычисляем хэш фиксированной длины, и сразу пытаемся вставить туда. Если место занято, то используем какой-нибудь алгоритм разрешения коллизий, вроде линейного поиска от первоначального места вставки, пока не найдём свободное место. Преимущество такого подхода: не нужно хранить деревья ключей, которые для больших баз данных могут занимать много места.
В некоторых языках (PHP, Java и кажись Python тоже) есть типы данных - мапы. Внутри они примерно так устроены, как описано в статье.
Описанные в статье хэш функции используются в основном в реализации структуры данных hash map/hash set, а так же bloom filter.
Данные хэш функции не являются криптографически стойкими, поэтому использовать их для аутентификации и прочих действиях связанных с безопасностью не лучшая идея(как предлагалось выше). https://en.wikipedia.org/wiki/Cryptographic_hash_function
Самое банальное — пароли к ЛК на сайте, например. Если их хранить в базе в чистом виде, то при утечке данных, злоумышленник получит все пароли ваших пользователей. Поэтому хранится только хэш пароля, а когда юзер авторизуется, введенный им пароль снова хэшируется и сравнивается с хэшем из базы данных. Если хэши совпали, значит пароль верный
Ага. Спасибо! Меня всегда смущало, что можно подобрать ДРУГИЕ входные данные, чтобы был такой же хэш, т.е. те самые коллизии.
Интересно, а есть какие-нибудь оценки трудоёмкости такой операции в зависимости от длины исходных данных для конкретной хэш-функции, для того же murmur3?
Обычные хэш функции никогда не используются для данных целей, по крайней мере адекватными людьми - они не являются криптостойкими. Для криптостойких хэш функций, сложность, как и обычно для всего в крипте - переборная.
PS: про коллизии и реальный криптоанализ обычных хэш функций http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/
1С, как минимум, 7.7, хранит в таблице пару "Логин"-"md5(пароль)", и да, при прямом доступе к таблице пользователей, пароли гуглятся на 1-2-3...
Мои, самые первые, реализации различных веб-интерфейсов, хранили "md5(login)"-"md5(password)", правда, это было прям реально давно - где-то до середины нулевых, сейчас я не программист, а если надо что-то "по-быстрому набросать на коленке с авторизацией", лезу освежать в памяти, как готовить "password_hash" (напомню - за PHP в частности, и за программирование вообще, я берусь крайне редко), так как на практике слишком много раз встречал неудачное хранение хэшей паролей.
Хеш-функции разные бывают. Те, которые еще называют чексуммами или контрольными суммами, возвращают число 32 или 64 бита и предназначены не для паролей, а для контроля того что данные не испорчены. Некоторые еще позволяют какие-то оишбки исправить. Сюда относятся CRC, Adler-32, MurmurHash и более современный xxhash. Пример применения -- записать в файл архива хеш исходных данных и после распаковки проверить, что распаковали правильно или записать в заголовок пакета, передаваемого по сети, чтобы получатель мог проверить, что данные доехали. Для защиты паролей не имеют смысла. Этими функциями занимаются математика и теория информации.
А есть криптографичесике хеш-функции. Сюда относятся md5 (устарела), sha-1 (устарела), sha-2 (пока не устарела, но осталось недолго), sha-3 (замена sha-2 и пока почти нигде не поддерживается). Их задача обнаружить изменение исходных данных, даже самое минимальное, и при этом минимизировать вероятность коллизии, особенно, умышленной. Их можно (но не нужно) использовать для защиты паролей. Можно использовать для электронной подписи. Считаем такой хеш и подписываем его ассиммитричной криптой. Если хеш не сошелся, значит документ был изменён. Еще их может использовать файловое хранилище для дедупликации. Посчитав такой хеш для файла и проверив по базе, можно понять, есть файл в хранилище или нет, и если есть, то не загружать. Благодаря тому что эти функции специально нацелены на минимизацию коллизий, в целом, вероятностью коллизии можно пренебречь при определенных условиях. Но поскольку мы сжимаем много данных (в случае файлового хранилища файлы могут был размером в гигабайты) в маленькое количество данных (256 бит для sha-256) коллизии все равно возможны. Но благодаря этому мы получаем еще одно свойство -- по хешу невозможно даже примерно получить представление об исходных данных, поэтому, например, практически невозможно понять, как поменять данные, чтобы получить заданных хеш. Еще одно требование к ним -- лавинный эффект, то есть при минимальном изменении исходных данных, хеш должен меняться до неузнаваемости (нельзя, чтобы менялась только часть хеша). Этими функциями занимается криптограция.
Теперь о паролях. Проблема в том, что хеш-функция для одних и тех же данных дает один и тот же хеш. Поэтому если у двух пользователей одинаковый пароль, в базе для них будут записаны одинаковые хеши, что плохо, так как упрощает атаку (можно атаковать одного пользователя и получить пароли от нескольких). Здесь сейчас приняты разные хитрые схемы, например, можно посчитать для кажого пользователя случайный массив байт и объединить его с паролем и хешировать уже результат такого объединения. Здесь можно посмотреть bcrypt.
Есть еще хеш-функции в хеш-таблицах (они же мапы, они же словари, они же ассоциативные массивы, много названий для одного и того же). У них чуть иные требования. Контроль целостности как таковой не нужен. Нужно для одних и тех же данных гарантированного давать один и тот же результат, время расчета должно быть минимальным и при этом разборс значений должен быть довольно велик. Используются для поиска того, в какой бакет (сегмент) ассоциативного массива положить данные или где их искать. Считаться быстро нужно чтобы этот поиск работал моментально, разброс значений нужен чтобы все данные не попали в один сегмент.
Есть еще практический пример атаки коллизиями. Во мнгоих языках десериализация json использует хеш-мапы. И отсылка на API-эндпоинт специально сформированного json, где все значения идут в один бакет, может сильно затормозить сервер. Относительно протой DoS.
Используйте нормальные библиотеки хэшмап (или языки, где хэшмап из коробки нормальный). И атака не состоится.
Нормальные - это те, где бакеты организованы в виде деревьев.
Чтобы бакет сделать деревом — нужен компаратор для элементов. А элементы в общем случае сравнить можно только по хеш-коду.
Правильная защита от этой атаки — рандомизация хеш-функции. Впрочем, её тоже в общем случае на классических языках не сделать.
Чтобы бакет сделать деревом — нужен компаратор для элементов. А элементы в общем случае сравнить можно только по хеш-коду.
Это же прямо ложно. Всё из чего можно сделать хороший хэш (и/или взять Eq) - можно сравнить побайтно лексикографически, что для наших целей вполне подходит.
Не говоря уже о том - что для сравнения можно использовать более сильные хэш ф-ии (SHA2 вроде не подвержено атаке искусственными коллизиями).
В общем это типичный пример когда "в теории" всё сложно, но если вам надо не шашечки, а ехать - то всё решаемо.
Это вы вообще про какой язык написали, что у вас есть бесплатный доступ к побайтовому сравнению любых данных?
Самое близкое что я могу вспомнить — это С++, но даже там будет проблема при наличии std::string как части ключа (а это одновременно и основной источник возможных атак!).
SHA2 да, атаке не подвержено. Но она сама по себе небыстрая, использовать её для хеш-таблиц — что из пушки по воробьям.
> Чтобы бакет сделать деревом — нужен компаратор для элементов. А элементы в общем случае сравнить можно только по хеш-коду.
> для чего можно взять hash можно и сравнить побайтно
Это вы вообще про какой язык написали, что у вас есть бесплатный доступ к побайтовому сравнению любых данных?
Вы меняете тезис в процессе обсуждения. Не надо так ;)
> Не говоря уже о том - что для сравнения можно использовать более сильные хэш ф-ии
SHA2 да, атаке не подвержено. Но она сама по себе небыстрая, использовать её для хеш-таблиц — что из пушки по воробьям.
А где вы видели использования для хэш-таблиц? Использование только для компарации по дереву внутри бакета (ну и да бакет становится деревом, есил элементов в нём больше, чем N, в java ЕМНИП=4). Т.е. исключительно редко или если нас начали DOS-ить.
Это не я меняю тезис, это вы приводите странные алгоритмы которых я вообще ни в одном языке не видел.
Что же до Java — там дерево строится по хеш-коду если ключи оказались не Comparable. А реализацию Comparable по умолчанию не генерирует ни Lombok, ни Java records.
Вы сказали фактически неверную вещь: "А элементы в общем случае сравнить можно только по хеш-коду".
Будучи пойманным за руку применили 2 очень некрасивые попытки выкрутиться:
1. Смена тезиса
2. "Это не я меняю тезис это вы (не важно что тут идёт, т.к. тезис был сменён)"
Если это ваша позиция - то разговор нужно завершать. Конструктив при такой позиции не просматривается.
А где вы меня поймали-то?
Общий случай — это когда у нас в классе нет случайной реализации особых интерфейсов вроде Comparable, которые обычно для ключей никто не реализует.
"можно организовать только через Х" и "через Х организовать проще всего, а ICmparable добавлять муторно" - разные утверждения.
Я уже молчу что от пользователя мы получаем +/- строки (строки \ xml-json \ кортежи SELECT из базы).
На момент прошлого коммента не понимал: выкручивание будучи пойманным за руку - принципиальная позиция или стечение обстоятельств, когда неудобно признаться в неправоте.
Сейчас понятно. DIXI.
"Можно организовать только через Х" и "можно организовать только через Х в общем случае" — это разные утверждения, и у меня с самого начала было написано второе.
А вы сначала невнимательно прочитали, а теперь вместо того чтобы признать ошибку — выкручиваетесь через обвинение оппонента. Не надо так делать.
В этом посте я собираюсь развенчать мифы вокруг этих функций.
Полезная статья для тех, кому хэш-функция — магия. Очень жаль только, что так и не удалось заслушать начальника транспортного цеха ни одного мифа. Оно и не удивительно, ведь у автора слово ”миф” в статье встречается ровно 0 раз :)
Но чтобы перевод сам не становился источником мифов о якобы невозможности полного избавления от коллизий, надо бы рассказать об “Идеальном хэше” (perfect hash). Чтобы не превращать комментарий в довольно объёмный текст, просто рекомендую интересующимся прочитать соответствующую статью в англоязычной википедии (в русской её нет).
Было неожиданно от автора увидеть такую сложную статью после простой и понятной каждому статьи про распределение памяти.
Достаточно частый вопрос: какие hash-функции дадут один и тот же результат на разных языках: JS, PHP, Python?
Как работает хэширование