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

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

    Итак, новые «криптографические игрища» пришли по мою душу. Поэтому сегодня поговорим о занудном упражнении, ориентированном на полный перебор паролей, реализации тривиального многопоточного брутера силами 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 байт).

    image

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


    Окей, для начала напишем быдлобыстро-скрипт для восстановления соли. Благо, 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) будет иметь вид "d\x00u\x00k\x00g\x00".

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


    Теперь предстоит выбрать инструменты для работы с криптографией. По порядку: сперва подумаем о получении ключа из пароля, затем о расшифровании сообщения. Для решения обоих вопросов сразу на ум приходят два возможных варианта: 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»):

    $|DDLLLLLL|=|\boldsymbol{!}D\boldsymbol{Q}LLLLL|=\widehat{A}^5_{26}*\widehat{A}^1_{10}*2*6=$

    $=(26*26*26*26*26)*(10) * (2*6)=26^5*120\approx1.43*10^9$


    Первые две скобки — количество размещений с повторениями из 26 по 5 и из 10 по 1 соответственно (5 букв и 1 цифра), множители в третьих скобках — перестановка "!" (может стоять на двух позициях) и перестановка «Q» (может стоять на шести позициях). Полную область перебора определим, домножив результат на 4, получая $\approx5,7*10^9$ или 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', '\0'
    	};
    
    	uint8_t num[11] = {
    		'0', '1', '2', '3', '4', '5', '6', '7',
    		'8', '9', '\0'
    	};
    
    #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] = '\0';
    			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. Выберем инстанс для вычислений с ЦПУ-преимуществом (характеристики приведены на скриншоте ниже) и посмотрим производительность.

    image

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

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

    $|DDLLLLLL|*4=\widehat{A}^6_{26}*\widehat{A}^2_{10}*4=(26*26*26*26*26*26)*(10*10)*4\approx1.24*10^{11}$


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

    Результаты


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

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

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


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

    Полный код брутера под спойлером:
    bruter.cxx
    /**
     * @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] = { '*','*','*','*','*','*','*','*', '\0' };
    	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++] = '\0';
    	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', '\0'
    	};
    
    	uint8_t num[11] = {
    		'0', '1', '2', '3', '4', '5', '6', '7',
    		'8', '9', '\0'
    	};
    
    #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] = '\0';
    			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;
    }
    


    Код мейкфайла, как обещано, под вторым спойлером:
    Makefile
    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"
    


    Спасибо за внимание, всем добра!
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 18

      +5
      Это где такие задачки задают?
        0

        Мне тоже интересно.

          –1
          «Лабораторная» в вузе)
            0

            А вуз, вуз какой?! У меня дочка поступать будет в следующем году!

          –1
          В Пайтоне вложенные циклы изящней получаются с использованием itertools.product()
            0
            Будьте добры, перепишите код на Python c использованием itertools (https://docs.python.org/2/library/itertools.html).

            Взамен смогу предоставить 2683v4x2 + 6380x2 для тестов (32 Gb RAM DDR3 и DDR4, OS увы Windows)

            Буду Вам признателен.
          0
          Не понял выражения из начала секции «Параллельный брутер»:

          ...=26^5*120 ~1.
          Где ~ приблизительно равно.
            0
            … = 26^5 *120 ~ 1.43 * 10^9 — формула не отрисовалась до конца
            0
            Код лексикографического перебора таким ужасным делать пришлось из-за #omp parallel for?
              0
              Тело цикла действительно нелицеприятное. Как было сказано, для #omp parallel for collapse(8) необходимо условие «идеально вложенных» циклов, поэтому пришлось выкручиваться.
                0
                Да нет, претензии не к телу цикла, а к 8 вложенным. Для пароля длины 32 у вас бы такой же алгоритм перебора был?
                  0
                  Не понимаю недовольства — полный перебор на то и полный, чтобы проходить по каждому элементу множества От и До, и вложенные for в такой ситуации отлично с этим справляются. Что касается 32-символьных паролей, вообще не понял к чему этот вопрос. Мало того, что пароли длины 11 и выше уже не поддаются перебору при ряде условий, так еще и описанный алгоритм рассматривается в рамках конкретной задачи, где длина строго 8.
                    0
                    Для того, чтобы перебрать все последовательности длины N, не требуется N вложенных циклов. Поскольку все остальное написано хорошо, то я попытался найти логичное объяснение такому коду. Вроде бы подходил вариант с ограничениями openmp, поэтому и спросил.
                      0
                      Мне подход с вложенными for видится естественным. Дело не в openmp, при желании можно обойтись и одним циклом (что собственно и делает collapse()). Но зачем, если так проще, легче читается и на производительности не сказывается?
                        0
                        Дело в алгоритмизации. Перебор всех строк фиксированной длины над фиксированным алфавитом — это отдельная первокурсная задачка, без ключевого слова «пароль» и громких слов о 100500 тысячах лет на проверку, ежели не 8. И 8 тут — всего лишь параметр, а перебор должен работать, если вместо 8 поставить N. Без изменения кода. И нет, 8 вложенных циклов не выглядят естественными (впрочем, один — тоже).
                          0
                          Алгоритмизация — это, бесспорно, хорошо и правильно. Только тут дело не в ней. Обратите внимание, я не выпускаю конечный продукт а-ля «Переборщик паролей любой длины на все случаи жизни» — я всего лишь прохожу путь решения конкретной задачи с фиксированными входными данными (речь в которой, к тому же, идет о переборе не всех строк указанной длины над алфавитом, а лишь тех, которые удовлетворяют маске). В условиях ограниченного времени, отведенного на решение, мне все же видится естественным использование цикла for (при учете того, что существует #omp parallel for!), нежели чем попытки эффективно распараллелить первокурсные задачи по типу «Выпиши все префиксы длины N над данным множеством». Если вы об этом спрашивали в своем первом комментарии, то да — код именно такой в том числе и из-за #omp parallel for.

            Only users with full accounts can post comments. Log in, please.