С—f---Z

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

Рассмотрим следующий аспект. Как правило, пароли состоят не из равнове­роятных символов. Хорошая перебирающая программа должна это учитывать. Может ли это обеспечить предложенный алгоритм? Рассмотрим такую функцию отображения f, которая отображает более одного индекса С на один и тот же элемент Z, задавая тем самым вероятность его появления в генерируемом пароле. Отметим, однако, что при этом возрастут накладные расходы. Пусть два элемента с1 и с2 отображаются на один и тот же элемент zl. Тогда мы получим дважды один и тот же пароль zl. Обычно этим можно пренебречь, так как доля дублирую­щихся паролей несущественна. Но когда она достигнет нескольких процентов от общего числа, то разумно запоминать все встретившиеся пароли и игнорировать повторные. Двоичное дерево обеспечивает приемлемую скорость поиска.

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

В качестве примера приведем усовершенствованный алгоритм с отображени­ем, выполняемым функцией xlat (file://CD:SOURCEASM_CPAROLEOIpa-roleOl.asm).

Repeat:

MOV AL, Byte Ptr DS:[SI+BP] ; Взять элемент psw

XLAT ; Отобразить его на мнж. alf

MOV [DI+BP], AL ; Записать результат

INС Byte Ptr [SI+ВР] ; Следующий

CALL WritePassword ; Вывести пароль

CMP [SI+BP],CL ; Проверка на переполнение

JB Repeat

 

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

Теперь можно атаковать любую одностороннюю функцию, перебирая все допустимые аргументы и занося их в таблицу, после заполнения которой можно найти все аргументы А, для которых справедливо f:a = key, где key — известный результат функции. Если выбранная функция инъективна и существует не более одного аргумента для заданного кеу, то в построении таблицы нет никакой необходимости. Первый совпадающий аргумент и будет искомым.

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

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

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

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

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

Рассмотрим еще одну область применения хеш-функций. Пусть у нас есть некоторый пароль р, который "зашит" в электронном ключе или введен пользо­вателем. Сравнивать пароль типа if(UserPassword!=MyPassword) abort(); нельзя так как это очень просто ломается. Можно расшифровать паролем некоторый фрагмент кода или использовать его как константу. Если для шифрования выбрана криптостойкая схема, пароль можно найти только перебором всех возможных. Контроль правильности ввода можно обеспечить с помощью конт­рольных сумм. Эта схема очень надежна, но в большинстве приложений реализо­вана с ошибками. Как уже догадался читатель, контрольная сумма снимается с пароля, а не с расшифрованных данных. Но это далеко не самая глупая ошибка! В целях безопасности электронный ключ не должен сообщать пароль в "прямом" виде. С него снимается хеш-сумма, которая и передается для расшифровки. Таким образом, мы имеем два значения разных хеш функций. Первое — для контроля правильности пароля, второе — для расшифровки. Мы получаем систему двух уравнений, решением которого будет пересечение двух множеств реверсирован-ных хеш-преобразований. Это сокращает множество перебираемых паролей вплоть до единственного. Такой подход применим в случае идеальных хеш-функ­ций. Другим решением будет попытка вычислить вторую контрольную сумму из первой.

Распространенной ошибкой является и использование "длинных" сгс, сравни­мых с длиной пароля. Читатель может сам подсчитать сколько возможных восьмисимвольных паролей имеют одно и то же значение 32-битной контрольной суммы. Однако использование более коротких хеш-сумм увеличивает вероятность того, что неверный пароль будет воспринят как правильный.

Популярная система Novell NetWare 3.х-4.х использовала уязвимый алгоритм. Суть его сводилась к тому, что с пароля снималась хеш-сумма, с которой затем сравнивался вводимый пароль. Эта функция была обратима. Таким образом можно было получитьмножество паролей, которые все воспринимались систе­мой как верные.

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

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

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

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

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

 

ReHashe (unsigned char hashe)

{

for (unsigned char a"'A';a<'a';a++)

{

if ( !hashe-=a} return;

ReHashe (hashe);

}

}

Данный пример не рекомендуется запускать. Легко доказать, что для любого hashe существует бесконечное множество таких ключей, что f(key) == hashe. Реально разрядность паролей ограничена емкостью стека. При исчерпании по­следнего возникнет исключительная ситуация и выполнение программы будет аварийно завершено.

Более того, легко доказать, что данный пример может "провалиться" в бесконечный рекурсивный спуск. Пусть hash — нечетное число, а А — четное. Тогда (hash-a) никогда не будет равно нулю.

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

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

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

Упорядочить должным образом обращаемые ключи можно отображением на заранее отсортированное множество, хотя это потребует накладных расходов на память и предварительную сортировку элементов.

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

Попробуем количественно выразить ожидаемое число паролей для другой популярной функции hashe(A)= а1 хог а2 хог аЭ ... xor an. Для начала докажем, что для любого а, равного х1 хог х2, существуют только две пары х1 и х2, при условии что Х [0,11. Как известно из булевой алгебры, операция хог может быть представлена следующей логической матрицей:

хог	0 1
	0 1
	1 0

Мы видим) что для каждого значения функции существуют ровно две пары х1, х2, что и требовалось доказать. Поэтому ожидаемое число паролей будет 2^n, где п — разрядность хеш-суммы. Разрядность пароля при этом не выше разряд­ности хеш-суммы. Т.е. мы провели простое побитовое обращение функции хог. Для восьмибитной хеш-суммы это число равно 0х100. Т.е. значение хеша нам абсолютно ничего не дает, так как х1 и х2 могут быть любыми! Однако, х1х2 это 2^16 вариантов, т.е. знание хеш-суммы все же позволяет сократить число переби­раемых паролей в 0х100 раз. Неплохо; но даже этот результат можно улучшить. Множество допустимых символов пароля, как правило, много меньше 0х100. Пусть ожидаемый пароль состоит только из символов 'A*..'Z'. Тогда для него существует не более 2^5 возможных пар х1 и х2!

Последним мы рассмотрим реверс мультипликационного алгоритма. Пусть А = СХ mod N, тогда Х = k*N/C+A, где k!=0. Но в пределах [0,М) мультипли­кационная функция инъективна! Для доказательства этого вспомним, что любое число можно представить как х*п+у единственным образом.

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

Все приведенные хеш-функции не являются односторонними и значительно уменьшают число возможных паролей. Совсем иначе дело обстоит с односторон­ними функциями, использующимися в криптостойких системах. Казалось бы, если обращение их дело безнадежное, то на этом можно ставить точку и даже не пытаться заниматься заведомо неразрешимой проблемой. Отчасти это верно. Действительно, необратимость большинства функций сомнений не вызывает, но другие, отличные от обращения, пути часто остаются неучтенными и не закрыты­ми, лишний раз подтверждая слабость большинства реализаций. Часто односто­ронние функции вычисляются очень быстро. Таким образом, выгоднее сначала последовательно перебрать все возможные пароли, дающие заданный хеш, а затем атаковать шифр заданным множеством паролей. Все "сильные" криптостойкие алгоритмы, как правило, очень медленны. Именно это и препятствует атаке. Так, например, на Р-120 скорость перебора UNIX — MD5 не превышает 200 паро­лей/с. Тогда как многие хеш-функции до 300.000 и выше! Однонаправленность сама по себе не спасает функцию. Да, реверс не возможен, но прямая атака (т.е. последовательный перебор всех аргументов до совпадения со значением функции) эффективнее прямой атаки на шифр. Впрочем, не стоит обольщаться. Весьма вероятно, что несмотря на грубые ошибки реализации криптосистемы взлом будет лежать за допустимой гранью. Скажем, мы найдем пароль не за биллион, а за десять лет. Так, вероятно, и рассуждают конструкторы защит. А ведь в эти рассуждения вкралась ошибка! На чем держится криптосистема? На малой скорости перебора паролей и большом количестве подходящих под хеш ключей. При условии использования бессмысленного пароля хакеру осталось бы только развести руками. Однако пользователи склонны выбирать осмысленные пароли. Если такой встретится в множестве подходящих под хеш паролей, то в дальней­шей атаке на систему, возможно, уже не будет нужды! Время, затраченное на атаку, в таком случае определяется только скоростью выполнения хеш-преобра­зования! Предложенный механизм очень близок к словарной атаке и основан на "слабых" паролях. Поиск "осмысленного" пароля представляет выборку всех паролей, включающих в себя по крайней мере трехсимвольный фрагмент словар­ного слова и отсортированных по убыванию длины подстроки.

Существует по крайней мере еще одно уязвимое место, введенное в некоторые криптосистемы под давлением правительства. Это так называемые "мастер-паро­ли". Предполагается, что они должны быть известны исключительно спецслужбам и не могут быть найдены иначе как методом перебора. Удивительно, но встреча­ются словарные мастер-пароли. Так, например, AWARD_SW. Забавно: когда даже пользователи начинают осознавать слабость словарных паролей и администрато­ры используют нечто вроде t%7Nh6i@SrF, самое мощное оружие (ведь оно дает доступ ковсем паролям) так уязвимо для атаки. Однако криптографы предпочи­тают использовать вместо мастер-паролей односторонние функции с секретом. Это означает, что в действительности эти функции совсем не односторонние и существует простое обратное решение. Но вот только найти его не более просто, чем атаковать пароль.

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

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