The tale of total brute force, or the tormenting wait of the decrypt

Greetings to the inhabitants of Habr!

So, new “cryptographic games” have come to my soul. Therefore, today we will talk about a boring exercise, focused on a complete brute force search, the implementation of trivial multi-threaded brutere by C ++ and OpenMP, as well as a brief use of the crypto-library CryptoPP and third-party fastpbkkdf2 module (for C and Plus) in our projects.

Go under the cat, cookies out there!

')

DISCLAIMER. It is impossible to go through other people's passwords, you cannot read texts addressed to you, it is impossible to create and distribute malicious software with the purpose of illegal access to computer information. Punishable under the Criminal Code. Dixi.

Parsing conditions

The real task wrapper is a small card with the following text:

SGFzaGVkU2FsdCg4Ynl0ZXNJblVURjE2TEUpQ291bnRlckNpcGhlcnRleHRB
RVMyNTZFQ0J8MWE0MDhhYTVhZjkzMDkxOGRkYjkyNzQ3NDBhMDJjMmJkM2Vl
N2NkNjU3MDQwMDAwMDQxN2E2Nzc4Yzc3YzYwZjcxMGJlNTNiNmViODQ0ZDg0
MmUwZWEwZGYwNDA2NTU4NWEzMzIzYTUwZjc2OGY1N3xQb3NzaWJsZVBhc3N3
b3JkUGF0dGVybnN8RERMTExMTEx8RExMTExMTER8TExMRERMTEx8TExMTExM
REQ=

Why in Base64? The teacher responded to this: "So that the options for the conditions do not have to be chosen". Not really wanted. Also, the information about the password-to-key conversion algorithm used (PBKDF2_HMAC_SHA1) was transmitted in words and the simple game conditions were formulated: “Choose a password to recover a message encrypted with a block cipher. The password is not vocabulary, it may consist of numbers and small letters of the Latin alphabet, salt - only from small letters. ” Let's see what the encoding hides:

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

What do we see? The first part of the message (before the first vertical slash) probably consists of the order of the data directly specified in the second part: the hash value of the salt (with encoding information in brackets), the iteration counter for PBKDF2, the block cipher used and the encryption mode. AES got to me and here, who would have thought ... The third part to the end - the potential masks of the desired password, where L is the letter (letter), D is the digit (digit). It is also determined that the password consists of 8 characters. It seems logical, now it would be nice to structure the information received.

Let's analyze the second message block. In the task there is no information about the salt hashing function used, so we will assume that this is SHA1, since this is the only widely used cryptographic hash function with an output length of 20 bytes (only this size fits the rest of the partition ideally). Also, it is obvious that the counter is represented in little endian , at least I really want to think so, because 0x57040000 = 1459879936 iterations of PBKDF2 is not the best prospect for iteration ... And finally, there are two AES blocks of 16 bytes each. Therefore, we have the following picture:

1A408AA5AF930918DDB9274740A02C2BD3EE7CD6 - salt hash (20 bytes);
0x00000457 = 1111 - iteration counter PBKDF2;
0417a6778c77c60f710be53b6eb844d8 - the first ciphertext block (16 bytes);
42e0ea0df04065585a3323a50f768f57 - the second ciphertext block (16 bytes).

Salt reduction

Okay, for starters, we will write a quick-script cattle for salt recovery. Fortunately, 4 characters (aka 8 bytes in UTF-16) will move in seconds, so we'll use Python without further ado:

 #!/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')) 

After 3 seconds, we have the result: " dukg ". Taking into account the 2-byte encoding, the final salt form (suitable for input into PBKDF2) will have the form " d \ x00 u \ x00 k \ x00 g \ x00 ".

Cryptographic needs

Now we have to choose the tools for working with cryptography. In order: first think about getting the key from the password, then decrypting the message. To solve both questions, two possible options immediately come to mind: OpenSSL or Crypto ++ (aka CryptoPP). Both packages are widely known and it is not difficult to work with them on C ++ (the choice of language came by itself based on the need for high search speed).

Key generation

Looking ahead a bit, it’s worth mentioning that the standard function PKCS5_PBKDF2_HMAC_SHA1 from OpenSSL at a given counter in 1111 iterations showed an average speed of 1000 keys / s when running in parallel on a 4-core Intel Core i5 2.60GHz. Not the best result, therefore, it was decided to look for an alternative “pumped” solution for key generation. This solution was the third-party fastpbkdf2 library. The library is based on the same OpenSSL (implementations of the hash functions themselves from there), however, as described, uses “various optimizations in the internal for loop” when calculating PBKDF2. This explanation suits me perfectly, besides, the productivity has increased by about 3.45 times: now the search goes at a speed of 3450 passwords / s.

The module is written in C and requires a compiler that supports C99, so to embed it (module) in the project on Pluses, compile from source and create a dynamic library like:

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

And now to launch the final brutera (which we haven’t written yet, but have already come up with the original name for it - “ bruter.cxx ”), you will need to feed him this library by writing:

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

At the end, add a Makefile for automation. Let us now estimate how the validity of the password will be checked:

 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; } 

