#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2011
    Posts
    2
    Rep Power
    0

    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 RSA-PSS 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 RSA-PSS and PKCS1-v1_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:
    1. Generate a public/private key pair
    2. Sign the password with the private key
    3. Discard the private key
    4. 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?
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    This is not a good way to protect your database. First in PKCS1.5 or RSA-PSS 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 non-traditionally 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 DSA-verify between the dictionary of hashes and the user's password (yes it's more expensive, but again that's not a well-researched use of DSA--there 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 signature--I.e. easy to perform a dictionary attack. (Since you usually don't sign 8-byte 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 verify--like 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 password-change requests)
    Last edited by OmegaZero; June 24th, 2011 at 05:37 PM.
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  4. #3
  5. No Profile Picture
    Lost in code
    Devshed Supreme Being (6500+ posts)

    Join Date
    Dec 2004
    Posts
    8,317
    Rep Power
    7170
    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 use-case, 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
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2011
    Posts
    2
    Rep Power
    0
    Thank you both for your comments.

    Originally Posted by OmegaZero
    First in PKCS1.5 or RSA-PSS 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 non-traditionally 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 DSA-verify 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.

    E-Oreo, no offense, but your comments seem a little off target.

    Originally Posted by E-Oreo
    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 E-Oreo
    In your particular use-case, 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 E-Oreo
    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 get-go.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Feb 2008
    Posts
    601
    Rep Power
    43
    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.

IMN logo majestic logo threadwatch logo seochat tools logo