Bruce Schneier on password matching algorithms
Bruce Schneier, in his author's column in Wired, talks about the offline brute force attack. This method is used very often, although in some situations it is unsuitable, for example, for selecting a pin-code in an ATM.
Programs for offline selection of passwords have become faster and more intelligent than ever. AccessData's Password Recovery Toolkit (PRTK) is able to check up to several hundred thousand passwords per second, and it checks the most obvious passwords first.
Thus, password security depends on two factors: the ability of the system to slow down the search for passwords and whether the password is “more obvious” from the point of view of a hacker program.
The speed of selecting a password directly depends on how this password is processed by the program. A good program does not use a password as a cryptographic key, but converts a password into a cryptographic key. In this case, it can slow down the process of checking the password for an arbitrarily long time.
')
Different programs show completely different results in this regard. For example, the password check for Microsoft Office applications is so primitive that the PRTK utility is capable of checking up to 350 thousand variants per second (on a Pentium 4 processor with a frequency of 3 GHz). The password for WinZip 7.0 is even easier to choose: this program allows you to check more than a million passwords per second. For comparison, in the ninth version of WinZip, the cryptosystem was significantly improved, so that the brute force speed dropped to 900 per second. The same "tough nut" for PRTK is the PGP program.
For a password of six English-language characters (without numbers) in one register, the number of variants during the search is more than 308 million combinations: from “aaaaaa” to “zzzzzz”. However, the smart PRTK program does not go through all the combinations in a row.
Eric Thompson of AccessData (developer of PRTK) explains that a typical password consists of a root and a prefix. The root of the password is, if not a dictionary word, then, usually, something pronounced. The prefix is ​​either a suffix after the root (in 90% percent of cases) or a prefix before the root (10%).
First of all, the PRTK program checks the base of about a thousand of the most common passwords , such as “password1”, “123456”, etc. After that, the program checks them in combination with hundreds of the most common prefixes (“1”, “69”, “abc”, etc.). This simple check allows you to successfully determine 24% of all passwords in just 100 thousand combinations.
At the second stage, the program checks the extended set of roots and suffixes. 5.000 of the most common words, 10,000 names, an additional dictionary of 100,000 elements and a dictionary of phonemes (0.01% of the theoretically possible set of combinations) are being tested. Markov models known in linguistics are used to generate phonemes. In addition, PRTK checks all of the above options, but with frequently occurring character substitutions, for example, “O” for “0”, “S” for “$”, etc.
The prefix dictionary includes all combinations of two and three numbers, dates from 1900 to 2006, single characters, character combinations and numbers, all combinations of two characters.
Typically, the PRTK program is run on a computer network. Large structures like the CIA or the FBI can run a task on hundreds or thousands of computers at the same time. Moreover, Tableau has already launched additional FPGA consoles, which speed up the search for “slow” programs, such as PGP and WinZip. Acceleration can be 150-300 times.
According to Eric Thompson, in two to four weeks of work, his program hacks from 55% to 65% of all passwords. And this is without the slightest use of social engineering, that is, without knowing anything about the user.
Based on the foregoing, it is possible to understand what an ideal password should be, so that it cannot be guessed by brute force. You can advise users to insert the prefix in the middle of the root, or select two roots, use both upper and lower case characters in the middle of the password, words of the greatest possible length, unusual prefixes.
Of course, the password can not be stored anywhere in the clear. Another Forensic Toolkit program from AccessData is designed to scan all files on the local network (email, instant messaging history, paging file) to find all the words mentioned there. From these words an additional dictionary is compiled. By the way, the computer's operating system stores the passwords in the RAM in open form and at any time can write this chunk of memory to the hard disk. Any password that you enter on the keyboard can go there.
Programs for offline selection of passwords have become faster and more intelligent than ever. AccessData's Password Recovery Toolkit (PRTK) is able to check up to several hundred thousand passwords per second, and it checks the most obvious passwords first.
Thus, password security depends on two factors: the ability of the system to slow down the search for passwords and whether the password is “more obvious” from the point of view of a hacker program.
The speed of selecting a password directly depends on how this password is processed by the program. A good program does not use a password as a cryptographic key, but converts a password into a cryptographic key. In this case, it can slow down the process of checking the password for an arbitrarily long time.
')
Different programs show completely different results in this regard. For example, the password check for Microsoft Office applications is so primitive that the PRTK utility is capable of checking up to 350 thousand variants per second (on a Pentium 4 processor with a frequency of 3 GHz). The password for WinZip 7.0 is even easier to choose: this program allows you to check more than a million passwords per second. For comparison, in the ninth version of WinZip, the cryptosystem was significantly improved, so that the brute force speed dropped to 900 per second. The same "tough nut" for PRTK is the PGP program.
For a password of six English-language characters (without numbers) in one register, the number of variants during the search is more than 308 million combinations: from “aaaaaa” to “zzzzzz”. However, the smart PRTK program does not go through all the combinations in a row.
Eric Thompson of AccessData (developer of PRTK) explains that a typical password consists of a root and a prefix. The root of the password is, if not a dictionary word, then, usually, something pronounced. The prefix is ​​either a suffix after the root (in 90% percent of cases) or a prefix before the root (10%).
First of all, the PRTK program checks the base of about a thousand of the most common passwords , such as “password1”, “123456”, etc. After that, the program checks them in combination with hundreds of the most common prefixes (“1”, “69”, “abc”, etc.). This simple check allows you to successfully determine 24% of all passwords in just 100 thousand combinations.
At the second stage, the program checks the extended set of roots and suffixes. 5.000 of the most common words, 10,000 names, an additional dictionary of 100,000 elements and a dictionary of phonemes (0.01% of the theoretically possible set of combinations) are being tested. Markov models known in linguistics are used to generate phonemes. In addition, PRTK checks all of the above options, but with frequently occurring character substitutions, for example, “O” for “0”, “S” for “$”, etc.
The prefix dictionary includes all combinations of two and three numbers, dates from 1900 to 2006, single characters, character combinations and numbers, all combinations of two characters.
Typically, the PRTK program is run on a computer network. Large structures like the CIA or the FBI can run a task on hundreds or thousands of computers at the same time. Moreover, Tableau has already launched additional FPGA consoles, which speed up the search for “slow” programs, such as PGP and WinZip. Acceleration can be 150-300 times.
According to Eric Thompson, in two to four weeks of work, his program hacks from 55% to 65% of all passwords. And this is without the slightest use of social engineering, that is, without knowing anything about the user.
Based on the foregoing, it is possible to understand what an ideal password should be, so that it cannot be guessed by brute force. You can advise users to insert the prefix in the middle of the root, or select two roots, use both upper and lower case characters in the middle of the password, words of the greatest possible length, unusual prefixes.
Of course, the password can not be stored anywhere in the clear. Another Forensic Toolkit program from AccessData is designed to scan all files on the local network (email, instant messaging history, paging file) to find all the words mentioned there. From these words an additional dictionary is compiled. By the way, the computer's operating system stores the passwords in the RAM in open form and at any time can write this chunk of memory to the hard disk. Any password that you enter on the keyboard can go there.
Source: https://habr.com/ru/post/4947/
All Articles