Как написать программу для перебора паролей

This workshop is about making a password cracker. We will be creating a password cracker which will be using the Brute Force technique to crack the password of your choice! So, let’s get started.

Disclaimer

The sole purpose of this workshop is to help you discover various ways via which you can be attacked ( in a cyber attack ) by someone. This is solely for educational purposes and using the knowledge provided here for ulterior motives is a cybercrime. The workshop is made so that you can be more aware of how these attacks are done and can protect yourself from them.

Hack Club doesn’t promote any kind of misuse of the knowledge being provided here and won’t be responsible for your participation in any sort of unlawful activities. So using the workshop for educational purposes only is strictly advised.

Prerequisites

The workshop is for anyone familiar with Python!

You don’t need to be a Guru in Python, a basic understanding of it is more than enough!

Souce Code

The final source code for the workshop is available here. This is on repl.it, you can use repl.it too for making this workshop!

You can use the final source code to cross-check your source code!

Introduction

The questions that would be arising in your mind would be that will this thing be a universal solution to cracking passwords? How the heck would it even be working?

Okay, so before I answer thess questions, I want to introduce you to some concepts. After going through these concepts you yourself would be able to answer all your questions.

What is the Brute Force technique?

Brute Force technique is a technique in which we check all the possible solutions for a problem against the actual solution.

In short, think that we have a list of passwords that we think can be someone’s password, then we try all of these passwords until unless we find the right one. Bizzare right? I know it sounds really inefficient but this solution is being used already with some efficiency improvements to it ( check Appendix ) also thanks to Moore’s Law that with increasing computing power the solution is becoming more and more efficient.

So, to conclude we will loop through a list of guess passwords ( but some other steps are also involved ) till any guess password matches the one we are looking for! In the later section of the workshop, I will share methods to make this guessing yield more accurate results.

What is a Wordlist?

A Wordlist is basically a collection of passwords that we are going to use in a Brute Force attack!

What is the source of these Wordlists?

If you follow the news then you know that database of big and small companies is being compromised. People are hacking in to get the passwords of the actual users on these platforms so that they could have a huge database of passwords that they can use for the Brute Force Attack. These wordlists of leaked databases are available over the internet and are being used for Brute Forcing.

Now in this workshop, we are using a wordlist to get a general idea about how this attack works and I strongly recommend going back to the Disclaimer Section if you have skipped it for some reason!

So, what can I expect from the password cracker ( of this workshop ) ?

Okay, so we will be using a really simple Wordlist so that you can crack very weak passwords. The passwords that people keep in a hurry like “Dinosaur, Cat, Dog, etc” are something that we will be able to crack.

We are on purpose using a Wordlist which is very small so that the purpose of the workshop ( which is teaching you how to be secure on the web ) can be accomplished.

Now, in reality, Brute Force can be made to yield more accurate result by social engineering the victim ( check Appendix ).

But I want to be a Hacking God :_:

I know everyone wants to be a cool hacker who can hack almost anything, I know you want to be the real-life Mr. ROBOT! But you have to start from the base to know how the tools that you use work under the hood and the prototype that we are going to make is more than enough to give you a basic idea about how password cracking tools work.

If you have learned making websites then remember we started by making simple HTML forms and slowly made our way through. You don’t become Mark Zuckerberg in a day!

Now, I hope the above info will be more than enough to answer all your questions about the password cracker that we are going to make.

What is hashing?

The developers usually run a Hash function on your password to transform them into another form which is known as the Hash of the password.

These Hash functions take your password as an input and transform them into a hash. Now if the hash of two inputs by Hash functions ( hash functions like SHA-1 ) are the same then it implies that the two inputs are the same. So this is how they verify whether the password you entered is right or wrong!

Examples of hash functions are SHA-1 and bcrypt. Now SHA-1 shouldn’t be used for storing passwords as it is really fast and hence really easy to Bruteforce.

bcrypt is slow and adds salt to your password while Hashing it ( there are also some other technical details to it, you can visit Wikipedia for that ). Salt is an additional input added by the function so that unlike SHA-1 the same password will not create the same Hash. These qualities make bycrypt a better option than SHA-1 as it is harder to Brute Force.

If you want to verify credentials ( when using bcrypt hash function ) then you will have a compare function which will take the actual hash of the password and the password that the user has entered and then will yield a boolean result telling whether they are the same or not!

The Scenario!

I believe giving people real-life scenarios while doing Hacking workshops make them perform better! So, here is your scenario:

• Assume you have landed a penetration testing contract and the web app has a vulnerability. You get access to its whole database and you have cloned it.

• Now, you discover that the developer that they had was really not aware of how to store the passwords and they have used SHA-1 to hash the passwords!

• Now, you are really smart and you know you can Bruteforce the database via a wordlist that you have! Now the Hack begins!

Create cracker.py

Now, create a file cracker.py in any folder of your choice on your computer. Now, Open it inside your favorite code editor.

