BugTraq.Ru
Русский BugTraq
http://www.bugtraq.ru/library/internals/pwl98.html

Восстановление паролей к PWL-файлам
PolASoft, http://www.insidepro.com/rus/
Опубликовано: dl, 01.08.03 12:10

Версия документа: 1.0
Скачать статью в виде ZIP-архива

Содержание

Введение

PWL-файлы (или так называемые парольные кэши Windows) - это файлы с именами пользователей компьютера и с расширениями *.PWL (к примеру, Master.PWL, Sales.PWL и пр.), которые находятся в директории Windows.

Это файлы, в которых хранятся различные аккаунты (т.е. сочетание логин/пароль) данного пользователя, т.е. пароли ко всем ресурсам, при первом подключении к которым в окне ввода пароля был включен флажок "Запомнить пароль". Таким образом, в нем хранятся пароли к "расшаренным" ресурсам сети, пароли на подключение к NetWare/NT-серверам, пароли на Dial-Up-соединения и пр.

Функция запоминания паролей в Windows реализована давно и была введена с "благой" целью - облегчение работы пользователей. И действительно - зачем вводить каждый раз при подключении к провайдеру пароль "q6Rf8UI24dq" :) , когда можно один раз ввести его с бумажки, а потом забыть про этот пароль вообще. Таким образом, Windows собирает все пароли пользователя, шифрует их с помощью логина (имени пользователя) и текущего пароля пользователя (т.е. того пароля, который вводится при загрузке Windows) и хранит в этом PWL-файле.

Естественно, все эти данные зашифрованы определенными алгоритмами, и для их дешифрования необходимо знать пароль пользователя - а это фактически пароль на вход в Windows. А так как людям свойственно забывать свои пароли, то подбор пароля, во-первых, позволяет его "вспомнить", а во-вторых, позволяет просмотреть список аккаунтов этого пользователя, которые Windows сохраняет в этом PWL-файле, например, там может быть и забытый пароль на подключение к провайдеру. ;)

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

И сразу оговорюсь, что речь пойдет только о PWL-файлах операционных систем Windows'OSR2/98/ME, т.к. в PWL-файлах ОС Windows'3.11/95 методы шифрования гораздо проще и подбор пароля любой сложности - дело одного часа работы любой программы по восстановлению к ним паролей, в том числе и PWLInside.

Вся информация в тексте о времени выполнения фрагментов кода в тактах дана для следующих типов процессоров:

  1. Intel Pentium MMX/II/III и все Celeron'ы из этих семейств.
  2. AMD K6-II/III, все Duron'ы и Athlon'ы.
Такая информация дается как усредненное время выполнения на всех этих типах процессоров.

Примеры кода, приведенные ниже, даны в синтаксисе Microsoft Visual С++ v6.0 и MASM v7.0.

Формат PWL-файлов Windows'OSR2/98/ME

Информация о формате PWL-файлов компанией Microsoft нигде и никогда не документировалась, и, хотя в Интернете можно найти много различных документов по форматам PWL-ок, вся эта информация взята из практического использования этих файлов и в основном написана авторами программ, аналогичных PWLInside.

Подробно рассмотрим в качестве примера следующий PWL-файл:

0000: E3 82 85 96 03 00 00 00 02 00 01 00 00 00 00 00
0010: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0030: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0040: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0050: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0060: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0070: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0090: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00A0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00B0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00C0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00D0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00E0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00F0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0100: 00 00 00 00 00 00 00 00 00 0D 03 FF FF FF FF FF
0110: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0120: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0130: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0140: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0150: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0160: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0170: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0180: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0190: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
01A0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
01B0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
01C0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
01D0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
01E0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
01F0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
0200: FF FF FF FF FF FF FF FF 52 02 00 00 00 00 00 00
0210: 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00
0220: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0230: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0240: 01 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00
0250: 00 00 88 51 47 58 2C 74 13 7C 6F D7 9E 9D 58 59
0260: 0B 3A A5 22 85 22 94 80 58 F9 61 00 B6 51 72 28
0270: D5 D7 3A 58 23 03 DD BC A7 4B E7 E2 71 65 66 CE
0280: 3F 58 FC 59 76 02 F0 12 8E 5F 79 94 39 E0 36 29
0290: 13 B9 8E 3B A1 F3 74 D4 78 38 01 E0 B5 FE DE A3
02A0: 80 CC 4E B7 67 1D 7C 36 7B C5 AA 76 4C D0 8E EE
02B0: 28 78 8A BB 7A 5A 81 2C AB 29 79 97 33 89 60 79
02C0: F7 6C 1C 72 1B 33 0A 09 F2 7E E4 3A A6 BE F4 C6
02D0: AE 06 DE 31 67 BB EA 7B D5 CA AE 01

