# 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.

• why do you assume the decryption is slower than encryption? Encryption and decryption themselves are relatively fast. The PBKDF is made to be slow (regardless encryption or decryption) what should make the brute-force less feasible (taking long time). The PBKDF takes as well the same longer time, however assuming human user it doesn't matter so much Nov 11 '17 at 13:38
• @gusto2 Having decryption that's slower than encryption is the goal, not an assumption. With a PBKDF, almost all the cost goes into the PBKDF computation which is identical for encryption and decryption. fgrieu is looking for a fundamentally different construction where $(\text{password}, \text{plaintext}) \mapsto \text{ciphertext}$ is fast but $(\text{password}, \text{ciphertext}) \mapsto \text{plaintext}$ is slow. Nov 11 '17 at 13:49
• A useful parameter would be quantifying your notions of slow and fast. What would you expect the ratio to be numerically? Nov 11 '17 at 15:48
• @Paul Uszak: I'm looking for encryption with overhead <0.1 s, and decryption<1 mn overhead, compared to straight AES. 1 mn of password hashing makes a mediocre password passable (28 bits of entropy translates into 250 years of attack by brute force on the same platform as the legitimate user).
– fgrieu
Nov 11 '17 at 17:38
• I think this misses the issue, it is not to make decryption slower than encryption, it is to make decryption with the correct password faster than an attempted decryption with an incorrect password. In the usual case of password verification the verifier is generated once (encryption) but verification (decryption) is performed very substantially more times. It is the verification that is the real consumer of CPU time over the life of the password by orders of magnitude.
– zaph
Nov 13 '17 at 14:08

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...

• I think that reducing the likelihood of quick decryption is a must, but found no way to do it without increasing the ciphertext size proportionally to the number of successive puzzles, and sizably for each; that's one motivation for asking. Combining that with Argon2 and a minute for decryption (which is acceptable for backups that one hopes to never use) makes a mediocre password passable (28 bits of entropy translate into 250 computer⋅years). There are other options, including asymmetric (the question intentionally has a wide definition of a password-based cipher).
– fgrieu
Nov 11 '17 at 16:46
• @fgrieu: I don't see much point in trying to prevent lucky attackers from quickly guessing the right secret bits, unless you can also do something to prevent an equally lucky attacker from quickly guessing the right password. And I don't really see any way to do that. Even with a fixed-time KDF, the attacker still has an $x$% chance of only needing to test up to $x$% of the keyspace before finding the right answer. Making the decryption time stochastic doesn't really change that to any significant degree. Nov 11 '17 at 18:25
• @IlmariKaronen: users will prefer decryption in 1 minute ± 5 s to decryption in 0 to 2 minutes, for the same security.
– fgrieu
Nov 11 '17 at 18:42
• @fgrieu: You'd probably do better by reducing $N$ by one, so that you'll have a 1 minute worst-case decryption time. Yes, this will reduce resistance to brute-force attack, too, but so (I believe) will any attempt to reduce the variance. Nov 12 '17 at 6:40
• The "puzzles in parallel" approach allows a check of $\text{Password }$ much less costly than average decryption, which is disastrous. The attacker computes $\text{Hash}(\text{Password}\|x)$ for $x$ over a fraction of the search space, and use that they match the $h_i$ (over the given $z$ bits) more often for correct password guess. This worsens when $k$ and $z-n$ increase. And we need a large number of puzzles (100?) so that deciphering time is seldom much larger than average. I'm still struggling to repel @Ilmari Karonen's curse that anything reducing the variance also lowers security!
– fgrieu
Nov 12 '17 at 8:56

I describe a dull solution to my question, so that others do not have to: use asymmetric hybrid encryption (such as curve25519xsalsa20poly1305), with the generation of the private key from the output of a state-of-the-art password-based key derivation function, such as Argon2.

The public key, used for encryption, is obtained once from the password, then stored; it is not secret. Thus encryption is fast with access to a trusted public key, or fast on average for whoever knows the password, does many encryption, and has storage with trusted integrity on which the public key can be written once. Decryption requires the password (the private key is not stored), or finding it by brute force.

Compared to the use of symmetric puzzles proposed in poncho's answer, this proposal has the serious practical drawback that the first encryption is as slow as decryption. It has the minor advantage that decryption time is very even, without incurring the ciphertext size overhead that I fail to avoid with multiple levels of puzzles something that's conjecturally impossible to obtain with the puzzle approach.

Note: I far from rule out there are yet other techniques.

