GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)

[David Shaw]

On Nov 28, 2009, at 9:42 AM, Ciprian Dorin, Craciun wrote:

>    Maybe someone could clear this out (at least from GnuPG part). (My
> original post was related with both GnuPG an OpenSSH).
>
> ~~~~~~~~~~ Original post:
>
>    (I have a very basic question that to most of the persons reading
> this news-group might seem trivial. But anyway...)
>
>    My concern (as stated in the subject) is related to the security
> strength of GnuPG and OpenSSH secret / private keys in the following
> context:
>    * the secret / private keys are encrypted by using a password that
> only me (the owner) knows;
>    * an attacker is in possession of my secret / private key files;
>    * the attacker wants to gain access to the secret / private key
> (thus being able to impersonate me);
>    * the attacker chooses as attack method to brute-force the files
> off-line, by trying to guess my password;
>    * (by guessing the password I mean trying all possible passwords
> that fit a given pattern; the password is not a dictionary word, but
> instead is (truly) randomly created (i.e. DiceWare);)
>
>    The question is: what does GnuPG or OpenSSH do to slow down
> password brute-force? I mean does the password derivation function use
> some iterations? If so how many? Can I configure them? I guess so but
> I couldn't find any data on the net on a quick search. (Any references
> are appreciated.)

GnuPG (really OpenPGP) does iterated password hashing.  See section  
3.7.13 "Iterated and Salted S2K" of RFC-4880 for the fine details, but  
the gist is as you surmised - the passphrase is run through many hash  
iterations.  This slows down passphrase guessers as they must also  
repeat the hashing part the same number of times.  By default, GnuPG  
uses 65536 iterations of the pasphrase hash, but can be configured via  
the --s2k-count option to be as high as 65011712 iterations.

Be careful though - in some cases, a too-large value can hurt you  
here.  If you create a passphrase-encrypted message on a fast machine,  
and pick a huge s2k-count, and then try to decrypt on a slow machine  
(say, a cell phone), the message may become effectively unusable since  
the repeated hashes can take an unusable amount of time on the slow  
processor.

I'd have to look up the details if anyone is interested, but there was  
a case a few months back of a huge s2k-count actually causing an  
embedded device to trigger its deadman timer - someone had generated  
the message on a fast machine (so never noticed the large iteration  
count), but sent it to the slow one which clobbered it.

>    Also, how many bits of security should my password have in order
> to withstand an attack from a small / medium enterprise? (Government
> is out of the question as they could get access to my infrastructure
> by force...)

Difficult question to answer, since everyone is going to wave around  
their opinion. :)

I'd suggest starting with the various calculators on http://www.keylength.com/

David