...decrypting the above [encrypted private key] is arguably as difficult as computing my secret key from the public one.
Is that an accurate comparison?
Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.Sign up to join this community
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:
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 2127 keys. Guessing the password means trying an average of 2s-1 passwords, where s is the password entropy, and each try involves computing about 210 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 2s+9 or 2127, 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 2105 and 2115. This corresponds to two sources of uncertainty:
As explained above, RSA-2048 breaking is about memory, while symmetric encryption breaking is pure CPU. The two are not immediately comparable.
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.
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.)
The long and short is: it depends!
A long, strong, random passphrase encrypted properly with lots of iterations is 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:
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
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
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.
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.
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 22048 divisions, and so on average you would expect 22047 division operations. (Note that there are about 2271 particles in the universe, so let's call that impossible.)
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.
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.