DSA generates different signatures with the same data

Question

I'm using the example given in this MSDN article about the DSACryptoServiceProvider class. The problem is that I get a different signature each time I run the code.

I tried OpenSSL and didn't get this problem but I need to work with System.Security.Cryptography this time.

This is some source code:

this is the hashed value to be signed

byte[] HashValue =
        {
            59, 4, 248, 102, 77, 97, 142, 201,
            210, 12, 224, 93, 25, 41, 100, 197,
            213, 134, 130, 135
        };

and this is where the problem lies

 // The value to hold the signed value.
 byte[] SignedHashValue1 = DSASignHash(HashValue, privateKeyInfo, "SHA1");
 byte[] SignedHashValue2 = DSASignHash(HashValue, privateKeyInfo, "SHA1");

I used the debugger to figure out the SignedHashValue1 doesn't equal SignedHashValue2

Code from article:

using System;
using System.Security.Cryptography;

public class DSACSPSample
{
    public static void Main()
    {
        try
        {
            DSAParameters privateKeyInfo;
            DSAParameters publicKeyInfo;

            // Create a new instance of DSACryptoServiceProvider to generate
            // a new key pair.
            using (DSACryptoServiceProvider DSA = new DSACryptoServiceProvider())
            {
                privateKeyInfo = DSA.ExportParameters(true);
                publicKeyInfo = DSA.ExportParameters(false);
            }

            // The hash value to sign.
            byte[] HashValue =
            {
                59, 4, 248, 102, 77, 97, 142, 201,
                210, 12, 224, 93, 25, 41, 100, 197,
                213, 134, 130, 135
            };

            // The value to hold the signed value.
            byte[] SignedHashValue = DSASignHash(HashValue, privateKeyInfo, "SHA1");

            // Verify the hash and display the results.
            bool verified = DSAVerifyHash(HashValue, SignedHashValue, publicKeyInfo, "SHA1");

            if (verified)
            {
                Console.WriteLine("The hash value was verified.");
            }
            else
            {
                Console.WriteLine("The hash value was not verified.");
            }
        }
        catch (ArgumentNullException e)
        {
            Console.WriteLine(e.Message);
        }
    }

    public static byte[] DSASignHash(byte[] HashToSign, DSAParameters DSAKeyInfo,
        string HashAlg)
    {
        byte[] sig = null;

        try
        {
            // Create a new instance of DSACryptoServiceProvider.
            using (DSACryptoServiceProvider DSA = new DSACryptoServiceProvider())
            {
                // Import the key information.
                DSA.ImportParameters(DSAKeyInfo);

                // Create an DSASignatureFormatter object and pass it the
                // DSACryptoServiceProvider to transfer the private key.
                DSASignatureFormatter DSAFormatter = new DSASignatureFormatter(DSA);

                // Set the hash algorithm to the passed value.
                DSAFormatter.SetHashAlgorithm(HashAlg);

                // Create a signature for HashValue and return it.
                sig = DSAFormatter.CreateSignature(HashToSign);
            }
        }
        catch (CryptographicException e)
        {
            Console.WriteLine(e.Message);
        }

        return sig;
    }

    public static bool DSAVerifyHash(byte[] HashValue, byte[] SignedHashValue,
        DSAParameters DSAKeyInfo, string HashAlg)
    {
        bool verified = false;

        try
        {
            // Create a new instance of DSACryptoServiceProvider.
            using (DSACryptoServiceProvider DSA = new DSACryptoServiceProvider())
            {
                // Import the key information.
                DSA.ImportParameters(DSAKeyInfo);

                // Create an DSASignatureDeformatter object and pass it the
                // DSACryptoServiceProvider to transfer the private key.
                DSASignatureDeformatter DSADeformatter = new DSASignatureDeformatter(DSA);

                // Set the hash algorithm to the passed value.
                DSADeformatter.SetHashAlgorithm(HashAlg);

                // Verify signature and return the result.
                verified = DSADeformatter.VerifySignature(HashValue, SignedHashValue);
            }
        }
        catch (CryptographicException e)
        {
            Console.WriteLine(e.Message);
        }

        return verified;
    }
}

Don't [cross-post](http://security.stackexchange.com/questions/46939/dsa-generates-different-signatures-with-the-same-data) — CodesInChaos, Dec 14 '13 at 19:01