Теперь внимательно посмотрим, из каких полей состоит файл:

  1. Сразу оговорю следующие ограничения PWL-файлов: в файле может находится максимум 16 блоков ресурсов. Максимальное количество ресурсов в файле - 255. Это ограничения самой Windows. В каждом блоке может располагаться любое количество ресурсов, но их суммарное количество не может быть больше 255. И еще одно ограничение PWL-файла - то, что он не может быть больше 64кБ.
  2. Итак, первое, что мы видим - это сигнатура (т.е. первые 4 байта файла), которая равна 0x968582E3, сразу же замечу, что у PWL-файлов от Windows'3.11/95 сигнатура другая - 0x4E464DB0.
  3. По смещению 0x4 следует DWORD с неизвестным содержимым.
  4. По смещению 0x8 следует WORD. Он определяет общее кол-во ресурсов в файле. В нашем примере - 2 ресурса.
  5. Начиная с адреса 0x00A до адреса 0x109 располагается странная таблица размером 255 байт. Какую она содержит информацию, известно лишь Microsoft. Есть предположение, что там хранятся номера ресурсов, хотя эта таблица для декодирования данных из файла в принципе не нужна.
  6. Начиная с адреса 0x109 до адреса 0x208 находится другая таблица (тоже размером 255 байт), в которой хранится такая информация: любой байт из этой таблицы равный i (кроме 0xFF) означает, что i-й блок содержит ресурсы. Количество одинаковых байт равных i в данной таблице отражает количество ресурсов в i-м блоке. В нашем примере - 1-й байт в таблице показывает, что у нас имеются ресурсы в 13-м (0x0D) блоке, а 2-й байт в таблице показывает, что у нас имеются ресурсы в 3-м блоке ресурсов.
  7. По адресу 0x208 находится DWORD (у нас он равен 0x00000252), который определяет смещение CryptoSign. Кстати, я в этом поле других значений не видел ни в одной PWL-ке!
  8. С адреса 0x20C по 0x24C располагается массив CryptoSeed[16], он необходим для декодирования всех 16 блоков ресурсов.
  9. По адресу 0x24C располагается CheckSeed (DWORD), с которого и начинается декодирование PWL-файла.
  10. Далее идут два нулевых байта. Какую они несут функцию - неизвестно.
  11. По адресу 0x252 располагается массив CryptoSign (16 байт).
  12. По адресу 0x262 располагается массив CheckSign (16 байт) - этот массив вместе с CryptoSign является "контрольным значением" для определения правильности пароля. Их применение рассмотрим ниже.
  13. По адресу 0x272 располагается массив из 15 WORD'ов - это адреса 15 блоков ресурсов, начиная со второго. Адрес же первого ресурса всегда один и тот же и составляет 0x290. Эти адреса уже являются зашифрованными. Посмотрим, что это будут за байты после декодирования правильным паролем:

    0270: .. .. 92 02 94 02 96 02 B2 02 B4 02 B6 02 B8 02
    0280: BA 02 BC 02 BE 02 C0 02 C2 02 C4 02 D8 02 DA 02
    

    Как мы видим - действительно там находятся адреса! Эти адреса никогда не могут быть одинаковыми и получается, что если блок ресурсов пустой, то он все равно занимает 2 байта  - это мы видим на начальных адресах: 0x292, 0x294 - эти значения ссылаются на "мусор", ресурсы же в этом файле находятся по адресам 0x296 ... 0x2B2 и 0x2C4 ... 0x2D8 - это видно по тому, что разница между этими соседними адресами больше двух байт и т.к. мы уже отмечали, у нас 3-й и 13-й блок имеют ресурсы (см. пункт 6).
  14. А с адреса 0x290 начинаются непосредственно ресурсы. Эти данные также зашифрованы. После дешифрования мы увидим, что с адресов 0x296 и 0x2C4 действительно есть что-то, похожее на ресурсы :)

    0290: 4C 9C 50 94 C9 82 1A 00 0A 00 08 00 01 03 43 52 |L.P...........CR
    02A0: 49 53 54 49 41 4E 5C 44 68 65 6C 6C 67 61 74 65 |ISTIAN\Dhellgate
    02B0: E3 A8 CF DD 80 8A 8D 9A 1B 97 6B B9 BD F0 AE 9A |....?.....k.....
    02C0: 5C D4 20 88 12 00 05 00 05 00 00 04 4D 41 50 49 |\. .........MAPI
    02D0: 00 4D 41 50 49 00 28 F3 1D B2 90 80             |.MAPI.(....?
    
Как правильно декодировать ресурсы и их формат будет показано ниже.

Описание алгоритмов, используемых для шифрования PWL-файлов

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

RC4

Краткое описание: на входе имеем ключ размером 16 байт, на выходе получаем массив из 256 байт, в котором равномерно и псевдослучайно распределены байты от 0 до 255, причем их распределение зависит от входного ключа:

byte t; //Временная ячейка
byte A = 0; //Здесь будем получать новый псевдослучайный индекс
byte M[256]; //Наш формируемый массив
byte Key[16]; //Исходный ключ, с помощью него будем формировать массив M

for (int i = 0; i < 256; i++)
   M[i] = i; //Последовательно заполняем массив значениями от 0 до 255


for (int i = 0; i < 256; i++)
{

   A += (M[i] + Key[i % 16]); //Вычисляем новый индекс для обмена байтами
   t = M[i]; 
   M[i] = M[A]; //Меняем местами i-й байт и байт по вычисленному индексу A
   M[A] = t; 
}

Далее по этому алгоритму байтами из массива M с помощью завершающей процедуры RC4 с применением операции XOR расшифровываются любые необходимые данные.

MD5

MD5 - это ни что иное, как операция свертки 64 байт в 16.
Посмотрим как эта функция описана в официальном документе - RFC1321 с небольшими упрощениями и нашими комментариями:

...
#define S11 7
#define S12 12
#define S13 17
#define S14 22
#define S21 5
#define S22 9
#define S23 14
#define S24 20
#define S31 4
#define S32 11
#define S33 16
#define S34 23
#define S41 6
#define S42 10
#define S43 15
#define S44 21

/* F, G, H and I are basic MD5 functions */
/* Основные макросы преобразования */

#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))

/* ROTATE_LEFT rotates x left n bits */
/* Этот макрос - это всего лишь элементарная команда циклического сдвига ROL
на Асме! Оригинальный вариант ротации на С работает быстрее на процессорах с
архитектурой RISC. Для x86 процессоров лучше использовать команду ROL */


#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
Rotation is separate from addition to prevent recomputation */
/* Основные макросы трансформации значений a, b, c и d */

#define FF(a, b, c, d, x, s, ac) { \
(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}

#define GG(a, b, c, d, x, s, ac) { \
(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}

#define HH(a, b, c, d, x, s, ac) { \
(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}

#define II(a, b, c, d, x, s, ac) { \
(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}

/* MD5 basic transformation. Transforms state based on block */
/* Непосредственно сам алгоритм MD5 */

static void MD5Transform (state, block)
{

UINT4 a,b,c,d,state[4], x[16];

a = state[0] = 0x67452301;
b = state[1] = 0xefcdab89;
c = state[2] = 0x98badcfe;
d = state[3] = 0x10325476;

/* Round 1 */
FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */

/* Round 2 */
GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */

/* Round 3 */
HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */

/* Round 4 */
II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */

state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
}

В итоге получаем из входного массива x (16 DWORD'ов) массив state (всего 4 DWORD'a).

Завершающая процедура XorT алгоритма RC4

Эта часть RC4 (не описанная выше), которая декодирует необходимые данные с помощью массива M:

...
//Массив M перерабатывается с помощью RC4
...
byte t; //Временная ячейка
byte A = 0; //Здесь будем получать новый псевдослучайный индекс

for (byte i = 1; i < 33; i++)
{
    A += M[i]; //Вычисляем новый индекс для обмена байтами
    t = M[i]; 
    M[i] = M[A]; //Меняем местами i-й байт и байт по вычисленному индексу A
    M[A] = t;
    //
    t = M[i] + M[A]; //Вычисляем еще один индекс
    Data[i - 1] ^= M[t]; //Декодируем 32 байта массива Data
}

Стандартный алгоритм восстановления паролей к PWL-файлам

  1. Считываем из исходного PWL-файла по смещению 0x24C - CheckSeed (DWORD).
  2. -//- по смещению 0x252 - CryptoSign (16 байт).
  3. -//- по смещению 0x262 - CheckSign (16 байт).
  4. Формируем массив X (размером 64 байта) следующим образом:
  5. Выполняем MD5 (массив X), получаем массив Cnt (16 байт), т.е. производим свертку логина.
  6. Формируем массив Y (размером 64 байта) следующим образом:
  7. Формируем массив Z (размером 64 байта) следующим образом:
  8. Выполняем MD5 (массив Z), получаем массив Key (16 байт), т.е. производим свертку пароля.
  9. Выполняем RC4, используя в качестве ключа Key.
  10. Копируем во временный буфер Temp (32 байта):
  11. Выполняем процедуру XorT (массив M, массив Temp), получаем модифицированный массив Temp.
  12. Копируем первые 16 байт из массива Temp в буфер Y с адреса (длина логина + 1)
  13. Выполняем MD5 (массив Y), получаем массив TempKey (16 байт).
  14. Сравниваем 16 байт массива TempKey и вторые 16 байт из массива Temp и если они не равны, то инкремент пароля и возврат на пункт 7, иначе - пароль верный!

Алгоритм декодирования ресурсов из PWL-файла с правильным паролем

  1. После нахождения правильного пароля прогоняем функцию XorT с индексами не 1...33, а 33...63. Таким образом мы декодируем 15 адресов блоков с ресурсами. Должны получиться значения типа 0x292, 0x294 и т.д. Как мы помним, адрес 1-го блока всегда равен 0x290. Таким образом, у нас будет массив Res[17] типа WORD, в первое значение - 0x290, далее 15 декодированных адресов, а последний WORD - это размер файла (в примере выше это будет значение 0x2DC).
  2. Далее следует цикл на 16 (проверка блоков с ресурсами), в начале его вычисляем разницу между соседними адресами N - если разница между ними равна 2, то переход на следующий адрес.
  3. Если N > 2, то данный i-й блок содержит ресурсы.
  4. Формируем новый массив X (размером 64 байта) следующим образом:
  5. Выполняем MD5 (массив X), получаем массив Cnt (16 байт), т.е. производим свертку логина с нужным CryptoSeed.
  6. Формируем массив Z (размером 64 байта) следующим образом:
  7. Выполняем MD5 (массив Z), получаем массив Key (16 байт), т.е. производим свертку пароля.
  8. Выполняем RC4, используя в качестве ключа Key.
  9. И теперь полученным массивом M начинаем декодировать весь блок с ресурсами длиной N процедурой, аналогичной XorT. Причем начинаем использовать массив M также с 1-го значения (не с нулевого(!)) до 255, если ресурс больше 255 символов, то i "переваливает" байтовую границу и уже массив M начинает использоваться с нуля, а не с единицы.
  10. Посмотрим на приведенном выше примере структуру первого из наших декодированных ресурсов:

    0290: .. .. .. .. .. .. 1A 00 0A 00 08 00 01 03 43 52 |..............CR
    02A0: 49 53 54 49 41 4E 5C 44 68 65 6C 6C 67 61 74 65 |ISTIAN\Dhellgate
    

    Ее формат такой:
    • длина ресурса (WORD), в нашем примере - 26(0x1A) байт.
    • длина логина (WORD), в нашем примере - 10 символов.
    • длина пароля (WORD), в нашем примере - 8 символов.
    • BYTE, назначение которого пока точно не известно.
    • тип хранимого ресурса (BYTE):
    • 1 = NT Domain
    • 2 = NT Server
    • 3 = Shared
    • 4 = MAPI
    • 6 = Dial-Up
    • 18 = NetWare
    • 19 = WWW
    Далее располагаются логин, а после него - пароль.
    В нашем примере - тип ресурса "Shared", логин "CRISTIAN\D", пароль "hellgate".
    (Примечание: для Shared-ресурсов запись CRISTIAN\D будет означать следующее: CRISTIAN - имя компьютера, а D - ресурс, предоставленный для общего пользования.)
  11. Далее анализируем текущий блок с ресурсами, пока не перевалили за N, "поглядывая" в таблицу по адресу 0x109, т.к. в PWL-файлах между блоками ресурсов очень часто бывает "мусор" (неисповедимы пути Microsoft), а в этой таблице будет точное указание - в каком блоке сколько ресурсов.

Оптимизация алгоритмов восстановления паролей

Вот и начинается самое интересное. ;)
Посмотрим, что же мы можем сделать для повышения быстродействия вышеприведенных алгоритмов.

