Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I know this is not the right way to store passwords, but I'm asking this from a theoretical perspective:

Suppose a web site's passwords were encrypted with RSA asymmetric encryption and the private decryption key was discarded, effectively making it a one-way trip. Now these password "digests" were somehow leaked.

Would it take any longer to decrypt the RSA encrypted passwords than it would to crack the passwords had they been hashed with PBKDF2?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

The two situations are not comparable. Indeed, RSA encryption, like all other asymmetric encryption algorithms, is a randomized process: if you encrypt the same data twice, with the same public key, you do not get the same encrypted message twice. This is by design: since asymmetric encryption uses the public key which is, yay, public, everybody can encrypt data with that key. Since we want to avoid exhaustive search on the data itself, we need this non-deterministic behaviour. As described in PKCS#1, at least 8 random padding bytes are appended to the input data before applying the modular exponentiation which is at the core of RSA encryption.

This has two consequences:

  1. This may not be cracked by enumerating possible passwords. If the attacker "guesses" the right password, he still cannot know that the password matches the encrypted one.
  2. Nobody can tell whether a given password matches what has been encrypted. Therefore, a RSA-encrypted password cannot be used to verify passwords (if the private key is lost), contrary to a hashed version of the password. Your passwords are as good as lost, and no server will be able to tell whether a given password is correct or not by using these RSA-encrypted passwords.

So it does not really make sense to compare "cracking times" between RSA and PBKDF2.

Now, of course, some wannabe programmer might have imagined something which vaguely looks like RSA, but without the random padding, and thus can be used as a password hash. This would indeed be a (homemade) password hash. Assuming that the said programmer did not botch it too thoroughly (an already quite optimistic assumption), then brute forcing would apply, with as much efficiency as the algorithm allows: this is simply a matter of trying passwords, a process which goes as fast as the algorithm is fast. Also, possibly, this not-quite-RSA password hashing would be unsalted, allowing for parallel attack of multiple passwords with cost sharing. PBKDF2 includes salts and also configurable slowness (with an iteration count), precisely to better resist such attacks.

share|improve this answer
3  
If you were a Dave, you could encrypt with RSA properly, with random padding, and claim that the padding is your salt and store it in plaintext. Which, as befits homemade cryptography, is more subtly wrong (in addition to not being slow). –  Gilles Jun 6 '13 at 23:09
    
Thanks for the detailed answer. I never realized that RSA produces a randomized cipher text, but now it makes sense why it would need to. –  John Jun 7 '13 at 13:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.