Password-based cipher with fast encryption Define a password-based cipher as a cipher which decryption key is a humanly memorable password, thus optimistically at most 28 to 44 bits of entropy (per the obligatory XKCD).

For a password-based cipher to have any practical security, decryption is bound to be slow (and encryption adjusted to keep decryption slow as technical progress makes password search faster). The traditional way to do this is using an appropriately parametrized entropy-stretching password-based key derivation function (such as PBKDF2, bcrypt, scrypt, or Argon2) to transform the password (and perhaps a random salt) into the key of a normal cipher. That's done for both encryption and decryption, making the two about as slow.

What are recommendable (and preferably common or/and standardized) password-based ciphers with fast encryption ?



One option would be a $(\text{password},\text{plaintext})\mapsto\text{ciphertext}$ that is fast, while $(\text{password},\text{ciphertext})\mapsto\text{plaintext}$ remains about as difficult as in traditional password-based cipher for a comparable level of security. There are other options, and I do not want to be too directive, to see what good ideas emerge.
One approach that you might consider is a puzzle; this is something where the decryptor must do some searching to find the result.

Here is one simple example: suppose the encryptor takes the password, and selects $N$ random bits; he concatenates the two and SHA-256 hashes the result.  He then takes the first 128 bits of the hash, places that in the ciphertext, and then uses the other 128 bits to AES encrypt the secret; that's the rest of the ciphertext.

He then discards the original $N$ bits he selected.

To decrypt this, we have to search for the $N$ random bits that were selected; to do that, we have to compute an average of $2^{N-1}$ hashes, which is fairly slow.  Once we have selected the correct set of random bits, it's easy to recognize it (by comparing that hash with the initial part of the hash in the ciphertext); we can then decrypt the message.

You can select $N$ to taste; perhaps 24 if you want decryption to take maybe a second; perhaps 32 if you want to make it more expensive.

There are tweaks you can do to this approach:


Use multiple levels of puzzles, to reduce the chance that decryption might be done quickly (by stumbling on the answer early)
Use something other than SHA-256 (which is fairly GPU friendly).


However, I don't see how this approach could be made that resistant to a large multi-CPU attack...



If it is important to mimimize the variation in the decryption time, one idea would be to arrange the puzzles in parallel rather than serial.  That is, we select $k$ distinct random values of $n$ bits each, and compute the $k$ values:

$$h_i = \text{Hash}( \text{Password} || r_i )$$

and expose $z$ bits of each (for some $z$ somewhat larger than $n$).

Then, we compute a final hash $\text{Hash}( h_0, h_1, ..., h_{k-1}$, expose 128 bits of that (and use the other 128 bits as the actual key).

To decrypt, someone would need to compute $\text{Hash}( \text{Password} || x )$ for various values of $x$, and see if that matches any of the partially revealed $h_i$ values.  The decrypter will need all $k$ of them, and hence will need to try almost all $2^n$ possible values of $x$.

As an example, for $\text{Hash} = \text{SHA-256}$, $n = 28$ (a single for of my test machine can perform $2^{28}$ SHA-256 hashes per minute), $z=32$ and $k = 10$, then this would yield a decryption with about 10% variation, with 56 bytes of overhead...