Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Такая операция дает нам неограниченную гибкость. Элементами перечисленного множества могут быть литеры, группы литер, а также целые слова. Таким образом, предложенный алгоритм позволяет полностью абстрагироваться от используемого типа данных.
Рассмотрим следующий аспект. Как правило, пароли состоят не из равновероятных символов. Хорошая перебирающая программа должна это учитывать. Может ли это обеспечить предложенный алгоритм? Рассмотрим такую функцию отображения f, которая отображает более одного индекса С на один и тот же элемент Z, задавая тем самым вероятность его появления в генерируемом пароле. Отметим, однако, что при этом возрастут накладные расходы. Пусть два элемента с1 и с2 отображаются на один и тот же элемент zl. Тогда мы получим дважды один и тот же пароль zl. Обычно этим можно пренебречь, так как доля дублирующихся паролей несущественна. Но когда она достигнет нескольких процентов от общего числа, то разумно запоминать все встретившиеся пароли и игнорировать повторные. Двоичное дерево обеспечивает приемлемую скорость поиска.
Отметим также гетерогенные свойства предложенного алгоритма. Т.е. функция отображения может одновременно работать с разными типами данных. Например, можно вести параллельный словарный поиск, перебор слогов и распространенных алфавитных сочетаний одновременно с последовательным перебором литер.
В качестве примера приведем усовершенствованный алгоритм с отображением, выполняемым функцией xlat (file://CD:\SOURCE\ASM_C\PAROLEOI\pa-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, самое мощное оружие (ведь оно дает доступ ко всем паролям) так уязвимо для атаки. Однако криптографы предпочитают использовать вместо мастер-паролей односторонние функции с секретом. Это означает, что в действительности эти функции совсем не односторонние и существует простое обратное решение. Но вот только найти его не более просто, чем атаковать пароль.
Существует несколько наивных подходов к этой проблеме, и некоторые секреты действительно легко вскрыть. Но не все так просто. Качественные алгоритмы для этого уже давно существуют. Ниже будет приведен один из них.
В заключении мы рассмотрим области применения хеш-функций, не относящиеся к криптографии и защите программ. Знание их существенно облегчает дизассемблирование и анализ изучаемых программ. Например, множество команд хешевого интерпретатора нельзя получить никаким образом, отличным от обращения хеш-функции. Аналогично обстоит дело и с хеш-поиском.
Дата публикования: 2014-11-18; Прочитано: 316 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!