Asymmetric password encryption - Viable? Which algorithm?

Question

We have an application that requires cleartext passwords for user authentication because of the authentication mechanism in use (RADIUS/CHAP), which unfortunately we cannot change. Since we don't want to store cleartext passwords, an idea is to use asymmetric encryption to secure them as good as possible. After creating/chaning a password, it will be encrypted with the public key and replicated through more or less unsecured channels to the authentication systems. When a user tries to authenticate, the encrypted password will be decrypted with the private key (which has to be available on the authentication servers, obviously).

So we would have a database with lots of encrypted passwords, but all encrypted with the same key. After some research I see that this not the way asymmetric encryption is commonly used. Usually the payload is encrypted with a block cipher and the symmetric key is encrypted with an asymmetric key. But since passwords are quite short I wonder if this additional encryption layer can safely be avoided or if this would be simplification would be a serious risk.

Related to this: What algorithm would you recommend? I kind of narrowed it down to RSA and Elgamal, mostly because these two seem to be most widely used and are available through well-known libraries (OpenSSL, gcrypt). RSA seems to require longer keys to provide the same security, so Elgamal seem to be the better option there's no other argument against it.

Comments?

Answer 1

This seems OK assuming you can trust the authentication servers to leak neither the private key nor the deciphered passwords; and, if you use RSA, assuming you use a standard encryption padding with randomization, e.g. one of the two RSAES schemes in PKCS#1.

Elgamal indeed can give you shorter cryptograms, which might be desirable in the context (an Elgamal cryptogram consists of two group elements; thus when the group is a 256-bit elliptic curve, you get security arguably better than 3048-bit RSA for 17% of the size of each asymmetric cryptogram).

But if ciphertext size is an issue, you can use hybrid encryption which gives you minimal ciphertext expansion, and can reduce the cost of deciphering one more password. That's by enciphering all passwords using a symmetric scheme (e.g. AES GCM, which also gives integrity) using the same random key, itself enciphered with an asymmetric scheme. As an additional (marginal) benefit, each server can have its own private key with minimal ciphertext expansion. Each server needs to store only a single RSA cryptogram (or whatever asymmetric cryptosystem is used), which holds the symmetric key allowing to decipher any password.

None of this will survive compromise of a server, unless everything sensitive (including RADIUS/CHAP) is in a separate trusted environment, such as an HSM or Smart Card.

Answer 2

I don't see a way to respond to fgrieu's answer. So am responding here. But I don't think his answer might work. The hybrid encryption scheme (which is the usual/practical way of encrypting using a public key) still produces the same number of bytes as the modulus, meaning if you are using a 2048 bit key it will produce 2k bytes. This might not be viable in the RADIUS/CHAP protocol if there is an assumed max limit for the password field. These are old protocols and I will not be surprised if there is a max limit on these fields. Barring that I see no problem.

EDIT: @agrieu - That is what I am saying too exactly. All I am saying is there could be some practical problems with the solution though theoretically possible.