The Curious Flaw in DSA Digital Signatures
Digital signature mimics a pen-paper signature. When we sign on a piece of paper using a pen, we vouch for something. We stand guarantee for something. For example, when we sign a cheque, we commit that we would honor the payment. Barring the case of cheque bouncing, this commitment works. Digital signatures attempt to do the same thing in electronic transactions. Great confusions about the term digital signature exist, and hence a quick clarification about the technology would help.
Every human being has a unique thumbprint. Given a person, we can precisely determine whether a thumbprint belongs to her or no. Similarly, a technology by the name message digest or hash exists. For every unique message, there is a definite message digest. In other words, we can take a message (the term message can mean a file, an email, all contents of a directory, or the entire disk – any piece of data of any size) and run a message digest algorithm on it. No matter how many times we do it, for a message, the digest must always be the same. Its length or contents will never change. This concept is shown in the figure below.
Typical message digest sizes are 128 bits, 160 bits, 256 bits, and so on, depending on the message digest algorithm (MD5, SHA-1, SHA-256) used.
Going one step further, if we compute the digest of a message, and then encrypt the message digest with the sender’s (or creator’s) private key, the output of the process is a digital signature of the original message. Since for a message, the digest can never change, and if this never-changing digest is encrypted by the sender’s private key (which is supposed to be known only to the sender), the signature will also never change! This is how the guarantee of digital signature works. This is how, even several years later, we can prove two things: (1) the message was indeed sent by the sender, who claims to have sent it, and (2) the contents of the message since it was signed were not changed (otherwise the signature verification would fail). There are two primary algorithms for digital signature computation: RSA and DSA.
Given that the digital signature for a message must never change, it is safe to assume that regardless of which of the algorithms (RSA or DSA) we use for computing digital signature, its behavior be no different. In other words, the digital signature that we compute over a message by using any of these two techniques should always remain the same. However, and this shocked us when we were doing some experimentation for a project, we realized that while the RSA algorithm always computes the same digital signature for a message no matter how many times we repeat the process; the DSA algorithm behaves very strangely!
When we use the DSA algorithm to compute the digital signature of a message, every time the signature is potentially, well, different! That is something that amazed me so much that I was sure there was some bug in our Java code somewhere. But then, when we attempted to verify the signature by using the standard code, it would verify it successfully! This meant that while the DSA signature was different every time, it kept something internally (timestamp, some unique ID), which allowed the external representation of the signature to be different every time. Hence, to naked eyes, the signature seems to be different every time. But for the code verifying the signature, it is never different!
This is a very confusing point, which has not been documented properly. This can lead to a serious misunderstanding that DSA has a flaw. As it is, DSA was perceived to be weak based on an alleged propaganda by RSA Inc (since they wanted to market their own digital signature algorithm). Moreover, big companies such as IBM, Novell, Lotus, Apple, Microsoft, DEC, Sun, Northern Telecom etc. had made large investments in implementing the RSA algorithm. Therefore, they were also against the use of DSA. This technical proof would make it sound right! However, that is not true at all, and it is quite acceptable to use DSA without any such worries.
To summarize, people implementing cryptography in their projects should be aware that digital signatures are computed differently by RSA and DSA. RSA computes the same signature every single time, and of course, it verifies it correctly as well. DSA, on the other hand, computes a different signature every time, and yet, is able to verify it successfully. There is no need to panic because of this – it is quite normal, and can be safely ignored!
About the author: Atul Kahate is Head – Technology Practice, Oracle Financial Services Software Limited (formerly i-flex solutions limited). He has authored 20 books on Information Technology, 2 on cricket, and over 2000 articles on both of these in various newspapers/journals. His site can be visited at www.atulkahate.com and he can be reached via email at [email protected].
Related
* What are Digital Signatures? Compute and Verify a Digital Signature
* Cryptographic Algorithms – Impact On Application Performance
* Xml Security using Xml Encryption and Xml Digital Signature
