Talk:Digital Signature Algorithm

From Wikipedia, the free encyclopedia

WikiProject on Cryptography This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.
WikiReader Cryptography It is intended that this article be included in WikiReader Cryptography, a WikiReader on the topic of cryptography. Help and comments for improving this article would be especially welcome. A tool for coordinating the editing and review of these articles is the daily article box.
Society Portal
This article is part of WikiProject Media, an attempt to better organize information in articles related to media. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
To-do list for Digital Signature Algorithm: edit · history · watch · refresh
  • Describe initial criticism of the standard
  • Describe Schnoor's claims of patent infringement

Contents

[edit] DSA and encryption

Recently removed from the article:

It was designed at the NSA as part of the Federal Government's attempt to control high security cryptography. Part of that policy included prohibition (with severe criminal penalties) of the export of high quality encryption algorithms. The DSS (Digital Signature Standard) was intended to provide a way to use high security digital signatures across borders in a way which did not allow encryption. Those signatures required high security asymmetric key encryption algorithms, but the DSA (the algorithm at the heart of the DSS) was intended to allow one use of those algorithms, but not the other. It didn't work. DSA was discovered, shortly after its release, to be capable of encryption (prohibited high quality encryption, at that) but to be so slow when used for encryption as to be even more than usually impractical.

Is this viewpoint not held by anyone, even a minority? (If so, it should be reinserted into the article in some form). User:Ww? — Matt 22:53, 5 Sep 2004 (UTC)

Schneier, Applied Cryptography, 2nd ed:

There have been allegations that the government likes the DSA because it is only a digital signature algorithm and can’t be used for encryption. It is, however, possible to use the DSA function call to do ElGamal encryption. — Matt 23:17, 5 Sep 2004 (UTC)

I would say the view is held not by a minority, but by everyone! We're not talking about some secret conspiracy here; NSA officials such as Bill Crowell spelled it out in Congressional testimony. The speculative part is whether or not DSA was specifically meant to hamper the commercialization of RSA. I think there is less agreement here, but it is still a pretty widely held opinion. And of course, the reasons that it failed (if that was the plan) are much more complex than the observation that it is possible to bludgeon DSA into doing encryption (very slowly). Securiger 06:22, 24 Sep 2004 (UTC)

I would at least point to the fact that DSA can be used for encryption (RSA and Elgamal) by choosing special inputs to the sign function (As described by Schneier). --Tobias 11:20, 20 December 2005 (UTC)

[edit] Schnorr patent dispute

The two links disputing the Schnorr patent claim are 404's:

http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-08/0006.html

http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-08/0009.html

Anyone has another source? Could not find a working archive.. --Tobias 11:18, 20 December 2005 (UTC)

NIST claims that they reviewed Schnorr's patent and concluded that DSA is not infriging the patent in http://csrc.nist.gov/publications/nistbul/csl94-11.txt. 24.228.93.22 00:48, 17 February 2006 (UTC)

[edit] Hmm, this looks like wide spread opinion

Interesting stuff, I will have to admit that paragraph will likely never stay on the front page for long. Too many people will think you are making it up unfortunately. In fact, the first time I had of it, was on a cryto related thread on lkml (Linux kernel mailing list) Even there, the suggestion was finding a lot of resistance.

Then, a month ago, I was in TLUG (Toronto Linux user group) and there was a discussion of ssh. The one thing everybody seemed to agree on is using DSA is a bad idea. RSA should be used whenever possible. Some books like UNIX System Administration Handbook (3rd Edition) (Paperback) by Evi Nemeth, Garth Snyder, Scott Seebass, Trent R. Hein don't advice it use, but others like Professional Red Hat Enterprise Linux 3 (Wrox Professional Guides) (Paperback) advice on its use.

In short, DSA has a perception issues whether one accept this as a fact is a different story. I guess we will have to wait until more people support the hypothesis before that paragraph can move in the front article. Remember people used to believe the world is flat until reality dawned at them one day. Here is to hoping it will happen again

[edit] DSA standard revised. Article needs updating.

See here: http://sdp.opendawn.com/index.php/DSA2_support

[edit] A little bit more info for signing description

I don't know squat about math, but when trying to implement DSA signing using the sequence of steps here Digital_Signature_Algorithm#Signing, it was not obvious to me that k-1 = the multiplicative inverse of k mod q. I had to go to the spec to figure that out. Does it make sense to add a small bit of verbiage to that effect, or is that something that should be obivous?

