DSA and patents

[Werner Koch]

I received good news concerning the Schnorr patent (see below).

I do not think that the other patent will make any problems; probably
the NIST wants that DSA is used and will keep it´s promise and make
the Kravits patent free.

By the way, I know of the security issues of ElGamal (after spending
some money on quite expensive Crypt lectures);  I didn´t know of my own
what generator g PGP uses, but that is a good thing (not knowing of too
much code).

-----Forwarded message from Peter Gutmann <pgut001 at cs.auckland.ac.nz>-----

>2. The Schnorr patent (4,995,082):  In a letter to the NIST Schnorr
>   claimed that the DSA infringes his patent.  FIPS 186 (about DSS)
>   states that "The Department of Commerce is not aware of any patents
>   that would  be infringed by this standard".  I also heard, that the
>   government will help if someone is sued on patent infringement while
>   working on a project implementing DSS for governmental purposes.
 
The Schnorr patent is a so-called "scarecrow patent" which only applies to a 
very restricted set of smart-card based applications.  A number of lawyers 
from companies big enough to care about possible lawsuits have examined it and 
decided that any claims against typical software implementations are baseless.
 
>Another issue with the OpenPGP draft is, that it requires DSA signatures
>and has no provisions for plain ElGamal signatures.  If itM-4s true, that
>DSA may infringe on some patents, can ElGamal signatures be made an option 
>for OpenPGP and DSA be a SHOULD and not a MUST?
 
There are various issues with Elgamal signatures, the main one is that the 
keys PGP 5 currently generates with g=2 makes the signatures forgeable using 
an attack which Daniel Bleichenbacher described at EuroCrypt'96.  You'd need 
to modify the PGP keygen to avoid this.  There's a draft RFC 
draft-rfced-info-gutmann-elgamal-00.txt which covers this and other issues.  
>From the draft:
 
>3. Security considerations
>
>Although the use of the Elgamal algorithm for digital signature
>generation is not directly addressed in this document, it should be
>pointed out that some care needs to be taken with both the choice of
>keys and the use of the algorithm.  Details on the safe use of Elgamal
>are given in [4].  A weakness of Elgamal when used for digital
>signatures, and workarounds to avoid the weakness, are given in [5].
>
>Ongoing research into the security of Elgamal may reveal other factors
>which need to be taken into account to provide adequate security for
>signature and encryption applications, for example it is desirable that
>g generate a large subgroup of Zp*; it is recommended that implementors
>keep abreast of current research on the choice of parameters and use of
>the algorithm in order to avoid potential security weaknesses.
 
Peter.
 


-----End of forwarded message-----

-- 
Werner Koch, Duesseldorf  -   werner.koch at guug.de   -  PGP keyID: 0C9857A5