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

[Ciprian Dorin, Craciun]

On Sat, Nov 28, 2009 at 5:47 PM, David Shaw <dshaw at jabberwocky.com> wrote:
> 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


    Thank you for the quick reply. (This is the kind of answer I was
hopping to get. :) ) It seems that `s2k-count` escaped me. :)

    Maybe there should be an entry in the FAQ about this topic.

    Related with my question about the password bit strength there
still is a vale on my eyes. So I guess (sorry for not being properly
documented here):
    * the private / public key pair is generated by using whatever
means (RSA / DSA);
    * my password is taken and fed into "Iterated and Salted S2K" to
obtain the secret key encryption.
    * the private key data is taken and fed into '????' algorithm that
uses as password what has been obtained at the previous step.

    So my question about key strength is: what symmetric key algorithm
is used to safeguard the key. (Again I'm not properly documented
here.) And based on the identity of this algorithm, I can use the site
cited (http://www.keylength.com/) to determine a "best practices" key
length. (Other wise I'll have to go with the generic term "symmetric
key encryption"... :) )


>  Now the interesting question would be, how to calculate the real bit
> length of a passphrasse? I googled, and found this message, from this list:
> http://lists.gnupg.org/pipermail/gnupg-users/2008-October/034842.html

    By key strength I mean the bits of entropy given by the password
generation pattern. For example a 4-digit PIN number has only 13.3
bits of entropy, even though we need at least 16 bits to store it.
(This was also pointed out by Farami in his reply.)

    Thanks again,
    Ciprian.


    P.S.: I'm also aware of the fact that iterations do not help at
all, if a big-budget agency (NSA and the like), is going to build a
hardware based brute-force key breaking, as they can build a pipeline
of iteration functions that would try one key in O(1) time. :) (Or I'm
wrong here?)