Циклический инкремент паролей

В данной статье мы рассмотрим один аспект перебора паролей, на котором обычно не заостряют внимание при написании программ-брутфорсеров (программ для подбора паролей), а именно - непосредственно сам инкремент пароля, т.е. формирование следующего пароля для его анализа.
Конечно, если проверка пароля (т.е. "тело" программы перебора) выполняется тысячи, десятки тысяч или же миллионы тактов процессора, то можно использовать любой способ инкремента пароля - заметного изменения скорости не будет. Но когда на проверку пароля уходит всего 150...300 тактов процессора и нам нужно быстро сформировать новый пароль, то, конечно же, вопрос оптимального инкремента пароля становится очень и очень актуальным.

Сразу оговорюсь, что рассматриваться будет именно вариант полного перебора всех паролей, без семантического анализа рядом стоящих букв, не используя перебор по маске, гибридный перебор и т.д. Т.е., мы собираемся последовательно перебирать комбинации "A", "B", ... "Z", затем - "AA" и т.д.

И еще одно условие - изменяемым символом в наших комбинациях будет первый символ пароля, а не последний, т.е. комбинации будут вида: 
AAA 
BAA 
CAA 
... 
а не 
AAA 
AAB 
AAC 
... 

Это существенно упрощает код инкремента пароля, да и, в принципе, нет особой разницы в том - слева или справа менять символы. Нам ведь главное - сделать это максимально быстро, не так ли? А, желательно, еще и компактно. 🙂

Способов инкремента пароля существует немало. Самым распространенным является "индексный" метод инкремента, когда пароль представлен в виде индексов используемых символов. Т.е. при алфавите "ABCDEFGHIJKLMNOPQRSTUVWXYZ" пароль ADMIN будет представлять собой массив значений {1, 4, 13, 9, 14, 0}, где ноль - конец пароля. Или же массив вида {0, 3, 12, 8, 13}, если для хранения длины пароля используется дополнительная переменная.

Данный метод, конечно же, является неплохим, но автор предлагает рассмотреть другой метод, называемый "циклическим" (и ниже мы рассмотрим, почему он так назван).

Этот метод, помимо того, что является крайне быстрым, является еще и очень компактным инкрементом, что с успехом позволяет использовать его как в крупных проектах, так и миниатюрных программках, где необходим перебор паролей. Также в этом варианте "накладные расходы" на изменение длины пароля и изменение
не крайнего символа также минимальны. Данный метод с успехом применяется во всех программах перебора паролей на сайте
www.InsidePro.com.

Примеры кода будут даны в синтаксисе языка Ассемблер, встроенного в Visual C++ 6.0 и, соответственно, самого языка C++ 6.0.

Итак, что мы имеем:

static char szPassword[256]; // Буфер для хранения текущего пароля 
static char szAlphabet[256]; // Алфавит, т.е. набор символов для перебора 
... 
strcpy(szAlphabet, "ABC"); // Для примера возьмем короткий алфавит "ABC" 
ZeroMemory(szPassword, sizeof(szPassword)); // Начинаем перебирать с пустого пароля 

Нам нужно:

получить символ "A"; 
записать его в ячейку szPassword[0]; 
затем получить следующий символ - "B"; 
также записать его вместо "A"; 
получить символ "C"; 
записать его вместо "B"; 
определить, что мы дошли до конца алфавита; 
взять заново первый символ "A" 
записать его в ячейку szPassword[0]; 
проверить ячейку szPassword[1]; 
если там ноль, то изменилась длина пароля, поэтому пишем туда символ "A"; 
если там НЕ ноль, то инкремент этого символа; 
и так далее... 

Идея нашего инкремента следующая - попробуем-ка мы получать следующий символ ("B", к примеру) автоматически на основе того, что мы знаем предыдущий символ -
"A". Для этого нам нужно, чтобы символ "A" был как-то связан с символов "B". Может, в виде таблицы? Или же ... да-да, нам нужна именно таблица, в которой по адресу 65 (код символа "A") будет расположен сам символ "B"!

Поэтому строим таблицу (массив bAlphabet) размером 256 байт следующего вида:

0-й байт = код символа "A", т.е. 65 
65-й байт = код символа "B", т.е. 66 
66-й байт = код символа "C", т.е. 67 
67-й байт = ноль. 
(все остальные байты не важны, т.к. к ним обращений не будет) 

Тогда перебор символов (в развернутом виде) будет происходить следующим образом:

mov ebx,offset bAlphabet // Адрес нашей таблицы 
xor eax,eax // В AL - ноль 
movzx eax,byte ptr [ebx+eax] // В AL - символ "A" 
movzx eax,byte ptr [ebx+eax] // В AL - символ "B" 
movzx eax,byte ptr [ebx+eax] // В AL - символ "C" 
movzx eax,byte ptr [ebx+eax] // В AL - ноль 
movzx eax,byte ptr [ebx+eax] // В AL - снова символ "A" 
... // И так далее 

(Примечание: использование команд "xor eax,eax" и "movxz eax,..." вместо "mov al,0" и "mov al,[ebx+eax] позволяет избежать больших штрафов на процессорах Intel, возникающих при чтении 32-битного регистра после модификации его 8-битной части).

Или же, используя однобайтовую команду XLAT, наш пример будет выглядеть так:

mov ebx,offset bAlphabet 
xor eax,eax 
xlat // В AL - символ "A" 
xlat // В AL - символ "B" 
xlat // В AL - символ "C" 
xlat // В AL - ноль 
xlat // В AL - снова символ "A" 
... // И так далее 

Таким образом, мы видим, что без лишних команд сравнения (хотя они, конечно, потом понадобятся, но их будет всего две) и лишнего кода мы осуществляем циклический "обход" символов нашего алфавита, причем переход от последнего символа к первому происходит автоматически!

Код для инициализации нашей таблицы может быть, к примеру, таким:

static unsigned char bAlphabet[256]; 
... 
int i = 0, k = 0; 
ZeroMemory(bAlphabet, sizeof(bAlphabet)); 
while (TRUE) 
{ 
bAlphabet[k] = (unsigned char)szAlphabet[i]; 
if (!szAlphabet[i]) 
break; 
k = (unsigned char)szAlphabet[i]; 
i++; 
} 

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

Теперь же приведем полный код циклического инкремента с подробными комментариями:

__asm 
{ 
L0: 
... 
// Проверка пароля, т.е. тело программы-брутфорсера 
... 

mov edi,offset szPassword // Адрес строки с паролем 
mov ebx,offset bAlphabet // Адрес таблицы 
L1: movzx eax,byte ptr [edi] // Текущий символ пароля 
cmp al,0 // Не изменилась ли длина пароля? 
je L4 
L2: xlatb // Следующий символ пароля 
cmp al,0 // Не последний ли символ алфавита? 
je L3 
mov [edi],al // Новый символ пароля 
... 
// Инкремент кол-ва обработанных паролей и другой завершающий код 
... 
jmp L0 // На начало глобального цикла 

L3: xlatb // AL = снова первый символ алфавита 
stosb // Его сохранение в [EDI], инкремент EDI 
jmp L1 

L4: inc dword ptr [nLen] // Увеличение длины пароля 
jmp L2 
} 

Если же нам проверка на изменение длины пароля не нужна (может быть мы перебираем до нажатия пользователем Ctrl+С, или же до установки какого-либо флажка, или же просто останавливаем наш поток по внешнему воздействию и пр.), то наш код можно упростить:

... 
mov edi,offset szPassword 
mov ebx,offset bAlphabet 
L1: movzx eax,byte ptr [edi] 
xlat 
cmp al,0 
je L3 
mov [edi],al 
... 
// Инкремент кол-ва обработанных паролей и другой завершающий код 
... 
jmp L0 

L3: xlatb 
stosb 
jmp L1 

Ну как? 😉 Затрачено каких-то 25 байт и у нас полноценный перебор паролей из любых 8-битных символов (в том числе и служебных 0x01...0x1F) и с любого начального пароля (при условии, что он состоит из символов нашего алфавита). Добавляем еще несколько байт и мы можем отслеживать длину текущего пароля!

Теперь посмотрим на время, затраченное на инкремент пароля.

Но сразу оговоримся, что если время исполнения нам более важно, чем объем кода, то сделаем следующую замену на более быстрый код: команды "mov ebx,offset bAlphabet" и "xlat" заменим на команду "movzx eax,byte ptr [bAlphabet+eax]".

Тогда переход от комбинации "A" к "B" будет таким (по командам):

... 
mov edi,offset szPassword // Адрес пароля 
L1: movzx eax,byte ptr [edi] // Текущий символ пароля - "A" 
movzx eax,byte ptr [bAlphabet+eax] // В AL - следующий символ пароля, т.е. "B" 
cmp al,0 // У нас НЕ равно нулю 
je L3 // Переход не происходит 
mov [edi],al // Сохраняем новый символ "B" вместо "A" 
... 

Смотрите - всего 6 команд процессора. На большинстве процессоров такой код исполнится за ... 4-5 тактов. 🙂
Вы можете измерить это время и сами, вставив до и после этого кода команды RDTSC.
А вот почему это происходит:

Нет ни одного ветвления, а значит нет и лишних штрафов на ошибочное предсказание ветвления, на повторное заполнение конвейера и т.д. 

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

Более того - в реальном коде декодирование (и исполнение) подобных простых команд тесно связано с последующим и предыдущим кодом, что может снизить среднее время выполнения этих 6 команд до 3-4 тактов.

Итак, 3-4 такта на замену одного пароля другим - совсем даже неплохой результат.

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

Теперь поговорим о "накладных расходах", возникающих при переходе на соседний символ и при изменении длины пароля. Это тоже немаловажный вопрос, т.к. если на эти переходы будет затрачено 20-30 тактов (к примеру), то при длине алфавита в 26 символов среднее время инкремента пароля увеличится на 1 такт. А если больше 20-30 тактов?

Здесь нужен более сложный подход, чем при простом переходе от "A" к "B", но все-таки мы дадим несколько рекомендаций для снижения временных затрат. 

Вместо второй команды "xlat" (более компактной) применим команду "movzx eax,byte ptr [bAlphabet+eax]".
Вместо команды "stosb" (тоже более компактной) применим пару команд "mov [edi],al" и "inc edi".
Адрес метки L1 должен быть кратен 32 байтам. Или же вместо выравнивания метки L1 "развернуть" этот мини-цикл и не делать перехода назад, а использовать "копию" кода, находящегося по адресу L1.
И т.п. И в итоге - немного арифметики.

Пусть среднее время цикла проверки одного пароля - 300 тактов процессора.
Тогда средняя скорость перебора на процессоре частотой 1 ГГц составит 3,33 миллиона паролей/сек.
При уменьшении времени цикла на 10 тактов (к примеру, за счет наших ухищрений) мы получим 290 тактов и среднюю скорость около 3,45 миллионов п/с.
Разница: ~110 тысяч паролей в секунду! Видите - снизив время, затраченное на работу с одним паролем, всего лишь на несколько тактов, ваша программа сможет перебирать быстрее на сотню (или даже сотни) тысяч паролей в секунду!

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

Итак, обычно счетчик паролей увеличивают так:

DWORD dwLow, dwHigh; 
... 
dwLow++; 
if (dwLow == 0) 
dwHigh++; 
Или, на Ассемблере:

inc dword ptr [dwLow] 
jnz L1 
inc dword ptr [dwHigh] L1: ... 

Что мы видим - 3 команды, из которых одна - команда проверки, причем практически всегда результат проверки будет TRUE и процессору придется "перепрыгивать" на команду по адресу L1, что влечет за собой штрафы и перезаполнение конвейера.
Либо же сделать проверку не JNZ, а JZ, перенести по адресу L1 команду "inc dword ptr [dwHigh]" и добавить еще одну команду - JMP обратно...

Но можно сделать такой трюк, используя следующую пару команд:

... 
add dword ptr [dwLow],1 
adc dword ptr [dwHigh],0 
... 

В первой команде мы инкрементируем младший DWORD счетчика, а во второй - увеличиваем старший DWORD на ... ноль? Да, на ноль, но только если не было переполнения младшего DWORD'a счетчика. Если же оно было, то включится флаг переноса "C" и команда ADC прибавит в значению dwHigh ноль и значение этого флага, т.е. единицу. Что нам и нужно.
И декодируется/выполняется наша пара команд за ... 1 такт. 🙂

Кстати, хитрые парни из Microsoft тоже не зря получают свою зарплату. 🙂
Если в Visual C++ 6.0 написать следующий код:

... 
unsigned __int64 qwCount; // Сразу используем переменную типа QWORD 
... 
qwCount++; 
... 

и сделать компиляцию с оптимизацией (не забудьте включить создание ASM-листинга), то вы можете увидеть, что команда "qwCount++;" откомпилируется в ту же пару команд ADD/ADC. Причем, это явно не "могучий интеллект" компилятора, а одна из "изюминок" оптимизации, заранее заложенных в компилятор его разработчиками.

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

Удачи всем! 

Листинг 1. Программа генерации паролей.
 
Для ее использования откройте пустой проект (Win32 Console Application) в пакете Visual Studio 6.0, создайте новый CPP-файл и скопируйте в него следующий код:
(Примечание: если вы проинициализируете строку szPassword своим паролем, состоящим из символов алфавита szAlphabet, то программа начнет инкрементировать пароль именно с него).

#include "stdio.h" 
#include "windows.h" 

L5: popad 
} 
printf("%s\n", szPassword); 
} 
return 0; 
} 

Copyright © 2003-2004, InsidePro. All rights reserved.