[E-Lang] Crypto analytic attack on DSA

Bill Frantz frantz@pwpconsult.com
Wed, 7 Feb 2001 20:24:58 -0800


Daniel Bleichenbacher of Bell Labs has found an attack on DSA when
implemented as recommended by FIPS 186.  It appears from examination of the
source code for Sun/Java 1.2, that their implementation suffers from this
problem.

We have several possible methods of dealing with this problem:

* Wait for Sun to fix the problem.
* Use another DSA implementation.
* Convert vat authentication to RSA.

Converting vat authentication to RSA will increase the time it takes to
generate the key pair, while cutting the time required for signing and
verification.

Here is a post from Wei Dai which gives an overview of the attack.   A
later post from Hal Finney quoted Bleichenbacher as writing, "Compare that
to DSA, where the attack requires 2^22 signatures 2^40 memory and 2^64
time."


Date: Tue, 6 Feb 2001 19:51:08 -0800
From: Wei Dai <weidai@eskimo.com>
Subject: Re: Has DSA been compromised?

Hal Finney wrote:
> Daniel Bleichenbacher's home page is at
> http://www.bell-labs.com/user/bleichen/ but it doesn't seem to have the
> report.  Anyone have pointers to it?

It doesn't seem to be public yet, but there is some useful information in
the Bell Labs' press release at
http://www.lucent.com/press/0201/010205.bla.html. It seems that most news
accounts simply copied and pasted parts of the press release.

> The DSS (FIPS 186) recommendation for choosing k amounts to using
> G(seed) mod q, where G is a random function that produces 160 bit
> output.  G can be built from SHA or DES, for example.
>
> Obviously this will be biased since q is a 160 bit prime and so the range
> of G's output will be slightly greater than [0..q-1].  This will produce
> a bias in the selection of k.  It seems unlikely that there is any way
> to exploit this; probably Daniel has simply recommended an alternative
> way of choosing k that eliminates this bias, and the whole thing has
> been blown out of proportion.  If he has found an actual exploit that
> would certainly be interesting and surprising.

That's exactly what the press release seems to imply. The non-uniformity
of k causes the signature to leak information about the private key. Even
though each signature only leaks a fraction of a bit, Daniel must have
found a way to add them up over multiple signatures. I guess the attack
should also extend to other ElGamal-type signature schemes if the secret
per-signature exponent isn't uniformly chosen.

The fix is obvious and easy: just pick k uniformly between 0 and q-1. Some
libraries (including my own Crypto++) already do this and so shouldn't be
affected.


-------------------------------------------------------------------------
Bill Frantz       | Microsoft Outlook, the     | Periwinkle -- Consulting
(408)356-8506     | hacker's path to your      | 16345 Englewood Ave.
frantz@netcom.com | hard disk.                 | Los Gatos, CA 95032, USA