Imports:

The first step is to make our Python imports, so type the following inside your cracker.py file:

import hashlib
from urllib.request import urlopen

Here the following has happened:

1. We imported hashlib, it will help us to create SHA-1 hashes.
2. We imported urlopen from urllib.request, this method will help us to open and read our wordlist file via an URL!

Functions

Now, we are going to create individual functions for tasks like hashing, reading wordlist file and then finally for Brute Forcing!

Append the following code to your cracker.py file ( new code is separated by a ###### append the below code ###### comment )

import hashlib
from urllib.request import urlopen

############# append the below code ################ 

def readwordlist(url):
    try:
        wordlistfile = urlopen(url).read()
    except Exception as e:
        print("Hey there was some error while reading the wordlist, error:", e)
        exit()
    return wordlistfile
 
 
def hash(password):
    result = hashlib.sha1(password.encode())
    return result.hexdigest()
 
 
def bruteforce(guesspasswordlist, actual_password_hash):
    for guess_password in guesspasswordlist:
        if hash(guess_password) == actual_password_hash:
            print("Hey! your password is:", guess_password,
                  "n please change this, it was really easy to guess it (:")
            # If the password is found then it will terminate the script here
            exit()

Here the following is happening:

1. We created readwordlist(url) function which takes an URL as a parameter and will then return us file content. If any exception is raised during this process then the program will exit() the script.

2. The hash function will take the password as a parameter and then will return us hash of the password as a string of double length, containing only hexadecimal digits. The hashlib.sha1 function expects the argument to be of type <class ‘bytes’> which is why we are passing password.encode() as its argument.
3. • The bruteforce function will take the wordlist as a List and the hash of the actual password that you want to find, and then it will loop through the wordlist for each item and will hash it and then will compare the hash with the actual password’s hash.
   • If it finds a hash equal to the actual password’s hash then it will return the equivalent passwords in the wordlist. Which will be the password we were guessing!

Completing the Script

Now, we will use these functions to write our final script.

Append the following code to your cracker.py file ( new code is separated by a ###### append the below code ###### comment )

import hashlib
from urllib.request import urlopen
 
def readwordlist(url):
    try:
        wordlistfile = urlopen(url).read()
    except Exception as e:
        print("Hey there was some error while reading the wordlist, error:", e)
        exit()
    return wordlistfile
 
 
def hash(wordlistpassword):
    result = hashlib.sha1(wordlistpassword.encode())
    return result.hexdigest()
 
 
def bruteforce(guesspasswordlist, actual_password_hash):
    for guess_password in guesspasswordlist:
        if hash(guess_password) == actual_password_hash:
            print("Hey! your password is:", guess_password,
                  "n please change this, it was really easy to guess it (:")
            # If the password is found then it will terminate the script here
            exit()
 
############# append the below code ################ 

url = 'https://raw.githubusercontent.com/berzerk0/Probable-Wordlists/master/Real-Passwords/Top12Thousand-probable-v2.txt'
actual_password = 'henry'
actual_password_hash = hash(actual_password)
 
wordlist = readwordlist(url).decode('UTF-8')
guesspasswordlist = wordlist.split('n')
 
# Running the Brute Force attack
bruteforce(guesspasswordlist, actual_password_hash)
 
# It would be executed if your password was not there in the wordlist
print("Hey! I couldn't guess this password, it was not in my wordlist, this is good news! you win (: ")
 

Here the following is happening:

• We created a variable url that will store the URL of the wordlist that we are going to use. The actual_password variable is being used to store the password, we will try to guess this password from its hash. Actual_password_hash variable stores the hash of the actual_password.

• wordlist variable stores the wordlist as a UTF-8 string, each password in the wordlist is separated by a «n» character. So we split this wordlist into a List and store it in guesspasswordlist variable.

• Then we bruteforce the guesspasswordlist variable and if our wordlist contains a password which has same hash as of the actual password’s hash, then we have cracked the password and the bruteforce function will print the cracked password.

• Else if we don’t have such a password in our wordlist then we print «Hey! I couldn’t guess this password, it was not in my wordlist, this is good news! you win (: «. This means we couldn’t guess the provided password.

Done!

Congratulations! You have successfully completed the journey of making this password cracker. I am checking the cracker to crack for hash of “henry” as a password but you can make it whatever you want.

Now, this password cracker will be able to crack almost all dumb passwords that you can think of. These are passwords that people who are in a hurry to create an account or who don’t take security seriously keep ( I am definitely sure you know such people ).

Running the script!

To run the Script simply double-click on it ( cracker.py file ). You can also run it from a terminal if you want. Try checking this script out with different passwords!

Next Steps!

I know it feels awesome to make it but don’t stop here, Create whatever you can from this crazy trick and share it with us in the #ship channel of Hack Club’s Slack.

I am available on Hack Club’s Slack by the username Harsh Bajpai, If you have any doubt or query regarding this workshop then feel free to reach out to me!

Appendix

The workshop is done and the below information is going to supplement what you have previously learned. This section isn’t necessary for completing the workshop.

Social Engineering is the practice of making people perform some actions and then get their personal data out from them ( their name, birthday, pet’s name, favorite place, etc ).

People generally use a combination of their personal data ( the ones discussed above ) to create their passwords, as it makes it easier to remember. Getting these data of the victim can help a person to Brute Force in a very targeted way where they will try different combinations of these data to get the victim’s password ( there are tools which help you do that ).

Rainbow Table Attack

In this attack, we use a Rainbow Table.

A rainbow table is a precomputed dictionary of plaintext passwords and their corresponding hash values that can be used to find out what plaintext password produces a particular hash ( this is an abstract definition, in order to know the technicalities visit here).

This saves us a lot of time as we are using a precomputed dictionary and not computing the hash during the run-time of the script!

Don’t be a script kiddo

The reason I believe making prototypes of these tools are important because they help you to understand how your tool works ( at least gives you a rough idea ). I know a lot of you might be thinking why not directly start with tools like John the Ripper? Sure, you can and it will be better too!

But the thing is that you must also push yourself towards making some small tools of yours so the tools that you don’t appear as magic to you. Making such small prototypes also increases your technical knowledge!

Сказ о тотальном переборе, или Томительное ожидание декрипта

Приветствую жителей Хабра!

Итак, новые «криптографические игрища» пришли по мою душу. Поэтому сегодня поговорим о занудном упражнении, ориентированном на полный перебор паролей, реализации тривиального многопоточного брутера силами C++ и OpenMP, а также кратко об использовании криптобиблиотеки CryptoPP и стороннего модуля fastpbkdf2 (для Си и Плюсов) в своих проектах.

Го под кат, печеньки out there!

ДИСКЛЕЙМЕР. Перебирать чужие пароли нельзя, читать тексты, адресованные не вам, нельзя, создавать и распространять вредоносное ПО с целью неправомерного доступа к компьютерной информации нельзя. Наказуемо согласно УК РФ. Dixi.

Разбор условия

Вещественная обёртка задачи представляет из себя небольшую карточку со следующим текстом:

SGFzaGVkU2FsdCg4Ynl0ZXNJblVURjE2TEUpQ291bnRlckNpcGhlcnRleHRB
RVMyNTZFQ0J8MWE0MDhhYTVhZjkzMDkxOGRkYjkyNzQ3NDBhMDJjMmJkM2Vl
N2NkNjU3MDQwMDAwMDQxN2E2Nzc4Yzc3YzYwZjcxMGJlNTNiNmViODQ0ZDg0
MmUwZWEwZGYwNDA2NTU4NWEzMzIzYTUwZjc2OGY1N3xQb3NzaWJsZVBhc3N3
b3JkUGF0dGVybnN8RERMTExMTEx8RExMTExMTER8TExMRERMTEx8TExMTExM
REQ=

Зачем в Base64? Преподавателем на это было отвечено: «Чтобы варианты условий не повадно выбирать было». Не очень-то и хотелось. Также на словах была передана информация об используемом алгоритме преобразования пароля в ключ (PBKDF2_HMAC_SHA1) и сформулированы простые условия игры: «Подобрать пароль для восстановления сообщения, зашифрованного блочным шифром. Пароль не словарный, может состоять из цифр и маленьких букв латинского алфавита, соль — только из маленьких букв». Давайте посмотрим, что скрывает кодировка:

HashedSalt(8bytesInUTF16LE)CounterCiphertextAES256ECB|1a408a
a5af930918ddb9274740a02c2bd3ee7cd6570400000417a6778c77c60f71
0be53b6eb844d842e0ea0df04065585a3323a50f768f57|PossiblePassw
ordPatterns|DDLLLLLL|DLLLLLLD|LLLDDLLL|LLLLLLDD

Что мы видим? Первая часть сообщения (до первого вертикального слэша), вероятно, представляет из себя порядок следования данных, непосредственно указанных во второй части: хеш-значение соли (с информацией о кодировке в скобках), счетчик итераций для PBKDF2, используемый блочный шифр и режим шифрования. AES добрался до меня и здесь, кто бы мог подумать… Третья часть и до конца — потенциальные маски нужного пароля, где L — буква (letter), D — цифра (digit). Также определено, что пароль состоит из 8-ми символов. Вроде звучит логично, теперь было бы неплохо структурировать полученную информацию.

Проанализируем второй блок сообщения. В задании нет информации об используемой функции хеширования соли, поэтому сделаем предположение, что это SHA1, т. к. это единственная широко используемая криптографическая хеш-функция с длиной выхода 20 байт (только этот размер идеально ложится под остальное разбиение). Также, очевидно, что счетчик представлен в little endian, по крайней мере очень хочется так думать, ибо 0x57040000 = 1459879936 итераций PBKDF2 — не самая лучшая перспектива для перебора… И, наконец, остается два блока AES по 16 байт каждый. Следовательно, имеем такую картину:

1A408AA5AF930918DDB9274740A02C2BD3EE7CD6 — хеш соли (20 байт);
0x00000457 = 1111 — счетчик итераций PBKDF2;
0417a6778c77c60f710be53b6eb844d8 — первый блок шифртекста (16 байт);
42e0ea0df04065585a3323a50f768f57 — второй блок шифртекста (16 байт).

Восстановление соли

Окей, для начала напишем

быдло

быстро-скрипт для восстановления соли. Благо, 4 символа (aka 8 байт в UTF-16) переберутся за секунды, поэтому воспользуемся пайтоном, не мудрствуя лукаво:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Usage: python3 crack_salt_hash.py

from hashlib import sha1
from itertools import product

ALPH = 'abcdefghijklmnopqrstuvwxyz'
SIZE = 4
TOTAL = len(ALPH)**SIZE


def crack_hash(func, output, enc):
	progress = 0
	for salt in product( *([ALPH]*SIZE) ):
		if func(''.join(salt).encode(encoding=enc)).hexdigest() == output:
			print(progress+1, 'of', TOTAL)
			return ''.join(salt)
		progress += 1
		if progress % 10000 == 0:
			print(progress, 'of', TOTAL)
	return None


if __name__ == '__main__':
  print(crack_hash(sha1, '1a408aa5af930918ddb9274740a02c2bd3ee7cd6', 'UTF-16LE'))

По прошествии 3-х секунд, имеем результат: «dukg«. С учетом 2-байтовой кодировки конечная форма соли (пригодная для ввода в PBKDF2) будет иметь вид «dx00ux00kx00gx00«.

Криптографические нужды

Теперь предстоит выбрать инструменты для работы с криптографией. По порядку: сперва подумаем о получении ключа из пароля, затем о расшифровании сообщения. Для решения обоих вопросов сразу на ум приходят два возможных варианта: OpenSSL либо Crypto++ (он же CryptoPP). Оба пакета широко известны и с ними нетрудно работать на C++ (выбор языка пришел сам собой исходя необходимости высокой скорость перебора).

Генерация ключей

Забегая немного вперед, стоит сказать, что стандартная функция PKCS5_PBKDF2_HMAC_SHA1 из OpenSSL при заданном счетчике в 1111 итераций показала среднюю скорость в 1000 ключей/с при параллельной работе на 4-ядерном Intel Core i5 2.60GHz. Не самый лучший результат, посему было решено поискать альтернативное «прокаченное» решения для генерации ключей. Таким решением стала библиотека fastpbkdf2 от стороннего разработчика. Библиотека основана на том же OpenSSL (реализации самих хеш-функций оттуда), однако, согласно описанию, использует «различные оптимизации во внутреннем цикле for» при высчитывании PBKDF2. Такое объяснение меня вполне устраивает, к тому же производительность возросла примерно в 3,45 раза: теперь перебор идет со скоростью в 3450 паролей/с.

Модуль написан на Си и требует компилятор, поддерживающий C99, поэтому для встраивания его (модуля) в проект на Плюсах, скомпилируем из исходников и создадим динамическую библиотеку как:

$ gcc fastpbkdf2.c -fPIC -std=c99 -O3 -c -g -Wall -Werror -o fastpbkdf2.o
$ gcc -shared -lcrypto -o libfastpbkdf2.so fastpbkdf2.o

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

$ g++ bruter.cxx -o bruter -L"/path/to/libfastpbkdf2.so" -Wl,-rpath="/path/to/libfastpbkdf2.so" -lfastpbkdf2

В конце добавим Makefile для автоматизации. Прикинем теперь, как будет происходить проверка валидности пароля:

bool checkPassword(
	uint8_t* password,
	const uint8_t* ciphertext,
	uint8_t* decrypted,
	int& decryptedLength
) {
	uint8_t key[KEY_LENGTH];

	fastpbkdf2_hmac_sha1(
		password,
		PASSWORD_LENGTH,
		salt,
		SALT_LENGTH,
		iterations,
		key,
		KEY_LENGTH
	);

	decryptedLength = CryptoPP_Decrypt_AES_256_ECB(
		ciphertext,
		(uint8_t*) key,
		decrypted
	);

	if (isPrintable(decrypted, decryptedLength))
		return true;

	return false;
}

где CryptoPP_Decrypt_AES_256_ECB — не написанная еще функция расшифрования. Возвращаемое значение — истина/ложь, в зависимости от исхода проверки критерия. Критерий же верного декрипта — печатаемость всех символов открытого текста, оценка критерия лежит на функции isPrintable (см. полный листинг в Заключении).

Расшифрование сообщения

Для расшифрования сообщения обратимся за помощью к библиотеки Crypto++.

Следуя порядку работы с блочными шифрами в рамках данного пакета, выполним следующие действия: создадим функциональный объект для расшифрования AES в режиме ECB (decryptor), инициализируем его ключом (размер ключа определяет версию AES — в нашем случае AES-256), назначим выходной буфер и выполним операцию преобразования шифртекста в открытый текст по алгоритму, который содержит decryptor. Также мы предполагаем, что добивание блока (PADDING) не использовалось вовсе, ибо условие умалчивает о формате добивания. Следовательно, длина исходного сообщение должна быть кратной длине одного блока AES.

int CryptoPP_Decrypt_AES_256_ECB(
	const uint8_t* ciphertext,
	uint8_t* key,
	uint8_t* plaintext
) {
	ECB_Mode<AES>::Decryption decryptor;
	decryptor.SetKey(key, AES::MAX_KEYLENGTH);
	ArraySink ps(&plaintext[0], PLAINTEXT_LENGTH);

	ArraySource(
		ciphertext,
		CIPHERTEXT_LENGTH,
		true,
		new StreamTransformationFilter(
			decryptor,
			new Redirector(ps),
			StreamTransformationFilter::NO_PADDING
		)
	);
	
	return ps.TotalPutLength();
}

Возвращать функция будет длину дешифрованного сообщения.

Новая информация

Пока в течении дня возился с подготовительными работами, описанными выше, на почту прилетело письмо от автора, в котором сообщалось, что «всплыла новая информация, касательно структуры пароля». В общих словах сообщалось, что при создании парольной фразы пользователь по ошибке зажал Shift во время ввода единицы и буквы «q«. Перефразируя сообщение, получим символ «!» (на месте цифры) и букву «Q» (на месте буквы), как гарантированные составляющие пароля. Для пользователя новость не самая лучшая, но для нас просто замечательная: это подразумевает существенное сужение области перебора. Численную оценку преимущества, которое так удачно было получено, проведем чуть позже, когда будем оценивать время, необходимое на полный перебор.

Параллельный брутер

Дело за малым: остается написать управляющую функцию и ввести элемент многопоточности. Для распараллеливания вычислений будем использовать прагмы OpenMP. Общее количество паролей для перебора — известная величина. Для примера рассмотрим одну из четырех моделей паролей (с учетом того, что одна из цифр — на самом деле «!», а одна из букв — «Q»):

Первые две скобки — количество размещений с повторениями из 26 по 5 и из 10 по 1 соответственно (5 букв и 1 цифра), множители в третьих скобках — перестановка «!» (может стоять на двух позициях) и перестановка «Q» (может стоять на шести позициях). Полную область перебора определим, домножив результат на 4, получая или 5,7 млрд.

Так как границы области определены, для выработки паролей воспользуемся вложенными циклами for и прагмой omp parallel for с параметром collapse() для «схлопывания» множественных петель в одну большую. Нужно помнить, что для того, чтобы пользоваться collapse(), необходимо поддерживать «идеальную вложенность» циклов. Это означает, что каждый следующий цикл (кроме последнего, разумеется) содержит в себе только очередную инструкцию for, а все операции выполняются в последнем по вложенности цикле.

Также, перед тем, как приступать к написанию кода, обратим внимание на интересную особенность: каждая следующая модель пароля является циклическим сдвигом на 1 или 3 позиции другой модели. Приняв это к сведению, мы сможем проще организовать перебор паролей из каждой модели за одну итерацию цикла:

void Parallel_TotalBruteForce(
	uint8_t* goodPassword,
	uint8_t* goodDecrypted,
	int& goodDecryptedLength
) {
	uint8_t alp[27] = {
		'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
		'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
		'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
		'y', 'z', ''
	};

	uint8_t num[11] = {
		'0', '1', '2', '3', '4', '5', '6', '7',
		'8', '9', ''
	};

#ifdef WITH_OPENMP
	omp_set_num_threads(myOMP_THREADS);
#endif

	uint64_t progress = 0;
	bool notFinished = true;

	#pragma omp parallel for shared(progress, notFinished) collapse(8)
	for (int a = 0; a  < 2; a++)
	for (int b = 2; b  < 8; b++)
	for (int c = 0; c < 26; c++)
	for (int d = 0; d < 26; d++)
	for (int e = 0; e < 26; e++)
	for (int f = 0; f < 26; f++)
	for (int g = 0; g < 26; g++)
	for (int h = 0; h < 10; h++) {
		if (notFinished) {
			uint8_t password[9]; password[PASSWORD_LENGTH] = '';
			uint8_t indeces[6] = { 2,3,4,5,6,7 };
			memmove(indeces+b, indeces+b+1, 5-b);
			uint8_t decrypted[100]; int decryptedLength;

			password[         a] =    '!';  // 0-1
			password[        !a] = num[h];  // 0-1
			password[         b] =    'Q';  // 2-7
			password[indeces[0]] = alp[c];  // 2-7
			password[indeces[1]] = alp[d];  // 2-7
			password[indeces[2]] = alp[e];  // 2-7
			password[indeces[3]] = alp[f];  // 2-7
			password[indeces[4]] = alp[g];  // 2-7

			if (
				// DDLLLLLL
				checkPassword(
					password,
					ciphertext,
					decrypted,
					decryptedLength
				) ||

				// DLLLLLLD      
				checkPassword(
					rotateLeft(password, 1),
					ciphertext,
					decrypted,
					decryptedLength
				) ||

				// LLLLLLDD
				checkPassword(
					rotateLeft(password, 1),
					ciphertext,
					decrypted,
					decryptedLength
				) ||

				// LLLDDLLL
				checkPassword(
					rotateLeft(password, 3),
					ciphertext,
					decrypted,
					decryptedLength
				)
			) {
				#pragma omp critical
				{
					memcpy(
						goodPassword,
						password,
						9
					);

					memcpy(
						goodDecrypted,
						decrypted,
						decryptedLength
					);

					goodDecryptedLength = decryptedLength;
					notFinished = false;
				}
			}

			if (progress % PROGRESS_SEP == 0)
				cout << progress << " of " << TOTAL << endl;
			progress += STEP;
		}
	}
}

Флаг notFinished используется для выхода из for. Такой подход более свойственен для работы с pthread напрямую, в OpenMP для этого есть #pragma omp cancel, однако меня компилятор засыпал предупреждениями, природа которых мне не до конца ясна, поэтому было решено использовать флаг.

Теперь посмотрим на производительность полученной системы и оценим время, необходимое на полный перебор.

Оценка производительности и поиск бо́льших мощностей

Как уже говорилось выше, при параллельной работе на 4-ядерном Intel Core i5 2.60GHz была достигнута скорость, примерно равная 3450 паролей/с. Всего 5,7 млрд. паролей, отсюда нехитрые вычисления дают оценку в 19 дней работы машины при условии, что нужный нам пароль окажется последним из всего множества. Не лучшая перспектива.

Самое время для маленького читерства. Воспользуемся небезызвестным сервисом облачных вычислений Amazon EC2. Выберем инстанс для вычислений с ЦПУ-преимуществом (характеристики приведены на скриншоте ниже) и посмотрим производительность.

Подняв количество потоков с 4 до 36 (+ более шустрые серверные процы), получили прирост в скорости аж в 10 раз даже несмотря на замедление работы сервиса из-за недавнего наката анти-Meltdown патчей. Подняв два инстанса таких виртуалок по спотовой цене в $0,37/ч получим возможность перебрать все множество за 24 часа, выложив при этом $17,76 (или около 1 тыс. руб. по текущему состоянию курса). Недешевое удовольствие для учебной задачки, но спортивный интерес все же победил, поэтому готов поделиться результатами.

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

Следовательно, для полного перебора на скорости 3450 п/с ушло бы больше года при использовании ЭВМ на процессоре, указанном в начале раздела, в многопоточном режиме и больше четырёх лет при работе в один поток [из цикла «Ужасы нашего Городка»].

Результаты

Восстановленный пароль: «ldQ9!nwd«.
Открытый текст: 2E2B2A602A2B2C20594F552044495341524D4544204D4521202C2B2A602A2B2E.
Сообщение: «.+*`*+, YOU DISARMED ME! ,+*`*+.».

Декрипт был получен чуть больше чем за 1/2 суток. При используемом подходе со сдвигами одной модели пароля относительно других получилась такая картина: успешной оказалась та итерация, когда первой сгенерировалась комбинация «9!nwdldQ» (из модели ), и после трех циклических сдвигов влево на проверку ушел нужный пароль.

Заключение, исходные коды

Новый год ознаменовался достаточно необычным для меня опытом, благодарность автору за сбалансированную игру

Полный код брутера под спойлером:

/**
 * @file bruter.cxx
 * @author Sam Freeside <snovvcrash@protonmail[.]ch>
 * @date 2018-01
 *
 * @brief Brute forcing 4 password patterns: "DDLLLLLL", "DLLLLLLD", "LLLLLLDD", "LLLDDLLL"
 */

/**
 * LEGAL DISCLAIMER
 *
 * bruter.cxx was written for use in educational purposes only.
 * Using this tool without prior mutual consistency can be considered
 * as an illegal activity. It is the final user's responsibility
 * to obey all applicable local, state and federal laws.
 *
 * The author assume no liability and is not responsible for any misuse or
 * damage caused by this tool.
 */

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <ctype.h>
#include <omp.h>

#include "cryptopp/filters.h"
#include "cryptopp/files.h"
#include "cryptopp/modes.h"
#include "cryptopp/hex.h"
#include "cryptopp/aes.h"

#include "lib/fastpbkdf2.h"

#define myOMP_THREADS          4  // == CPU(s) = [Thread(s) per core] * [Core(s) per socket] * [Socket(s)]
#define myOMP_SCHEDULE_CHUNKS  4

#define TOTAL         5703060480  // == 26*26*26*26*26*10 * 2*6 * 4
#define STEP                   4
#define PROGRESS_SEP     1000000

using namespace std;
using namespace CryptoPP;

const uint8_t ciphertext[100] = {
	0x04, 0x17, 0xA6, 0x77, 0x8C, 0x77, 0xC6, 0x0F,
	0x71, 0x0B, 0xE5, 0x3B, 0x6E, 0xB8, 0x44, 0xD8,
	0x42, 0xE0, 0xEA, 0x0D, 0xF0, 0x40, 0x65, 0x58,
	0x5A, 0x33, 0x23, 0xA5, 0x0F, 0x76, 0x8F, 0x57
};

const int PLAINTEXT_LENGTH  = 32;
const int CIPHERTEXT_LENGTH = 32;
const int SALT_LENGTH       =  8;
const int PASSWORD_LENGTH   =  8;
const int KEY_LENGTH        = 32;

const uint8_t salt[SALT_LENGTH] = {
	'd', 0x00,
	'u', 0x00,
	'k', 0x00,
	'g'
};

const uint32_t iterations = 0x00000457;  // == 1111

void Parallel_TotalBruteForce(
	uint8_t* goodPassword,
	uint8_t* goodDecrypted,
	int& goodDecryptedLength
);

int CryptoPP_Decrypt_AES_256_ECB(
	const uint8_t* ciphertext,
	uint8_t* key,
	uint8_t* plaintext
);

bool checkPassword(
	uint8_t* password,
	const uint8_t* ciphertext,
	uint8_t* decrypted,
	int& decryptedLength
);

uint8_t* rotateLeft(
	uint8_t* password,
	int n
);

bool isPrintable(
	uint8_t* text,
	int textLength
);


int main() {
	uint8_t goodPassword[9] = { '*','*','*','*','*','*','*','*', '' };
	uint8_t goodDecrypted[100];
	int goodDecryptedLength = 0;

	HexEncoder encoder(new FileSink(cout));
	cout << "[*] Ciphertext:" << endl;
	encoder.Put(ciphertext, CIPHERTEXT_LENGTH);
	encoder.MessageEnd();
	cout << endl << endl;

	Parallel_TotalBruteForce(goodPassword, goodDecrypted, goodDecryptedLength);

	cout << endl << "[+] Decrypted block:" << endl;
	encoder.Put(goodDecrypted, goodDecryptedLength);
	encoder.MessageEnd();
	cout << endl;

	goodDecrypted[goodDecryptedLength++] = '';
	cout << "[+] Decrypted string:" << endl;
	cout << '"' << goodDecrypted << '"' << endl;

	cout << "[+] Password:" << endl;
	cout << '"' << goodPassword << '"' << endl << endl;

	return 0;
}


void Parallel_TotalBruteForce(
	uint8_t* goodPassword,
	uint8_t* goodDecrypted,
	int& goodDecryptedLength
) {
	uint8_t alp[27] = {
		'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
		'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
		'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
		'y', 'z', ''
	};

	uint8_t num[11] = {
		'0', '1', '2', '3', '4', '5', '6', '7',
		'8', '9', ''
	};

#ifdef WITH_OPENMP
	omp_set_num_threads(myOMP_THREADS);
#endif

	uint64_t progress = 0;
	bool notFinished = true;

	#pragma omp parallel for shared(progress, notFinished) collapse(8)
	for (int a = 0; a  < 2; a++)
	for (int b = 2; b  < 8; b++)
	for (int c = 0; c < 26; c++)
	for (int d = 0; d < 26; d++)
	for (int e = 0; e < 26; e++)
	for (int f = 0; f < 26; f++)
	for (int g = 0; g < 26; g++)
	for (int h = 0; h < 10; h++) {
		if (notFinished) {
			uint8_t password[9]; password[PASSWORD_LENGTH] = '';
			uint8_t indeces[6] = { 2,3,4,5,6,7 };
			memmove(indeces+b, indeces+b+1, 5-b);
			uint8_t decrypted[100]; int decryptedLength;

			password[         a] =    '!';  // 0-1
			password[        !a] = num[h];  // 0-1
			password[         b] =    'Q';  // 2-7
			password[indeces[0]] = alp[c];  // 2-7
			password[indeces[1]] = alp[d];  // 2-7
			password[indeces[2]] = alp[e];  // 2-7
			password[indeces[3]] = alp[f];  // 2-7
			password[indeces[4]] = alp[g];  // 2-7

			if (
				// DDLLLLLL
				checkPassword(
					password,
					ciphertext,
					decrypted,
					decryptedLength
				) ||

				// DLLLLLLD      
				checkPassword(
					rotateLeft(password, 1),
					ciphertext,
					decrypted,
					decryptedLength
				) ||

				// LLLLLLDD
				checkPassword(
					rotateLeft(password, 1),
					ciphertext,
					decrypted,
					decryptedLength
				) ||

				// LLLDDLLL
				checkPassword(
					rotateLeft(password, 3),
					ciphertext,
					decrypted,
					decryptedLength
				)
			) {
				#pragma omp critical
				{
					memcpy(
						goodPassword,
						password,
						9
					);

					memcpy(
						goodDecrypted,
						decrypted,
						decryptedLength
					);

					goodDecryptedLength = decryptedLength;
					notFinished = false;
				}
			}

			if (progress % PROGRESS_SEP == 0)
				cout << progress << " of " << TOTAL << endl;
			progress += STEP;
		}
	}
}

uint8_t* rotateLeft(
	uint8_t* password,
	int n
) {
	rotate(&password[0], &password[n], &password[PASSWORD_LENGTH]);
	return password;
}

bool checkPassword(
	uint8_t* password,
	const uint8_t* ciphertext,
	uint8_t* decrypted,
	int& decryptedLength
) {
	uint8_t key[KEY_LENGTH];

	fastpbkdf2_hmac_sha1(
		password,
		PASSWORD_LENGTH,
		salt,
		SALT_LENGTH,
		iterations,
		key,
		KEY_LENGTH
	);

	decryptedLength = CryptoPP_Decrypt_AES_256_ECB(
		ciphertext,
		(uint8_t*) key,
		decrypted
	);

	if (isPrintable(decrypted, decryptedLength))
		return true;

	return false;
}

int CryptoPP_Decrypt_AES_256_ECB(
	const uint8_t* ciphertext,
	uint8_t* key,
	uint8_t* plaintext
) {
	ECB_Mode<AES>::Decryption decryptor;
	decryptor.SetKey(key, AES::MAX_KEYLENGTH);
	ArraySink ps(&plaintext[0], PLAINTEXT_LENGTH);

	ArraySource(
		ciphertext,
		CIPHERTEXT_LENGTH,
		true,
		new StreamTransformationFilter(
			decryptor,
			new Redirector(ps),
			StreamTransformationFilter::NO_PADDING
		)
	);
	
	return ps.TotalPutLength();
}

bool isPrintable(
	uint8_t* text,
	int textLength
) {
	// OuKSJJRlqS7Tqzn+r9GZ4g==
	for (int i = 0; i < textLength; i++)
		if (!isprint(text[i]))
			return false;

	return true;
}

Код мейкфайла, как обещано, под вторым спойлером:

CXXTARGET  = bruter

CXXSOURCES = $(wildcard *.cxx)
CXXOBJECTS = $(patsubst %.cxx, %.o, $(CXXSOURCES))
CSOURCES   = $(wildcard */*.c)
CHEADERS   = $(wildcard */*.h)
COBJECTS   = $(patsubst %.c, %.o, $(CSOURCES))

SHARED_LIB = lib/libfastpbkdf2.so

CXX = g++
CC  = gcc

CXXFLAGS += -std=c++11 -O3 -c -g -Wall
CXXLIBS  += -L"./lib" -Wl,-rpath="./lib" -lfastpbkdf2 -L"/usr/lib" -lssl -lcrypto -lcryptopp

CFLAGS  += -fPIC -std=c99 -O3 -c -g -Wall -Werror -Wextra -pedantic
CLIBS   += -lcrypto

.PHONY: all default openmp clean
.PRECIOUS: $(CXXSOURCES) $(CSOURCES) ($CHEADERS) $(SHARED_LIB)

default: $(CXXTARGET)
	@echo "=> Project builded"

all: clean openmp

$(CXXTARGET): $(SHARED_LIB) $(CXXOBJECTS)
	@echo "=> Linking project files"
	@echo "(CXX) $?"
	@$(CXX) $(CXXOBJECTS) $(CXXLIBS) -o $@

$(CXXOBJECTS): $(CXXSOURCES)
	@echo "=> Compiling project files"
	@echo "(CXX) $?"
	@$(CXX) $(CXXFLAGS) $< -o $@

$(SHARED_LIB): $(COBJECTS)
	@echo "=> Creating shared library"
	@echo "(CC) $?"
	@$(CC) -shared $< -o $@

$(COBJECTS): $(CSOURCES) $(CHEADERS)
	@echo "=> Compiling fastpbkdf2 sources"
	@echo "(CC) $?"
	@$(CC) $(CFLAGS) $(CLIBS) $< -o $@

openmp: CXXFLAGS += -fopenmp -DWITH_OPENMP
openmp: CXXLIBS  += -fopenmp
openmp: CFLAGS   += -fopenmp -DWITH_OPENMP
openmp: default
	@echo "WITH OPENMP"

clean:
	@rm -rfv *.o */*.o $(SHARED_LIB) $(CXXTARGET)
	@echo "=> Cleaning done"

Спасибо за внимание, всем добра!