Kaspersky Password Manager: All your passwords are belong to us

[aum]

 

tl;dr: The password generator included in Kaspersky Password Manager had several problems. The most critical one is that it used a PRNG not suited for cryptographic purposes. Its single source of entropy was the current time. All the passwords it created could be bruteforced in seconds. This article explains how to securely generate passwords, why Kaspersky Password Manager failed, and how to exploit this flaw. It also provides a proof of concept to test if your version is vulnerable.

 

The product has been updated and its newest versions aren’t affected by this issue.

Introduction

Two years ago, we looked at Kaspersky Password Manager (KPM), a password manager developed by Kaspersky. Kaspersky Password Manager is a product that securely stores passwords and documents into an encrypted vault, protected by a password. This vault is protected with a master password, so, as with other password managers, users have to remember a single password to use and manage all their passwords. Product is available for various operating systems (Windows, macOS, Android, iOS, Web…) Encrypted data can then be automatically synchronized between all your devices, always protected by your master password.

 

The main functionality of KPM is password management. One key point with password managers is that, contrary to humans, these tools are good to generate random, strong passwords. To generate secure passwords, Kaspersky Password Manager must rely on a secure password generation mechanism. 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.

 

After 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

For 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 KeePassLib.Cryptography.PasswordGenerator namespace. KeePass provides 3 methods to generate a password: a charset-based, a pattern-based and a custom generation method.

 

The simpler method is the charset-base generator, which creates a password from a given charset. Let see how it works. Here is the main loop responsible for the password generation:

PwCharSet pcs = new PwCharSet(pwProfile.CharSet.ToString());
if(!PwGenerator.PrepareCharSet(pcs, pwProfile))
    return PwgError.InvalidCharSet;

char[] v = new char[pwProfile.Length];
try
{
    for(int i = 0; i < v.Length; ++i)
    {
        char ch = PwGenerator.GenerateCharacter(pcs, crsRandomSource);
        if(ch == char.MinValue)
            return PwgError.TooFewCharacters;

        v(i) = ch;
        if(pwProfile.NoRepeatingCharacters) pcs.Remove(ch);
    }
    ...
}

The GenerateCharacter method is called to generate every single character from the password. It takes a charset and a random source, and outputs a random character from the charset. Its implementation is rather straightforward:

internal static char GenerateCharacter(PwCharSet pwCharSet,
                                       CryptoRandomStream crsRandomSource)
{
    uint cc = pwCharSet.Size;
    if(cc == 0) return char.MinValue;

    uint i = (uint)crsRandomSource.GetRandomUInt64(cc);
    return pwCharSet(i);
}

Finally, GetRandomUInt64 is a uniform random number generator that outputs values between 0 and cc - 1:

internal ulong GetRandomUInt64(ulong uMaxExcl)
{
    if(uMaxExcl == 0) { Debug.Assert(false); throw new ArgumentOutOfRangeException("uMaxExcl"); }

    ulong uGen, uRem;
    do
    {
        uGen = GetRandomUInt64();
        uRem = uGen % uMaxExcl;
    }
    while((uGen - uRem) > (ulong.MaxValue - (uMaxExcl - 1UL)));
    // This ensures that the last number of the block (i.e.
    // (uGen - uRem) + (uMaxExcl - 1)) is generatable;
    // for signed longs, overflow to negative number:
    // while((uGen - uRem) + (uMaxExcl - 1) < 0);

    return uRem;
}

What is important here is that each character is generated independently from the other ones: every character is random, and knowing which character has been generated before does not give us information about the next char that will be generated.

 

Finally, let’s assume GetRandomUInt64 is cryptographically strong, and generates a random 64-bit number. Why is there a loop here, and why does this function is not simply implemented as return GetRandomUInt64() % uMaxExcl;?

Uniform random number generation

This loop is essential to uniformly generate numbers in a range.

 

Imagine you want to get a random char from a charset of 10 possible chars, and you have a random number generator method GetRandom32 which outputs number between 0 and 32 (32 excluded). The straightforward way to output such char would be:

const string charset = "0123456789";
return charset[GetRandom32() % 10];

Let’s see how characters are generated:

 

• “4” is returned if GetRandom32() returns 4, 14 or 24 (3 possible values)
• “5” is returned if GetRandom32() returns 5, 15 or 25 (3 possible values)
• But “1” is returned if GetRandom32() returns 1, 11, 21 and 31 (4 possible values!)

 

The distribution is given below:

So there is a bias with this method: as one can see from the outputs, digits 0 and 1 will be output more frequently than the other ones. It is commonly called the “modulo bias”. You should check the excellent Definitive guide to “modular bias” and how to avoid it, by Kudelski Security, for more information.

 

To remove this “modulo bias”, a common method is to discard all the numbers greater than or equal to 30 (the biggest multiple of 10 lower than 16):

