Two-Way Encryption: I Need to Store Passwords That Can Be Retrieved

Two-way encryption: I need to store passwords that can be retrieved

Personally, I would use mcrypt like others posted. But there is much more to note...

How do I encrypt and decrypt a password in PHP?
See below for a strong class that takes care of everything for you:
What is the safest algorithm to encrypt the passwords with?
safest? any of them. The safest method if you're going to encrypt is to protect against information disclosure vulnerabilities (XSS, remote inclusion, etc.). If it gets out, the attacker can eventually crack the encryption (no encryption is 100% un-reversible without the key - As @NullUserException points out this is not entirely true. There are some encryption schemes that are impossible to crack such as one-time pad).
Where do I store the private key?
I would use three keys. One is user supplied, one is application specific and the other is user specific (like a salt). The application specific key can be stored anywhere (in a configuration file outside of the web-root, in an environmental variable, etc.). The user specific one would be stored in a column in the db next to the encrypted password. The user supplied one would not be stored. Then, you'd do something like this:
```
$key = $userKey . $serverKey . $userSuppliedKey;
```
The benefit there, is that any two of the keys can be compromised without the data being compromised. If there's a SQL injection attack, they can get the $userKey, but not the other two. If there's a local server exploit, they can get $userKey and $serverKey, but not the third $userSuppliedKey. If they go beat the user with a wrench, they can get the $userSuppliedKey, but not the other two (but then again, if the user is beaten with a wrench, you're too late anyway).
Instead of storing the private key, is it a good idea to require users to enter the private key any time they need a password decrypted? (Users of this application can be trusted)
Absolutely. In fact, that's the only way I would do it. Otherwise you'd need to store an unencrypted version in a durable storage format (shared memory, such as APC or Memcached, or in a session file). That's exposing yourself to additional compromises. Never store the unencrypted version of the password in anything except a local variable.
In what ways can the password be stolen and decrypted? What do I need to be aware of?
Any form of compromise of your systems will let them view encrypted data. If they can inject code or get to your filesystem, they can view decrypted data (since they can edit the files that decrypt the data). Any form of replay or MITM attack will also give them full access to the keys involved. Sniffing the raw HTTP traffic will also give them the keys.
Use SSL for all traffic. And make sure nothing on the server has any kind of vulnerabilities (CSRF, XSS, SQL injection, privilege escalation, remote code execution, etc.).

Here's a PHP class implementation of a strong encryption method:

/**
 * A class to handle secure encryption and decryption of arbitrary data
 *
 * Note that this is not just straight encryption.  It also has a few other
 *  features in it to make the encrypted data far more secure.  Note that any
 *  other implementations used to decrypt data will have to do the same exact
 *  operations.
 *
 * Security Benefits:
 *
 * - Uses Key stretching
 * - Hides the Initialization Vector
 * - Does HMAC verification of source data
 *
 */
class Encryption {

    /**
     * @var string $cipher The mcrypt cipher to use for this instance
     */
    protected $cipher = '';

    /**
     * @var int $mode The mcrypt cipher mode to use
     */
    protected $mode = '';

    /**
     * @var int $rounds The number of rounds to feed into PBKDF2 for key generation
     */
    protected $rounds = 100;

    /**
     * Constructor!
     *
     * @param string $cipher The MCRYPT_* cypher to use for this instance
     * @param int    $mode   The MCRYPT_MODE_* mode to use for this instance
     * @param int    $rounds The number of PBKDF2 rounds to do on the key
     */
    public function __construct($cipher, $mode, $rounds = 100) {
        $this->cipher = $cipher;
        $this->mode = $mode;
        $this->rounds = (int) $rounds;
    }

    /**
     * Decrypt the data with the provided key
     *
     * @param string $data The encrypted datat to decrypt
     * @param string $key  The key to use for decryption
     *
     * @returns string|false The returned string if decryption is successful
     *                           false if it is not
     */
    public function decrypt($data, $key) {
        $salt = substr($data, 0, 128);
        $enc = substr($data, 128, -64);
        $mac = substr($data, -64);

        list ($cipherKey, $macKey, $iv) = $this->getKeys($salt, $key);

        if (!hash_equals(hash_hmac('sha512', $enc, $macKey, true), $mac)) {
             return false;
        }

        $dec = mcrypt_decrypt($this->cipher, $cipherKey, $enc, $this->mode, $iv);

        $data = $this->unpad($dec);

        return $data;
    }

    /**
     * Encrypt the supplied data using the supplied key
     *
     * @param string $data The data to encrypt
     * @param string $key  The key to encrypt with
     *
     * @returns string The encrypted data
     */
    public function encrypt($data, $key) {
        $salt = mcrypt_create_iv(128, MCRYPT_DEV_URANDOM);
        list ($cipherKey, $macKey, $iv) = $this->getKeys($salt, $key);

        $data = $this->pad($data);

        $enc = mcrypt_encrypt($this->cipher, $cipherKey, $data, $this->mode, $iv);

        $mac = hash_hmac('sha512', $enc, $macKey, true);
        return $salt . $enc . $mac;
    }

    /**
     * Generates a set of keys given a random salt and a master key
     *
     * @param string $salt A random string to change the keys each encryption
     * @param string $key  The supplied key to encrypt with
     *
     * @returns array An array of keys (a cipher key, a mac key, and a IV)
     */
    protected function getKeys($salt, $key) {
        $ivSize = mcrypt_get_iv_size($this->cipher, $this->mode);
        $keySize = mcrypt_get_key_size($this->cipher, $this->mode);
        $length = 2 * $keySize + $ivSize;

        $key = $this->pbkdf2('sha512', $key, $salt, $this->rounds, $length);

        $cipherKey = substr($key, 0, $keySize);
        $macKey = substr($key, $keySize, $keySize);
        $iv = substr($key, 2 * $keySize);
        return array($cipherKey, $macKey, $iv);
    }

    /**
     * Stretch the key using the PBKDF2 algorithm
     *
     * @see http://en.wikipedia.org/wiki/PBKDF2
     *
     * @param string $algo   The algorithm to use
     * @param string $key    The key to stretch
     * @param string $salt   A random salt
     * @param int    $rounds The number of rounds to derive
     * @param int    $length The length of the output key
     *
     * @returns string The derived key.
     */
    protected function pbkdf2($algo, $key, $salt, $rounds, $length) {
        $size   = strlen(hash($algo, '', true));
        $len    = ceil($length / $size);
        $result = '';
        for ($i = 1; $i <= $len; $i++) {
            $tmp = hash_hmac($algo, $salt . pack('N', $i), $key, true);
            $res = $tmp;
            for ($j = 1; $j < $rounds; $j++) {
                 $tmp  = hash_hmac($algo, $tmp, $key, true);
                 $res ^= $tmp;
            }
            $result .= $res;
        }
        return substr($result, 0, $length);
    }

    protected function pad($data) {
        $length = mcrypt_get_block_size($this->cipher, $this->mode);
        $padAmount = $length - strlen($data) % $length;
        if ($padAmount == 0) {
            $padAmount = $length;
        }
        return $data . str_repeat(chr($padAmount), $padAmount);
    }

    protected function unpad($data) {
        $length = mcrypt_get_block_size($this->cipher, $this->mode);
        $last = ord($data[strlen($data) - 1]);
        if ($last > $length) return false;
        if (substr($data, -1 * $last) !== str_repeat(chr($last), $last)) {
            return false;
        }
        return substr($data, 0, -1 * $last);
    }
}

Note that I'm using a function added in PHP 5.6: hash_equals. If you're on lower than 5.6, you can use this substitute function which implements a timing-safe comparison function using double HMAC verification:

function hash_equals($a, $b) {
    $key = mcrypt_create_iv(128, MCRYPT_DEV_URANDOM);
    return hash_hmac('sha512', $a, $key) === hash_hmac('sha512', $b, $key);
}

Usage:

$e = new Encryption(MCRYPT_BLOWFISH, MCRYPT_MODE_CBC);
$encryptedData = $e->encrypt($data, $key);

Then, to decrypt:

$e2 = new Encryption(MCRYPT_BLOWFISH, MCRYPT_MODE_CBC);
$data = $e2->decrypt($encryptedData, $key);

Note that I used $e2 the second time to show you different instances will still properly decrypt the data.

Now, how does it work/why use it over another solution:

Keys

The keys are not directly used. Instead, the key is stretched by a standard PBKDF2 derivation.
The key used for encryption is unique for every encrypted block of text. The supplied key therefore becomes a "master key". This class therefore provides key rotation for cipher and auth keys.
Important note, the $rounds parameter is configured for true random keys of sufficient strength (128 bits of cryptographically secure random at a minimum). If you are going to use a password, or non-random key (or less random then 128 bits of CS random), you must increase this parameter. I would suggest a minimum of 10000 for passwords (the more you can afford, the better, but it will add to the runtime)...

Data Integrity

The updated version uses ENCRYPT-THEN-MAC, which is a far better method for ensuring the authenticity of the encrypted data.

Encryption:

It uses mcrypt to actually perform the encryption. I would suggest using either MCRYPT_BLOWFISH or MCRYPT_RIJNDAEL_128 cyphers and MCRYPT_MODE_CBC for the mode. It's strong enough, and still fairly fast (an encryption and decryption cycle takes about 1/2 second on my machine).

Now, as to point 3 from the first list, what that would give you is a function like this:

function makeKey($userKey, $serverKey, $userSuppliedKey) {
    $key = hash_hmac('sha512', $userKey, $serverKey);
    $key = hash_hmac('sha512', $key, $userSuppliedKey);
    return $key;
}

You could stretch it in the makeKey() function, but since it's going to be stretched later, there's not really a huge point to doing so.

As far as the storage size, it depends on the plain text. Blowfish uses a 8 byte block size, so you'll have:

16 bytes for the salt
64 bytes for the hmac
data length
Padding so that data length % 8 == 0

So for a 16 character data source, there will be 16 characters of data to be encrypted. So that means the actual encrypted data size is 16 bytes due to padding. Then add the 16 bytes for the salt and 64 bytes for the hmac and the total stored size is 96 bytes. So there's at best a 80 character overhead, and at worst a 87 character overhead...

Is it ok to store passwords that are able to be retrieved?

You mean, inside an application which stores passwords for user authentication.

Normally the motivation for hashing them vs storing encrypted is that it prevents someone who has stolen the database or compromised the server from obtaining the passwords.

If you encrypt them with AES, you're clearly going to have to keep the key somewhere, and can't ever change it (unless of course, you decrypt them all and re-encrypt).

If someone compromises the machine, they can obtain the key, as it is necessarily kept (at least) in memory at some time to decrypt the passwords.

It's either that, or use some fancy PKI. AES is a symmetric cipher.

Encrypting the passwords won't really help the application defend its database against any but the most casual attackers (as an attacker MUST be able to obtain the key). Hashing them makes it difficult for the cleartext to be obtained if passwords are strong.

How to securely store a password in a database while still being recoverable

You should encrypt them, preferably with asymmetric encryption. Ideally the application (web app) encrypts them (w public key), and the daemon decrypts them (w private key), and the application and daemon and db live on different machines in different network zones.

Ideally the private key lives in a hardware security module attached to the daemon server. YubiHSM is ~ $500.

Please note that this only applies to passwords that you need to send to another party. If the password is for authenticating users with your system, then they should be hashed (and salted, and peppered).

Storing passwords safely in a database

You mention the goal is to build a password manager as a cloud service. First I'd like to say that if you want to build this in production, you will want to have really good security consult. Also, before deploying this you will want to have it audited by a security company. Generally I'd recommend not going there at all.

Note: If you are doing this as a hobby project and only risk compromising your own security, go for it. I have also once built such a system for myself (although I never used it :P).

The most secure way of storing the passwords is by only storing the encrypted form on the server. Most importantly, store the key on the user's device and do all the encryption/decryption there. In theory, as long as the key stays on the device, the passwords are secure, even if the server is hacked.

In practice this is a Hard Problem. You have to think of using a 2nd factor for decryption (keyfiles, passwords, maybe NFC tokens), backups, access control, key revocation, re-encryption, protection against data exfiltration (keyloggers, screenshots, clipboard, side-channel attacks), et cetera. All these factors make it nigh-on impossible to make these kinds of schemes both usable and secure.

How the handle/store encryption key in 2 way encryption to encrypt user password?

That is the start of a good solution.

Do the encryption and decryption on the second server (encryption server). Pass the password to the encryption server for encryption and it returns the encrypted password to store in the DB. When the password is needed pass the encrypted password to the encryption server for decryption.

Have the encryption server monitor request activity, if an unusual number of requests are received sound an alarm and in extreme cases stop processing requests.

Make the second server very secure. No Internet access, minimal access accounts, 2-factor authentication.

The encryption server becomes a poor-man's HSM (Hardware Encryption Module).

Can I save passwords securely and retrieve them without asking for a master password?

On Windows your best solution is to use the Data Protection API, used by Chrome, IE, Remote Desktop Connection, and dozens of other technologies, to encrypt data.

The virtue is that the data is encrypted (in a round-about way) with the user's own Windows password. When the user types their password into Windows, it makes all the "protected" data available.

Features:

the data is encrypted
the user doesn't have to enter their password to encrypt data
only the user can ever decrypt it
the user does not have to enter their password to decrypt data

Sample pseudo-code

The API you want is CryptProtectData and CryptUnprotectData:

public bytes[] ProtectBytes(bytes[] plaintext)
{
   DATA_BLOB dataIn;
   dataIn.cbData = plaintext.Length;
   dataIn.pbData = Addr(plaintext[0]);

   DATA_BLOB dataOut;

   BOOL bRes = CryptProtectData(
         dataIn,
         null,     //data description (optional PWideChar)
         null,     //optional entropy (PDATA_BLOB)
         null,     //reserved
         null,     //prompt struct
         CRYPTPROTECT_UI_FORBIDDEN,
         ref dataOut);
   if (!bRes) then
   {
      DWORD le = GetLastError();
      throw new Win32Error(le, "Error calling CryptProtectData");
   }

   //Copy ciphertext from dataOut blob into an actual array
   bytes[] result;
   SetLength(result, dataOut.cbData);
   CopyMemory(dataOut.pbData, Addr(result[0]), dataOut.cbData);

   //When you have finished using the DATA_BLOB structure, free its pbData member by calling the LocalFree function
   LocalFree(HANDLE(dataOut.pbData)); //LocalFree takes a handle, not a pointer. But that's what the SDK says.
}

Later, when you need to decrypt the blob, you use CryptProtectData.

The data is (effectively) encrypted with the user's Windows password; and only the person with their Windows password can decrypt it.

Note: Any code released into public domain. No attribution required.

Two-Way Encryption: I Need to Store Passwords That Can Be Retrieved