Леонтьев Б. - Введение в криптосистемы
Стать хакером очень просто. Достаточно выучить и понять: математические дисциплины (математический анализ , теорию функций комплексного переменного, алгебру, геометрию, теорию вероятностей, математическую статистику, математическую логику и дискретную математику...
Борис Леонтьев Хакеры Internet
Существуют два основных подхода, применяемых в системах защиты информации. Первый
построен на затруднении прямого или косвенного анализа алгоритма путем применения оригинальных приемов программирования (использование недокументированных функций, специальных анти-отладочных приемов). Такой подход широко применяется в условнобесплатных программах, однако, крайне неэффективен. Он обладает плохим соотношением накладных расходов на создание\вскрытие защиты и кроме того не обеспечивает даже минимальной безопасности.
Большинство подобных программ ломаются в течении от нескольких минут до нескольких дней.
Сегодня большинство коммерческих защит основано на криптографических протоколах, а потому выглядит неломаемыми. Выглядит потому, что разработчики не учитывают разницу между теоретическими моделями и практической реализацией. Подробнее перечень основных ошибок в популярных системах изложен Павлом Семьяновым в статье Почему криптосистемы ненадежны.
Здесь отмечу лишь следующие - да,действительно, очень многие используемые криптосистемы ненадежны, и практически все имеют нижнюю границу разрешимости намного хуже паспортной.
Кроме того, обычно такие оценки исходят из предположения, что злоумышленник будет просто перебирать последовательно все пароли один за другим. Наивно, не так-ли? Лобовая атака на современных вычислительных мощностях персональных компьютеров сегодня попросту невозможна.
Сколь нибудь удовлетворительные результаты могут быть получены только при объединении десятков тысяч компьютеров.
Совсем другая картина выходит при анализе криптосистемы и поиске уязвимого места для атаки. Маловероятно, что бы конечная реализация не имела слабых мест.
Это, конечно, никак не означает, что как следует проанализировав ситуацию, можно найти дырку и быстренько в нее пролезть. Возможно, что криптостойкость даже самого слабого места в системе окажется вполне достаточной для защиты последней.
Но математический подход дает нам зрение и возможность качественной и самое главное количественной оценки сложности атаки.
К сожалению, сейчас многие (с позволения сказать) недохакеры не обладают даже минимальными математическими познаниями. Более того, академическую математику закидывают камнями, обвиняя последнюю в полной бесполезности для прикладных и системных программистов.
Увы, это кризис нашего (да и не только нашего) образования.
И проблема не в математике, а в людях, которые не могут увидеть в строчках формул живой реализации. Было бы хвастовством с моей стороны обещать восполнить пробелы знаний читателя. Никто кроме его самого ему не поможет.
Моей задачей будет показать практические реализации, и дать необходимый теоритическй минимум для их обоснования.
Быть может это откроет многим в мире сухих формул неограниченные перспективы их применения?
Несмотря на то, что первая часть является неизбежным теоретическим введением в ней все положения будут рассмотрены на примерах конкретных реализаций. Для этого необходимо выбрать платформу. Приучая читателя к детальному (низкоуровнему) мышлению я выбираю ассемблер.
Реже буду использовать IDA Си и MS VC. Поклонники Паскаля и Делфи должны будут делать свой выбор самостоятельно. Во всяком случае без знания ассемблера изучение и защита программ в большинстве случаев невозможна.
Эта книга не научит вас основам ассемблера и рассчитана на уже подготовленного читателя.
В отличие от этого никакой математической подготовки книга не требует. Однако, я надеюсь, что в процессе чтения, читатель будет обращаться к соответствующим источникам для получения более детальный картины подаваемого материала.
Настоящий хакер никогда не откажет себе удовольствие копания не только в недрах кода, но и литературы (не важно, бумажной или электронной). Соблазн использовать готовые схемы и решения AS IS достоин только коммерческих кракеров (поставившим взлом на поток и зарабатывающим деньги на эксплуатации часто чужих идей и инструментов).
Я не хочу вдаваться в этическую полемику и задаваться извечным вопросом что такое хорошо и что такое плохо? Так или иначе это есть.
Любая законченная технология не требует для использования понимания ее функционирования. Воплощенная в конкретный программный код, она становится в руках вандалов разрушающим программным оружием. Выход из ситуации методом Страуса невозможен.
Сегодня вычислительная техника уже не контролируется и такая программа будет создана и распространена если не одним, так другим человеком.Распространение технологий и инструментов для взломов и атак не является актом вандализма, а напротив указанием на уязвимость существующих систем, побуждая к исправлению последних.
Препятствование к распространению информации об атаках приводит к опасной иллюзии безопасности, которая в любой момент может рухнуть, погребая под своими обломками труды, возможно, тысяч людей.
Все прилагаемые к книге программы предназначены в первую очередь для системных администраторов и разработчиков систем безопасности для оценки их уязвимости.
Предполагается, что существующие дырки будут исправлены, и весь инструментарий, содержащийся на компакт диске окажется бесполезным в руках вандалах.
Это не относится к теоретическим выкладкам, отвязанным от конкретных платформ и реализаций. К счастью,маловероятно, что бы вандалы дали себе труд глубоко разобраться в последних.
В любом случае известно, что даже техническое образование культурно воспитывает человека. Знания дают человеку великолепный полигон для самовыражения, в котором растворяется желание пакости ближнему своему.
Хеши. Односторонние функции.
Ночь - это туннель,- подумала она. - Это дыра в завтра, если только оно наступит, это завтра.
Ф.Херберт. Дюна
Вся современная криптография основана на использовании методов хеширования. Метод
хеширования позволяет хранить множество элементов множества А в линейном массиве Х. Как правило, число элементов А много больше, чем Х. Математически это можно записать:
h: А -- {0,x-1}
Это читается функция h отображает каждый элемент А в индекс множества Х. Поскольку число элементов А как правило намного больше Х, то функция h наверняка неинъективна. Однако, возможно существование такого интервала на области определения функции, в границах которого она становится инъективной. Это означает, что только для одного элемента А существует индекс x1.
Функция будет инъективной и в том случае, если ни один элемент А не отображается на интервал {x1,x2} при условии, что последний не равен нулю.
В любом другом случае на каждый индекс множества Х отображается более одного элемента А. Это так называемая коллизия хеш-функции. Реверс хеш функции заключается в поиске всех отображаемых на данный индекс элементов.
Для любого конечного множества А это разрешимая задача, которая наиболее простое решение имеет на инъективных интервалах хеш-множества.
Давайте остановимся на инъективных интервалах. Невозможно практическое использование хеш-преобразований без понимания их значения.
В качестве примера рассмотрим следующую задачу: пусть нам требуется эффективный алгоритм сравнения строк, допустим, для синтаксического анализатора. Простое посимвольное сравнение потребует значительной памяти для хранения образов строк. Представим все возможное множество строк в данной разрядной сетке массивом S, тогда мы можем хеш-преобразованием привести его к множеству b {0,0xFF}.
Разумеется b много меньше S и требует для хранения значительно меньше памяти.
Рассмотрим практическую реализацию для некоторого множества команд TF','THEN', 'BEGIN','END'. Выберем простейшую хеш функцию посимвольно складывающую элементы строки.
Это плохая хеш-функция и ниже мы поясним почему, но для нашего примера ее будет достаточно.
Для начала нужно построить хеш таблицу значений для всех элементов множества S. Воспользуется для этого программой file://CD:/SRC/hash00.exe - хеш-калькулятор. Рассмотрим ее ключевой фрагмент:
BYTE GetHash(CString s0)
{
BYTE hash=0;
for (int a=0;as0.GetLength();a++) hash=hash+s0[a]; // Вычисляем хеш-сумму return hash;
Мы посимвольно складываем элементы множества символов s0, получая в результате некоторый элемент из множества calc {0,0xFF}.Как нетрудно видеть на каждый элемент множества calc отображается не более, чем один элемент S. Отсюда в заданных рамках функция calc=calc+s0[a] инъективна. Следовательно для заданного индекса единственным образом определяется элемент S. Этим доказывается корректность работы хеш-анализатора.
Ниже приведен фрагмент реально работающего эмулятора виртуального процессора GetMe01 (file://CD:\CrackMe\GetMe01.asm).
|
I |
| CALL | BX | ; Вызвать обработчик данной команды |
| RET | ; --\ | |
| err: | ; Исключительная ситуация. Неверная команда | |
| MOV | AH,9 | ; Печать строки MS-DOS |
| LEA | DX,errr | ; Смещение печатаемой строки |
| INT | 21h | 5 |
| MOV | AH,4Ch | ; Завершение работы |
| INT | 21h | ; --\ |
| errr DB ENDP | 'Неизвестная команда',0Dh,0Ah,'$' |
; // ТАБЛИЦА ПОДДЕРЖИВАЕМЫХ КОМАНД И СООТВЕТСТВУЮЩИМ ИМ
ОБРАБОТЧИКОВ
; //------------------------------------------------------------------------
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 практически всегда много меньше его мощности.
Например в множество слов русского языка представляется множеством последовательностей от одного до десяти и более символов,но общее число существующих слов заведомо меньше OxFFFFFFFF. Поэтому возможно существование 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) = у не разрешимо полиномиально. Это показывает, что 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, а ниже приводится только ключевой фрагмент.
Предложенный алгоритм является воплощением простоты и при этом шустро работает и достаточно гибок, что бы в последствии мог быть применен для произвольных перечисленных множеств.