RC4 (1-я часть)

1. Сразу же бросается в глаза инициализация массива значениями от 0 до 255, которое происходит при каждом новом значении ключа (т.е. фактически при каждом новом пароле). Как же можно сделать ее более эффективной?

Выход есть - инициализировать массив не побайтно (256 команд), а, например, используя 32-битные регистры процессора, по 4 байта за 64 команды - и действительно, выигрыш по времени будет в 4 раза (конечно же, если массив M выровнен минимум по границе DWORD'a). А есть ли еще более "широкие" регистры, чтобы за одну команду "махом" записывать бОльшее кол-во байт? Регистры FPU отпадают, т.к. операции с ними выполняются очень долго, остаются, конечно же, MMX-регистры:

.DATA
qwInit DQ 0706050403020100h
qwAdd DQ 0808080808080808h
...
.CODE
mov edi,offset M+128
movq mm0,qword ptr [qwInit]
movq mm1,qword ptr [qwAdd]
movq [qword ptr edi-128],mm0

paddb mm0,mm1
movq [qword ptr edi-120],mm0
paddb mm0,mm1
movq [qword ptr edi-112],mm0
...
paddb mm0,mm1
movq [qword ptr edi+112],mm0
paddb mm0,mm1
movq [qword ptr edi+120],mm0

Чтобы не писать 31 одинаковый фрагмент кода, гораздо проще использовать зарезервированный макрос Ассемблера IRP, тогда последние строки кода можно заменить на следующую конструкцию:

IRP i,<-15,-14, ... ,14,15>
   paddb mm0,mm1
   movq [qword ptr edi+(i*8)],mm0
ENDM

Итого получаем - на инициализацию массива из 256 байт затрачиваем 66 команд процессора, которые выполняются за ~35-40 тактов, т.к. команды PADDB и MOVQ выполняются синхронно.
Нетрудно догадаться, ЧТО наворотил бы на месте этого цикла любой компилятор С, если этот код писать не на Асме. ;)