score 4 · Accepted Answer · edited Dec 13 '13 at 20:50

4

If you look at how DSA works (e.g. on Wikipedia), you'll see that the first step while generating a signature is selecting a random value:

Generate a random per-message value k where 0 < k < q

Later on you'll find that this randomness is necessary:

With DSA, the entropy, secrecy, and uniqueness of the random signature value k is critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping k secret), using a predictable value, or leaking even a few bits of k in each of several signatures, is enough to break DSA.

A very prominent case of breaking ECDSA (which is derived from DSA but working on elliptic curves) is mentioned thereafter.

Therefore, you should be happy you never got identical signatures. Otherwise your private key would have been endangered.

edited Dec 13 '13 at 20:50

poupou

43,413
6
77
174

answered Dec 13 '13 at 20:47

mkl

90,588
15
125
265

1

There are ways to generate DSA signatures deterministically. The basic idea is to use a hash of the message and the private key as k. Personally I strongly prefer those deterministic variants. – CodesInChaos Dec 14 '13 at 19:03
There are, yes, but you can't count on algorithms implemented in some os or sdk to do that. And if they do, their scheme may differ from yours. In essence all you have is the description of the algorithm which asks for random numbers. – mkl Dec 14 '13 at 22:12
@CodesInChaos i dont understand the per message key thing. If we generate different per message key other than private key, how can signatures be verified then? If the same message is signed twice which results in 2 different hashes, how can it be verified using the same public key only? confused! Please help! – fresh learner Jul 11 '17 at 05:11
@IbrahimNadir CodesInChaos does not say that there shall be a different *key* for each message. He merely points out that the *random per-message value k* may be created in a deterministic way as long as **A** this deterministic way cannot be reproduced by others and **B** for different messages you (nearly) always get different values. A hash of private key plus message has these properties, it cannot be reproduced by others who don't have the private key, and different messages result in different values unless there is a seldom collision. – mkl Jul 11 '17 at 08:44
@mkl Thank you for the response. I just want to clarify. Lets say we have the same message and we use two different random per-message value k to create two different hashes of the same message. How are they going to be verified at the receiver end? Is it the math that somehow verifies it because we send the hash along with the message. We never send the per message value k. Just a confusion in my head. Can you please clarify? – fresh learner Jul 11 '17 at 12:14
@IbrahimNadir Don't confuse the hashes! The hashing mentioned by CodesInChaos and explained by me is **not** the hash value *signed* in the process, it merely is a method to create a pseudo-random number deterministically based on some input. The *signed* hash still is the normal hash of the message itself. – mkl Jul 11 '17 at 13:56

score 1 · Answer 2 · edited May 23 '17 at 12:29

1

AFAIK, it is generating a new key pair each time, so the signature should be different, right?

        // Create a new instance of DSACryptoServiceProvider to generate
        // a new key pair.
        using (DSACryptoServiceProvider DSA = new DSACryptoServiceProvider())
        {
            privateKeyInfo = DSA.ExportParameters(true);
            publicKeyInfo = DSA.ExportParameters(false);
        }

Should you not be saving the key pair and load the same pair each time to achieve the same result each time? see How to store/retrieve RSA public/private key

edited May 23 '17 at 12:29

Community

1
1

answered Dec 13 '13 at 16:00

Rudi

3,124
26
35

could you please try adding `byte[] SignedHashValue1 = DSASignHash(HashValue, privateKeyInfo, "SHA1");` after `byte[] SignedHashValue = DSASignHash(HashValue, privateKeyInfo, "SHA1");` and compare them – Ibrahim.I Dec 13 '13 at 16:02
It gives different signatures within the same session of debugging – Ibrahim.I Dec 13 '13 at 16:13
I'm not familiar with the DSA algo, so I can't say if given the same HashValue it can still verify the different SignedHashValues for it. – Rudi Dec 13 '13 at 16:21
I'm not as familiar with DSA as RSA, but I know certain RSA signature schemes incorporate random data and so results will *always* differ. – Duncan Jones Dec 13 '13 at 16:48
DSA (just like ECDSA) requires the user of a random value during signature creation. – mkl Dec 13 '13 at 17:33

DSA generates different signatures with the same data

Code from article:

2 Answers2

Linked