----- Original Message ----- From: "Perry E.Metzger" <[EMAIL PROTECTED]>
> 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 [EMAIL PROTECTED]