У читателя, наверное, возник вопрос - почему мы инициализируем EDI не на начало массива M, а на его середину?
Просто дело в том, что при таком варианте программы дополнительное смещение к EDI будет приводить к увеличению длины команды MOVQ всего на один байт (знаковый диапазон -128...+127) и команда получает длину в 4 байта. А если, к примеру, прибавить к EDI +256, то смещение будет расширено до DWORD'a и длина команды увеличится до 7 байт. Использование же более коротких команд является предпочтительным, т.к. идет более "плотное" заполнение буфера предвыборки команд и более оптимальное их декодирование процессорами.

И еще - вдумчивый читатель скажет, что есть ведь еще более "широкие" XMM-регистры - те, которые используются в наборах команд SSE (которые, кстати, поддерживают и Athlon'ы) и SSE2 от Intel. Используя их, можно оперировать с памятью блоками по 16 байт за такт!

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

RC4 (2-я часть)

Теперь рассмотрим "перетасовку" байт в массиве M, используя входной ключ.
Здесь получается такая картина - на обработку одного байта массива M необходимо минимум 7 команд, покажем это на примере одной итерации:

xor eax,eax ;в AL будем хранить индекс A
mov ebp,offset Key
mov edi,offset M
...
add al,byte ptr[ebp+i] ;A += Key[i % 16]
mov dl,byte ptr [edi+i] ;Считываем M[i]
add al,dl ;A += M[i]
movzx esi,al
mov bl,byte ptr [edi+esi] ;Считываем M[A]
mov byte ptr [edi+esi],dl
mov byte ptr [edi+i],bl
...

Причем такая конструкция имеет ряд особенностей:

  1. Использование команды MOVZX ESI,AL устраняет следующий конфликт на процессорах Intel: обращение к 32-битному регистру сразу после модификации его младшей (16- или 8-битной) части. В этом случае ко времени выполнения команды добавляется несколько тактов штрафа. Кстати, на процессорах от AMD таких штрафов нет. :)
  2. Конфликты по чтению/записи в одну кэш-линейку процессора.
    Известно, что при обращении к ячейке памяти процессор считывает из памяти (или кэша 2-го уровня) не одну эту ячейку, а целую строку (например, 32 байта), которую и размещает в кэше 1-го уровня. При этом ВСЯ эта строка помечается как доступная либо только для чтения, либо для записи. Поэтому, если прочитать байт по адресу X, а потом записать байт по адресу (X + 1), то несмотря на то, что байт по адресу (X + 1) уже в кэше(!), процессор после выполнения первой команды должен сначала "освободить" всю строку, а лишь потом снова ее загрузить, но уже для записи в нее, что, естественно, приводит к штрафам. Но, т.к. алгоритм формирует равномерное распределение байт, то такие конфликты возникают нечасто.
  3. Возможно, есть еще ряд конфликтов именно по работе с памятью, т.к. такие алгоритмы - это для процессоров не самый "удобный" код :)
