![]() ![]() We will first see an example of a good password generation method, to explain after why the method used by Kaspersky was flawed, and how we exploited it. As we will see, passwords generated by this tool can be bruteforced in seconds.Īfter a bit less than two years, this vulnerability has been patched on all versions of KPM. Vulnerability has been assigned CVE-2020-27020. Generating robust passwords from a charsetįor the sake of simplicity, let’s study how passwords are generated in KeePass, an open source project. Password generation is implemented in various classes in the namespace. KeePass provides 3 methods to generate a password: a charset-based, a pattern-based and a custom generation method. ![]() Internal ulong GetRandomUInt64 ( ulong uMa圎xcl ) dx \\ Here is the main loop responsible for the password generation: The simpler method is the charset-base generator, which creates a password from a given charset. The distribution of this function is not uniform: lower positions have more chances to occur than values near from 1. How is created the charset? Is it fully ordered, like “abcdefghij…”? No… Such method is quite puzzling, but it seems it is exactly what KPM wanted to implement.For the first three chars, charset is fully ordered (almost… we will see that later).Then, for the next chars, KPM relies on letter frequency: it assumes least frequent letters (in some language) should appear more often in the generated password.The supposed frequency of apparition of each letter, as used in KPM, is shown in the graph below: Then, charset is ordered according to the inverse frequency of appearance of each letter: q, x, z, w… n, a, e.Īs lower values are more likely to appear given the distribution function, we can assume some chars like “q” and “x” are much more likely to appear in passwords generated by KPM. If these stats were taken independently to generate every char of a password, we could see often several “q”, “x” or “z” in the passwords. However, things are more complex: generated chars are taken into account in the computation of the frequencies of appearance. If a “z” is generated, then the probability of appearance of “z” in the frequency table will be strongly increased. Once the charset is ordered according to this table, “z” will be at the end of the table, and will have much less changes to be taken. These changes also affect other letters: after “z” has been picked, the probability of “a”, “e”, “m”, “q”, “s” and “x” has also increased. But, after “h” is picked, its probability of appearance will then increase a lot. Our hypothesis is that method has been implemented to trick standard password cracking tools. ![]() ![]() Password crackers such as Hashcat or John the Ripper try to break first probable password, e.g. Their password cracking method relies on the fact that there are probably “e” and “a” in a password created by a human than “x” or “j”, or that the bigrams “th” and “he” will appear much more often than “qx” or “zr”.ĭedicated techniques such as Markov generator, which assume that there is a hidden Markov model in the way passwords are generated by humans, can directly break this method of generation (see Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff for more details). ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |