22.3. Идентификация криптографических примитивов

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

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

22.3.1. Идентификация функций по шаблонам

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

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

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

В дизассемблере IDA и сопутствующем ему инструментарии разработчика (Software Development Kit, SDK) реализованы средства, значительно облегчающие идентификацию функций. Для построения и удобного хранения шаблонов библиотек используется набор утилит FLAIR (Fast Library Acquisition for Identification and Recognition, быстрая обработка библиотек для идентификации и распознавания). Для распознавания функций применяется технология быстрой идентификации FLIRT (Fast library Identification and Recognition Technology).

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

Предположительно, FLAIR и FLIRT основаны на работах Кристины Цифу-ентес (Cristina Cifuentes) и Майкла Ван Еммерика (Michael Van Emmerik).

22.3.2. Константы в алгоритмах

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

Так, например, при инициализации многих хэш-функций (таких как MD4, MD5, SHA-1, RIPEMD-160) используются константы 0x67452301, 0xEFCDAB89, 0x98BADCFE и 0x10325476. В SHA-1 и RIPEMD-I60 используется также значение 0xC3D2ElF0.

В функции трансформации, используемой при вычислении SHA-1, применяются константы 0х5А827999, Qx6ED9EBAl, 0x8FlBBCDC и 0хСА62СЮ6. Эти константы являются представлением целой части чисел 230xSqrt(2), 230xSqrt(3), 230xSqrt(5) и 230xSqrt(10), где Sqrt(jt) — функция извлечения квадратного корня из х.

В функции трансформации RIPEMD-160 последняя константа вместо 0xCA62ClD6 имеет значение QxA953FD4E, что соответствует 230xSqrt(7).

Функция трансформации MD5 использует 64 константы, вычисляемые как 232xAbs(Sin(/)), где i— номер раунда, от 1 до 64. Sin(jt) вычисляет синус аргумента, заданного в радианах, a Abs(x) возвращает абсолютное значение х (без знака). Так, например, константы для первых четырех раундов равны 0xD76AA478, QxE8C7B756, Qx242070DB и OxClBDCEEE соответственно.

При вычислении хэш-функции MD2 используется таблица перестановок (S-Box) размером 256 байт, начинающаяся с последовательности 0x29, 0х2Е, 0x43, QxC9, 0xA2, 0xD8, Qx7C, 0x01.

При шифровании по алгоритму RC5 используются две константы Р и Q, значения которых основаны на двоичном представлении чисел е и тт. Для версии RC5, работающей с 64-битовыми словами, эти константы имеют значения 0xB7E151628AED2A6B и 0x9E3779B97F4A7Cl5.

В спецификации некоторых алгоритмов, например RC4, нет вообще ни одной константы, позволяющей выполнять поиск (числа 256 и QxFF, используемые при загрузке ключа и при шифровании, применяются настолько часто, что будут найдены и в сотнях посторонних функций). Однако если в программе используется оптимизированная версия RC4, подходящая константа может быть найдена. Дело в том, что процедура загрузки ключа начинается с того, что 256-байтовый массив заполняется последовательно числами от 0 до 255. Существует весьма эффективный способ выполнения данного цикла:

Как видно, использование оптимизации привело к появлению сразу двух констант, позволяющих выполнить идентификацию: 0x03020100 и 0x04040404.

Когда известно, какие константы присутствуют в том или ином алгоритме, остается найти эти константы в теле исследуемой программы. Поиск можно выполнять вручную или воспользоваться готовым инструментом, таким как СС (Crypto Checker), созданный человеком с псевдонимом Aleph, или KANAL (Krypto ANALyzer), разработанный группой uNPACKiNG gODS.

Crypto Checker 1.1 beta 7 умеет распознавать алгоритмы Blowfish, CAST-128, CAST-256, HAVAL, MARS, MD4, MD5, RC5, RC6, Rijndael, RIPEMD-128, RIPEMD-160, SHA-1, SHA-256, Tiger, Twofish, WAKE, а также некоторые генераторы псевдослучайных чисел, функции вычисления CRC16 и CRC32 и более 3000 простых чисел.

22.3.3. Принцип локальности

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

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

Вторая эвристика использует тот факт, что очень часто отдельные стадии алгоритма выполняются непосредственно друг за другом. То есть, например, при вычислении значения хэша используются три функции. Первая функция (init) устанавливает начальное значение контекста. Вторая функция (update) обрабатывает очередную порцию данных, от которых вычисляется значение хэша и обновляется состояние контекста. Третья функция (Final) завершает процедуру вычисления и возвращает итоговое значение. И в реальной программе вызов функции mit обычно находится в непосредственной близости от первого вызова функции update, а последний вызов update — прямо перед вызовом Final. Следовательно, найдя любую из этих функций, очень просто найти все остальные. На рис. 22.1 приведен пример процедуры, вычисляющей хэш-значение по алгоритму MD5. Функции MD5_Init и MD5_Update легко опознать по константам, a MD5_Final можно найти исходя из того, что она вызывается сразу после MD5_update.

Третья эвристика очень помогает, если криптографический примитив реализован как класс в объектно-ориентированном языке. При компиляции класса создается таблица виртуальных функций (Virtual Function Table, VTable), содержащая адреса всех функций, являющихся методами данного класса. Следовательно, определив расположение одного из методов, можно найти ссылку на него из таблицы виртуальных функций, а значит, отыскать и все остальные методы класса. На рис. 22.2 проиллюстрированы структуры данных класса, предназначенного для вычисления значения хэш-функции. Конкретный экземпляр класса вычисляет хэш-функцию MD5.

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