В итоге такая конструкция выполняется в среднем за 5 тактов, т.к. все эти команды простые и на процессорах P-II/III от Intel могут декодироваться всеми 3-мя декодерами. Таким образом, декодирование может происходить по 3 команды за такт, что частично компенсирует вышеописанные штрафы.
А на процессорах от AMD цифра в 5 тактов получается из-за того, что некоторые из этих команд не зависят друг от друга и после декодирования следующая команда начинает выполняться, когда предыдущая еще заканчивает свое исполнение в конвейере.

Итого на весь алгоритм RC4 уходит: 5 x 256 = примерно 1280-1300 тактов.
Конечно же, подразумевается, что никаких циклов нет и код весь "развернут".

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

И действительно - рассмотрим ту часть кода, где вычисляемый индекс A суммируется с байтом из массива Key.

Индекс - это же один байт(!), который суммируется с текущим байтом M[i].
А затем суммируется с байтом из массива Key.

А если сразу суммировать два байта (одной командой) для 2-х разных ключей и, соответственно, 2-х разных паролей не в 8-битном регистре, а в 16-битном? Сказано - сделано.

В результате скорость упала.
Да-а-а, значит прирост от этого не перекрыл увеличение "накладных расходов" из-за того, что теперь в программе формируется два массива Z, два массива M и пр. Плюс штрафы от использования 16-битных команд в 32-битном коде.