const string charset = "0123456789";
do {
    uGen = GetRandom32();
} while (uGen >= 30);
return charset[uGen];

This is exactly what KeePass does, though the bias in KeePass would be much less significant than in the current example, because the GetRandomUInt64 generates values much bigger than the size of the password character set.

 

We saw how to uniformly select a character from a given range of characters, assuming our random source is uniform. Let’s see now what kind of source is suitable to generate cryptographically strong random numbers.

Cryptographically secure PRNG

Generated numbers must be random. But what does that mean exactly? An ordinary good PRNG will pass a series of tests, mainly statistical randomness tests such as Diehard or Dieharder tests.

 

A cryptographically secure PRNG (CSPRNG) will also pass those tests, but it also has two other requirements:

 

• It must satisfy the next-bit test. Knowing all the bits already generated by a CSPRNG, there is no polynomial-time method that will predict the next bit with a probability higher that 0.5.
• If, at any moment, the whole state of the CSPRNG is compromised, there is no way to retrieve the bits previously returned by the CSPRNG.

 

These points are essential for password generation. For example, if a password has been compromised for some reason, and if a non-CSPRNG has been used to generate this password, an attacker could then be able to retrieve the other password generated using this PRNG. Most operating systems provide CSPRNG implementations: CryptGenRandom on Windows, or /dev/random on UNIX-like operating systems.

 

Some software prefer to use their own implementation, often seeded, fully or partially, by the operating system PRNG. KeePass uses two PRNG, based either on Salsa20 and ChaCha20, and a legacy one based on a variant of ARCFour. Let’s assume the first two PRNG are cryptographically secure: we have now all the elements to generate random, secure passwords from a given charset.

Kaspersky’s Password Generation Method

Kaspersky Password Manager has a built-in password generator, which creates password from a given “policy”. The policy settings are simple: password length, uppercase letters, lowercase letters, digits, and a custom set of special chars. All these settings can be configured in the Password generator interface, as shown here (this is the standard setting):

 

 

By default, KPM generates 12-character passwords with an extended charset.

Tricking the frequency of appearance

The generation procedure is much more complex than the Keepass method. KPM first picks two random floats r1r1 and r2r2 between 0 and 1, and multiplies them with the length of the password charset to pick a value in the charset table:

charset = ...  # character set to use r1 = random.random()
r2 = random.random()
pos = r1 * r2 * len(charset)
return charset[pos]

The distribution of r1×r2r1×r2 is (thanks to MathWorld😞

P[r1r2=a]=====∫10∫10δ(xy−a)dydx∫10∫x−a−aδ(z)1xdzdx∫101(x≥a)1xdx∫1a1xdx−ln(a)P[r1r2=a]=∫01∫01δ(xy−a)dydx=∫01∫−ax−aδ(z)1xdzdx=∫011(x≥a)1xdx=∫a11xdx=−ln(a)

 

Let’s plot it:

The distribution of this function is not uniform: lower positions have more chances to occur than values near from 1. Such method is quite puzzling, but it seems it is exactly what KPM wanted to implement.

 

How is created the charset? Is it fully ordered, like “abcdefghij…”? No…

 

• 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.

 

As 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. On the contrary, “h” has decreased. 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. passwords generated by humans. 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”.

 

Dedicated 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).

 

Hence, passwords generated by KPM will be, on average, far in the list of candidate passwords tested by these tools. If an attacker tries to crack a list of passwords generated by KPM, he will probably wait quite a long time until the first one is found.

 

This is quite clever.

 

However, if an attacker knows that a password has been generated by KPM, he can adapt his tool to take into account the model followed by KPM. As these passwords are, in a certain sense, biased (to tackle password crackers), this bias can be used to generate the most probable passwords generated by this tool, and test them first. A straightforward way to do it could be to use a Markov generator, as the one provided by John the Ripper (This method has not been tested).

 

We can conclude that the generation algorithm in itself is not that bad: it will resist against standard tools. However, if an attacker knows a person uses KPM, he will be able to break his password much more easily than a fully random password. Our recommendation is, however, to generate random passwords long enough to be too strong to be broken by a tool.

 

We previously saw that KPM picked two random values r1r1 and r2r2 to compute an index in the charset table. Let’s see now how these values are computed.

KPM’s Random Number Generator

These two values come directly from the KPM PRNG. This PRNG outputs uniformly floats between 0 and 1, 1 excluded.

 

The PRNG used differs in the Desktop and the Web version:

 

• The Web version used Math.random(). This function is not suitable to generate cryptographically secure random numbers (which includes entropy required to generate passwords), as explained in https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random. The underlying PRNG used by Chrome, Firefox and Safari for Math.random() is xorshift128+. It is very fast, but not suitable to generate cryptographic material. The security consequences in KPM has not been studied, but we advised Kaspersky to replace it with window.crypto.getRandomValues(), as recommended by the Mozilla documentation page previously mentioned.

 

