Содержание статьи
Параллельный алгоритм взлома хеша SHA-1 с помощью Microsoft Robotics
Возможности среды Microsoft Robotics, о которой мы говорили в прошлых номерах, намного шире, чем может показаться на первый взгляд. Например, в состав Robotics входят библиотеки для организации параллельных и распределенных вычислений. Естественно, данные библиотеки ты можешь использовать не только для разработки программ управления роботом, но и в других целях. В этой статье я расскажу о способе распараллеливания алгоритма взлома хеша SHA-1.
Введение в Microsoft Robotics
Приложение, разрабатываемое в Microsoft Robotics, называется сервисом и по своей структуре отличается от консольного или визуального приложения. Поэтому в самом начале статьи рассмотрим эти отличия.
Программы для Robotics можно разрабатывать только в среде Visual Studio на Visual C#. После установки Microsoft Robotics в списке проектов, доступных для создания на C#, должна появиться папка «Microsoft Robotics». Если этого не произошло, значит, ты установил Visual Studio после установки MRDS. В этом случае переустанови MRDS.
Сервисы могут подключаться друг к другу и обмениваться сообщениями. Эти возможности реализуются с помощью библиотек «Concurrent and Coordination Runtime» (CCR, параллельные вычисления) и «Decentralized Software Services» (DSS, распределенные вычисления).
После компиляции сервиса генерируется набор DLL-библиотек и манифест. Манифест — файл в XML-формате, содержащий ссылки на сервисы, с которыми взаимодействует разрабатываемый сервис. Настройки проекта сервиса установлены так, что после компиляции сервиса созданные DLL-библиотеки копируются в каталог bin.
Запуск сервиса выполняется с помощью программы dsshost, которая загружает манифест и все сервисы, указанные в нем.
Создай проект сервиса и установи для него настройки, показанные на рис. 1. В диалоговом окне на рис. 1 я изменил только имя сервиса (Name) и пространство имен (Namespace). Остальные настройки можно не изменять, так как они требуются для более сложных приложений (например, для сервисов, взаимодействующих друг с другом).
Рис. 1. Окно настройки сервиса
В состав проекта сервиса входит несколько файлов:
PasswordBruteForce.cs — ядро сервиса;
- PasswordBruteForce.manifest.xml — манифест, который используется DSS для загрузки сервиса;
- PasswordBruteForceTypes.cs — содержит описание типов, которые используются сервисом.
В структуру кода сервиса входят описания различных структур данных, необходимых для функционирования сервиса. Однако сейчас нас интересует только метод Start, который вызывается, когда DSS-узел (dsshost.exe) запускает сервис (поэтому в метод Start обычно помещают действия по инициализации данных):
protected override void Start()
{
base.Start();
// Команды инициализации сервиса добавляются ниже
}После компиляции проекта сервиса генерируются три DLL-библиотеки:
- PasswordBruteForce.Y2012.M12.dll — библиотека реализации сервиса, формируемая на основе файлов исходного кода, включенных в проект сервиса;
- библиотека PasswordBruteForce.Y2012.M12.proxy.dll позволяет использовать твой сервис другим сервисам;
- библиотека PasswordBruteForce.Y2012.M12.transform.dll содержит описание соответствия между типами, определенными в реализации сервиса и реализации proxy библиотеки. Данная библиотека загружается автоматически с помощью среды выполнения DSS.
Внимательно изучи настройки проекта сервиса. В них указываются команды для компиляции и выполнения сервиса. Результат запуска сервиса показан на рис. 2.
Рис. 2. Результат запуска сервиса
После разработки сервиса ты можешь запустить его на компьютере, на который никогда не устанавливали Microsoft Robotics. Используй для этого утилиту dssdeploy, которая формирует самораспаковывающийся архив из файлов, необходимых для запуска сервиса.
Выполнить созданный сервис можно не только через в Visual Studio, но и через командную строку. Для этого выполни командный файл env.cmd (он находится в каталоге установки Robotics) или выбери пункт «DSS Command Prompt» в меню «ПускMRDS». В результате запустится окно командного интерпретатора, будет установлен корневой каталог и переменные окружения. В открывшемся окне выполни следующую команду (файл манифеста хранится в папке с проектом сервиса):
dsshost /p:50000 /t:50001 /m:"<путь к файлу манифеста сервиса>"INFO
Рекомендуется устанавливать Microsoft Robotics в каталог, путь к которому состоит только из символов английского алфавита.
Параллельные вычисления
Библиотека CCR — одна из разработок Microsoft для организации обработки данных с помощью параллельно и асинхронно выполняющихся методов. Взаимодействие между такими методами организуется на основе сообщений (сообщение — экземпляр любого типа данных). Рассылка сообщений основана на использовании портов. Порт — очередь сообщений типа FIFO (First-In-First-Out).
Сообщение остается в порте, пока не будет извлечено из очереди порта получателем. Получатель — структура, которая выполняет обработку сообщений. Данная структура объединяет:
- один или несколько портов, в которые отправляются сообщения;
- метод (или методы), который используется для обработки сообщений (такой метод называется задачей);
- логическое условие, определяющее ситуации, в которых активизируется тот или иной получатель.
Получатели сообщений бывают временные и постоянные. Временный получатель, обработав сообщение (или несколько сообщений), удаляется из списка получателей сообщений данного порта.
Процессом запуска задач управляет диспетчер. После выполнения условий активации задачи (одним из условий активации может быть получение некоторым портом сообщения) диспетчер назначает задаче поток из пула, в котором она и будет выполняться.
При создании DSS-сервиса базовый класс (DSSServiceBase) создает диспетчер и очередь диспетчера. Управлять настройками этого диспетчера можно только до компиляции. Однако существует возможность явного создания диспетчера, для которого можно указать количество потоков в пуле.
Вычисление хеша в Visual Studio
В неймспейсе System.Security.Cryptography описан класс SHA1, который вычисляет хеш по алгоритму SHA-1 для входных данных:
ASCIIEncoding enc = new ASCIIEncoding(); SHA1 sha = new SHA1CryptoServiceProvider(); byte[] shaHash = sha.ComputeHash(enc.GetBytes(pass));В нем также определены методы для вычисления хешей MD5, SHA-256, SHA-384, SHA-512 и RIPEMD-160.
Реализация сервиса
Перейдем к самому интересному. Рассмотрим сервис, который реализует параллельный алгоритм взлома хеша. Пусть задан алфавит, из символов которого, как мы предполагаем, составлен пароль, и хеш, который сгенерирован по неизвестному паролю. Тогда, чтобы определить пароль по его хешу, нужно перебрать все возможные сочетания символов данного алфавита (разной длины), сгенерировав таким образом все возможные пароли. Далее, по каждому сформированному паролю нужно вычислить хеш, сравнить его с заданным и в том случае, если хеш пароля совпадет с известным нам хешем, можно считать, что задача взлома решена.
Увеличить скорость вычисления хешей можно за счет распараллеливания алгоритма. Для этого нужно запустить несколько экземпляров метода, выполняющего перебор паролей. Каждый такой экземпляр должен перебирать пароли, которые начинаются с определенных символов алфавита. Допустим, если есть алфавит, состоящий из символов a, b, c, d, e и f и существует возможность запуска двух экземпляров метода перебора паролей, тогда первый экземпляр должен перебирать все пароли, начинающиеся на символы a, b и c, а второй — на d, e и f.
Алгоритм функционирования сервиса показан на рис. 3. Пунктирными линиями на рисунке показаны связи, по которым передаются сообщения между методами. В сервисе для управления процессом вычислений определено три порта:
- menu — используется при организации пользовательского ввода/вывода;
- time — используется для оценки времени поиска пароля;
- notfound — нужен для обработки ситуации, в которой пароль, после перебора всех возможных сочетаний значений символов алфавита, не найден.
Рис. 3. Блок-схема программы
После запуска сервиса в порт menu отправляется сообщение, после чего активируется получатель, связанный с портом. Данный получатель выводит на экран меню и выполняется всякий раз, когда в порт menu приходит сообщение (сообщение в данный порт можно отправить из любой точки сервиса):
...
menu.Post(1);
Arbiter.Activate(Environment.TaskQueue,
Arbiter.Receive(true, menu, delegate(int n) {
...
}
...Для создания получателя используется метод Arbiter.Activate. Получатель, созданный с помощью данного метода, будет управляться встроенным диспетчером задач — Environment.TaskQueue.
При вызове метода Arbiter.Receive для создания получателя укажи следующие параметры:
- флаг, определяющий тип получателя: временный (false) или постоянный (true);
- порт (menu), в который нужно отправлять сообщение для активации получателя;
- делегат, который будет выполняться при получении сообщения.
Сразу после вызова Arbiter.Activate выполнение сервиса должно продолжиться со следующего после Arbiter.Activate оператора. Если сообщение отправить в порт menu до активации получателя, получатель запустится сразу после вызова Arbiter.Activate.
Порт time связан с получателем, который выполняется, когда алгоритм поиска пароля находит пароль, соответствующий заданному хешу. Порт notfound приписан к получателю, который выполняется, когда обнаруживается, что пароль, соответствующий хешу, не найден ни одним из экземпляров метода подбора пароля. Поэтому данный получатель может быть запущен только тогда, когда в порт notfound придет N сообщений (N — количество запущенных экземпляров метода подбора паролей). Описание такого получателя немного отличается от описания получателя для порта menu:
Arbiter.Activate(Environment.TaskQueue, Arbiter.MultipleItemReceive(false, notfound, N, delegate(int[] array) {
nFlag = true;
sFlag = true;
time.Post(1);
Thread.Sleep(300);
menu.Post(1);
}));Продолжим рассматривать работу сервиса. В зависимости от выбора, который сделал пользователь в меню:
- Программа завершает работу.
- Вычисляется хеш введенного пароля, который сохраняется в файл hash.txt текущего каталога (для сервиса текущий каталог — каталог установки Microsoft Robotics).
- Запускается метод поиска хеша по паролю; для этого запускается несколько экземпляров задачи, предназначенной для перебора паролей; в каждой из задач по сгенерированному паролю вычисляется хеш и если искомый хеш совпал с хешем, вычисленным по паролю, то процесс поиска останавливается и программа рапортует об успехе!
Поиск пароля выполняет метод Brute. Количество запускаемых экземпляров данного метода зависит от количества ядер процессора компьютера. Количество ядер определяем так:
int N = (Int32)System.Environment.ProcessorCount;Далее создай диспетчер задач, количество потоков в пуле которого зададим равным количеству ядер:
Dispatcher d = new Dispatcher(N, "Brute Pool");
DispatcherQueue dq = new DispatcherQueue("Brute Queue", d);И запускай процесс перебора паролей:
for (int i = 0; i < N; i++) {
Arbiter.Activate(dq, new Task<HelpClass>
(ClArr[i], Brute));
}Передача параметров в метод Brute основана на использовании массива объектов, тип объекта — InputData:
public class InputData
{
public int start; // начало диапазона
public int stop; // начало диапазона
}Для вычисления SHA-1-хеша в C# используй класс SHA1, находящийся в пространстве имен System.Security.Cryptography.
Online-сервисы для работы с хешами
Взлом хеша:
Генерация хеша:
Заключение
Описанный принцип распараллеливания обработки данных может использоваться при решении и других задач. В перспективе можно создать приложение для перехвата и взлома паролей. Причем роль координирующего центра будет отводиться мобильному роботу, который будет перехватывать пароли и отправлять их на анализ мощным компьютерам. Однако, как говорил Киплинг, «это уже другая история».
Хеши и хеширование
Хеширование — это преобразование входного массива данных произвольной длины в выходную строку фиксированной длины (хеш). Отмечу, что замена одного символа в исходных данных приведет к значительным изменениям в хеше. Хеширование данных применяется при решении разных задач. Например, вместо паролей в различных системах с ограничением доступа (СУБД, ОС) хранятся их хеши.
Одним из известных алгоритмов хеширования является алгоритм SHA-1 (Secure Hash Algorithm 1), который описан в RFC 3174. Входное сообщение, максимальная длина которого может составлять 2^64 – 1 бит, данный алгоритм преобразует в 160-битный хеш, который также называют дайджестом сообщения.
