Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Хеширование? Что это и зачем?

1. Что такое хеширование и хеш-функции

Пусть у нас есть множество X каких-то объектов. Пока что не важно каких. Текстовых файлов, чисел, бутылок пива... Ещё есть множество чисел Y(N) = {0, 1, 2, ..., N-1}. Имеем функцию f(x) = k, где x - объект из X, k - из Y(N). Такая функция будет зваться хеш-функцией (можно звать её также функцией хеширования). Она по сути разбивает X на N непересекающихся подмножеств, это разбиение имеет название хеширование. В 1950-х гг. советский академик А.П. Ершов предлагал термин расстановка, то есть русскоязычный эквивалент хеширования, но термин не прижился, и вообще-то это плохо...

Пример: X - целые неотрицательные числа, f(x) = x mod N (ищем остаток от деления). Эта хеш-функция называется методом деления. Она обалденно популярна в сфере структур данных, и наверное, её любят студенты-прогеры, потому что её сделать проще, чем что-то другое.

Ещё пример: X - опять целые неотрицательные числа. Функция f берёт первую цифру x. В этом случае N = 10. Хеширование применяется для быстрого поиска в структурах данных и в криптографии. При этом хеш-функции, хорошие для первого, вряд ли хороши для второго применения, и наоборот. хеш-функции, применяемые в криптографии, также называются функциями криптографического хеширования. Как правило, хеш-функции в сфере структур довольно просты, функции криптографического хеширования имеют довольно сложное тело.

В криптографии полагается, что X - множество строк или текстов, а N - степень двойки. При этом традиционно значение f пишут не как обычное десятично число, а в двоичной или 16-ичной системе, и эту гадость называют хеш-значением или просто хешем. Если N - 2 в степени h, то говорят, что h - длина хеш-значения (длина хеша). При этом чем больше h, тем лучше. И ясно, что чем больше это h, тем больше возможных хеш-значений у хеш-функции.

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

2. Требования к криптографическим хеш-функциям

Если в X больше объектов, чем N, то можно найти такую пару x, z из X, что f(x) = f(z). То есть аргументы разные, а хеш-значение одинаковое. Такая ситуация называется коллизией, иногда - столкновением.

Представьте, что хеш-значение - своего рода стул. Представьте себе, что на него захотели усеться двое) Разница в том, что в сфере криптографического хеширования нету понятия хеш-пенделя и хеш-посыла со словами "иди ..., я первым пришёл") Равно как нету и хеш-уступки) А если по-умному, в криптографическом хешировании нету механизмов разрешения коллизий.

Для сравнения заметим, что в хешировании, предназначенном для структур данных, есть методы разрешения коллизий (кто в универе, желая стать прогером, хорошо учил суровую дисциплину с названием САОД, наверняка видел сокращение CRM - Collisions Resolution Method). Дело в том, что в случае структур хеш-значения связаны с адресацией. При этом нельзя втиснуть оба элемента в одну ячейку, если в ней есть место только для одного. Но нельзя и выкидывать запись только потому, что ячейка, "указанная" хеш-функцией, занята - требуется как-то найти другую - свободную ячейку, причём так, чтобы при надобности мы могли отыскать эту запись. Если свободная ячейка выбирается "от балды", запись будет "потеряна".

Пусть известно хеш-значение f(x). Тогда x называется прообразом для данного хеш-значения, а нахождение x по хеш-значению - восстановлением прообраза. Этот процесс - решение обратной хешированию задачи: теперь текст ищем по хешу, а не хеш-значение по тексту. Поскольку можно придумать сколь угодно много текстов, причём в них может быть и больше, чем h, бит информации, то у одного хеш-значения будет много прообразов. Ищется один из них.

Теперь о требованиях к хеш-функциям.

хеширование: сведения о хешировании * хеширование + хеширование
1. Хеш-функции должны быть непредсказуемыми, то есть выглядеть похожими на случайные генераторы битовых наборов. Если исходная строка x изменилась немного (на 1 бит), то хеш-значение f(x) должно измениться в большинстве из h бит.

2. Должно быть трудно найти прообраз для любого заданного хеш-значения (стойкость к восстановлению прообраза).

3. По заданному тексту x должно быть трудно найти z со свойством f(x) = f(z) (стойкость хеш-функции к коллизиям первого рода или поиску второго прообраза).

4. Должно быть трудно найти произвольные x = z, такие что f(x) = f(z) (стойкость хеш-функции к коллизиям второго рода).
хеширование: информация хеширование * о хешировании + хеширование

Из-за этих требований криптографические хеш-функции оказываются довольно мудрёными. Допустим, взять просто сумму кодов символов исходной строки, найти остаток от деления на N и записать в виде набора бит - не пройдёт. Чтобы понять, что это за мудрёные хеш-функции, можно прочесть про SHA1, MD5. А вот приведённые выше - в пункте 1 - примеры хеширования - едва ли пригодны для применения в нуждах защиты информации.

