Библиотека Интернет Индустрии I2R.ru

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

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

Кроме того, обычно такие оценки исходят из предположения, что злоумышленник будет просто перебирать последовательно все пароли один за другим. Наивно, не так-ли? Лобовая атака на современных вычислительных мощностях персональных компьютеров сегодня попросту невозможна. Сколь нибудь удовлетворительные результаты могут быть получены только при объединении десятков тысяч компьютеров.

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

К сожалению, сейчас многие (с позволения сказать) недохакеры не обладают даже минимальными математическими познаниями. Более того, академическую математику закидывают камнями, обвиняя последнюю в полной бесполезности для прикладных и системных программистов. Увы, это кризис нашего (да и не только нашего) образования.

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

Несмотря на то, что первая часть является неизбежным теоретическим введением в ней все положения будут рассмотрены на примерах конкретных реализаций. Для этого необходимо выбрать платформу. Приучая читателя к детальному ("низкоуровнему") мышлению я выбираю ассемблер. Реже буду использовать IDA Си и MS VC. Поклонники Паскаля и Делфи должны будут делать свой выбор самостоятельно. Во всяком случае без знания ассемблера изучение и защита программ в большинстве случаев невозможна. Эта книга не научит вас основам ассемблера и рассчитана на уже подготовленного читателя.

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

Настоящий хакер никогда не откажет себе удовольствие копания не только в недрах кода, но и литературы (не важно, бумажной или электронной). Соблазн использовать готовые схемы и решения "AS IS" достоин только коммерческих кракеров (поставившим взлом на поток и зарабатывающим деньги на эксплуатации часто чужих идей и инструментов). Я не хочу вдаваться в этическую полемику и задаваться извечным вопросом "что такое хорошо и что такое плохо?" Так или иначе это есть. Любая законченная технология не требует для использования понимания ее функционирования. Воплощенная в конкретный программный код, она становится в руках вандалов разрушающим программным оружием. Выход из ситуации "методом Страуса" невозможен. Сегодня вычислительная техника уже не контролируется и такая программа будет создана и распространена если не одним, так другим человеком.Распространение технологий и инструментов для взломов и атак не является актом вандализма, а напротив указанием на уязвимость существующих систем, побуждая к исправлению последних.

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

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

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

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

Хеши. Односторонние функции

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

h: А -->

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

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

Рассмотрим практическую реализацию для некоторого множества команд 'IF','THEN', 'BEGIN','END'. Выберем простейшую хеш функцию посимвольно складывающую элементы строки. Это плохая хеш-функция и ниже мы поясним почему, но для нашего примера ее будет достаточно.

Для начала нужно построить хеш таблицу значений для всех элементов множества S. Воспользуется для этого программой file://CD:/SRC/hash00.exe - "хеш-калькулятор". Рассмотрим ее ключевой фрагмент:

        BYTE GetHash(CString s0)
        {
                BYTE hash=0;
                for (int a=0;a<s0.GetLength();a++)
                hash=hash+s0[a]; // Вычисляем хеш-сумму
                return hash;
        }

Мы посимвольно складываем элементы множества символов s0, получая в результате некоторый элемент из множества calc .Как нетрудно видеть на каждый элемент множества calc отображается не более, чем один элемент S. Отсюда в заданных рамках функция calc=calc+s0[a] инъективна. Следовательно для заданного индекса единственным образом определяется элемент S. Этим доказывается корректность работы хеш-анализатора.

