Could a fixed RSA encryption be used instead of a salt to prevent rainbow table attacks?

Question

It's common to use a salt before hashing a password in order to prevent an attack by rainbow tables.

Would it also work to encrypt the password for instance by RSA encryption - by a permanent RSA private key stored on the server - before hashing?

In other words: $hash = SHA(RSA(password))$

For me this looks secure because rainbow tables wouldn't work with the encrypted cipher $RSA(password)$, would they?

(Side note: Since that RSA private key is not used for encryption at all, it would never have to been replaced...it would just work as a totally deterministic pseudo-random function in this case!)

Answer 1

I don't see a point of using RSA for password hashing. Using SHA and RSA will not make the bruteforce attack slower. The massive GPU/ASIC attacks will still work if we assume the public key $(e,n)$ is known. That is why we need memory hard functions to make the attacks slower. Sticking the standard is still better like using Argon2id ( Argon2 was the winner of the Password Hashing Competition in 2015). The unique salt also helps to eliminate the rainbow tables. Rainbow tables are dead for passwords system that deploys unique salts!.

A minor point is that one doesn't need to store the RSA private key $(d,n)$ since one cannot reverse the SHAx. So it is useless.

Back to Rainbow

in case of protection against the rainbow tables, one needs to make sure that every password needs a domain separations. This is achieved by unique salt for all. If you want to use the RSA then you need to use OAEP padding or PKCS#1 v1.5. padding. Both are probabilistic encryption scheme that as long as you have a good random number source like /dev/urandom then if you encrypt the same message again and again you will get different results, up to a huge limit of course ( the size of $r$ in the OAEP). One can think of the salt as this randomization.

A side note: the pepper, which is unique salt for each application server, is used to separate the domains of the applications in the case of hitting the same salt for the same user. Also, If an attacker downloads the users' table with only an SQL injection, then they cannot apply even brute-force without the pepper of the server.

Note 2: According to Hashcat list, only OpenSSH uses RSA in a combined mode RSA/DSA/EC/OpenSSH

---

Addendum

This part is based on the comments of @fgrieu in the case that @marcus considered these;

1. $(\text{salt},hash = \text{PasswordHash}(\text{salt},\text{DeterministicPadding}(\text{password})^d\bmod n))$

2. $(\text{salt}, hash = \text{Hash}(\text{DeterministicPadding}(\text{salt}\mathbin\|\text{password})^d\bmod n))$

Here the deterministic padding stands for padding the message for RSA encryption, but deterministically, like RSASSA-PKCS1-v1_5.

It is obvious that if the salt is unique for each user then it is already secure against the rainbow tables. The password crackers if access to the passwords' hashes, cannot test it without the knowledge of the private key.

The biggest problem is the protection of the RSA private key. The usual approach is using HSM to handle those encryptions where the RSA key is stored, too, however, for heavy systems, it may be a bottleneck for the speed. This is no a real comparison, and the usual advice for the password hashing algorithms is adjusting the iteration so that it takes around 1 second per user. This is for user-friendliness. i.e. the general user may not want to wait too much for the login process.

Knowing the public key $(n,e)$ won't help the attackers since they, as of public knowledge, cannot break RSA > 829-bit. See current records on How big an RSA key is considered secure today?

We can consider this RSA operation as a pepper of the application server, too. Also, instead of RSA, one can use HMAC-SHA256 for the same usage, which has a lower key size.

In short, if the key can be protected, It has more protection against the usual approach.

Answer 2

What you are describing is called pepper.

What you are doing is just using RSA as a cryptographic hash function. That probably reduces performance and makes your system more complicated.

Generally, people install a random number directly in to the program as a literal. It is safe as long as your source code and binary is safe. You could use it as an RSA key, but the more efficient way is to add the pepper the same way you add the salt. (the clue is in the name.)

Basically, you take the password, append the salt, append the pepper, and hash them together.

Answer 3

Rainbow tables are essentially an optimized dictionary attack, which rely on two assumptions:

• That two different applications will hash the same input to the same output, e.g. the password "Password123" will always hash to "42f749ade7f9e195bf475f37a44cafcb". This allows the attacker to re-use a rainbow table database to attack multiple targets.
• That two different entries within one application will hash the same input to the same output, e.g. two different users with the password "Password123" will have the same hash stored. This allows the attacker to calculate hashes based on a dictionary and try them against all the entries at once.

Adding additional steps to the hashing process - appending a global "pepper", double-hashing, encrypting-then-hashing - will generally break the first assumption: your hash for "Password123" now no longer looks like my hash for "Password123".

However, to break the second assumption, you need to do something different for every entry in your application, and that is what adding a salt provides. The only way an encryption step would perform the same function is if it happened to contain a salt of its own, with the encryption being essentially irrelevant.

In general, it's a bad idea to roll your own crypto algorithms, or combine them in unintended ways, without a really strong knowledge of the underlying theory, so you're better off sticking to well-understood-hash-function( password + per-user-salt + per-application-pepper ).

Answer 4

Both a hash (like SHA-1) and a cipher (like RSA) are designed to not be reversible. That is, given their outputs (the digest or ciphertext) it should not be feasible to figure out what the input was.

The value of a salt is not in making it harder to figure out what the password was from the hashed password. Passwords are often easy to guess. A salt makes it harder for an attacker to guess, because the salt is different for each user. Thus, the attacker must guess at individual users ("user 3198721 has password 'qwerty'") rather than guessing at the whole database at once ("some user in this database has password 'qwerty'").

This significantly increases the number of guesses that must be made, and thus the time required to successfully compromise a user, especially when the hash function is selected to be expensive to compute as all good password hash functions are. A well designed system would never use SHA, but instead something like bcrypt, scrypt, or PBKDF2.

Adding RSA encryption to the mix does not, in itself, accomplish what a salt does. Perhaps with RSA encryption, the digest of "qwerty" is not "63edc12362821bd115f7" but instead "ee69076c5a27c1c476". But it's still the same for every user, and so one guess can be checked against all users in the database.

There is some benefit in that the attacker must also compromise the encryption key, and that's worth something. However this is usually accomplished by storing the entire user database in encrypted storage, rather than encrypting each password individually before hashing it. One reason: it makes rotating the encryption key possible.

However, some encryption schemes use an initialization vector (IV), which is similar to a salt in that it's a random value. RSA does not always use an IV, but it could, in which case your proposed scheme would essentially be salting the passwords by a different name.