2.1. Хеш-функции, параллелизм и длина хешей

Системы, где используется хеширование с целью защиты данных, в настоящее время имеют нехилого и вообще довольно перспективного противника. Его зовут Параллелизм. Сейчас у нормальных юзеров уже бывают компы и ноуты с многоядерными процессорами. Команда из 5-6 корешей + на каждом компе по 4 ядра + сетевое соединение - и уже набирается "отряд" из 20 потоков. Автору сей статьи в июле 2011 г. в ходе научной работы удалось собрать 28 потоков. А серьёзные структуры соберут сеть и побольше) Плюс ещё учтём, что уже созданы процессоры с 8, 16 ядрами, предназначенные для ПК... В ближайшее десятилетие ГАРАНТИРОВАННО будет и 32, причём таких процессоров будут больше, чем десяток на весь мир.

В результате даже идеально спроектированные функции хеширования с хешами в 32-48 бит вообще может крушить команда "местных умельцев", было бы кому написать параллельную прогу) Функции с хешами в 128 и 160 бит пока ещё используются, но спецы уже и на них не надеятся, иначе зачем было создавать 256- и 512-битные функции?

3. Применение хеш-функций

Безопасное хранение паролей с помощью хеш-функций

Пусть есть у нас социальная сеть, база данных или прочее, где может быть вход по логину и паролю. Чтобы система проверила, правильно ли введён пароль, требуется где-то хранить пароли. Если они хранятся в "сыром" виде, то любой, кто найдёт файл хранения, сами понимаете... Проще всего порыться в чужих паролях будет админам. Ну и у остальных шансы есть при должном мастерстве. То есть если пароли в файле хранения никак не маскируются, то даже юзер, не щёлкающий по подозрительным ссылкам и придумывающий сверхдлинные пароли, не будет в безопасности.

Можно хранить пароли в зашифрованном виде. Это чуть лучше, чем в сыром, но бесполезно, если кто-то, способный найти файл хранения, знает алгоритм и ключ шифра. А вот если прибегнуть к хешированию - использовать хеш-функции с длинными хеш-значениями (скажем, 256, 512, 1024 бит), то завладеть чужим аккаунтом сложно любому, кто не знает всего одного - пароля. Ну здесь полагаем, что юзер не придумал тупой пароль вроде "111".

Вместо паролей будем хранить их хеш-значения. Юзер вводит при входе логин и пароль. В файле по логину ищется нужный хеш. Он сравнивается с хешем того, что введено в поле "пароль" юзером. Если равны, то юзера пропускают, иначе - ШИШ. Может быть, что пароль неправильный, но хеш-значения совпали. Если хеш-значение длинное, то такой прокол маловероятен и может произвойти только чудом.

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

Наглядно эту схему защищённого хранения паролей с помощью хеширования можно нарисовать так:


Эта схема неплохо усиливает безопасность юзеров, но она не всесильна. Если юзер придумывает пароли вроде даты рождения, имени, слова password, "111" или клички домашнего скунса, а также держит на виду у окружающих бумажку, где записан пароль, то создатели хеш-функций тут ни при чём.

Хеш-функции в электронно-цифровой подписи

Хеш-функции обычно являются частью механизма электронно-цифровой подписи. Технология ЭЦП является современной заменой обычной бумажной подписи и часто удобнее её. Даже сложные закорючки обычной подписи при должном старании реально подделать. Изучив, что такое ЭЦП, легко понять, что её подделать крайне трудно, есть только законный подписывающий не раздолбай. И вообще рост известности понятия ЭЦП вполне согласуется с явлением роста электронного документооборота.

Другие применения хеш-функций

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

4. Конкретные криптографические хеш-функции

Большинство хорошо известных хеш-функции разработали заокеанцы. Особо известны семейства SHA и MD, из них самые знаменитые - SHA1 и MD5, хотя они уже не лучшие представители своих "семей". Об этих хеш-функциях часто говорят в статьях и на форумах. Из других зарубежных хеш-функций можно рассмотреть, например, RIPEMD-160, разработанную в Бельгии.

Но не следует зацикливаться только на иностранных функциях хеширования. У нас есть ГОСТ Р34.11-94 - российский стандарт хеширования с 256-битными хеш-значениями. Заметим: SHA1 даёт только 160-битный хеш. Принципиальная особенность ГОСТовского хеширования: оно базируется на ГОСТовском же алгоритме шифрования.

Также заслуживает внимание семейство Skein, обеспечивающее хеширование с выходами 256, 512, 1024 бит. Заметим: самая "длинная" из хвалёных хеш-функций SHA2 даёт хеш в 512 бит.

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

copyright © Исканцев Н.В., 2012

На главную
X