Subject: Re: Removing Elgamal signatures

From: "Hal Finney" <[email-masked]>
Date: Mon, 1 Dec 2003 08:46:25 -0800

I'd like to see some technical details about the attack, if they can be
made available.  The ElGamal signature formulas are:

   r = g^k mod p
   s = (H-rx)/k mod q

The latter comes from rx+sk=H mod q.

I gather from what Werner has said that choosing small x and k in this
formula is unsafe.  This looks similar to a lattice problem where there
are relatively efficient articles for finding "small" vectors.  But I
am not that familiar with the mathematics.

Incidentally, in trying to research this I found that the attack by
Bleichenberger on poorly-chosen random numbers in DSA signatures had never
been published.  I'm not sure if that was a lattice based attack or not.

It would be good to see these results made available because they might
turn out to be applicable to other types of keys that we might consider
in the future.

Hal Finney

---

From: David Shaw <[email-masked]>
Date: Mon, 1 Dec 2003 12:31:11 -0500

> turn out to be applicable to other types of keys that we might consider

The paper is as yet unpublished, but the author's web page with
contact info is http://www.di.ens.fr/~pnguyen/

David

---

From: Michael Young <[email-masked]>
Date: Mon, 01 Dec 2003 15:22:32 -0500

Hal Finney wrote:
 > It would be good to see these results made available because
 > they might turn out to be applicable to other types of keys
 > that we might consider in the future.

While we're at it, I'd like the specification to include references to
the research that was the rationalization for using a small "k" for
encryption.  Given that a full-width "k" is impractical (for cost
reasons) and every implementation will be inclined to use a small "k",
it's important that we make note of the security limitations.
This is particularly true when they're based on the *relative*
performance of known methods, which can change over time.

[As I recall, the published PGP6 source code contained a comment with
a reference.  I don't have that handy, but perhaps someone here does.]