Ниже приведен фрагмент реально работающего эмулятора виртуального процессора GetMe01 (file://CD:\CrackMe\GetMe01.asm).

        LEA     SI,     Buffer   ; Буфер исполнительных команд
start_r:                         ; <--------------------------------------¬
        CALL    GetHashe         ; Вычисление хеш-суммы очередной команды ¦
        CALL    CallIt           ; Вызов обработчика  для  данной команды ¦
        MOV     SI,DI            ; Позиционирование     указателя команд  ¦
        CALL    Seek             ; ^                                      ¦
        JMP     short start_r    ; --[uncond]------------------------------


GetHashe        PROC    NEAR
        PUSH    SI               ; Сохраняем виртуальный указатель команд
        XOR     AX,AX            ; AH == сумматор
gh_Repeat:                       ; <--------------------------------------¬
        LODSB                    ; Берем очередной элемент множества s0   ¦
        ADD     AH,AL            ; Добавляем в сумматор                   ¦
        XOR     AL,':'           ; Проверка на конец команды              ¦
        JNZ     gh_Repeat        ; --([SI]==':')---------------------------
        POP     DI               ; si-->di; return SI
        RETN                     ; --\
ENDP


Seek            PROC    NEAR
s_repeat:                        ; <--------------------------------------¬
        LODSB                    ; Взять следующий символ                 ¦
        OR      AL,AL            ; Проверить на равенство нулю            ¦
        JNZ     s_repeat         ; --([SI]==NULL)--------------------------
        RETN                     ; --\
ENDP

CallIt  Proc NEAR
        PUSH    SI               ; Сохранить SI
        LEA     SI,TableOfRange  ; Таблица указателей на обработчики
        XCHG    AX,BX            ; BH == AL
ci_rep:                          ; <--------------------------------------¬
        LODSB                    ; Читаем очередную хеш-сумму             ¦
        OR      AL,AL            ; Конец таблицы?                         ¦
        JZ      _err             ; --достигнут конец таблицы-->           ¦
        CMP     AL,BH            ; Хеш найден?                            ¦
        LODSW                    ; Читаем очередное смещение обработчика  ¦
        JNZ     ci_rep           ; --(!Hash)-------------------------------
        XCHG    AX,BX            ; BX == AX == смещение обработчика
        POP     SI               ; Восстановить SI
        CALL    BX               ; Вызвать обработчик данной команды
        RET                      ; --\

_err:                            ; Исключительная ситуация. Неверная команда
        MOV     AH,9             ; Печать строки MS-DOS
        LEA     DX,errr          ; Смещение печатаемой строки
        INT     21h              ;
        MOV     AH,4Ch           ; Завершение работы
        INT     21h              ; --\

errr     DB      'Неизвестная команда',0Dh,0Ah,'$'
ENDP

; //////////////////////////////////////////////////////////////////////////
; //     ТАБЛИЦА ПОДДЕРЖИВАЕМЫХ КОМАНД И СООТВЕТСТВУЮЩИМ ИМ ОБРАБОТЧИКОВ
; //------------------------------------------------------------------------
TableOfRange:
        DB      0EFh             ; Хеш-сумма команды
        DW      Offset Proc1     ; Обработчик данной команды
        DB      0E3h
        DW      offset Proc2
        DB      79h
        DW      offset Proc3
        DB      0E6h
        DW      offset Proc4
        DB      01h
        DW      offset Proc5
        DB      0D1h
        DW      offset Proc7
        DB      054h
        DW      offset Proc8
        DB      0ADh
        DW      offset Proc9
        DB      0                ; Конец таблицы

Buffer:                          ; Буфер исполнительных команд

Данный пример хранит восьмибитную хеш сумму каждой команды. Следовательно независимо от длины используемых команд для хранения потребуется всего N байт памяти (где N - число команд), что существенно меньше объема необходимого для полного хранения тех же самых команд. Теоретически восьмибитная хеш-сумма может вместить до 0xFF+1 команд. Однако, практически предложенная реализация при добавлении некоторого числа команд окажется неработоспособной. Это случится когда двум разным командам будет соответствовать одна и та же хеш-сумма. В таком случае математики говорят о коллизии хеш-функции. Следовательно на выбранном интервале хеш функция становиться неинъективной и для рассматриваемой задачи непригодной.

Казалось бы, раз множество S намного больше A, то любая хеш функция на полной области определения S окажется неинъективной. На самом деле число элементов S практически всегда много меньше его мощности. Например в множество слов русского языка представляется множеством последовательностей от одного до десяти и более символов,но общее число существующих слов заведомо меньше 0xFFFFFFFF. Поэтому возможно существование 32-битной инъективной хеш функции для синтаксического анализатора русского языка.

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

Наиболее часто используется и хорошо изучен мультипликационный метод отображения. Математически его можно выразить как h(S[x])=C*S[x] mod N, где N - это число элементов хеш-множества или другими словами его мощность. С - любая константа из интервала [0,N). При C=1 эта формула приобретает вид h(S[x])=S[x] mod N и является самостоятельным хеш преобразованием, называемым методом остатка. Данный алгоритм так же широко используется и для генерации псевдослучайных чисел. И неудивительно, ведь генераторы случайных чисел являются ничем иным как хеш-преобразованием!

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

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

Рассмотрим алгоритм этой функции. Целую беззнаковую 32-х битовую переменную инициализируем значением 0FFFFFFFFh. Далее умножаем на 2 аргумент функции и значение CRC. Если старшие биты окажутся не равны, тогда CRC = CRC XOR 0xEDB88320. И так до последнего бита аргумента. Если аргумент строковая (или какая-либо другая последовательность), то операции проводятся над двойными словами. В каноническом варианте в конце цикла требуют инвертировать все биты CRC, но это играет роль исключительно для совместимости результатов, полученного разными функциями, и никак не сказывается на качестве. "Магическое число" 0xEDB88320 есть стандартный полином, менять который не следует, т.к. это ухудшит качество функции.

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

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

     p
   F(Ai) ------> Aj

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

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

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

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

Функция f: X -> Y называется односторонней, если f(x) может быть легко вычислена для любого элемента X, тогда для всех элементов Y вычисление такого аргумента f для которого f(x) = y не разрешимо полиномиально. Это показывает, что CRC32 не является односторонней функцией и,невзирая на распространенное мнение, подлежит реверсированию. Поскольку для каждого значение х CRC32 существует бесконечное множество верных аргументов А, таких что F:CRC32(A) = x, то получение множества подходящих аргументов А' нам не дает никаких намеков для нахождения в нем искомого элемента. Именно этим и вызвана беспечность широкого (и между прочим не оправданного) применения CRC32 в криптографии. Односторонность этой функции держится всего лишь на ее неинъективности. Однако, как было показано выше, возможно существование такого интервала I на котором выбранная хеш функция является инъективной. Практически во всех популярных криптосистемах не делается никаких попыток проверки принадлежности хешируемых данных к этому интервалу. Более того, для любого конечного перечисленного множества Z возможен как прямой (пред вычисленный), так и обратный реверс хеш-функции. CRC32 успешно обращается полиномиально. В результате часто становиться уязвимым местом криптозащит.

Рассмотрим табличное реверсирование. Для этого вычислим CRC32 каждого элемента перечисленного множества Z и сравним ее и исходной. Среди полученных элементов находится по крайней мере один действительный пароль. Множество Z в нашем случае это множество возможных паролей. Нетрудно вычислить, что даже для восьмисимвольных паролей потребуется по крайней мере 4^8 (или 2^16) байт памяти для хеш-сумм и еще больше для хранения образа паролей. Кроме того это потребует очень большого числа итераций.

Поэтому особый интерес представляет обратный полинормальный алгоритм. Заметим сразу - он является полинормальным только для конечных перечисленных множеств. А выглядит для каждого бита обращенного аргумента так:

   b == !Hibit(xor (crc32,0xEDB88320)) | Hibit(crc32)

Т.е. предположим, что каждый бит аргумента может являться как нулем, так и единицей. Проверим оба результата на принадлежность к множеству Z и отбросим ненужные. Если оба значения принадлежат Z, то запоминаем оба и дальше вычисляем оставшиеся биты для обоих из них и так до тех пор пока не будет отброшен последний элемент, как не принадлежащий к множеству Z. Иначе говоря мы строим бинарное дерево. Очень легко подсчитать необходимое число итераций для нахождения все возможных паролей. Кроме того для этой ситуации применимы все эффективные алгоритмы, работающие с двоичными деревьями. Сбалансированное двоичное дерево позволит эффективно реверсировать crc32 даже в случае большого рассеяния элементов Z. Иначе говоря мы можем быстро проверить не является-ли этот хеш контрольной суммой какого-нибудь словарного слова. Обратное преобразование сделает это существенно быстрее прямого перебора множества словарных слов. Подробнее операции с двоичными деревьями изложены в книге Майкла Ласло "Вычислительная геометрия и компьютерная графика на C++" (Москва БИНОМ 1997) или во многих других изданиях. Очень рекомендую ознакомиться с конспектами лекций Манфрейда Броя "ИНФОРМАТИКА" Диалог-Мифи 1998 год.

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

Чтобы научиться строить эффективные алгоритмы необходимо хотя бы вкратце ознакомиться с теорией формальных языков. Понятие формального языка требует рассмотрения алфавита. Алфавитом является конечное перечисленное множество A. Множество всех конечных последовательностей элементов А называется формальным языком. Языки оперируют словами. Для заданного множества A последовательность элементов x1..xn принадлежащим A образует слово длины n, которое записывается как <x1..xn>. Множество всех слов равняется AxAx...xA, что принято записывать как A*. Для каждого слова формального языка существует отображение length:A' --> N, где N - длина слова.

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

Для начала рассмотрим простейший алгоритм генерации паролей построенный на последовательном множестве. Полный исходный текст находится на file://CD:/SRC/parole.asm, а ниже приводится только ключевой фрагмент. Предложенный алгоритм является воплощением простоты и при этом шустро работает и достаточно гибок, что бы в последствии мог быть применен для произвольных перечисленных множеств.

        MOV     AH, 9h                  ; Телетайпный вывод
        LEA     SI, Password            ; Начальный пароль
        MOV     DX, SI                  ; для f.9/Int 21h
NextPassword:                           ; > Генерация следующего пароля <--¬
        XOR     BX, BX                  ; С нулевого разряда               ¦
CheckOver:                              ; > Проверка на переполнение <----¬¦
        INC     Byte Ptr DS:[SI+BX]     ; Увеличиваем первый слева символ ¦¦
        CMP     Byte Ptr DS:[SI+BX],'z' ; Выход за допустимые границы?    ¦¦
        JB      WritePassword           ; --{Нет переноса}-----------------+
        MOV     Byte Ptr [SI+BX], ' '   ; Сбрасываем текший разряд        ¦¦
        INC     BX                      ; Перенос на следующий разряд     ¦¦
        JMP     Short CheckOver         ; ---------------------------------¦
WritePassword:                          ; > Вывод пароля на экран          ¦
        INT     21h                     ; ^                                ¦
        JMP     SHORT   NextPassword    ; ----------------------------------
Password        DB 8 Dup(' ')           ; <- - начальный пароль
                DB 13, 10, '$'          ; <- - конец строки

Тот же алгоритм изящно выражается одной строкой на языке Cи (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     AL, Byte Ptr DS:[SI+BP] ; Взять элемент psw
        XLAT                            ; Отобразить его на мнж. alf
        MOV     [DI+BP], AL             ; Записать результат

        INC     Byte ptr [SI+BP]        ; Следующий

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

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

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

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

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

Возможна ли эффективная атака на 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 ¦  0   1
        ----+------------
         0  ¦  0   1
            ¦
         1  ¦  1   0
            ¦

Мы видим, что для каждого значения функции существуют ровно две пары x1, x2, что и требовалось доказать. Поэтому ожидаемое число паролей будет 2^n где N разрядность хеш-суммы. Разрядность пароля при этом не выше разрядности хеш-суммы. Т.е. мы просто провели простое побитовое обращение функции xor. Для восьмибитной хеш-суммы это число равно 0x100! Т.е. значение хеша нам абсолютно ничего не дает, т.к. x1 и x2 могут быть любыми! Однако, 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 самое мощное оружие (ведь оно дает доступ ко ВСЕМ паролям) так уязвимо для атаки. Однако, криптографы предпочитают использовать вместо мастер-паролей односторонние функции с секретом. Это означает, что в действительности никакие они не односторонние и существует простое обратное решение. Но вот только найти его представляет не менее простую задачу, чем атаковать пароль.