where CryptoPP_Decrypt_AES_256_ECB is a decryption function not written yet. The return value is true / false , depending on the outcome of the test of the criterion. The criterion of the correct decrypt is the printability of all the characters of the plaintext, the evaluation of the criterion lies on the isPrintable function (see full listing in the Conclusion).

Message decryption

To decrypt the message, contact the Crypto ++ library for help.

Following the order of working with block ciphers within this package, we perform the following actions: create a functional object to decrypt AES in ECB mode (decryptor), initialize it with a key (the key size determines the AES version - in our case AES-256), assign the output buffer and Perform the operation of converting the ciphertext into plaintext using the algorithm that contains decryptor. We also assume that the blocking of the block ( PADDING ) was not used at all, because the condition is silent on the format of the blocking. Therefore, the length of the original message must be a multiple of the length of one AES block.

 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(); } 

Return function will be the length of the decrypted message.

New information

So far during the day I was busy with the preparatory work described above, a letter from the author arrived at the post office saying that "a new information has come up about the password structure". In general terms, it was reported that when creating a passphrase, the user mistakenly held Shift while entering the unit and the letter " q ". Paraphrasing the message, we get the character " ! " (In place of the number) and the letter " Q " (in place of the letter), as guaranteed components of the password. For the user, the news is not the best, but for us it is simply wonderful: this implies a significant narrowing of the search area. We will conduct a numerical evaluation of the advantage, which was so well received, a little later, when we estimate the time required for a complete search.

Parallel bruter

Things are going well: it remains to write the control function and enter the element of multithreading. For parallelization of computations, we will use OpenMP pragmas. The total number of passwords for enumeration is a known value. For example, consider one of the four password models (given that one of the numbers is actually “!”, And one of the letters is “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$$

The first two brackets are the number of placements with repetitions from 26 to 5 and from 10 to 1, respectively (5 letters and 1 digit), the factors in the third brackets are the permutation "!" (can stand in two positions) and shift “Q” (can stand in six positions). We define the full search area by multiplying the result by 4, getting $$$\ approx5.7 * 10 ^ 9$or 5.7 billion

Since the boundaries of the area are defined, to generate passwords, we use nested for loops and the omp parallel for pragma with the collapse () parameter to “collapse” multiple loops into one big loop. It must be remembered that in order to use collapse () , it is necessary to maintain the “perfect nesting” of cycles. This means that each next cycle (except the last, of course) contains only the next for statement, and all operations are performed in the last nested cycle.

Also, before starting to write the code, let's pay attention to an interesting feature: each following password model is a cyclic shift by 1 or 3 positions of another model. Taking this into account, we can more easily organize the search of passwords from each model for one iteration of the cycle:

 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; } } } 

The notFinished flag notFinished used to exit for . This approach is more peculiar to working with pthread directly, OpenMP has #pragma omp cancel for this, but the compiler bombarded me with warnings, the nature of which is not completely clear to me, so it was decided to use the flag.

Now let's look at the performance of the resulting system and estimate the time required for a full brute force.

Performance evaluation and search for more power

As mentioned above, with parallel operation on a 4-core Intel Core i5 2.60GHz, a speed of approximately 3450 passwords / s was achieved. Only 5.7 billion passwords, hence simple calculations give an estimate of 19 days for the machine to work, provided that the password we need is the last of many. Not the best perspective.

It's time for a little cheating. Let's use the well-known Amazon EC2 cloud computing service. Select an instance for computing with the CPU advantage (the characteristics are shown in the screenshot below) and see the performance.


By raising the number of threads from 4 to 36 (+ more nimble server processes), we received a 10-fold increase in speed even despite the slowdown of the service due to the recent rollback of anti-Meltdown patches. Having raised two instances of such virtual locks at a spot price of $ 0.37 / h, we will be able to sort through the whole set in 24 hours, laying out $ 17.76 (or about 1 thousand rubles according to the current status of the course). Not a cheap pleasure for a learning task, but sports interest has won, so I am ready to share the results.

But first of all, for the sake of interest, we’ll see how much time it would take if “additional information on user’s errors during input would not“ suddenly surface ”. In this case, the power of the total set of passwords would be written as:

$$

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

Therefore, for a full bust at a speed of 3450 p / s, it would take more than a year when using a computer on the processor indicated at the beginning of the section in multi-threaded mode and more than four years when working in one thread [from the "Horror of Our Town" cycle].

results

Recovered password: " ldQ9!nwd ".
Open text: 2E2B2A602A2B2C20594F552044495341524D4544204D4521202C2B2A602A2B2E .
Message: ". + *` * +, YOU DISARMED ME!, + * `* +.".

The decrypt was received in just over 1/2 day. With the approach used with shifts of one password model relative to others, the following picture was obtained: the iteration turned out to be successful when the “ 9! NwdldQ ” combination was generated first (from the $$$DDLLLLLL$), and after three cyclic shifts to the left, the required password went to check.

Conclusion, source codes

The new year was marked by a rather unusual experience for me, thanks to the author for a balanced game;)

The full code of the bruther under the spoiler:

Makefile code, as promised, under the second spoiler:

Thank you for your attention, all good!