A complete brute force attack

 Now let's focus on a radical way to open the encryption key or password.

          Let's assume that the author avoided common implementation errors and did not provide the cracker with either the key (password) in plain text, or comparison commands and explicit conditional transitions. In addition, the password is chosen according to all the rules and cannot be selected "manually". In this case, the hacker will try to iterate through all possible passwords.

          A few years ago, the power of computers made it possible for the authors of the protections to declare that a complete search of passwords / encryption keys is impossible due to the huge number of possible passwords /keys. Even now, to demonstrate the effectiveness of the protection system, the power of many keys (passwords) is cited, and the reliability is confirmed by the length of the key.

"According to Bruce Schneier, an attack on a 128-bit key requires 4.2 x 1022 processors with a capacity of 256 million encryption operations per second. In this case, the key will be hacked in 1 year. The cost of such a number of processors by 2000 is estimated at 3.5 x 1024 dollars" [25].

      "The RSA method is absolutely reliable. Even when using MailSafe (a product based on RSA technology) in the lowest level of secrecy mode, it will take about 10 years of operation of the Gray-1 supercomputer to "crack" the cipher. If it is necessary to achieve a high level of secrecy, MailSafe can use a 700-bit key instead of a 400-bit one. This will slow down the encryption process by 5 times, and decryption on Gray (by trial and error) will take 36 million years" [26].

But modern computer capacities and the latest computing technologies, for example, using computer clustering, allow for a complete search of even sufficiently long passwords within an acceptable period of time[2].

Experiments with hacking the famous cryptographic standard of the USA - DES-algorithm (Data Encryption Standart) are widely known. The 56-bit key of the DES algorithm was undisclosed for about twenty years. "... it fell on June 17, 1997, 140 days after the start of the competition (about 25% of all possible keys were tested and ≈ 450 MIPS years were spent[3]"[24]. In 1998, a report appeared about the hacking of the DES algorithm in 56 hours [19].

The RSA algorithm first encountered a sharp jump in computing performance, for the opening of which it is necessary to solve the factorization problem. In March 1994, the factorization of a number of 129 digits (428 bit6), which lasted for 8 months, was completed. 600 volunteers and 1,600 machines connected via e-mail were involved in this. The machine time spent was equivalent to about 5,000 MIPS-years [24].

 
On January 29, 1997, RSA Labs announced a competition to open the symmetric RC5 algorithm. The 40-bit key was opened 3.5 hours after the start of the competition! (This did not even require connecting computers via the Internet - a local network of 250 machines at Berkeley University was enough). After 313 hours, the 48-bit key was also opened [ 24].

 
Even a novice programmer can write a program that builds all possible sequences of characters from a given sequential enumerable set. Obviously, the calculation of the author of the defense should be based on the fact that a complete search takes a period of time beyond the reasonable. And the first thing that developers use for this is to increase the length of the key (password). In their own way, they are right. But

Firstly, as already noted, the power of computers is growing, and if a full search required a long period of time yesterday, the time that the computer will need tomorrow will most likely be acceptable to remove protection.

Due to the sharp increase in computing power, brute force attacks have a much better chance of success than before. If for the UNIX system the crypt() function, which is responsible for hashing passwords, was implemented in such a way that it was performed for almost 1 second on a PDP-class machine, then in twenty years the speed of its calculation increased 10,000 times (!). Therefore, if earlier hackers (and developers who limited the password length to 8 characters) and they could not imagine a complete bust, but today such an attack will lead to success in 125 days on average [24].

 
Secondly, effective algorithms (usually based on formal logic and using set theory, probability theory and other areas of mathematics) have already been proposed and can be improved to increase the speed of iteration. In addition, fast search algorithms are also used. (For example, it is proposed to use self-organizing tabular search to attack RSA and similar systems.)

Moreover, special equipment has already been created that performs the functions of brute force.

It is important to note that storing the password hash function does not exclude the possibility of a complete search, but only changes the time required for hacking. Indeed, now the program that performs password brute force must be supplemented by calculating the hash function of each option and comparing the result with the hash standard.

Let's pay attention to another circumstance related to password hashing protection. Some hash functions may return a result that matches the original, and for an incorrect password. To remove the protection in this case, it is enough to find any suitable password, which obviously weakens the protection and reduces the cost of hacking. (This property is possessed by hash functions that give a result comparable in length (in bits) to a password.)

Let's focus on another type of password brute force technique - the so-called dictionary attack. This is a method by which you can open a meaningful password. The method is based on the fact that the user selects an existing (dictionary) word in some language for easier memorization. Considering that there are no more than 100,000 words in any language, it is obvious that a complete search of vocabulary words will occur within a short period of time.

There are now widespread programs that select passwords based on dictionary words. Now only an irresponsible or lazy user can choose a meaningful password. Recall that, in addition to checking the dictionary, such programs "know how" to change the case of characters, "know" punctuation marks, "guess" that the user can flip a word, glue two words using a punctuation mark or a number, etc. transformations.

It is noteworthy that modern advanced means of protection against unauthorized access, allowing the user to independently choose a password for access, are equipped with modules that verify the selected password for belonging to such dictionaries and do not allow the password to be used in this case.

Programs that carry out dictionary attacks work quite quickly, as they implement effective search and comparison algorithms. For example, they do not use slow string comparison, but checksum comparison, etc. Many of them do not even contain a database of words, but use dictionaries built into common text editors.

Let's draw conclusions and give some recommendations for strengthening protection.

* Password protection should be used in cases where either a brute force attack will be ineffective, or an attacker will obviously not have access to sufficiently powerful computing tools to perform a complete brute force (we must not forget about the possibility of using network technologies).

* To enhance password protection, you should use any original techniques that reduce the speed of password brute force.

* You can slightly strengthen password protection by performing two (dependent) checks in the program: both the password and the result of the password hash function, while at the same time "hiding" the protective mechanism at the proper level, or, at least, abandoning direct comparison. At the same time, it is advisable to specifically select a hash function that gives a large number of passwords suitable for the hash standard. With this implementation of the security mechanism, the attacker will need to attack two parameters.

* Protection works even more effectively if the password (or better yet, the password function) serves as the encryption key for some part of the program code. In this case, the hacker will have to decrypt the code after going through all possible passwords (giving the specified hashing result).

!

Note that in this type of protection, that is, when checking several parameters at the same time, the hash function, which gives the desired result for a large number of passwords, significantly complicates hacking.