Как атаковать шифр

При атаке на шифр считается, что криптоалгоритм известен с точностью до реализации и требуется найти пароль. В качестве примера рассмотрим программу crackmeO.com (file://CD:SOURCEA5M_CCRACKmeOCrackMe0.com). Ал­горитм расшифровки ничем не защищен и его легко можно изучить. Однако это нам не дает никакой информации об исходном пароле

LODSB ; Читаем байт введенного пароля.

ADD АН, AL ; Суммируем

LOOP CalcCRC ; —{СХ}—

Эта процедура вычисляет CRC с введенного пароля. CRC очень простой и ( плохим рассеиванием. Множество паролей будет иметь одно и то же CRC поэтому нет никакой возможности предсказать на основе всего восьмибитного числа исходный пароль.

LEA SI, Crypt ; На начало зашифрованных данных:

Decrypt: ; <—

XOR [SI] ,АН ; Расшифровать байт

INC SI ; Следующий байт

СMР SI,offset Buffer; ?Мы уже все расшифровали

JB Decrypt ; —{SI<offset Buffer—

Шифротекст расшифровывается значением контрольной суммы от пароли Причем всего может существовать 0х100 (256) вариантов расшифровки! Нетрудно было бы перебрать их всех и найти исходный. Даже если бы использовалось слово (0х1000), то вариантов было бы все равно немного!

Между прочим, это довольно распространенный прием в некоммерчески программах. Удивительно, как это не учитывают авторы защит! Если перебирать не пароли, а ключи (т.е. сами хеш-значения), то можно достичь скорости порядка нескольких сотен тысяч ключей в секунду. Таким образом не спасет даже использование двойного слова (0х100000000). Оценим, какое наибольше время необходимо для перебора тридцатидвухбитного ключа. Исходя из средней скорости миллион ключей в секунду, мы найдем результат не более чем 4295 секунд т.е. приблизительно за 71 минуту. Практически за час с небольшим, не так ли? Все дело в высокой скорости перебора ключей, обусловлены простотой алгоритма.

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

DEC SI ; Следующий байт
ADD CL, [SI] ; Суммировать
СMР SI, offset Crypt ; Конец
JHB CmpCRC ; —{Sl>offset Crypt)-

CMP CL,0C3h ; ?3начение CRC верно

JZ Crypt ; CRC OK >
; CRC FAIL

Ясно, что проверяется контрольная сумма исходного текста. Мы можем исследовать хеш-алгоритм и хеш-сумму исходного текста. В нашем случае она равна 0х03.

Но, сколько существует неправильных вариантов расшифровки, для которых их контрольные суммы тем не менее совпадают? Очевидно, что больше одного! И с ростом числа вариантов расшифровки количество "ложных" ключей стреми­тельно растет! Так, уже при 32-битных ключах основную проблему будет пред­ставлять не поиск подходящих ключей, а выборка единственного верного исход­ного текста среди расшифрованных вариантов! При этом у нас нет никаких достаточно строгих критериев, позволяющих автоматически отличить ложные варианты. Разработчик защиты добился-таки своего! Вероятность, что пользова­тель введет неправильный, но подходящий пароль, достаточно мала, поэтому ей кржно пренебречь. Действительно, предположим, что хотя бы 1 % паролей будет давать ложные срабатывания, тогда для 0х10000 (65536) ключей это составит 655 вариантов, а для 0х100000000 уже 42.949.672! Заметим, что с точки зрения ' криптографии все эти варианты равноценны!

Разумеется, мы в любом случае имеем хотя бы косвенное представление об 1 исходном тексте. Но как его использовать? Можно по типу данных предугадать вероятность того или иного символа, проверить на совпадение со словарем, поискать некоторые закономерности... Но как же все это будет медленно рабо­тать! И в любом случае (особенно на коротких фрагментах) нет никакой гарантии, что даже самый надежный алгоритм всегда распознает исходный текст.

Разработчики защиты могут торжествовать! Они заставили хакера призаду­маться. Хакеры же пошли другим путем. Криптографам был давно известен метод атаки по открытому тексту. В самом деле, если злоумышленник обладает хотя бы частью открытого текста, то он может сделать обратную шифрованию операцию 1 найти ключ! Вспомним свойство операции хог:

Х хог Key = Y, Y хог Key = X, но Х хог Y = Key!

В нашем примере с восьмибитным ключом достаточно достоверно знать всего лишь один байт открытого текста, чтобы получить Key, который можно применить Ко всему шифротексту в целом. Но можем ли мы узнать какой-то байт чужого текста, и к тому же достоверно? Оказывается, можем, да еще как! Конечно, не достоверно, но с определенной степенью вероятности мы можемпредположить его наличие

Весьма вероятно, что в приведенном шифротексте встретится инструкция INT 0х21. Ее двухбайтовый опкод 0х21 CD (мы ведь помним про обратный порядок байт в слове!) превышает длину ключа, а значит, делает его на этом промежутке неслучайным. В самом деле, в уравнении Х xor Y = key мы не знаем ни X, ни key, при выбранном Y они могут быть любыми.

Если #Y > #Кеу, то мы получим XI xor YI == Х2 xor Y2== key!'

Может быть это объяснение покажется туманным, поэтому приведем практи­ческий пример, С помощью утилиты HIEW попробуем расшифровать секретный фрагмент, применяя операцию XOR 0х21 CD.

Обратим внимание на последовательность 0х2020. Весьма вероятно, что оригинальном тексте здесь находилось 0х21 CD, зашифрованное ключом 0х2< Следует учитывать, что данный метод допускает ложные срабатывания. Поэтом предпочтительнее использовать по возможности более длинные последовательности. В этом случае мы получили только один возможный ключ, а что мы стал бы делать, если бы их оказалось несколько? Если мы знаем частоту появлени выбранной последовательности (а именно такие и стоит выбирать), то мы моим определить истинный ключ простым сравнением! Однако допустим, что два иЛ более ключей имеют очень близкую к ожидаемой вероятность появления, и быть тогда? В этом случае необходимо поискать другую последовательною ожидаемую в шифротексте. В нашем примере это может быть OxAOD — лереШ строки. Весьма вероятно, что пример выводит какую-то строку, которая заверш ется возвратом каретки. Предоставляю читателю провести этот эксперимеи самостоятельно, а сам замечу, что на деле редкая программа обходится без выви текстовых сообщений. Но ведь в любом языке не так уж много слов, а тем боя распространенных! Это очень уязвимое место подобных систем. Не потребует даже утомительного перебора. Поищем такие строки, как (с), Copyright, О Cancel, Yes, No... Хорошо действует двойной пробел, пробел+запятая и т.д.

Кроме того, не забываем, что нам известен CRC исходного текста, '• следовательно, можно быстро определить, какой ключ из нескольких — п] вильный.

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

Таким образом, криптостойкость данного шифра при атаке по открыв» тексту (даже если неизвестно точное расположение последнего) равна нулю!.

В данном примере использовался ключ 0х20. Внешне этот ключ абсолютно ничем не примечателен, но взгляните на зашифрованный фрагмент:

И этозашифрованный текст? Как же такое могло произойти? Магическое свойство хог 0х20 — переводить английский текст в противоположный регистр — сыграло с автором защиты очень злую шутку. У каждого алгоритма есть некото­рое числослабых паролей, которые в разной степени снижают его криптостой-кость. Об этом мы говорили выше. А теперь, если вспомнить, что 0х20 — ЮООООЬ, нетрудно убедиться, что такой ключ меняет всего один бит на каждый байт! Т.е. шифротекст будет мало чем отличаться от исходного. Хорошие крипто­системы делают проверку на слабые ключи, плохие — нет. Учитывая, что число слабых ключей у иных шифров не так мало, как кажется на первый взгляд, с вероятностью использования такого ключа стоит считаться.

Выше мы отмечали, что использование 32-битного ключа дает 0х100000000 вариантов и потребует около 71 минуты перебора. А если длина ключа все 64 бита? 0х10000000000000000 вариантов потребует 28014 секунд или почти восемь часов перебора (и выдаст еще больше ложных срабатываний). Если бы мы могли достоверно знать хотя бы одну шестнадцатибайтовую последовательность, при­сутствующую в исходном тексте...

Крайне маловероятно, что мы располагаем такой информацией! Однако на самом деле положение вовсе не безнадежно, и у нас по-прежнему хорошие шансы найти даже такой длинный ключ. Сначала заметим, что минимально необходимый фрагмент открытого текста в действительности равен длине ключа плюс единица. Естественно, это увеличит число ложных срабатываний, но не так сильно, как кажется на первый взгляд. Представим для начала, что нам известен лишь фрагмент А. Какова вероятность того, что он совпадет с А'?

---------------------------------------------------

| | A | | | | | | | A’ |

|--------------L---------------------|

 

Давайте представим себе последовательность АА. Естественно, что она будет "вмещать" в себя #А'2 элементов. У скольких элементов левая "половина" равна правой? Обозначим левую часть как L, а правую как R. Легко видеть что для каждого L существует только один равный ему R. Число совпадающих вариантов равно множеству элементов А. Тогда вероятность совпадения произвольных А и А' равна #A/#A^2 == 1/#А, где # — число элементов множества.

Однако нас интересуют только те совпавшие числа, которые находятся строго на расстоянии L друг от друга, где L как видим, равна длине ключа. Задачу подсчета данной вероятности я оставляю любопытным читателям, отмечу только, что она на несколько порядков ниже общего числа ключей, которые нам пришлось бы перебирать в противном случае. Даже если #"А равна одному биту (!), у нас неплохие шансы. И гораздо более высокие, чем показал расчет любознательных читателей. Точнее говоря онимогут стать несравненно выше. Используемая нами математическая модель исходила из предпосылки равновероятности всех символов. Это очень упрощает расчеты, но не соответствует действительности. Как правило, нам известно хотя бы приблизительное распределение вероятности встречаемых символов. Это поможет отбросить часть вариантов как заведомо ложные или, (что более правильно) начать перебор с наиболее вероятных ключей, а затем переходить к менее вероятным.

Вышесказанное звучит захватывающе, однако так и не объясняет, где нам взять хотя бы 64+1 битовую последовательность для атаки по открытому тексту. Кажется, что ассемблерных команд такой длины и даже устойчивых их сочетаний не существует. Но может быть, мы плохо искали? Например, все языки высокого уровня используют стандартные библиотеки, сигнатуры которых известны, а число пренебрежительно мало (по сравнению с числом возможных ключей, разумеется). Это применимо далеко не к каждой программе, но к значительному их числу.

Допустим, автор защиты это учел и использовал неизвестный доселе комли лятор или полностью реализовал весь код на ассемблере и отважился выбрать н) очень длинный ключ — не будем даже уточнять, насколько длинный. Восторже ствует ли он на этот раз? Увы (или ура — в зависимости от ориентации читателя) Злоумышленник применит масочную атаку! Суть ее сводится к следующему пусть нам не известно сколь-нибудь длинной строки из зашифрованного текста но мы наверняка знаем много коротких! И с некоторой достоверностью расстояние L между ними.

Алгоритм атаки следующий: пусть s0 одна из существующих в шифротекст< последовательностей. Применим атаку по открытому тексту и в результат получимогромное множество подходящих, но ложных ключей. То, что ни оди1 из них не верен это ясно из того, что длина каждого равна #s0. По условию s( короче пароля; следовательно, ни один ключ не является законченным паролем Однако, ясно, что настоящий пароль включает в себя некоторые элемент полученного множества. Возьмем другую известную последовательность si i повторим аналогичную операцию. Теперь выберем общие для f(s0) и для f(sl элементы. Вероятнее всего, что именно из них и составлен пароль. С каждо итерацией число символов, общее для всех последовательностей стремительн уменьшается, а вместе с ним и число вероятных паролей. Когда все последов^ тельности исчерпаны, выберем только те, которые разнесены в границах предпс лагаемого расстояния (если такая информация имеется). Существует множеств вариантов получения пароля из заданного множества фрагментов, однако не нужды перебирать их все. Я доставлю читателю удовольствие самому решит несложную задачку уменьшения числа возможных вариантов. (Привычка пол) чать все в готовом виде очень вредна, а для хакера — в корне неприемлема! моем понимании хакер — это человек, который в любой ситуации привы рассчитывать только на себя. Готовые технологии и знания — непозволительная роскошь.)

Однако наводящую подсказку я все же дам. Пусть нам неизвестна вepoятнoc^ ни одного из встречаемых в шифротексте символов, но для каждой последовател ности Sn вероятность образующих ее элементов известна наверняка!

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

В заключении мы рассмотрим атаку по открытому тексту на зашифрованный архиватором arj-файл. Несмотря на высокую скорость перебора существующих взломщиков требуется немало времени на поиски паролей более чем из восьми символов. В то же время, если есть хотя бы один незашифрованный файл из архива, задача решается очень просто. Часто в архивы попадают общедоступные файлы (pgp — подписи, рекламные проспекты, стандартные файлы типа dos4gw или *.DLL). Содержимое некоторых файлов иногда можно попытаться угадать, В первую очередь это относится к bat-файлам. Самое главное то, что длина bat-файлов обычно очень мала, а содержимое состоит из ограниченного набора словарных последовательностей.

Но перейдем собственно к реализации атаки. Для нее нам потребуется знать используемый криптоалгоритм и формат файлов архиватора. Этот формат добро­совестно описывается в прилагаемой документации. А вот криптоалгоритм авто­ром arj не разглашается. Что само по себе уже подозрительно. Как учит рыночная политика — если производитель о чем-то пытается умолчать, то можно не сомневаться в качестве (точнее, его отсутствии). Не должна стойкость криптоси­стемы зависеть от знания ее алгоритма, никак не должна. Правило, сформулиро­ванное голландцем Кирхгоффом, гласит: стойкость шифра должна определяться только секретностью ключа. Роберт Янг к этому не прислушался и приложил гораздо больше усилий к сокрытию криптоалгоритма, чем к качеству реализации, В техническом описании он не раскрывает значение байта ОхВ заголовка, оставляя его "зарезервированным". Между тем он активно используется при шифровке паролем!

Есть два пути для отождествления криптоалгоритма: анализ большого числа открытых и зашифрованных текстов или дизассемблирование и анализ кода программы. Я всегда выбираю последний. Это не всегда самый быстрый, но гарантированный вариант. Дизассемблирование — довольно трудоемкая работа, которая может растянуться на долгие недели, если нет соответствующих навыков. Подробнее об этом я собираюсь рассказать в следующей моей книге "Образ мышления — IDA".

В рамках данной главы можно отметить, что не обязательно анализировать весь arj.exe, воспользуемся самораспаковывающимся архивом, который не в пример короче. Дизассемблирование последнего быстро покажет, что в arj используется система шифрования Вернама, которая сводится к следующему: для пароля SIS2S3 получим бесконечную последовательность sls2s3sls2s3sls2s3, и тогда NN-ый символ открытого текста преобразуется в шифротекст простым XOR [Sn], (Nnl + MAG_VALUE.

Что такое MAG_VALUE? А это и есть тот "зарезервированный" символ, назначение которого Роберт Янг не раскрыл в документации.

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

Любопытно, что пароли аЬс и abcabc абсолютно идентичны! (И, кстати, об этом умалчивается в документации)! Отсюда вытекает, что выбор "неудачного" пароля может позволить "прямую" атаку на шифр!

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

for (int a=0;a<MAX_AVIRLABLE_FASSWORD_SIZE;a++)

{

NormalByte = (unsigned char) pNormalBuffer[a];

ProtectByte = (unsigned char) pProtectBuffer[a];

ResByte= (unsigned char) (NormalByte ^ ProtectByte) - MagValue;

st=st+(char) KesByte;

}

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

Вместе с Янгом этот бой проиграли и все пользователи его криптосистемы. Зашифрованные данные оказались уязвимы без ведома их обладателей. Сколько архивов было (или могло быть) вскрыто за это время?

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