howto secure older keys after the recent attacks

[David Shaw]

On Sep 10, 2009, at 8:02 AM, Philippe Cerfon wrote:

> On Thu, Sep 10, 2009 at 3:45 AM, David Shaw <dshaw at jabberwocky.com>  
> wrote:
>> Yes, but it won't actually go away completely.  SHA1 is special in  
>> OpenPGP.
>>  Unlike the other hashes, SHA1 is required to be supported.   
>> Removing SHA1
>> from an OpenPGP preference list doesn't actually remove it, but  
>> instead
>> effectively puts it at the end of the list (so it is the lowest  
>> ranked
>> choice).
> Uhm,.. what a pity. What would happen if SHA1 gets fully broken? Would
> we have to create a new OpenPGP and new keys?

Not a new OpenPGP, exactly, but certainly a revised one.  New keys,  
yes.  Of course, SHA1 is nowhere near being fully broken.  Heck, even  
MD5 is nowhere near being "fully" broken (which doesn't mean I  
recommend people use it, of course).

>>> -But I'd also like to have the signatures themselves using e.g.  
>>> SHA256 or
>>> SHA512,... but they're alread using SHA1
>>> Can this be changed?
>>> Or can I simply add new self signatures?
>> Yes
>
> Does this work via --cert-digest-algo option?
> If so what must I do to get gpg to:
> - resign my own key
> - resign other keys
> Is it simply with the sign command, or will it complain that there's
> already a signture there?

Yes.  To re-sign a key with a new hash, do this:

gpg --cert-digest-algo sha256 --expert --edit-key (thekey)
(pick the user IDs you want to sign)
sign

The "cert-digest-algo" tells GPG which hash to make key signatures  
with, and the "expert" tells GPG that it is okay to re-sign a user ID  
that is already signed.

>> To change the hash you sign with, stick this in your gpg.conf file:
>>
>> personal-digest-preferences sha256
>
> Oh,.. so what is this --cert-digest-algo then good for?

personal-digest-preferences sets the hash for signatures you make on  
data.
cert-digest-algo sets the hash for signatures ("certifications") you  
make on keys.

>>> Another thing I've read about is, that gpg keys are using SHA1  
>>> hard coded
>>> in some places with no way to use another algortihm... which  
>>> places are
>>> these so one could avoid them perhaps?
>>
>> You pretty much can't.  The key ID itself is derived from SHA1.
>
> I thought the key ID is only used for humans to short check the
> keys,.. but not in the system itself?!
> So this would basically mean, once SHA1 is broken, we're totally  
> screwed?!

No, just that we need to revise OpenPGP.  It's not a disaster - we've  
done it in the past, and can do it again in the future.  It's just a  
specification that describes a cryptographic system using the best  
knowledge of the time.  If the knowledge changes, we change the  
specification.

The real headache here is (as always) the practical - what to do with  
existing keys and such.  I suspect that removing SHA1 would  
effectively mean a new key type for OpenPGP (again, not a disaster -  
we're on our 4th key type today).

> I'd have some additional poor men's questions ;-)...
> - When creating a new key,.. it uses the entropy, right? So is there
> some way to improve this entropy? Perhaps not using Linux but instead
> OpenBSD which might have a better PRNG (don't know if this is actually
> the case ;) ) or use a specific Linux kernel version where a newer and
> better PRNG was added?

There are occasional debates on who has the better PRNG.  The debates  
usually end with no changes on either side :)

That isn't to say there aren't differences between systems - the  
FreeBSD PRNG (which seems to have been inherited by OSX) is of a  
fairly different construction than the Linux one, which has led to  
some mild controversy in the past.  Notably, the Linux one blocks if  
you run out of gathered entropy, and the FreeBSD one does not.   
FreeBSD /dev/random is similar to Linux's /dev/urandom.

See also http://www.entropykey.co.uk/

> -Currently the default (and I assume suggested) algorithm is RSA,
> right? How does DSA2 compare with it?

Given the same key length and same hash, they are (massive armwave!)  
roughly equal for real-world use.  If you like, you can define  
"roughly equal" as "usually so much stronger than the rest of the  
system that fiddly differences are irrelevant". The actual difference  
you find between the two is more in implementation and use issues,  
like DSA signatures being physically smaller than RSA signatures (nice  
for email), RSA being more widely supported in hardware doodads  
(smartcards, crypto math chips, etc), and RSA allowing more hash  
flexibility than DSA.

Read NIST SP 800-57 for lots of detail on strength, but they basically  
conclude the same thing: roughly equal for real-world use.

> I once read, that RSA would
> provide a hash algorithm armor which the DSA's wouldn't have. Is this
> still true?

I'm not exactly sure what you mean by "hash algorithm armor".  RSA in  
OpenPGP does have a additional protection (usually called a "hash  
firewall") that DSA lacks.  This gives some protection against hash  
substitution attacks, but it's not a major deal either way.

> -My course's professor showed us some number from NIST (don't recall
> the exact ones, though) where they suggested about something like
> this:
> 15360 (or so) bits for the asymetric key <-> 512 bits for the hash
> size <-> 256 symmetric key
> should lead to about the same "strenght"...
> So we have 512/256 bits for the later two,.. but per default much less
> for the asymmetric... Does this mean, that the other two are overkill
> for what we use in gpg?

It's true that NIST's guidelines say that to truly get the maximum  
juice out of a 512-bit hash, you should use a 15360-bit key, but that  
doesn't mean you must.  That overall strength of the system is the  
weakest point, so as long as that weakest point is strong enough,  
you're fine.

A 15360-bit key is wildly impractical.  I doubt we'll ever see keys of  
that size in use.  When technology progresses to the point of that  
being necessary (no time soon) we'll move on to other algorithms that  
are stronger per-bit, like ECDSA.

> - When creating new keys (I'd like to "convince" some more friends to
> take part :) )... should they create their keys with gpg1 or gpg2? Or
> is the key generation equally secure?

Equally secure.  In fact, it's almost the same code.

David