June 24th, 2011, 04:14 PM

Public digital signature with secret message (OR an alternative to password salting)
I want to store the signature of a secret message and a public key, without storing the message itself or the private key that was used to sign it. If I receive the same message in the future, I need to be able to verify that it matches the original signature using only the public key.
This sounds like a job for a digital signature algorithm like RSAPSS or DSA, but I need to to guarantee that the message itself is not revealed if the signature were made public. I don't know which, if any, signature algorithms have this property. In fact, I'm pretty sure RSAPSS and PKCS1v1_5 do not. What about DSA? Rabin? BLS?
Can anyone help me out here?
Here's my concrete use case: verifying passwords without storing them. The pervasive thinking is to hash passwords with a salt, either concatenated with the password before hashing or as an HMAC key. While this renders big precomputed dictionaries ineffective, it doesn't prevent an attacker who's compromised a system from generating new dictionaries once he knows the salts. I believe the current state of the art is to employ a key derivation function or other form of key stretching, which makes the former attack infeasible.
Key stretching may be the best approach, but I'm wondering why I've never seen anyone store passwords as digital signatures as an alternative salting.
Here's how it would work to store a new password:
 Generate a public/private key pair
 Sign the password with the private key
 Discard the private key
 Store the signature and the public key
As long as the password itself (or the password digest depending on the algorithm) cannot be extracted from the signature, I think this would work great. Any thoughts? Are there any digital signature algorithms where the signed message is not compromised if the signature is made public along with the public key?
June 24th, 2011, 05:34 PM

This is not a good way to protect your database. First in PKCS1.5 or RSAPSS signatures, the hash can be recovered. If the attacker has the public key (which seams likely since the server will need it and you have it included in the database) they can recover the hash and your passwords are no more secure than if you ran them through an unsalted SHA (or your hash of choice)i.e. making them less secure than the traditional salted hash.
Other algorithms like DSA don't provide a way to recover the hash of the message being signed. However I would not trust this to protect your passwords. Using a crypto nontraditionally is always bad since there is little to no research to prove the security of the implementation. Also you've only changed the dictionary attack to perform a DSAverify between the dictionary of hashes and the user's password (yes it's more expensive, but again that's not a wellresearched use of DSAthere may be flaws one can exploit).
The design of signature algorithms is working against you here. The idea is to make it infeasible to forge a signature while leaving it easy to verify a signatureI.e. easy to perform a dictionary attack. (Since you usually don't sign 8byte messages composed of common words this isn't a big deal.) For protecting passwords what you really want is an algorithm that is expensive to verifylike how bcrypt runs a few hundred salted hashes over the input.
Current methods for improving protection on passwords involve:
* Using a different salt for every user so that a separate dictionary would have to be computed to attack each password.
* Using an expensive hashing algorithm such as bcrypt or HMACs to make it that much harder to compute a dictionary.
(edit: Generating a new key pair is a rather costly operation. I'd worry that your server could be DOS'd by an attacker firing off a stream of passwordchange requests)
Last edited by OmegaZero; June 24th, 2011 at 05:37 PM.
sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}>(\&Meh);
June 24th, 2011, 05:46 PM

To save you the trouble of reading my entire post, let me start by saying that no asymmetric encryption algorithms consist of a public key that cannot decrypt messages encrypted using the private key, as this defeats the entire point of asymmetric encryption.
This fact alone defeats your idea, but if you keep reading I will explain why.
In your particular usecase, it would be a very bad idea to encrypt the original password using the private key and then save that as your signature. If you encrypt the password using the private key and then store the encrypted password along with the public key, and attacker can simply obtain the password by decrypting the encrypted message using the stored public key (assuming that if they can obtain the encrypted password they can also obtain the public key).
If you first hash the password and then encrypt the hash using the private key, then it is impossible for the attacker to easily recover the original password using only the public key and the signature. However, if the attacker has the public key and the signature, then they can decrypt the signature and get the hash of the password, and they are right back at the step of attacking a hash (this is why your algorithm is pointless). Since this decryption can be done in essentially O(1) time, there is no benefit in terms of security to this. Even worse, if you hadn't salted the hash as part of the algorithm then it could easily be attacked using a rainbow table.
I need to to guarantee that the message itself is not revealed if the signature were made public
That is essentially the definition of a hash. In a digital signature algorithm, it is assumed that the receiver already has the message; thus there is no requirement for the signature to protect the message (although signatures are frequently based on hashing algorithms, so often they do actually protect the message, but it's the hash part of the algorithm that protects the message, not the digital signature part).
PHP FAQ
Originally Posted by Spad
Ah USB, the only rectangular connector where you have to make 3 attempts before you get it the right way around
June 24th, 2011, 07:33 PM

Thank you both for your comments.
Originally Posted by OmegaZero
First in PKCS1.5 or RSAPSS signatures, the hash can be recovered. If the attacker has the public key (which seams likely since the server will need it and you have it included in the database) they can recover the hash and your passwords are no more secure than if you ran them through an unsalted SHA (or your hash of choice)i.e. making them less secure than the traditional salted hash.
Agreed, of course. This was the basic premise of my original post: which algorithms don't provide a way to recover the message or message digest from the signature?
Originally Posted by OmegaZero
Other algorithms like DSA don't provide a way to recover the hash of the message being signed. However I would not trust this to protect your passwords. Using a crypto nontraditionally is always bad...
I absolutely agree that crypto technologies shouldn't be used beyond their intended purpose, but I'm suggesting that by restating the password protection problem it can be seen as a subset of the problems that digital signatures are designed to address. With the only added requirement being that the signature itself does not reveal the message or message digest. I suspect the presence of this feature can be easily proved or disproved for DSA.
Originally Posted by OmegaZero
Also you've only changed the dictionary attack to perform a DSAverify between the dictionary of hashes and the user's password...
Yes. I'm not trying to contrive a solution to that; I'm simply exploring an alternative to salting, which is vulnerable to the same attack.
EOreo, no offense, but your comments seem a little off target.
Originally Posted by EOreo
To save you the trouble of reading my entire post, let me start by saying that no asymmetric encryption algorithms consist of a public key that cannot decrypt messages encrypted using the private key, as this defeats the entire point of asymmetric encryption.
No one is disputing this.
Originally Posted by EOreo
In your particular usecase, it would be a very bad idea to encrypt the original password using the private key and then save that as your signature...
I'm not talking about encrypting passwords. I'm talking about actual digital signatures using signature algorithms, not encryption algorithms.
Originally Posted by EOreo
If you first hash the password and then encrypt the hash using the private key, then it is impossible for the attacker to easily recover the original password using only the public key and the signature. However, if the attacker has the public key and the signature, then they can decrypt the signature and get the hash of the password, and they are right back at the step of attacking a hash (this is why your algorithm is pointless).
You've basically described the RSA digital signature algorithms, which were ruled out from the getgo.
June 27th, 2011, 02:04 PM

Why is knowing the hash a disadvantage? The whole point is that you can't easily reverse back to the original string that results in that hash.
If you create a HMAC and run that operation several hundred times, there should be no issue.
At the end of the day, if an attacker is snooping around in your database, regardless of the form you chose, he/she will still have deterministic output from the original input.
Don't go trying to invent a method  chances are it won't be secure.
You'd also be wise to try and prevent your database being accessed in the first place. Security isn't one thing in isolation, less so when you make it up.
Best regards,
AstroTux.