2

Given the following scenario:

  • the user has a password and a symmetric key is derived from it by PBKDF2 or bcrypt
  • a private RSA key is protected by the above symmetric key
  • the encrypted private key in binary format is available to the attacker
  • all the details of the KDF algorithm are available to the attacker (salt, no of iterations, source code)

My understanding is that an attacker who wants to decrypt the private key can perform a brute-force attack by guessing passwords and applying the KDF.

How would the attacker know if a guess is successful?

Besides the brute force, are there other approaches to decrypt the private key given the above information?

Are there significant differences between PBKDF2 and bcrypt in this scenario?

Thanks!

vidi
  • 287
  • 1
  • 8

3 Answers3

2

How would the attacker know if a guess is successful?

There are only so many formats in which private keys are stored. As an attacker, if I could assume that you didn't store your private key in your own, home-grown format, I'd just see if my brute-force guess decrypted the private key to any one of the formats I'd expect a private key to be in.

For example, if I assumed that your private key was an ASCII-armored PGP key, I'd simply check whether the first few bytes decrypted to

-----BEGIN PGP PRIVATE KEY BLOCK-----

and vice versa for other formats.

If the attacker had a list of possible public key candidates for the private key, he could also compare the modulus of the resulting decrypted private key against the modulus of the public keys and if one matched, he'd know he had a correct decryption.

Besides the brute force, are there other approaches to decrypt the private key given the above information?

None I know of, as long as you use a strong symmetric cipher. Other avenues of attack would mean there were serious weaknesses in the symmetric cipher you use to encrypt the private key.

Are there significant differences between PBKDF2 and bcrypt in this scenario?

Probably not. Both are considered strong for key derivation, even though opinions differ on the exact advantages and disadvantages. One disadvantage they both share is that they don't use very much memory to derive keys, so they can be implemented on very fast, highly parallel processors (think GPUs and FPGAs).

(edit: added the part about comparing with the public key modulus to confirm a correct decryption)

Out of Band
  • 9,150
  • 1
  • 21
  • 30
  • I said it in the question title but I for got to say it in the body: the private key is stored as binary data. I'll fix the question. How does that change your answer? – vidi Feb 10 '17 at 22:02
  • It doesn't. Even if it's binary data, it's probably still stored in a specific format that has a magic number in the header, specific header fields that must have certain values etc. As long as you don't just store the modulus and exponent as raw binary data, without any header information at all, you can write software to detect whether the decrypted data matches what you'd expect given the storage format used. I just made the PGP example because it's easier to illustrate. – Out of Band Feb 10 '17 at 22:04
  • I've normally seen keys stored as ASCII-armored files but from your answer I understand that if the key is stored as binary without any magic number/fixed headers etc then the attacker cannot know if he guess was successful or not. Does such a format exist? – vidi Feb 10 '17 at 22:12
  • Of course: It would simply be a string of bytes which together represented two very large numbers, the modulus and the exponent of the private key. You'd know where one number ended and the other started because you could fix the size of both numbers, but to an attacker the resulting file would simply look like a random string of bytes. But if the attacker had a matching public key, he could check the number representing the modulus with the modulus of the public key and if they matched, he'd know he had the right decryption. Or he could see if the key he got decrypted ciphertext successfully. – Out of Band Feb 10 '17 at 22:19
1

It depends. How exactly is the private RSA key protected by the symmetric key?

If the encryption procedure protects the integrity as well there will be an authentication tag or mac. If this mac is calculated from the plain symmetric key it will reveal the correct solution. However, modern procedures use encrypt-than-mac, where the cipher text is hashed, therefore no information about the solution is revealed.

On the other side, if the public key is known to the attacker he could check for each private key if it matches the public key. Knowledge of the public key is a fair assumption given the whole concept of asymmetric cryptography.

Note that in both cases additional computation has to take place to check whether a candidate is a solution. This is likely more expensive for the info the second place, since asymmetric cryptography is typically more demanding than hashing. So it makes sense to use a proper encryption procedure.

fzgregor
  • 111
  • 2
1

Look for the public key

A RSA private key includes the RSA public key (see this answer for an XML example). So if the hacker knows the public key, this attack becomes very similar to a known plaintext attack, except only part of the plaintext is known.

So the hacker would simply need to keep going through symmetric keys and checking the output to see if it contains a byte sequence that is the public key.

There is a very, very, very small chance that the public key byte sequence would appear in a false positive, but the the hacker would just need to encrypt and decrypt a short nonce to verify that it is a correct match.

Community
  • 1
John Wu
  • 9,101
  • 1
  • 28
  • 39