Problems with GPG El Gamal signing keys?

[Anton Stiglic]

----- Original Message ----- 
From: "Perry E.Metzger" <perry at piermont.com>

> Some notes have been floating around claiming that there are bugs in
> GPG's use of El Gamal keys. For example, see:
>
http://groups.google.com/groups?selm=E1AOvTM-0001nY-00%40alberti.g10code.de&oe=UTF-8&output=gplain
>
> Can anyone confirm these reports?

The note talks about GPG Elgamal encryption and signature schemes
using small value of k (where k is the random value that you pick for
each signature, each encryption).  For encryption choosing a small k
is o.k. (by small I mean something like 160 bits when you have a 1024
bit prime), but this was never recommended for the signature scheme,
and the note states that this would in fact be a security
vulnerability.  The note says that with one signature using a certain
private key x, generated using a small random k, you can compute the
private key x.  So if you are also using this key for decryption, the
private key found could also be used to decrypt everything that was
encrypted to you.

I haven't put any taught yet in how you would retrieve the private key
given the signature (I just read this email), but it sounds plausible.
One thing I can confirm however is that GnuPG 1.2.3 (the latest
version available from the GnuPG we site) indeed has is that both the
encryption and signature schemes use a small k.

If you have the source code, just take a look at cipher/elgamal.c,
there is a function gen_k( MPI p ) that is called by both
do_encrypt(...) and sign(...)  functions.  In the function gen_k, k is
chosen to be of size nbits, where nbits is smaller than the size of
the prime.  Look at the comment in the code:
 /* IMO using a k much lesser than p is sufficient and it greatly
     * improves the encryption performance.  We use Wiener's table
     * and add a large safety margin.
     */
    nbits = wiener_map( orig_nbits ) * 3 / 2;

wiener_map maps sizes of primes to sizes for k and q.  For example,
for a 1024 bit prime, the function will return 165, so in this case
nbits would be 165*3/2 = 247.

I give credit to Phong Nguyen which the note says was the person who
observed this and came up with the attack.

--Anton

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com