Difficulty of breaking private key password

Question

I was recently reading up on the practices of keybase.io and came across this blog post. In it, the author says:

...decrypting the above [encrypted private key] is arguably as difficult as computing my secret key from the public one.

Is that an accurate comparison?

Answer 1

The long and short is: it depends!

• A long, strong, random passphrase encrypted properly with lots of iterations is very safe

  • unless there's a flaw in gpg somewhere (which is possible, of course), very safe.

• A weak passphrase is always unsafe.

• A small number of iterations on encryption makes the area of "weak passphrase" bigger, and the area of "strong passphrase" smaller.

Let's experiment, so you can see for yourself!

We'll more or less start with the Ubuntuvibes article Recover your gpg passphrase using John the Ripper.

Create a GPG key, nice and default, with a weak passphrase to validate the technique:

gpg --gen-key

Follow the defaults FOR THIS DEMONSTRATION, but name it "CrackingTestDefault"

To change the passphrase, you can simply use the following and then re-export to try again!

gpg --edit-key <keyid>
  passwd

Now, export the test secret key

gpg -a -o ctd.asc --export-secret-key CrackingTestDefault

Download and compile John the Ripper 1.8.0-jumbo-1 or the latest when you read this - configure and compile. Or just use Kali linux.

Now extract the important bits into John's format using a John the Ripper helper app that came with the Jumbo version

run/gpg2john ctd.asc >ctd.john

Now let's just try the default mode and see what happens

IF your weak password was TestTest, like mine, then you found it nearly instantly! Let's show the password

run/john --show ctd.john

See our password of TestTest?

Reset John's list of cracked passwords, the "pot", and do something different just to show what people are talking about when they say a password will take days (on an 8 core CPU)

mv run/john.pot run/john.pot.found1

Now let's try incremental mode, lower case only, and see what happens run/john --format=gpg --mask=?u?l?l?l?u?l?l?l ctd.john

Let it settle out for a few seconds, then check your CPU use and hit a key. If you compiled John correctly, it's maxed out all your CPU cores, and it's still going to take a few weeks, because it is - STUPIDLY - trying every single combination.

Note the speed - on my 8 core box, it's getting right around 50,000 guesses per second. That's 129.6 BILLION guesses every 30 days, and a targeted attack against a GPG passphrase is likely to be worth quite a lot more than most password cracking exercises, so expect more than a single CPU running for more than a single month!

Let's try a real rule

Press Ctrl-C and stop it. Mask attacks are fine for very small keyspaces, or very fast hashes.

Try a real attack - a rules-based wordlist attack!

run/john --format=gpg --wordlist=run/password.lst --rules:Jumbo ctd.john

It shouldn't take long to find TestTest, or Test7, or quite a few other word based passwords. Play with it!

Rule #1 - Use a long, strong, random GPG passphrase.

If your passphrase is weak by the definition of cracking attacks Let's try something else! Let's try changing how GPG protects the key!

We're going to encrypt the key with AES256, use a SHA-512 digest, and drastically increase our iteration count.

Change the password to Chameleon98 now:

gpg --s2k-mode 3 --s2k-digest-algo SHA512 --s2k-cipher-algo AES256 --s2k-count 70000000 --edit-key CrackingTestDefault
   passwd
       enter your old password, then Chameleon98, the new password, twice
   save

Now, use the previous instructions to extract it to ctdcham.asc, create ctdcham.john, and attack it.

If your system is like mine, the cracking speed is now about 32 guesses per second, instead of 50,000 guesses per second; more than three orders of magnitude slower.

Now, unless you want to wait for the hours or days your machine will take to go through the entire John wordlist with that ruleset, you can create a file called cham.lst, with a single line that has the word

chameleon

in it, and use THAT as your wordlist with the Jumbo rules based attack above just to see if Chameleon98 is vulnerable to the Jumbo ruleset. You will, in fact, see that John the Ripper will use the base word, and it will finally get to a rule that capitalizes the first letter and adds 98 to the end, cracking it - but now it takes quite a lot longer.

WARNING: the Jumbo ruleset is not the be-all or end-all. See some of the rulesets that come with Hashcat which are much, much longer, and Hashcat has rules John doesn't, too, though as of Jan 2016 I don't think Hashcat has a mode for GPG in specific.

WARNING: Whenever the gpg attack is ported to GPU, the attack may get a MASSIVE speedup.

Try decrypting a file, too - note there's a second or two's pause (more on a slower CPU) after entering your passphrase. Cracking takes 1500 times longer; well, normally use of the passphrase ALSO takes 1500 times longer. However, unless you're decrypting lots and lots of files, you can probably afford to take a couple seconds after entering your passphrase, in exchange for making attackers spend more resources and/or test a smaller keyspace.

Rule #2: Use the --s2k* options when generating keys, AND when changing passphrases!!!

Feel free to use Luis Rocha's JtR cheat sheet to play around further.

Answer 2

To give an exact mathematical answer I'd need more details like which encryption cipher, which public key algorithm, etc. But generally speaking yes, it is at least as difficult.

