I'm wondering about some of the semantics and security implications of using something like scrypt
or bcrypt
to "enhance" a password protecting a PGP private key. Essentially, I'm asking about the implications of using the scrypt
of a password as the password for my PGP private key.
From my understanding, a PGP keypair is essentially just two large primes and their product, and the private key is symmetrically encrypted.
My current thoughts are that this is a very good idea, for two main reasons. First, this makes your password unsusceptible to dictionary attacks, as the output of scrypt
is VERY unlikely to be a dictionary word (and you could check it).
The second, and more complex reason, is the computational power required in a brute-force attempt.
Let's assume that the cost of checking a single guess for the (decrypted) prime stored in the private key is A
. Assume that, given a compromised encrypted private key, the cost of checking a single guess is B
. Assume that the cost of computing scrypt
is C
.
Brute-forcing a 2048-bit prime would cost, at most, pi(2^2048) * A
, where pi(x)
is the number of primes less than x
. Assuming the private key is compromised, and assuming a not-unreasonable upper-limit of a 20-character (160 bit) password, the maximum cost to brute force the password is 2^160 * B
. Assuming a compromised key with a password known to be the result of a N
-character (N*8
bit) scrypt
, the maximum cost to brute force the password is 2^160 * C * B
OR 2^(N*8) * B
(because the attacker could either attempt to use scrypt
or just crack the hash itself).
Note that using standard estimators, pi(2^2048) ~= 2.28*10^613
.
Let's fix A = 1
for the purpose of computation, and we'll assume B >= 2
which seems reasonable given the low-cost of integer multiplication.
With scrypt
, C
is variable. If we consider C = 10
(it is 10 times harder to compute scrypt
than to multiply two large numbers), then:
- Cost to brute force the key:
2.28*10^613
- Cost to brute force the password:
2^160 * 10 * 2 = 2.9 * 10^49
OR2^(N*8) * 2 = 2^(8N +1)
Here, 2^(8N +1) = 2.9 * 10^49
at around N = 21
, which means that if C = 10
, you only need a 21-character hash to make it easier to crack the input to the hash than the hash. Of course, it would still be beneficial to have the private key itself.
However, scrypt
has varying difficulty, and 10
is probably a SUPER-conservative estimate. If we instead fix N = 128
:
- Cost to brute force the key:
2.28 * 10^6131
- Cost to brute force the password:
2^160 * C * 2
or2^1024 * 2
Here, 2^160 * C * 2 = 2^1024 * 2
at around C = 1.23 * 10^200
, which is obviously completely unreasonable. This means that, for a reasonable hash length, it'll probably always be better to crack the input to the hash than the hash itself.
Obviously, if I use a value of N = 256
, then as long as C > 1
, it'll actually be easier to crack the key than it would be to crack the hash.
I think it would be reasonable to assume C >= 1000
. With this assumption, and fixing N=256
, and assuming our password is P
characters:
- Cost to brute force the key:
2.28 * 10^6131
- Cost to brute force the password:
2^(8P) * 1000 * 2
or2^2048 * 2
One would need around P = 255
to make cracking the password harder than cracking the key, which seems unreasonable.
So it seems that using a tough hash function like scrypt
or bcrypt
could greatly improve key-guessing difficulty, even with conservative estimates for their toughness. It also appears that hashing a password could help in a key-compromised situation, but not all that much.
Are there any other concerns I should consider? I'm currently considering a sort of "dual password" approach, where the key password is passphrase + hash(another passphrase)
. This seems like it would mitigate any bizarre mathematical properties of encrypting a prime with the result of a hash I may have overlooked.
Edit: Just preemptively, I'm not (entirely) an idiot. I am aware that PGP defines it's own hashing mechanism, S2K
, but almost no one uses the "good" version of the hash (it isn't enabled by default), it suffers from a lack of good configurability, and it is easily crackable on accelerators like GPUs. So, yes, I'm suggesting "double hashing" here to a degree -- but scrypt
uses a specific hash-and-grab approach with preset data, and S2K
uses the good ol' fashion exponent-and-bitwise approach. If I remember my cryptology classes, there's no issue with the combining the functions as long as the output of one is within the domain of the other (which, in this case, it is).
bcrypt
orscrypt
-- that would serve no purpose, as memorizing random characters would be more effective. I met that a PGP frontend would take in one (or two, in my potential case) password and calculate the hash and use it as the password.scrypt
should add additional cost the brute-force, I believe.