Перенос на следующий разряд
MOV AH, 9h LEA SI, Password MOV DX, SI NextPassword:
XOR BX, BX
; Телетайпный вывод ; Начальный пароль ; для f.9/Int 21h
CheckOver: ; Проверка на переполнение -|
INC Byte Ptr DS:[SI+BX] ; Увеличиваем первый слева символ || CMP Byte Ptr DS:[SI+BX],'z' ; Выход за допустимые границы? ||
MOV Byte Ptr [SI+BX], ' ' ; Сбрасываем текший разряд ||
INC BX ; Перенос на следующий разряд ||
Вывод пароля на экран
WritePassword:
JMP SHORT NextPassword ;------------------------
Password DB 8 Dup(' ') ; - - начальный пароль
DB 13, 10, '$' ; - - конец строки
Тот же алгоритм изящно выражается одной строкой на языке ^ (file://CD:/SRC/PA
E/Pae.cpp):
while ((pasword[index++]++)'z') pasword[index-1]=' ';
Математический смысл сводится к последовательному перебору всех элементов множества ['
','z'] путем добавления единицы с учетом переноса. Т.е. иначе можно эту функцию можно назвать как INC x - где x число практически неограниченной разрядности.
Данный алгоритм относится к числу простейших, но для практического применения не годится. Нам необходимо перебирать пароли из произвольного множества символов. Данный пример работает на единственном интервале [x1, xn] линейного множества C.
Вот тут нам и пригодится математика! В самом деле усложнять алгоритм нет никакой нужды, достаточно лишь отобразить линейное множество C на перечисленное Z.
f
C --- Z
При этом такая операция дает нам неограниченную гибкость. Элементами перечисленного
множества могут быть литеры, группы литер, а так же целые слова. Таким образом предложенный алгоритм позволяет полностью абстрагироваться от используемого типа данных.
Рассмотрим следующий аспект. Как правило пароли состоят не из равновероятных символов.
Хорошая перебирающая программа должна это учитывать. Может ли это обеспечить предложенный алгоритм?
Рассмотрим такую функцию отображения f, которая отображает более одного индекса C на один и тот же элемент Z. Таким образом, задавая вероятность его появления в генерируемом пароле. Отметим, однако, что при этом возрастут накладные расходы.
Пусть имеем для элемента c1 и с2, которые отображаются на один и тот же элемент z1. Тогда мы получим дважды один и тот же пароль z1. Обычно этим можно пренебречь, т.к. доля дублирующихся паролей несущественна. Но когда она достигнет нескольких процентов от общего числа, то разумно будет запоминать все встретившиеся пароли и игнорировать повторные.
Двоичное дерево обеспечивает приемлемую скорость поиска.
Отметим так же гетерогенные свойства предложенного алгоритма. Т.е. функция отображения может одновременно работать с разными типами данных.
Например, можно вести параллельный словарный поиск, перебор слогов и распространенных алфавитных считаний одновременно с последовательным перебором литер.
В качестве примера приведем усовершенствованный алгоритм с отображением выполняемым функцией xlat (file://CD:/SRC/Parole01.asm).
Next:
| MOV XLAT MOV |
AL, Byte Ptr DS:[SI+BP] ; Взять элемент psw ; Отобразить его на мнж. alf [DI+BP], AL ; Записать результат | |
| INC | Byte ptr [SI+BP] | ; Следующий |
| CALL | WritePassword | ; Вывести пароль |
| CMP [SI+BP],CL JB Repeat |
; Проверка на переполнение |
предложенная реализация не самая эффективная. Есть множество других интересных алгоритмов.
На каком-нибудь одном из них мы останавливаться не будем, т.к. это было бы слишком утомительно и не интересно.
Теперь можно атаковать любую одностороннюю функцию перебирая все допустимые аргументы и занося их в таблицу, после заполнения которой можно найти все аргументы А, для которых справедливо f:a = key, где key известный результат функции. Если выбранная функция инъективна, и существует не более одного аргумента для заданного ^y, то в построении таблицы нет никакой необходимости.
Первый совпадающий аргумент и будет искомым.
Обращаю еще раз внимание, что хеш-функция и односторонняя функция не одно и то же. Так, например, произведение двух простых чисел это хороший пример качественной односторонней функции, не обладающей свойствами и не являющейся хеш-преобразованием.
Возможна ли эффективная атака на RSA и подобные системы? Над проблемой разложения чисел на простые сомножители безуспешно бились многие знаменитые математики. Но до сих пор не доказано, что это не возможно.
Быть может и среди хакеров найдется математический гений который решит эту проблему? Но пока же ничего кроме перебора предложить не удается. Единственным выходом является не полный, а самоорганизующийся табличный поиск. Возможно создание специализированного чипа, занимающегося таким перебором.
Умножение очень простая операция, поэтому она легко реализуется аппаратно, и такой чип может очень дешево стоить.
Системы, построенные на односторонних функциях при условии отсутствия ошибок реализации, взлому как правило, не подлежат. Впрочем, программы без ошибок сегодня редкость.
Как уже отмечалось - использование контрольной суммы это один из способов этот пароль найти. Крайне редко в системах массового применения используют односторонние хеш-функции.
Множество полученных паролей много меньше всего допустимого множества, кроме того среди них можно поискать осмысленные последовательности, которые с большой вероятностью и являются искомым паролем.
Как ни парадоксально, но использование хороших хеш-функций уменьшает число возможных паролей, облегчая работу взломщика. Использование плохих - дает об исходном пароле информацию по которой его возможно частично восстановить. Поэтому, никакие хеш функции нельзя использовать для свертки с пароля.
Например RAR не проверяет пароль на валидность, а сверяет CRC расшифрованных данных. Это не дает никакой информации об исходном пароле, но медленно работает.
С другой стороны у всех быстрых алгоритмов шифрования (хвалебные сообщение о которых периодически появляются в разных источниках) есть существенный недостаток - быстрый перебор увеличивает шансы лобовой атаки.
Рассмотрим еще одну область применения хеш функций. Пусть у нас есть некоторый пароль p, который зашит в электронном ключе или введен пользователем. Сравнивать пароль типа if(UserPassword!=MyPassword) abort(); нельзя т.к. это очень просто ломается.
Можно расшифровать паролем некоторый фрагмент кода или использовать его как константу. При условии что для шифрования выбрана криптосктойкая схема пароль нельзя найти никак кроме перебором всех возможных.Контроль правильности ввода можно обеспечить с помощью контрольных сумм. Эта схема очень надежна, но в большинстве приложений реализована с ошибками.
Как уже догадался читатель, контрольная сумма снимается с пароля, а не с расшифрованных данных. Но это далеко не самая глупая ошибка! В целях безопасности эл. ключ не должен сообщать пароль в прямом виде. С него снимается хеш-сумма, которая и передается для расшифровки.
Таким образом, мы имеем два значения разных хеш функций. Первое для контроля правильности пароля, второе - для расшифровки. Мы получаем систему двух уравнений решением которого будет пересечение двух множеств реверсированных хеш-преобразований.
Это сокращает множество перебираемых паролей вплоть до единственного. Такой подход применим в случае идеальных хеш функций.
Другим решением будет попытка вычислить вторую контрольную сумму из первой.
Распространенной ошибкой является и использование длинных crc, сравнимых с длинной пароля. Читатель может сам подсчитать сколько возможных восьми-символьных паролей имеет одно и то же значение 32-битной контролькой суммы.
Однако использование более коротких хеш-сумм увеличивает вероятность того, что неверный пароль будет воспринят как правильный.
Популярная система Novell NetWare 3.x-4.x использовала уязвимый алгоритм. Суть его сводилась к тому, что с пароля, снималась хеш-сумма с которой затем сравнивался вводимый пароль. Эта функция была обратима.
Таким образом можно получить МНОЖЕСТВО паролей, которые все воспринималось системой как верные.
Сегодня не существует алгоритмов однозначно определяющих является произвольная функция односторонней или нет. Вынесение такого заключение всегда сопряжено со сложным комплексным анализом поиска от противного.
Если алгоритм обращения не будет найден коллективом математиков, то следовательно полагается, что не будет он найден и взломщиком.
Реально же редкие фирмы могут позволить себе анализ подобного уровня. Обычно ограничиваются беглым осмотром.
К чему это приводит мы уже имеем возможность наблюдать.
Из этого факта вытекает невозможность существования универсального алгоритма для реверсирования хеш функций. Даже если бы и предположить, что такой существовал бы, то все хеш-функции в первую очередь проверялись на устойчивость перед последним.
Однако, в качестве примера реверсируем популярные хеш функции. Существует довольно универсальный пошаговый алгоритм. Суть его в следующем - для каждого допустимого символа выполняем хеш-обратную операцию.
Полученный результат рекурсивно обращаем до получения последовательности заданной длины.
Ниже приведен упрощенный алгоритм для получения всех допустимых паролей для заданной хеш-суммы посимвольного подсчета суммы всех элементов (см. функцию GetHashe в примере 'GetMe01').
ReHashe(unsigned char hashe)
{
for (unsigned char a='A';a'a';a++)
{
if (!hashe-=a) return;
ReHashe(hashe);
}
}
Данный пример не рекомендуется запускать. Легко доказать, что для любого hashe
существует бесконечное множество ключей, таких что f(key) == hashe. Реально разрядность паролей ограничена емкостью стека.
При исчерпании последнего возникнет исключительная ситуация и выполнение программы будет аварийно завершено.
Более того, легко доказать, что данный пример может провалиться в бесконечный рекурсивный спуск. Пусть hash - нечетное число, а A - четное.
Тогда hash-a никогда не будет равно нулю.
Кроме этого нужно ввести ограничение на глубину рекурсии, определяемую максимально допустимой длинной ожидаемого пароля.
Не менее очевидный недостаток предложенного алгоритма, что выдаваемые им пароли не отсортированы по длине. Необходимо, что бы используемый алгоритм начинал с коротких паролей переходя к более длинным.
Выше мы доказывали, что хеш функция может быть реверсирована только на конечном перечисленном множестве Z. Для этого на каждом шаге мы должны проверять является ли полученная последовательность подмножеством хотя-бы одного элемента Z и если нет, исключать данную ветвь двоичного дерева.
Упорядочить должным образом обращаемые ключи можно отображением на заранее отсортированное множество, хотя это потребует накладных расходов на память и предварительную сортировку элементов.
В ряде случаев использование универсальных алгоритмов оказывается неприемлемо и тогда для каждой функции разрабатывается собственный уникальный алгоритм.
Попробуем количественно выразить ожидаемое число паролей для другой популярной функции hashe(A)= a1 xor a2 xor a3...xor an. Для начала докажем что любого a, равного x1 xor x2 существуют только две пары x1 и x2 при условии, что X [0,1].
Как известно из булевской алгебры операция xor может быть представлена следующей логической матрицей.
xor I 0 1 -+------------
0 | 0 1
I
1 I 1 0
I
Мы видим, что для каждого значения функции существуют ровно две пары x1, x2, что и
требовалось доказать. Поэтому ожидаемое число паролей будет 2Лп где N разрядность хеш-суммы.
Разрядность пароля при этом не выше разрядности хеш-суммы. Т.е. мы просто провели простое побитовое обращение функции xor. Для восьмибитной хеш-суммы это число равно 0x100!
Т.е. значение хеша нам абсолютно ничего не дает, т.к. x1 и х2 могут быть любыми! Однако, x1x2 это 2Л16 вариантов, т.е. знание хеш суммы все же позволяет сократить число перебираемых паролей в 0x100 раз. Неплохо, но даже этот результат можно улучшить.
Множество допустимых символом пароля, как правило много меньше 0x100. Пусть ожидаемый пароль состоит только из символов 'A'..'Z'.
Тогда для существует не более 2Л5 возможных пар x1 и x2!
Последним мы рассмотрим реверс мультипликационного алгоритма. Пусть A = CX mod N, тогда X = k*N/C+A, где k !=0. Но в пределах [0,N) мультипликационная функция инъективна!
Для доказательства этого вспомнить, что любое число можно представить как x*n+y единственным образом.
Мультиплекстый алгоритм относится к числу наиболее популярных. Это лишний раз подчеркивает, что разработчики систем защиты наплевательски относятся к своим продуктам и не обладают даже начальными знаниями в области криптоанализа.
Все приведенные хеш-функции не являются односторонними и значительно уменьшают число возможных паролей. Совсем иначе дело обстоит с односторонними функциями, использующимися в криптостойких системах.
Казалось бы, раз обращение их дело безнадежное, то в этом месте главы можно ставить точку и даже не пытаться заниматься заведомо неразрешимой проблемой. Отчасти это верно. Действительно, необратимость большинства функций сомнений не вызывает, но другие, отличные от обращения пути часто остаются неучтенными и не закрытыми, лишний раз подтверждая слабость большинства реализаций. Часто односторонние функции вычисляются очень быстро.
Таким образом, выгоднее сначала последовательным перебором все возможные пароли, дающие заданный хеш. После атаковать шифр заданным множеством паролей.
Все сильные криптостойкие алгоритмы как правило очень медленные. Именно это и препятствует атаке. Так например на P-120 скорость перебора UNIX - MD5 не превышает 200 паролей\сек.
Тогда как многие хеш-функции до 300.000 и выше! Однонаправленность сама по себе не спасает функцию. Да, реверс не возможен, но прямая атака (т.е. последовательный перебор всех аргументов до совпадения со значением функции) эффективнее прямой атаки на шифр. Впрочем, не стоит обольщаться.
Весьма вероятно, что не смотря на грубые ошибки реализации криптосистемы взлом будет лежать за гранью возможного времени. Ну найдем мы пароль не за биллион, а за десять лет, Так, вероятно, и рассуждают конструкторы защит. А ведь в этих рассуждения вкралась ошибка! На чем держится криптосистема?
На малойскорости перебора паролей и большом количестве подходящим под хеш ключей. При условии использования бессмысленного пароля хакеру осталось бы только развести руками. Однако, пользователи склонны выбирать осмысленные пароли. Если такой встретиться в множестве подходящим под хеш паролей, то в дальнейшей атаке на систему, возможно уже не будет нужды!
Время затраченное на атаку в таком случае определяется только скоростью выполнения хеш-преобразования! Предложенный механизм очень близок к словарной атаке, и основан на слабых паролях.
Поиск осмысленного пароля представляет выборку всех паролей, включающих в себя по крайней мере трех-символьный фрагмент словарного слова и отсортированный в убывании длины подстроки.
Существует по крайней мере еще одно уязвимое место, введенное в некоторые криптостимемы, под давлением правительства. Это так называемые мастер-пароли, Предполагается, что они должны быть известны исключительно спец-службам и не могут быть найдены иначе, как методом перебора. Удивительно, но встречаются словарные мастер-пароли.
Так, например, AWARD_SW. Забавно, что когда даже пользователи начинают осознавать слабость словарных паролей и администраторы используют нечто вроде t%7Nh6i@SrF самое мощное оружие (ведь оно дает доступ ко ВСЕМ паролям) так уязвимо для атаки. Однако, криптографы предпочитают использовать вместо мастер-паролей односторонние функции с секретом.
Это означает, что в действительности никакие они не односторонние и существует простое обратное решение. Но вот только найти его представляет не менее простую задачу, чем атаковать пароль.
Существует несколько наивных подходов к этой проблеме и некоторые секреты действительно легко вскрыть. Но не все так просто и качественные алгоритмы для этого уже давно существуют.
Покажем ниже один из них.
В заключении рассмотрим области применяя хеш функций, не относящиеся к криптографии и защитой программ. Знание их существенно облегчает дизассемблирование и анализ изучаемых программ.
Например, множество команд хешовый интерпретатора нельзя получить никаким образом, отличным от обращения хеш-функции. Аналогично и с хеш-поиском.
