7
$\begingroup$

I'm looking for an encryption scheme that has the following properties:

  1. Decryption is CPU intensive, so decrypting an encrypted text may take some time (relatively, of course). Preferably, encryption should be negligible.
  2. The time to decrypt can be easily raised.
  3. The time to decrypt can be easily lowered.

Naively, I could accomplish #2 and #3 by re-encrypting the data n times and increasing and decreasing n to raise or lower the decryption time.

Is there any such encryption method?

$\endgroup$
  • $\begingroup$ What sorts of communication requirements/limitations are there? $\endgroup$ – mikeazo Feb 16 '18 at 19:28
  • 7
    $\begingroup$ You could throw away bits of the encryption key so that there is a brute-force portion to decrypting e.g. encrypt with a 128-bit key but only share 96 bits. Or protect the key using something like an RSA time-lock puzzle. $\endgroup$ – user13741 Feb 16 '18 at 19:28
  • $\begingroup$ @Omer Are you talking symmetric or asymmetric crypto? $\endgroup$ – mikeazo Feb 16 '18 at 19:30
  • $\begingroup$ What I'm actually looking for is a way to create a synthetic cost to access data and increase/decrease it as I see fit. I was thinking about having the secret in plain-text and having the user take that at will and decrypt the data at a high cost to them. $\endgroup$ – Omer van Kloeten Feb 16 '18 at 19:41
  • $\begingroup$ @user13741 I really like your answer :) $\endgroup$ – Omer van Kloeten Feb 16 '18 at 19:43
14
$\begingroup$

You could throw away bits of the encryption key so that there is a brute-force portion to decrypting e.g. encrypt with a 128-bit key but only share 96 bits.

Or protect the key using something like an RSA time-lock puzzle. The benefit of this is recovering the key cannot be sped up with parallelism.

$\endgroup$
  • $\begingroup$ The drawback of this method is that the time it takes to guess the correct key is a matter of luck. But if you would combine this with multiple layers of encryption, then the mean time to crack could become more predictable. $\endgroup$ – Philipp Feb 16 '18 at 20:47
  • 2
    $\begingroup$ A note about discarding key bits and making the decryptor guess them: You would need a new key for every message in order to maintain the decryption work factor. If the key is actually secret and shared between two parties that implies an asymmetric key exchange per message. You might discard bits of the IV instead and have the decryptor work to guess those instead of the key. That way you could re-use the same key for an arbitrary number of messages while maintaining the decryption work factor. $\endgroup$ – Ella Rose Feb 17 '18 at 0:38
  • $\begingroup$ @Philipp I would love to see your answer for this, too. $\endgroup$ – Omer van Kloeten Feb 17 '18 at 11:58
  • $\begingroup$ @user13741 Is there a way to predict how fast decryption would take for each bit of shared key? $\endgroup$ – Omer van Kloeten Feb 17 '18 at 12:00
  • 2
    $\begingroup$ This is not a good solution since once you recover the full key, you can no longer alter the time to decrypt. The hidden values should be part of the encryption/decryption process and independent for each ciphertext. $\endgroup$ – Yehuda Lindell Feb 18 '18 at 9:14
7
$\begingroup$

One idea not already mentioned might be to hash the message data with a key and initialization vector, and have the decryptor crack the hashes.

The encryptor would output blocks of $hash(K || m_{next} || IV || m_{cumulative})$ as "ciphertexts", for some a shared secret key $K$, random initialization vector $IV$, and message $m$. $m_{next}$ indicates the next $n$ bits of the message, while $m_{cumulative}$ indicates all of the message up to the current block:

  • Encryption outputs $hash(K || m_{0:n} || IV)$ for the first $n$ bits of the message $m$.
  • Subsequent blocks are computed as $hash(K || m_{next} || IV || m_{cumulative})$
  • Repeat until all of $m$ is "encrypted"
    • Subsequent blocks incorporate previous bits of $m$ to prevent each "ciphertext" block from being decryptable in parallel
    • The ordering $hash(K || m_{next}|| IV || m_{cumulative})$ ensures pre-computation of the partial hash is not possible
  • Decryption computes the first block of $m$ by brute force guessing the first $n$ bits of the message stored in the first "ciphertext"
  • Subsequent blocks are decrypted similarly, incorporating the previously obtained decrypted message bits.

Decryption speed is tunable by making $n$ smaller/larger. The effect of $n$ on encryption speed is negligible.

This method is also re-usable without having to re-establish a key for every new message.

Disclaimer

This is somewhat of an abuse of a hash function - hashing is not encryption!