Ну что ж, а если одновременно 4 байта для 4-х паролей? ;)
Та-а-ак, здесь уже относительно начального (однопарольного) варианта есть прирост производительности на 3-5%.

А если еще "шире"? :)
"Конечно же, MMX!" - скажете Вы и будете правы! :))

И вот мы приходим к тому варианту, который и был реализован в PWLInside и дал прирост скорости относительно начального варианта на 20-25%. Все просто:
  1. Формируем 8 массивов M, которые располагаются в памяти таким образом:
    - 0-й байт 1-го массива
    - 0-й байт 2-го массива
    ...
    - 0-й байт 8-го массива
    - 1-й байт 1-го массива
    - 1-й байт 2-го массива
    ...
    - 1-й байт 8-го массива
    и так далее.
  2. Формируем 8 паролей, идущих "подряд" при переборе выбранным алфавитом.
  3. На основе этих восьми паролей через вызов MD5 формируем 8 массивов Key в таком же порядке:
    - 0-й байт массива Key от 1-го пароля
    - 0-й байт массива Key от 2-го пароля
    ...
    - 0-й байт массива Key от 8-го пароля
    - 1-й байт массива Key от 1-го пароля
    - 1-й байт массива Key от 2-го пароля
    ...
    - 1-й байт массива Key от 8-го пароля
    и так далее.
  4. И вот что получаем - теперь все 8 индексов для разных паролей хранятся в одном(!) MMX-регистре, в разных его 8-битных частях.
    Помните строчку:

    A += (M[i] + Key[i % 16]);
    

    Теперь этот фрагмент кода для 8-ми паролей (и ключей, соответственно) выполняется двумя MMX-командами:

    
    mov edi,offset M
    mov ebp,offset Key
    ...
    pxor mm0,mm0 ;Начальные значения обнуляем
    ...
    ;Вот этот фрагмент:
    paddb mm0,qword ptr [edi] ;Все восемь A += M[i] 
    paddb mm0,qword ptr [ebp] ;Все восемь A += Key[i % 16]
    

    Вот в чем неоспоримое достоинство MMX-регистров - возможность оперировать с 8-, 16- или 32-битными частями всего регистра независимо друг от друга!
  5. После этого выделяем байты из MM0 любым способом, формируем адреса, меняем байты в массивах M и далее все то же самое, что выше.
  6. И, конечно же, инициализация массивов M будет такая же, что приведена выше - по 40 тактов на один пароль. Но 8 раз.