• 'without incurring the ciphertext size overhead that I fail to avoid with multiple levels of puzzles'; actually, I'm pretty sure that the overhead associated public key crypto (even one as cheap as curve25519) will be at least as much as you would get with multiple levels of puzzles (where, if you tune things, you might get 32 bits of overhead per puzzle; 4 levels means only 128 bits of overhead...) Nov 11 '17 at 17:41
• @poncho: any example of puzzle with low overhead and negligible odds of wrongly thinking having solved the puzzle? Or way to cascade puzzles so that the overall odds of wrongly thinking having solved the cascade are negligibly low?
– fgrieu
Nov 11 '17 at 17:57
• Well, the probability of finding a solution to an intermediate puzzle doesn't have to be negligible; only the last one (as a false solution to an intermediate only slows the decryptor down, and you want to slow the decryptor down). So, what you could do with $n$ puzzles is have each intermediate have (say) 32 check bits (bits that are used to tell the decryptor when he found a potential intermediate solution), and the last one having 128 check bits, for a total of $32n + 96$ bits of overhead. Nov 11 '17 at 19:42
• @poncho: indeed the probability of finding an incorrect solution to an intermediate puzzle doesn't have to be negligible, if we can detect it reliably and we can efficiently recover. The later is not trivial though. If solving a puzzle depends on the solution of the previous one, we'll most often end up with an impossibility in the next puzzle; but things start to get hairy when we consider consecutive errors, and with 32 hints bits and $2^{24}$ step max ($2^{23}$ expected) per puzzle, $k$ consecutive errors have odds like $2^{-8k}$.
– fgrieu
Nov 11 '17 at 23:02
• Actually, if you approach it the right way, it's actually pretty straight-forward. One way is to keep a list of all current potential solutions, and attempt to advance them in sequence. If we find a potential intermediate hash for one, that's a new potential solution (one level deeper), but we keep the the current one on the list; if we go through all the possibilities of one level, then we can strike that possibility from the list. Nov 11 '17 at 23:21

Building on poncho's answer, I believe there's a way to increase the decryption (and encryption) time linearly with minimal ciphertext bloat (e.g. a $k+1$ fold increase using $k$ extra ciphertext bits) and negligible effect on the decryption time variance.

The trick is to append a random $n+k$ secret "tweak" to the passphrase before deriving the message key from it, and including $k$ "hint bits" in the ciphertext, where the $i$-th hint bit is determined by hashing the (possibly salted) passphrase and the first $n+i-2$ bits of the tweak. (Obviously, the ciphertext should also include a regular key check value that depends on the full $n+k$ bit tweak and passphrase.)

This allows the decryptor to interatively reconstruct the tweak using on average $(k+1)2^{n-1}$ hash computations, with a standard deviation of about $2^n/\sqrt{12}$ hash computations regardless of $k$ (as long as $k \ll 2^n$), and $O((n+k)2^{n})$ bits of storage.

Meanwhile, rejecting a wrong passphrase takes on average $(k+2)2^{n-1}$ hash computations, and thus finding the right passphrase from among $N$ choices requires $N(k+2)2^{n-2}$ hash computations on average.

However, I don't think this scheme is actually worth using with $k > 0$. The problem is that, even though the time to reconstruct the message key from a correct passphrase grows in proportion to $k+1$, the average time to test and reject a wrong passphrase grows only in proportion to $k/2+1$.

Thus, let's say we want a brute-force search of an $N$-passphrase space to require about $N2^m$ hash computations on average. We can achieve this by either:

1. letting $n = m+1$ and $k = 0$: this makes encryption take only one hash computation and makes decryption take at most $2^{m+1}$ hash computations in the worst case, with an average of $2^m$; or
2. letting $n \le m$ and $k = 2^{m-n+2}-2$: this makes encryption take $k+1 = 2^{m-n+2}-1$ hash computations and makes decryption take on average $(k+1)2^{n-1} = 2^{m+1}-2^{n-1}$ hash computations (with a small but non-zero probability of exceeding $2^{m+1}$).

Essentially, for a given target value of $m$, decreasing $n$ and increasing $k$ reduces the variance in decryption time by pushing the average decryption time up towards what would, for $k = 0$, be the worst case. So instead of a random chance of fast (legitimate) decryption, we get guaranteed slow decryption, while the expected speed of a brute-force attack stays the same.

Also, increasing $k$ slows down encryption and makes decryption take exponentially more space. So there really is no advantage to using $k > 0$, and plenty of disadvantages.

(It's possible to do decryption using only constant space even for $k > 0$, by using a depth-first instead of a breadth-first search of the prefix space, but this pushes the standard deviation of encryption time back up to around $(k+1)2^n/\sqrt{12}$ hash evaluations. Of course, a brute-force attacker would almost surely use this method, since they won't care about the variance.)

Furthermore, I strongly suspect that this problem is not specific to this particular scheme, but rather a fundamental limitation. While I haven't managed to formulate a rigorous proof, it seems likely to me that any attempt to reduce the variance of the decryption time below that of the uniform distribution will inevitably either increase the mean decryption time, decrease the mean time for a brute force attack to succeed, or both — and will do so to such a degree that it will effectively negate any possible benefit from the reduced variance.