Assuming I'm working on an environment that currently uses MD5 to hash passwords, and I want to switch to something more secure.

I already heard of bcrypt, but I had another idea.

Would it be possible to use RSA2048 to hash passwords if I just threw away the private key of the key pair?

If so, is that less secure then using a dedicated hashing algorhitm like for instance bcrypt? (Assuming you use salt/pepper in both cases in addition):

I have following process in mind:

  • Every password gets its own public RSA2048 key, the private keys are discarded.

  • MD5 Hash the password

  • Encrypt the MD5 Hash using RSA2048 with that password's specific RSA2048 public key
  • Pepper the result with pepper of fixed lenght

Is this a secure password hashing scheme? On the same level as running a password through bcrypt or scrypt?

  • Are you going to generate a new key pair for each password (very expensive) or use the same key for all? – 5gon12eder Feb 8 '17 at 8:37
  • @5gon12eder My first idea was to use one key for all, but I suppose generating a new key for each password wouldn't be too bad (You'd only have to do it during user creation and password changes, right?). Wouldn't that in essence work like a super-salt? – Magisch Feb 8 '17 at 8:39
  • 4
    See also Using RSA for hash – Sjoerd Feb 8 '17 at 8:39
  • 1
    The problem with using a single key for all passwords is that if an attacker breaks (or otherwise obtains) that key, they have a universal way to decrypt an arbitrary number (all) of your passwords. While you could argue that this is not feasible, I still see it as a disadvantage compared to using a non-bijective hash function which an attacker would have to break for each password individually. – 5gon12eder Feb 8 '17 at 8:46
  • 2
    @Magisch: If someone make a collision on the MD5, they'll have a collision on the RSA as well. Also, adding a single step of RSA wouldn't really add sufficient work factor against brute force attack. Your proposed method doesn't really address these issues. – Lie Ryan Feb 8 '17 at 10:56
up vote 4 down vote accepted

Your proposed hashing scheme has no real advantage over existing schemes and some potential downsides.

A password hashing scheme must have three key properties:

  • it must be one-way: no way to recover the password from the hash, the only way to find the password is to guess it;
  • it must be salted: each hash incorporates a unique value so that an attacker can't reuse the same computations to attack many hashes;
  • it must be expensive (at the very least, slow): calculating a hash must require significant resources, so that mass attacks require a huge investment in hardware.

Your proposed scheme is one-way — but the first hashing step with MD5 is sufficient for that. (Incidentally, although MD5 is has no known weaknesses for this use case, it's sufficiently broken that it's strongly recommended not to use it at all. But you could just substitute SHA-256 and your question would remain valid, as would my answer.) Performing an RSA operation on top doesn't improve this aspect.

Your proposed scheme is salted, by using a different key for each hash. That's fine. But there's an easier way to do the salting: you essentially take hash(password + salt) instead of hash(password). (The devil is in the details but I'll stick to the high-level summary here.) So we already know how to do this.

Your proposed scheme is not expensive. Expensiveness needs to be tunable, to go to the maximum resource usage that is bareable on the legitimate server that verifies the password, and keep up with technological evolution (e.g. increase the number of iterations from 105 to 106 every 5 years as computers are ~10 times faster). A simple way to do this is to take a fast hash and iterate it, which requires a long sequential computation; this is what PBKDF2 does. More complex schemes try to be optimal on PC hardware and less good on e.g. GPU or FPGA; see Do any security experts recommend bcrypt for password storage?. It is not clear how your proposal could be tuned for expensiveness: use larger RSA keys?

A major potential flaw in your proposal is that the core RSA operation (modular exponentiation) does not have good security properties when used directly, because it is subject to algebraic relations such as xe·ye = (x·y)e. This is why “RSA encryption” is not a simple exponentiation, but instead adds some padding to the data; OAEP is the modern standard. You cannot use OAEP as it is because it's non-deterministic: running it twice on the same input yields different ciphertexts. It is probable that a derandomized version of OAEP would work, or even some simpler scheme given that you're in a very special case where no ciphertext is ever going to be decrypted, which means that many attacks on encryption schemes are not applicable.

Note that you cannot go as far as not adding any padding, not without additional constraints: y = xe mod n absolutely must wrap modulo n, otherwise x can be computed from y simply by taking the eth root in the reals. As specified in your question, e is not constrained, allowing the common choice of e = 3. Since x is a 128-bit number (256-bit if you use SHA-256 instead of MD5) and n is a 2048-bit number, xe would not wrap, so x can be recovered trivially from y. There's still the one-wayness of the hash, but you lose the salting which was only provided by the RSA step. There are easy solutions to this problem, of course: require a sufficiently large e, and include a salt in the hashed data. But if you have to rely on the rest of the design, why would you put RSA into the mix at all? This illustrates the risk of adding more stuff to a cryptographic algorithm: you can make it weaker even if you thought you were adding a security feature.

To summarize:

  • Your proposal lacks a key property of password hashing functions: expensiveness.
  • It may be possible to modify this proposal to have this property, but it is not clear how.
  • You add a potential attack vector (algebraic relations); defenses exist but it is not clear what you are gaining.
  • So what you are saying (in condensed form) is that I'd be better off using a garden variety bcrypt implementation? – Magisch Feb 8 '17 at 18:10
  • @Magisch Sure. If you aren't a professional cryptographer, it's always a safe bet that you'd be better off with an algorithm that has been vetted by professional cryptographers rather than rolling your own. Even if you are a professional cryptographer, you are better off with an algorithm that has been vetted by many professional cryptographers than doing your own thing. As Schneier puts it (and Babbage before him…), anybody can invent a cryptosystem they can't break, the trick is to invent a system that others can't break. – Gilles Feb 8 '17 at 18:17
  • I'm a apprentice software developer and standard modus operandi in my company is using md5 to hash passwords. I read about it a bit and it says that MD5 (without salt or pepper) is ridiculously vulnerable to rainbow table attacks and collision. That prompted me to read up on salt and pepper and at least look into doing something less vulnerable for my applications. – Magisch Feb 8 '17 at 18:21
  • @Magisch Ok, then as a practical matter, go read our reference question on the topic. Thomas's answer is interesting, but if you just want the TL&DR, it's “use PBKDF2, bcrypt or scrypt”. BTW, collisions are not the problem with the use of MD5 for password hashing (they're a problem for most other uses of MD5); even rainbow tables aren't the #1 problem: most people's passwords' MD5 can be found in a simple Google search! Salting is absolutely indispensible to defend against this attack method. – Gilles Feb 8 '17 at 18:28

Assuming I'm working on an environment that currently uses MD5 to hash passwords, and I want to switch to something more secure.

If this is a practical question, then it deserves a practical answer:

Don't invent your own password storage schemes. Do it according to best practices.

There is no benefit to your scheme over using the standard options (pbkdf/bcrypt/scrypt/argon2). There are many potential security downsides, plus general bugs in the implementation (since you're constructing this yourself instead of using a commonly-used library). Implementing this in a production environment borders on professional negligence.

On the subject of its security: at the very least you suffer from it being easy to parallelize, so an attacker who has obtained a dump of the database can do the old "spin up a bunch of ec2 instances" attack to crack your hashes. This is the point behind bcypt, but you don't seem to have addressed that at all.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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