# Solution with high decryption cost and low encryption cost

I am looking for any cryptographic solution that will meet those requirements :

1. Only known method to get the encrypted string need to be brute force.
2. Decrypting on modern computer not more than around 1000 decrypting operations per second. (in other words, only 1000 bruteforce tries per sec)
3. Very fast encryption, with little computation cost, with possibility of 100 000+ operations per sec on the same modern computer.

Solution can be for example wrapping this string with n different algorithms/hashing functions. Solution can include for example other resource bound functions, like for example memory bound function.

• Your requirements don't seem sensible. With at least 128-bit encryption a brute force attack isn't possible regardless of how fast the brute force guesses can be made. I suggest you rethink your requirements, show what research you've done and why e.g. AES does not fulfill your needs. – otus Aug 25 '14 at 11:54
• Because possible attacker have always access to full valid decryption function, second is because password will be only 5-6 alphanumeric chars which attacker KNOW (length of it) (that's why needed max 1000 brute force tries per sec as there is time validation), third is because second part of the encoded string is known to attacker at all times so he will know if he tried valid password while doing bruteforce – devd Sep 14 '14 at 1:39
• I have an opposite question, I need high encryption cost and low decryption cost: crypto.stackexchange.com/questions/60356/… – k06a Jun 27 '18 at 19:09

The obvious way to come up with a 'fast encryption/slow decryption' algorithm is to make it a puzzle; that is, to encrypt, you randomly select a puzzle (which is fast), to decrypt, you must solve the puzzle (which is slow).

Here is one way to come up with a tunable puzzle (which can be solved in deterministic time, and for it is rare that a descriptor randomly stumbles on the answer quickly):

To encrypt, you pick a random vector $S$, and $k$ distinct $n$-bit vectors $r_1, r_2, ..., r_k$. You hash the vectors $SHA( r_1, r_2, ..., r_k )$ into an encryption key $k$, and you publish as a ciphertext the values $S$, $SHA(S || r_1)$, $SHA(S || r_2)$, ..., $SHA(S || r_k)$, and $AES_k( Message )$

To decrypt, we have to recover the values $r_1, r_2, ..., r_n$. The most efficient way to do that is to try various values $r_{trial}$, compute $SHA(S || r_{trial})$, and see if it's in the list. Because we use $k$ distinct values (for, perhaps $k=10$), we'll (with high probability) need to try almost all $2^n$ vectors until we've solved them all; by selecting $n$ properly, we can tune the exact slow-down between encryption and decryption.

If part of the requirement is that someone without a secret key cannot decrypt, then all we need to do is modify how we compute the encryption key $k$ as $k = Hash( Key, r_1, r_2, ..., r_k)$, where $Key$ is the secret key.

• An attacker can find the $r_i$ in $O(2^n)$ time, but can then test many keys quickly. I.e. only the first guess will be slow. – otus Aug 25 '14 at 12:43
• @otus: If you are saying "he can decrypt multiple messages quickly", well, no, that's why I stir in $S$ (a nonce) into the puzzle that hides $r_i$; different messages will have different $S$ values. If you're saying "he can then test multiple values of $Key$ quickly", I didn't believe that was an issue; $Key$ is (say) a 128 bit value (and hence is immune from brute force search). $Key$ is present solely in case we want to forbid a third party from decrypting at all. If that is not a requirement, $Key$ can be omitted. – poncho Aug 25 '14 at 13:18
• I meant the latter. While I agree it isn't a problem with 128-bit keys, I don't see what use the puzzle is if it only slows down the receiver who knows the key. – otus Aug 25 '14 at 13:20
• @otus: I don't know why we'd want to slow down the decryptor either; however I believe that's what devd asked for... – poncho Aug 25 '14 at 13:21
• @poncho, you could make the ciphertext; $S,SHA(S||r_1),SHA(S||r_1||r_2),...$ so that the hashes cannot be solved in parallel. – jkj yuio Feb 24 '18 at 3:07

Poncho's answer seems to have the right general idea: to slow down decryption while keeping encryption fast, make the decryptor solve a proof-of-work puzzle. His system seems a bit unnecessarily complicated, though, so let me try to present a simpler one.

This scheme is based upon the commonly used practice of key wrapping, where the actual message $m$ is encrypted with a randomly chosen message key $K_m$ using an "inner" encryption algorithm $E_m$, and this message key is then encrypted with a key encryption key $K_k$ (possibly derived e.g. from a password) using an "outer" encryption algorithm $E_k$, with the final ciphertext consisting of the outputs of both $E_k$ and $E_m$.

Such schemes have various other advantages, such as the ability to change $K_k$ without re-encrypting the whole message, which is why they're quite commonly used. With such a scheme, slowing down decryption is simple: simply throw away part of the message key $K_m$ before encrypting it. This forces anyone wishing to decrypt the message to guess the discarded part of the message key by brute force, thus slowing down decryption by any desired factor.

Note that, for this to actually work as an effective deterrent against brute force attacks, the inner and outer encryption algorithms need to have some specific properties. In particular, the outer encryption algorithm $E_k$ must not be authenticated — specifically, every key encryption key $K_k$ must yield a valid-looking truncated message key when used to decrypt the output of $E_k$. On the other hand, the inner encryption algorithm should be authenticated, or at least should provide an effective mechanism for verifying whether a specific message key $K_m$ is correct.

Here's a more detailed description of a specific system like suggested above:

• Let $E_m$ be an authenticated encryption algorithm, such as AES-GCM, with $E_m(K_m, m)$ denoting encryption of the message $m$ with the key $K_m$ using $E_m$.

• Let $E_k$ be a non-authenticated encryption algorithm, with the property that, as long as the correct plaintext is a random bitstring, it is not possible the distinguish the correct key from an incorrect one just by examining the decrypted text. For example, any block cipher in CTR mode, such as AES-CTR, will do here. Let $E_k(K_k, x)$ denote the encryption of the bitstring $x$ with the key-encryption key $K_k$ using $E_k$.

• Let $D_m$ and $D_k$ denote the decryption algorithms corresponding to $E_m$ and $E_k$, such that $D_m(K_m, E_m(K_m, m)) = m$ and $D_k(K_k, E_k(K_k, x)) = x$.

• Let $\rm KDF$ be a key derivation function, such as HKDF (RFC 5869) taking an arbitrary bitstring and producing a value suitable for use as $K_k$ or $K_m$ (depending on context). Note that this KDF does not need to implement key stretching, even if $K_k$ is derived from a password, since the scheme described here already provides equivalent protection against brute force attacks.

(The use of a KDF to derive $K_m$ is essential if the algorithm $E_m$ requires multiple keys or has specific requirements on the format of valid keys. If the keyspace of $E_m$ consists of all bitstrings of a particular length, and if decrypting with a partially incorrect key never reveals any information about the plaintext, then the KDF step may be omitted — although I'd still include it, just to be sure.)

• Let $s$ be a security parameter describing the slowness of decryption, such that decrypting a (short) message shall require about $2^s$ times as much work as encrypting it. Reasonable values might be, say, $7 \le s \le 20$, corresponding to slowdown factors between $2^7 \approx 100$ and $2^{20} \approx 1{,}000{,}000$.

To encrypt a message $m$ using a master key / password $P$:

1. Securely choose a random bitstring $R = R_0 \,\|\, R_1$, where $R_0$ denotes the first $s$ bits of $R$, and $R_1$ denotes the rest. The length of $R$ should equal or exceed the effective keylength of $E_m$ (e.g. 128 bits for AES-128-GCM).

2. Let $K_m = {\rm KDF}(R)$ be a message key derived from $R$, and let $C_m = E_m(K_m, m)$ be the result of encrypting $m$ with $K_m$ using $E_m$.

3. Let $K_k = {\rm KDF}(P)$ be the key encryption key derived from $P$, and let $C_k = E_k(K_m, R_1)$ be the result of encrypting the partial random string $R_1$ with $K_k$ using $E_k$. (The initial part $R_0$ of $R$ is not encrypted.)

4. Output the concatenated ciphertext $C = C_k \,\|\, C_m$.

To decrypt a ciphertext $C$ using the master key / password $P$:

1. Split the ciphertext $C$ into $C_k$ and $C_m$.

2. Let $K_k = {\rm KDF}(P)$ be the key encryption key derived from $P$, and let $R_1 = D_k(K_m, C_k)$ be the result of decrypting the ciphertext $C_k$ with $K_k$ using $D_k$.

3. Securely generate a random $s$-bit mask string $M$. (This should be done to avoid potential timing attacks on the following decryption step.)

4. For each possible $s$-bit prefix $R_0$, let $R = (R_0 \oplus M) \,\|\, R_1$, where $\oplus$ denotes bitwise XOR, and let $K_m = {\rm KDF}(R)$. Attempt to decrypt $C_m$ with $K_m$ to obtain the message $m = D_m(K_m, C_m)$. If the decryption succeeds, output $m$.

5. If decryption fails for all $s$-bit prefixes $R_0$, raise an error indicating that $P$ is incorrect.

As an optimization, it may be useful to include some form of fast key validity check in $E_m$ / $D_m$, e.g. by prepending a constant prefix to all messages before encrypting them (and verifying it early during decryption), or by prepending a cryptographic hash of $K_m$ to the ciphertext $C_m$. This makes the time needed to locate the correct message key $E_m$ independent of the length of the message.

• Hello, thank you for reply, before i fully analyze your solution would you be so kind and tell me if any of disclosed environment properties that i added to my question in comments make this answer invalid ? – devd Sep 14 '14 at 1:50
• You mean the comment you left on the question above? I don't see any obvious issues there; obviously with such a small keyspace, you'll want to use a large slowdown factor; say, at least around $s = 32$ (or more, if practical). – Ilmari Karonen Sep 14 '14 at 14:13
• @IlmariKaronen let $s=20$, how can you be sure in decrypt step (4), that a significant space of $2^s$ is searched. For example, if the actual $R_0 << 2^s$ then it will be found too quickly. – jkj yuio Feb 24 '18 at 3:12
• @jkjyuio: The probability that the decryptor only needs to test at most $p2^s$ prefixes before finding the correct one is $p$. So the probability of the decryptor having to test only an "insignificant" fraction of the prefixes is itself insignificant (for whatever definition of insignificant you're using). Of course, they could get lucky and find it on the first try, but that's an inherent issue with any cryptosystem that isn't information-theoretically secure. Your AES key, for example, is useless against a magically lucky attacker who just happens to guess it on their first try, – Ilmari Karonen Feb 24 '18 at 11:46

Just encrypt with a random key, then throw the key away. The recipient must use brute force to try all keys.

To reduce the decryption time from "impossible" to "slow", keep an appropriately-sized part of the key.

• Yes, large enough random key is the way to go, but you can brute force much more than 1000 keys per second. That isn't actually a problem, but is contrary to #3. – otus Aug 25 '14 at 11:58
• I interpret "decryption operation" as a successful decryption. – CL. Aug 25 '14 at 12:05
• "1000 bruteforce tries per sec" is the one I don't think is fulfilled. – otus Aug 25 '14 at 12:07

Since both the other answers let the attacker try more than the specified ~1000 keys per second, here's a solution that doesn't.

1. Use 256-bit authenticated encryption, like AES GCM or AES CTR + HMAC-SHA-256.
2. Use a 128-bit key.
3. Derive the encryption key from the 128-bit key using PBKDF2-HMAC-SHA-256 with e.g. a million iterations – or more, whatever gets you a decent rate on a desktop. If you picked AES CTR + HMAC, use SHA-512 in PBKDF2 so that you get a key for authentication as well.
4. If keys are not single use, add a unique salt to each message which is used with PBKDF2.

Using this for normal encryption doesn't actually make sense, because 128-bit keys are not brute forceable even at a billion keys per second per core. The PBKDF2 will mostly just slow down legitimate users and consume power. You can just use 128-bit or 256-bit authenticated encryption instead, without a key derivation step.

• Alas, this does not meet the 100,000+ messages/sec encryption requirement, at least not if the messages have different keys. – Ilmari Karonen Aug 28 '14 at 21:28