--Geechorama 17:15, 4 August 2006 (UTC)

You have a good point here. Cryptographers use modular arithmetic so frequently that they forget to include pointers to the relevant pages. I've added links to some articles that should be helpful. 67.84.116.166 15:25, 16 August 2006 (UTC)

[edit] k is not a nonce

Calling the variable k a nonce might mislead some readers. Specially the description of a nounce says

it should be time-variant (including a suitably granular timestamp in its value) ...

Including a timestamp intok would make some bits of k predictable. This might allow lattice based attacks that can recover the secret key x. k or even parts of k must not be predictable. 67.84.116.166 23:44, 14 September 2006 (UTC)

[edit] data type....

hey guys.... i just wanted to know the data type in java that can support the global variables in DSS...the length of 'p' cud vary from 512 bits to 1024 bits....i m confused as to how shall i proceed with the project.... —The preceding unsigned comment was added by 125.23.19.220 (talk) 15:27, 8 January 2007 (UTC).

[edit] DSA weakness?

Upon reading PuTTYgen's docs on selecting a key type, I came across this line:

The PuTTY developers strongly recommend you use RSA. DSA has an intrinsic weakness which makes it very easy to create a signature which contains enough information to give away the private key! This would allow an attacker to pretend to be you for any number of future sessions. PuTTY's implementation has taken very careful precautions to avoid this weakness, but we cannot be 100% certain we have managed it, and if you have the choice we strongly recommend using RSA keys instead.

Can anyone elaborate on what this weakness is, and (although off topic) why is RSA any worse/better than DSA for TLS? -- PaperWiki (talk) 22:10, 18 November 2007 (UTC)

It sounds like they refer to the fact that the per-message value k must be cryptographically random, be kept secret, and never reused. If an attacker (who knows the public key) can guess the k used to sign any single message, possibly by tricking the signer into using a k of his choosing, it is a matter of simple arithmetic for him to recover the full private key, as x is then the only unknown in the equation for s. Similarly, if the same k is ever used to sign two different messages, an attacker can (1) immediately see that this is the case because the two signatures will have the same r, (2) find the value of the reused k by dividing the difference of the message hashes by the difference of the s values, (3) recover the private key as before.
This means that the security of a DSA signing routine is at the mercy of the security of the PRNG it uses to generate k. Deploying a PRNG such that it cannot be fooled or predicted is surprisingly tricky; one has to either trust an OS-provided source of randomness, or do complex and easy-to-get-wrong platform-dependent stuff in order to gather entropy from the environment oneself.
An RSA signer does not have this problem, because no random value is needed for its basic signing primitive. –Henning Makholm 00:03, 19 November 2007 (UTC)
There are some comments in the file sshdss.c of Putty's implementation, which amount to what you just mentioned. Apparently Putty's implementors don't trust their own pseudorandom number generator, hence they use a method that derives k deterministically from the private key x and the message m by hashing these values. Such a method has been analyzed in the paper "Computational Alternatives to Random Number Generators" by M’Raihi, Naccache, Pointcheval, Vaudenay presented at SAC'98. Since RSA also needs to be implemented very carefully, I don't agree with the strong preference above. Also, there are quite a few people that prefer the randomized RSA signatures over the deterministic variants. 85.2.78.238 (talk) 06:34, 19 November 2007 (UTC)
As an interesting aside, that's what happened because of CVE-2008-0166. Since the PRNG was extremly weak, any DSA key merely used on a buggy system should be considered compromised[1]. --cesarb (talk) 02:49, 3 June 2008 (UTC)

[edit] Statement that the signature=(r, s)

It is stated that the signature is (r, s), but shouldn't this be (r, s, H(M)) as the verifier must calculate Hw mod q? —Preceding unsigned comment added by James mcl (talk • contribs) 14:23, 3 January 2008 (UTC)

The statement assumes that the recipient of the signature knows, by means external to the signature itself, which message it is supposed to sign. He can therefore compute H(M) himself. If he tries to do the calculation with the hash of a different message, he will simply find that it fails.
The article's description is consistent with what a "DSA signature" is considered to consist of in, for example, RFC 3279. –Henning Makholm 01:25, 6 January 2008 (UTC)