Области применения хэш-функций

Хеши

Лекция 2. Защита информации

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

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

1) хеш-функция имеет бесконечную область определения;

2) хеш-функция имеет конечную область значений;

3) она необратима;

4) изменение входного потока информации на один бит меняет около половины всех бит выходного потока, то есть результата хеш-функции.

Эти свойства позволяют подавать на вход хеш-функции пароли, то есть текстовые строки произвольной длины на любом национальном языке и, ограничив область значений функции диапазоном 0..2^N-l, где N - длина ключа в битах, получать на выходе достаточно равномерно распределенные по области значения блоки информации - ключи.

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

Характер применения блочного шифра для хеширования определяется отношением размера блока используемого криптоалгоритма и разрядности требуемого хеш-результата.

В случае, если указанные выше величины совпадают, то используется схема одноцепочечного блочного шифрования. Первоначальное значение хеш-результата Н₀ устанавливается равным 0, вся строка-пароль разбивается на блоки байт, равные по длине ключу используемого для хеширования блочного шифра, затем производятся преобразования по реккурентной формуле

H_j=H_j-1 XOR EnCrypt(H_j-1,PSW_j),

где EnCrypt(X,Key) - используемый блочный шифр.

Последнее значение Н_k используется в качестве искомого результата.

В том случае, когда длина ключа ровно в два раза превосходит длину блока, а подобная зависимость довольно часто встречается в блочных шифрах, используется схема, напоминающая сеть Фейштеля. Характерным недостатком и приведенной выше формулы, и хеш-функции, основанной на сети Фейштеля, является большая ресурсоемкость в отношении пароля. Для проведения только одного преобразования, например, блочным шифром с ключом длиной 128 бит используется 16 байт строки-пароля, а сама длина пароля редко превышает 32 символа. Следовательно, при вычислении хеш-функции над паролем будут произведено максимум 2 «полноценных» криптопреобразования.

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

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

Вся современная криптография основана на использовании методов хеширования. Метод хеширования позволяет хранить множество элементов множества А в линейном массиве X. Как правило, число элементов А много больше, чем X. Математически это можно записать:

h: А --> {0, х-1}

Это читается так функция h отображает каждый элемент А в индекс множества X. Так как число элементов А как правило намного больше X, то функция h наверняка неинъективна. Однако, возможно существование такого интервала на области определения функции, в границах которого она становится инъективной. Это означает, что только для одного элемента А существует индекс xl. Функция будет инъективной и в том случае, если ни один элемент А не отображается на интервал {xl,x2} при условии, что последний не равен нулю. В любом другом случае на каждый индекс множества X отображается более одного элемента А. Это так называемая коллизия хеш-функции. Реверс хеш-функции заключается в поиске всех отображаемых на данный индекс элементов. Для любого конечного множества А это разрешимая задача, которая наиболее простое решение имеет на инъективных интервалах хеш-множества.

Наиболее часто используется и хорошо изучен мультипликационный метод отображения. Математически его можно выразить как:

h(S[x])=C*S[x] mod N

где N - это число элементов хеш-множества или другими словами его мощность. С - любая константа из интервала [0,N).

При С=1 эта формула приобретает вид:

h(S[x])=S[x] mod N

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

Другой, нашедшей популярность, является необычайно мощная функция CRC 32 (crcl6). Расшифровывается это как cyclic redundancy check (код циклического контроля) и в первую очередь призвана подтверждать неискаженность выбранной числовой последовательности. Это еще одна область применения хеш-преобразований. В самом деле - это все тоже хеш-сравнение. Конечно, существует определенная вероятность таких искажений, которые не отразятся на хеш-сумме, но она достаточно невелика при условии хорошего рассеяния и чувствительности к незначительным изменениям выбранного хеш-преобразования.

Может возникнуть такая ситуация, когда требуемое число элементов хеш-множества будет заметно меньше, чем 2³². Избежать лишних расходов можно умножив результат сам на себя и взяв N старших бит так, что бы 2^N было по возможности близко к требуемому значению. Смысл этой операции в том, чтобы получить битовую последовательность, чувствительную ко всем битам значения CRC.

Рассмотрим теперь применение хеш-преобразований в криптографии. Одной из задач последней является проверка достоверности пароля. Для этого используют особые хеш-функции. Почему особые, мы поймем, рассмотрев принцип действия криптосистем. Пусть имеется некоторая криптографическая функция F, расшифровывающая паролем р последовательность A_i в последовательность A_j.

p

F(Ai) --> Aj

Разумеется только для одного-единственного р мы получим исходную последовательность A_j, а для всех остальных р - «мусор». Каким способом можно удостовериться в том, что полученная A_j и есть искомая последовательность (при условии, что самой последовательности в наличие не имеется)? Можно сохранить фрагмент исходной последовательности и затем сверить его с полученным результатом. Однако, это делает возможной атаку по открытому тексту на шифр, кроме того очень ненадежно, т.к. не гарантируется что совпадение одного фрагмента обеспечивает совпадение всей последовательности.

Вот тут-то на помощь и приходит хеш-преобразование. Мы можем вычислить CRC32 для исходного текста. Сравнивая его с CRC32 A_j мы можем проверить правильность расшифровки. Так как A_j наверняка больше 2³², то хеш-функция окажется неинъективной и хеш-значение совершенно не даст никакого представления об исходной последовательности.

Однако, этот способ достаточно медленный. Гораздо быстрее сравнивать хеш-суммы паролей. Учитывая число возможных паролей можно прийти к выводу, что с большой вероятностью выбранная хэш-функция может оказаться инъективной. Следовательно, реверсировав последнюю, мы получим исходный пароль. Это делает уязвимыми многие защиты, использующие данный алгоритм.

Выше мы упоминали специальные хеш-функции. Развитие криптографии привело к исследованию так называемых односторонних функций. Во многих некомпетентных источниках смешивают понятия хеш и односторонних функций. На самом деле они изучаются разными разделами математики и обладают разными свойствами. Однако, среди них есть и такие, которые удовлетворяют двум критериям сразу. Или иначе говоря, есть односторонние хеш-преобразования. Строго говоря, на сегодняшний день не найдено ни одной идеальной односторонней функции. Более того, до сих пор не доказано, что такие функции существуют. Поэтому мы будем говорить лишь о приближенных к этому реализациях.

Функция f: Х-> Y называется односторонней, если f(x) может быть легко вычислена для любого элемента X, тогда для всех элементов Yвычисление такого аргумента f для которого f(x) = у не разрешимо полиномиально.

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

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

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

Как ни парадоксально, но использование хороших хеш-функций уменьшает число возможных паролей, облегчая работу взломщика. Использование плохих - дает об исходном пароле информацию, по которой его возможно частично восстановить. Поэтому, никакие хэш-функции нельзя использовать для «свертки» с пароля. Например, RAR не проверяет пароль на валидность, а сверяет CRC расшифрованных данных. Это не дает никакой информации об исходном пароле, но медленно работает. С другой стороны, у всех быстрых алгоритмов шифрования (хвалебные сообщение о которых периодически появляются в разных источниках) есть существенный недостаток - быстрый перебор увеличивает шансы лобовой атаки.

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

Реально же редкие фирмы могут позволить себе анализ подобного уровня Обычно ограничиваются беглым осмотром.

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

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

Дата добавления: 2014-01-11