$\endgroup$
  • $\begingroup$ This is really nice, taking @user13741's answer and turning it on its head, making the message itself become the part that is brute-forced. Unfortunately, that takes away from the pseudo-random nature of the brute-forcing method, since the decryptor may infer things about the next parts of the message from the previously decrypted ones. $\endgroup$ – Omer van Kloeten Feb 17 '18 at 11:48
  • $\begingroup$ On that last note - hashing sometimes is encryption (but only sometimes). The Blake2 cipher, for example, uses a hashing function internally and simply xor's the hashed values into plaintext to "encrypt" data. In this sense the security of Blake2 is entirely on the cryptographic features of it's internal hash. $\endgroup$ – cegfault Feb 17 '18 at 14:58
  • 1
    $\begingroup$ @cegfault I have never heard of the Blake2 cipher, do you have a link to it? I am familiar with the Blake2 hash function, based off the chacha function, but I have never heard of a Blake2 cipher. $\endgroup$ – Ella Rose Feb 17 '18 at 15:23
5
$\begingroup$

I think that the easiest thing to do is to use an authenticated encryption scheme that relies on a random IV, and then not provide all of the IV in the ciphertext. For example, assume that you use AES-GCM with a random IV of length 96 bits. Then, in order to require time to decrypt of $2^t$, you provide the first $96-t$ bits of the IV and not the rest. The decryption process works as follows. Try all possible $2^t$ strings to complete the IV until decryption succeeds (you know when decryption succeeds or fails since you are using an authenticated encryption mode). The average time taken to succeed is $2^{t-1}$. (Note, if all fail, then you know that the ciphertext is invalid.)

$\endgroup$
  • $\begingroup$ In your comment to @user13741 you said their solution was incorrect because you couldn't increase/decrease the decryption time. How is this different? $\endgroup$ – Omer van Kloeten Feb 19 '18 at 7:04
  • 1
    $\begingroup$ In their solution, the work needed only to be done once since it was related to the key. Here, you need to do the work independently each time for each ciphertext. In addition, here you can make the work required different for different messages. This is because the work is needed for every ciphertext independently (the missing random bits of the IV are random and independent for every encryption). $\endgroup$ – Yehuda Lindell Feb 19 '18 at 7:07
  • $\begingroup$ Interesting. In my specific case, I don't mind having a different key for each ciphertext if the key is public. $\endgroup$ – Omer van Kloeten Feb 19 '18 at 11:17
1
$\begingroup$

I've been made aware of this question as a possible dup of one i have asked. I'm surprised that there is not much already established in this area. So here's my idea so far, but i think it needs more work;

instead of finding by brute force progressive segments of the plaintext as suggested by @Ella Rose, my idea instead was to do the same but to the key;

Make a, say, 2048 bit key at random and encrypt the plaintext. Split the key into n parts of m bits each (ie m*n = 2048), then emit n hashes, each of separately the m bit segments, using your favourite hash algorithm. Throw original key away.

To decode, brute force guess each of the n segments until its hash agrees with the given. Finally decode the ciphertext using the recovered key.

Making m bigger and n smaller increases decode time. Keep n a reasonable size to allow "guess" averaging of time.

I didn't previously think of overlapping the hashes as suggested by @Ella Rose's answer. this is a good idea as well to resist a parallel attack.

$\endgroup$
0
$\begingroup$

One idea might be to use byte stuffing; that is, use a normal, fast encryption scheme but add random bytes to the encrypted text in a pseudo-random way. The decryption method could either know where the stuffed bytes are (based on the key), or have to utilize a MAC scheme to one-by-one find, hash, and test for the stuffed bytes.

Because the stuffed bytes would radically alter the decryption process, stuffed bytes would have to be found and removed before normal decryption. This process would rely on multiple re-hashing, which is a long and tedious process. Because encryption is merely adding the random bytes, there would be little to no overhead on the encryption.

$\endgroup$
  • $\begingroup$ I honestly have problems following the description of the proposed scheme. $\endgroup$ – Maeher Feb 17 '18 at 15:25
  • $\begingroup$ I have to agree with @Maeher can you please formulate a short example of your idea using mathematical notation (or pseudocode)? $\endgroup$ – SEJPM Feb 17 '18 at 21:02
  • $\begingroup$ Do you mean that you take the encrypted text and add n random bytes, causing the decryptor to brute-force finding which n bytes to remove, each time trying to decrypt, causing high CPU usage? Isn't this easily parallelizable? $\endgroup$ – Omer van Kloeten Feb 18 '18 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.