• The desktop version used a PRNG provided by Boost: the mt19937 Mersenne Twister. Mersenne Twister is very good and widely used PRNG, and MT 19937 is the most popular Mersenne Twister. It is uniformly distributed, has a very long period, and is fast compared to the other “good” PRNGs.

 

However, is using a Mersenne Twister a good idea to create passwords? Definitely not.

 

The problem with this generator is that it is not a CSPRNG. Knowing a few of its ouputs (624 in that case) allows to retrieve its full state, and to predict all the values it will generate, plus all the values it has already generated (see Berlekamp-Massey or Reeds-Sloane algorithms).

 

Off-the-shelf tools like randcrack are available to break Python’s random module, which uses a very similar (if not the same) implementation of MT 19937. Only very minor adaptations should be necessary to break Boost implementation.

 

In practice, exploiting such flaw in the context of Kaspersky’s Password Manager is hard:

 

• Passwords are short: 12 chars by default. Retrieving 624 password chars requires to grab 52 passwords.
• The raw output value is not known: output value is the position in the charset of each letter of the password. More values could be necessary.
• And we saw that this position in the charset is a the product of two values produced by the PRNG.

• We do not see a straightforward way to attack this PRNG in the context of KPM.

  Seeding the Mersenne Twister

  We saw that the PRNG uniformly generates floats in [0, 1[. The code responsible for its initialization should look like:

  mt19937::result_type seed = ...;
  auto mtrand = std::bind(std::uniform_real_distribution<float>(0,1), mt19937(seed));
  

   

Where does the seed come from? The password generation function is called like this:

std::string pwlib::generatePassword(pwdlib::Policy policy, int seed)
{
    if (seed == 0) {
        FILETIME ft;

        GetSystemTimeAsFileTime(&ft);
        seed = ft.dwLowDateTime + ft.dwHighDateTime;
    }
    auto mtrand = std::bind(std::uniform_real_distribution<float>(0,1), mt19937(seed));
    return generateRandomPassword(policy, mtrand);
}

This is super interesting for two reasons:

 

• The seed is just 32 bits. That means it can be bruteforced easily.
• An instance of the PRNG is created every time a password is generated. It means Kaspersky Password Manager can generated at most 232232 passwords for a given charset.

• GetSystemTimeAsFileTime is used as a seed only if a seed is not provided to the generatePassword method. How is called this method when a user requests a new password? The answer is:

  std::string pwlib::generatePassword(pwdlib::Policy policy)
  {
    return generatePassword(policy, time(0));
  }
  

  So the seed used to generate every password is the current system time, in seconds. It means every instance of Kaspersky Password Manager in the world will generate the exact same password at a given second. This would be obvious to spot if every click on the “Generate” button, in the password generator interface, produced the same password. However, for some reason, password generation is animated: dozens of random chars are displayed while the real password has already been computed:

 

 

 

This animation takes more than 1 second, so it is not possible to click several times on the “Generate” button within a second. That is definitely why the weakness had not been discovered before.

 

The consequences are obviously bad: every password could be bruteforced. For example, there are 315619200 seconds between 2010 and 2021, so KPM could generate at most 315619200 passwords for a given charset. Bruteforcing them takes a few minutes.

 

It is quite common that Web sites or forums display the creation time of accounts.

 

Knowing the creation date of an account, an attacker can try to bruteforce the account password with a small range of passwords (~100) and gain access to it.

 

Moreover, passwords from leaked databases containing hashed passwords, passwords for encrypted archives, TrueCrypt/Veracrypt volumes, etc. can be also easily retrieved if they had been generated using Kaspersky Password Manager.

 

An unexpected source of entropy: out-of-bounds read

We wrote a proof of concept to make sure we were not missing something. It generates a list of 1000 possible passwords from the current time. To test the PoC:

 

• Compile the provided PoC (pwlib.cpp). File must be compiled with Visual C++ (floating values in the source code have not the exact same values when compiled with Clang or gcc). I used Visual C++ 2017 for my tests. Using a command invite for Visual C++ 32 bits, enter:

   cmake -Bbuild -H.
   msbuild build\pwbrute.vcxproj
  

• Run compiled executable to create a list of 1000 passwords.

   Debug\pwbrute.exe > pass.txt
  

• Create a password in Kaspersky Password Manager with the following policy:
  • Lowercase only
  • 12 chars
• Verify that the generated password is indeed present in pass.txt.

• It is not completely functional, but allowed us to discover a bug in the password generation process, in the function that computes the probability of appearance of a given letter knowing the previously generated chars. Here is the pseudo code for the getContextProbabilities method:

    const float *getContextProbabilities(const std::string &password) {
      std::string lowercasePassword;
  
      // Convert to lowercase, keep only lowercase
      for (char c : password) {
        if (islower(c)) {
          lowercasePassword += c;
        } else if (isupper(c)) {
          lowercasePassword += char(c - 'A' + 'a');
        }
      }
  ...
      int n = 0;
      for (int i = lowercasePassword.length() - 1; i >= 0; i--) {
        int index = password[i] - 'a'; // FIXME: replace with lowercasePassword
  

  The password being built is converted to lowercase. Non-letters are removed. Then, there is an iteration on the password instead of the lowercase password just created. This leads to a wrong computation of the index variable (the position of a letter in the alphabet). This index is used to retrieve an element of an array. That leads to an out-of-bounds read of this array.

 

 

Frequency of appearances are then computed from uninitialized or arbitrary data in some cases. Although the algorithm is wrong, it actually makes the passwords more difficult to bruteforce in some cases.

 

The attacked PoC generates candidates for lowercase passwords only so that the index is always correctly computed (else the PoC requires to be adapted).

 

Kaspersky assigned CVE-2020-27020 to this vulnerability, and published a security advisory on their web page: https://support.kaspersky.com/general/vulnerability.aspx?el=12430#270421.

 

All the versions prior to these ones are affected:

 

• Kaspersky Password Manager for Windows 9.0.2 Patch F
• Kaspersky Password Manager for Android 9.2.14.872
• Kaspersky Password Manager for iOS 9.2.14.31

• On Windows, the Mersenne Twister PRNG has been replaced with the BCryptGenRandom function:

  float RandomFloat(BCRYPT_ALG_HANDLE *hAlgorithm) {
      uint32_t l;
      BCryptGenRandom(*hAlgorithm, (uint8_t *)&l, sizeof(l), 0);
      return (float)l * (1.0f / 0x100000000);
  }
  

  The return value of this function was not checked in the beta versions provided by Kaspersky, but we guess this has been fixed now.

 

 

Math.random() in the Web version has been replaced with the secure window.crypto.getRandomValues() method.

 

Android and iOS versions have also been patched, but we have not looked at the fixes.

Conclusion

Kaspersky Password Manager used a complex method to generate its passwords. This method aimed to create passwords hard to break for standard password crackers. However, such method lowers the strength of the generated passwords against dedicated tools. We showed how to generate secure passwords taking KeePass as an example: simple methods like random draws are secure, as soon as you get rid of the “modulo bias” while peeking a letter from a given range of chars.

 

We also studied the Kaspersky’s PRNG, and showed it was very weak. Its internal structure, a Mersenne twister taken from the Boost library, is not suited to generate cryptographic material. But the major flaw is that this PRNG was seeded with the current time, in seconds. That means every password generated by vulnerable versions of KPM can be bruteforced in minutes (or in a second if you know approximately the generation time).

 

Finally, we provided a proof of concept that details the full generation method used by KPM. It can be used to verify the flaw is indeed present in Windows versions of Kaspersky Password Manager < 9.0.2 Patch F. Incidentally, writing this PoC allowed us to spot an out of bounds read during the computation of the frequency of appearance of password chars, which makes passwords a bit stronger that they should have been.

Timeline

• June 15, 2019: report and proof of concept sent to Kasperky through HackerOne.
• June 17, 2019: Kaspersky acknowledges it has received the report.
• June 25, 2019: Kaspersky confirms the vulnerability.
• October 4, 2019: Kaspersky sends a private Windows build so we can check the bugs have been fixed, and informs us they will rollout a solution to handle previously generated passwords before the end of the year.
• October 8, 2019: we confirm the vulnerabilities have been fixed, but reported a new small defect in the fix.
• October 10, 2019: Kaspersky Password Manager for Windows 9.0.2 Patch D is released, fixing the vulnerabilities, but without the fix for the reported defect. Web version is also updated.
• October 9, 2019: Kaspersky Password Manager for Android version 9.2.14.872 with the fix is released.
• October 10, 2019: Kaspersky Password Manager for iOS version 9.2.14.31 with the fix is released.
• December 10, 2019: Kaspersky Password Manager for Windows 9.0.2 Patch F is released closing the defect in patch D.
• April 9, 2020: Kaspersky informs us they will release a patch in October to handle previously generated passwords.
• October 13, 2020: Kaspersky Password Manager 9.0.2 Patch M is released, with a notification to users to inform them some password must be re-generated. Kaspersky informs us the same notification will also be present in mobile versions during the first quarter of 2021. CVE-2020-27020 has also been reserved.
• December 28, 2020: Kaspersky agrees a report about the vulnerability can be disclosed after the CVE is published.
• April 27, 2021: Kaspersky security advisory is published.
• May 14, 2021: Information for the CVE-2020-27020 is published.

 

Source