The public key part imported just fine - see below - so it is his key, he's not lying about that, but the private key appears to be encrypted with a password-based symmetric cipher. Alright, let's compare the two cases.

Case 1: deriving his private key given that we have his public key

In theory, knowing someone's public key does not help you to guess their private key. As @TheSchwa points out, you only have to check up to the squareroot of the modulus, so cracking a 4096-bit RSA key should only take 2²⁰⁴⁸ divisions, and so on average you would expect 2²⁰⁴⁷ division operations. (Note that there are about 2²⁷¹ particles in the universe, so let's call that impossible.)

Case 2: Cracking the password

To get his private key I only have to guess the password on the file. For his claim that this is "as hard", his password would need 2047 bits of security, which you would get from a 256 character random password with no detectable patterns or dictionary words. Even the most hard-core security nuts I know only use 32-character passwords, so I'm willing to bet that I'd guess his password long before I guessed his secret key. But assuming he did use a randomly generated 32-character password, we're still in the trillions of trillions of years range to crack it.

Conclusion

Technically he's wrong, guessing the password is easier, but when both take longer than the age of the universe, does it really matter?

That said, the point of his article is "go ahead and upload your protected private keys to keybase.io" and this I don't agree with because while cracking a 32-character password is infeasible, most people on this planet do not use strong passwords, and cracking the average password on the internet takes only a couple of minutes.

Answer 3

There are subtleties about such comparisons.

To crack symmetric encryption, like this password-based encryption of the private key, one needs to one either of the following:

• guess the password;
• guess the symmetric key derived from the password;
• leverage a structural weakness in the encryption algorithm or how it is used.

In the page you link, the encrypted private key is actually a set of "sub -keys" of type RSA-2048: each private key is encrypted with a key derived from the protection password, and the public part is signed with the user's "master key" (of type RSA-4096). The master private key is not included in the blob. The symmetric encryption system uses the following:

• The password is hashed into a key by processing the salt and the password with the iterated and salted S2K transform. This is basically SHA-1, computed over multiple repetitions of the salt and password, concatenated, up to some size (here, 65536 bytes). To make the story short, processing a putative password into a key costs 1025 elementary invocations of SHA-1.

• The resulting key is use for symmetric encryption. The algorithm is here CAST-128, in CFB mode. The symmetric key has size 128 bits.

There is no known structural weakness in CAST-128, that could be leveraged here. Guessing the key would entail trying an average of 2¹²⁷ keys. Guessing the password means trying an average of 2^s-1 passwords, where s is the password entropy, and each try involves computing about 2¹⁰ SHA-1 instances. Each SHA-1 instance is about as expensive as one CAST-128 block.

Thus, the breaking cost for the symmetric encryption will be either 2^s+9 or 2¹²⁷, whichever is lower. It really depends on how the user generated his password. See this answer for details on how to calculate password entropy.

To crack the asymmetric key, one has to factor the RSA public modulus. Here, we are talking about 2048-bit integers, and the best factorization for such integers is the General Number Field Sieve. Running the algorithm still requires both a lot of CPU, and an awful lot of fast RAM, for the final linear algebra phase. For big modulus (1000 bits or more), the final phase is the bottleneck.

2048-bit RSA factorization is completely out of our technological reach, but the memory usage is a lot more into the infeasible realm than the CPU cost. Various people and bodies have tried to make estimates of how much breaking such a key would cost, to try to equate security with that of symmetric keys. See this site for a lot of data on that subject. Roughly speaking, a 2048-bit RSA key is estimated to be "somewhat equivalent" to a symmetric key of 105 to 115 bits, depending on whom you ask.

There is a 1000x factor between 2¹⁰⁵ and 2¹¹⁵. This corresponds to two sources of uncertainty:

1. As explained above, RSA-2048 breaking is about memory, while symmetric encryption breaking is pure CPU. The two are not immediately comparable.

2. All of this is quite beyond what can be done with existing technology, and, more importantly, with existing energy production (for very expensive tasks, the limit is not the hardware, but the electricity and the cooling). We do not know how costs scale when we enter areas where usual notions of cost cease to make sense.

To summarize:

• The big unknown is the quality of the encryption password. If the password entropy is below, say, 60 bits, then breaking the encryption is within reach of (very rich) organizations. If the password entropy is below 35 bits or so, amateurs could break it.

• The symmetric encryption layer and the asymmetric key are both in the realm of the infeasible, making them quite hard to compare. From a not very realistic academic point of view, the RSA should fall first, but that depends on a lot of unknowns. From a practical point of view, they are both unbreakable (right now and for the next few decades as well) so neither is "more secure" than the other.

So if the user generated a good, strong password when exporting, then these private keys should be safe from attackers. Note that the string-to-key process is not very strong here: only 1000 SHA-1 invocations. This translates into a need for a rather high password entropy. Not a lot of users will accept to remember and type a password whose generation process offers at least 70 bits of entropy...

(Remember, entropy is not length. Entropy is randomness. Not at all the same thing.)