Такой прием привел к тому, что на проход алгоритма RC4 на один ключ/пароль уходит ~980...1000 тактов, что означает в среднем менее 4-х тактов на обработку одного байта в массиве M!

А если использовать XMM-регистры, то можно анализировать 16 паролей одновременно и это даст еще прирост скорости, но только на тех процессорах, которые поддерживают набор команд SSE. Попробуйте, может следующий "прорыв" в области восстановления паролей к PWL-файлам сделаете именно Вы! ;)

MD5

Первый момент в оптимизации этого алгоритма - это замена следующих макросов с 4-мя логическими операциями:

#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))

На макросы с 3-мя логическими операциями:

#define F(x, y, z) ((((y) ^ (z)) & (x)) ^ (z))
#define G(x, y, z) ((((x) ^ (y)) & (z)) ^ (y))

Конечно же, это даст небольшой, но все-таки прирост в скорости.

Второй же момент заключается в следующем: присмотримся внимательно к пункту 7 стандартного алгоритма и увидим, что если мы ограничим пароль для перебора 16-тью символами (т.к. на бОльшую глубину перебор уже бесполезен), то при формировании буфера Z у нас остаются несколько DWORD'ов, которые заполнены нулями. Посмотрим, какие именно:

16 символов пароля + 1 байт нуля + Cnt (16 байт) + 1 байт (0x80) = итого 34 байта или 9 DWORD'ов.

Далее у нас идут нули, до конца же массива занят еще только один DWORD - x[14].

И фактически пустые DWORD'ы - это x[9], x[10], x[11], x[12], x[13] и x[15].

Поэтому, во всех 64 итерациях (4 блока по 16 строк) алгоритма MD5, везде, где к результату прибавляется какой-то из этих DWORD'ов, то его можно не прибавлять вообще - там же нуль!

Этот нехитрый маневр увеличивает скорость данной конкретной реализации MD5 еще на 8-10%.

Кстати, эту идею можно развить и дальше:

Что еще немного, конечно, но все-таки увеличит скорость перебора.

Итого - после всех этих манипуляций время выполнения алгоритма MD5 стало занимать ~280-320 тактов, т.е. в среднем около 5 тактов на каждую из 64 итераций. Неплохо. :)

Но, уже создавая эту статью, у меня появились определенные мысли, как можно еще оптимизировать этот код. ;) Вполне возможно, что в следующей версии PWLInside будет еще что-то новенькое в плане оптимизации MD5!

Я также надеюсь, что вышеприведенная информация по оптимизации RC4 и MD5, возможно, поможет кому-нибудь, кто использует эти алгоритмы в своих разработках и позволит с минимальными "затратами" сделать эти программы еще более быстрыми :)

Стандартный алгоритм восстановления паролей к PWL-файлам

Внимание! А на "десерт" - самое вкусненькое ;) - то, что позволило в свое время программе PWLInside существенно увеличить скорость перебора и по этому параметру здорово "оторваться" от своих конкурентов.

Оказывается, для быстрой оценки - тот пароль или нет, можно пункты 10...14 не выполнять, а значит и не вызывать второй раз MD5, который (как уже было сказано) выполняется около 300 тактов, что дает прирост скорости еще на 20-25%!

Дело вот в чем.

Если внимательно присмотреться к процедуре декодирования ресурсов, то мы увидим, что с помощью массива M после пункта 9 стандартного алгоритма при проходе с правильным паролем мы декодируем:

Поэтому можно не выполнять операции над CryptoSign и CheckSign (для проверки правильности пароля), а просто проверить после XOR'a адрес первого блока ресурсов, который находится по адресу 0x272.

Если он лежит в диапазоне 0x292...(длина PWL-файла), то есть вероятность, что этот пароль верный! Для окончательной же проверки правильности пароля нужно выполнить пункты 10...14, т.к. только в этом случае (когда совпадут все 16 байт массива Temp), можно быть уверенным, что это именно верный пароль.

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

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

Поэтому код предварительной оценки пароля в упрощенном виде будет выглядеть так:

...
//Массив M перерабатывается с помощью RC4
...
byte t; //Временная ячейка
byte A = 0; //Здесь будем получать новый псевдослучайный индекс
WORD Offset = (WORD *)&lpFile[0x272]; //Зашифров. адрес 1-го блока ресурсов
WORD Len = XXX; //Длина исходного PWL-файла
//
for (int i = 1; i < 35; i++)
{
   A += M[i]; //Вычисляем новый индекс для обмена байтами
   t = M[i]; 
   M[i] = M[A]; //Меняем местами i-й байт и байт по вычисленному индексу A
   M[A] = t;
   //
   t = M[i] + M[A]; //Вычисляем еще один индекс
   if (i == 33)
      ((byte *)&Offset)[0] ^= M[t]; //Декодируем 1-й байт адреса
   if (i == 34)
       ((byte *)&Offset)[1] ^= M[t]; //Декодируем 2-й байт адреса
}

//

if ((Offset > 0x291) && (Offset < Len))
{
   //Есть вероятность, что пароль верный,
   //делаем полную перепроверку по пунктам 10...14
}
else
{
   //Однозначно пароль неверный, переходим на новый пароль
}

Как видим, переработка массива M все равно остается, но(!) - первые 32 итерации мы НИЧЕГО не XOR'им, а декодируем ТОЛЬКО на 33 и 34 итерациях адрес блока ресурсов.

Таким образом, зачем нам делать пункты 10...14 и проверять 16 байт, когда можно выполнить "упрощенный" вариант процедуры XorT и проверить всего 2 байта! ;)

При всем моем уважении к Microsoft, однако, это еще одна их "дыра" в реализации качественных методов хранения паролей пользователей!

Итак, что мы получили в среднем: В итоге мы получаем суммарное время обработки одного пароля около 1500 тактов на всех типах процессоров, что приведены в начале статьи, кроме процессора Pentium 4. :(

Дело в том, что микроархитектура P4 по сравнению с P-II/III была существенно переработана - увеличено время выполнения команды (до 20 стадий), изменились размеры строк кэша данных и кода и еще ряд "усовершенствований", поэтому этот код (в особенности, реализация алгоритма RC4) для P4 не является оптимальным и в следующей версии PWLInside будет модифицирован. При этом на процессорах AMD, даже последних, таких проблем не возникает - на Athlon'e XP 1700+ (1466МГц) с ядром ThoroughBred программа исправно выдает около миллиона паролей в секунду. Вот так AMD делает аналоги процессоров Intel в чем-то лучше, чем сама Intel. :)

Заключение

Вот и подошло к концу наше описание. Надеюсь, теперь по работе с PWL-файлами от Windows'OSR2/98/ME ни у кого не осталось "темных пятен". Видно, что данные алгоритмы можно было бы прооптимизировать еще больше с применением команд современных процессоров, но - операционные системы этих поколений уже уходят "в прошлое" - процент этих ОС и так уже невысокий, со временем снижается все больше и больше, и восстановление паролей к PWL-файлам уже не столь актуально, как несколько лет назад.

Хотя, возможно, стоит еще поработать в этой области. ;)

Сейчас основной процент ОС семейства Windows - это Windows'2000, Windows'XP, а теперь уже и Windows'2003. Так как у всех этих систем ядро другое (на базе NT), то и методы хранения, шифрования, а также восстановления ;) паролей пользователей тоже другие.

В них информация о паролях пользователей хранится в SAM-файлах, которые представляют собой ветку "HKEY_LOCAL_MACHINE\SAM" реестра Windows, и пароли зашифрованы другими алгоритмами, нежели в PWL-файлах.

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

В операционных системах Windows'NT, начиная с 6-го сервис-пака, Windows'2000, Windows'XP (а по всей видимости и в Windows'2003) применяется дополнительное шифрование хешэй пользователей (которые и так получены путем шифрования паролей определенными алгоритмами) с использованием утилиты Syskey.

Данный механизм успешно просуществовал несколько лет. Его многократно пытались взломать, но все попытки были безуспешны, пока этой проблемой не заинтересовались мы с Ocean'ом. ;)

И механизм был "взломан"! Это наглядно демонстрирует программа SAMInside.

Но про SAM-файлы и методы восстановления к ним паролей расскажу как-нибудь в другой раз. :)

Особую благодарность выражаю Ocean'у, т.к. только наша с ним совместная деятельность в этой области привела к появлению на свет таких программ как PWLInside, SAMInside и ряда других.

Удачи всем!

Copyright (c) 2003 PolASoft
www.InsidePro.com

обсудить  |  все отзывы (0)

[21923; 12; 7.75]




  Copyright © 2001-2024 Dmitry Leonov Design: Vadim Derkach