5
$\begingroup$

I have a string that I will encrypt on the server. I then want to send the encrypted string along with a decryption method for it to be decrypted in the browser.

I want the decryption to take some time for the end user. Let's say ~10 minutes.

Let me be clear:

  1. I want the decryption to happen.
  2. It must happen on the browser (I understand that some might cheat but let's assume I don't care much about these cases even if they happen).
  3. It must take some time (~10 minutes).

I understand that decryption time depends on many parameters. You can assume that at least the string of data to be encrypted can be as small or as big as we need it to be in order to achieve the above 3 things. And we can assume the processing power of an average computer/browser.

Is this possible and how?

I am a JavaScript developer so a JS solution would be preferable. Some pseudocode/steps would also help.

I know nothing about cryptography so I would appreciate it if you could please refrain from using too much jargon I will probably not understand.

$\endgroup$
16
  • 4
    $\begingroup$ Use password hashing algorithms with adjustable parameters so that deriving the key from the password takes the required time? This of course requires you need to tune and you have to spend the same amount. This also has faster on some platforms. $\endgroup$ – kelalaka Apr 6 at 16:22
  • 5
    $\begingroup$ You can also look into time-lock puzzles, see for example this question. $\endgroup$ – Mark Apr 6 at 17:30
  • 31
    $\begingroup$ There may be non-cryptographic solutions as well. For example, you could have an interested party query your server and get some token (say a signature of a nonce + date/time info of when the query occurs). After 10 minutes, you could then allow the browser to query the server with that token to get a file which can be decrypted in a standard way. This makes the protocol be interactive, which may not be desired, but enforces the "it takes 10 minutes on all architectures" in a stronger way than any non-interactive solution I can think of. $\endgroup$ – Mark Apr 6 at 17:44
  • 3
    $\begingroup$ My ex has a laptop that would easily take an hour doing something my laptop does in 10 minutes. If you want ‘at least 10 minutes’ on even the top of 99% of devices (already excluding people with massive workstations), you or your users are not gonna like the time it will take on the slowest ~20% $\endgroup$ – Sebastiaan van den Broek Apr 7 at 16:18
  • 27
    $\begingroup$ Why do you want to annoy your users and waste their CPU cycles? $\endgroup$ – John Coleman Apr 8 at 1:02
32
$\begingroup$

As I indicated in the comments, I believe a non-cryptographic solution may be the best for this task, where instead of attempting to measure "10 minutes" by the average amount of time it takes to do some computational task, you simply measure it by the wall-clock time. Note that this solution still uses some cryptography, but not as a proxy to measure 10 minutes.

Concretely, when a user wants the document, you can generate a key (say an AES private key) $k$, create a payload = $k || D$ where $D$ is the current date/time formatted in some standard way, let $h= H(k || D)$ be a hash of the payload, and then store $[h, k, D]$ in some table, and send $h$ to your user, along with the document (encrypted under the key $k$).

The user can then query you later with some hash $h'$. Upon recieving such a query, check if $h$ is in your stored table as part of some entry $[h, k, D]$. If so, and if at least 10 minutes have passed since the date/time $D$, return the key $k$ to the user, who can now decrypt. You can also evict the table entry $[h, k, D]$ at this point.

The pros/cons of this versus a "intentionally slow decryption" solution are:

  1. There is less wasted computational effort on the part of the user

  2. The limit of 10 minutes is enforced regardless of the user's particular architecture (and their desire to "cheat")

  3. The operations on the server side of things are likely more efficient than the other RSA-based solution (for example, you have to use ~128 bits of randomness per user, instead of >2k for RSA to be secure).

The cons are:

  1. The user has to query your server a second time
  2. You must store some intermediate state for each user (the $[h, k, D]$). This should be rather small (a few hundred bits) per user, but is greater than zero.

I think it is worth mentioning that I expect it would be difficult to get a uniform "10 minute decryption time" in the browser using time lock puzzles, even among honest users. I have not thought through this in detail, but I imagine that differences in hardware architectures (especially with respect to the presence of certain SIMD instructions, i.e. Intel SSE / AVX type instructions) may be able to get a constant factor speedup on your users architectures in the underlying BigInt multiplication for RSA, which would then result in users having architecture-dependent decryption times.

If you implement things correctly (and make sure that auto-vectorization does not occur), you may avoid this issue. But even differences in clock speed (say 2GHz vs 3.5GHz, or whatever numbers are reasonable for a few-year-old phone vs a enthusiast's desktop) would likely make a big enough difference that it would be difficult to enforce a 10min decryption time for all users (you could likely ensure that decryption for all users takes at least 10 minutes, but for some users it may take 20 minutes, or whatever).

$\endgroup$
8
  • 18
    $\begingroup$ This technique has two huge advantages over the other one: [A] it taxes less energy / releases less greenhouse gazes / drains less battery // [B] the 10 minute delay is accurate, rather than varying by a factor ≫10 depending on browser and browser platform. $\endgroup$ – fgrieu Apr 7 at 5:37
  • $\begingroup$ The goal is not for the decryption to be slow for the sake of being slow. The goal is for the decryption to consume processing power. "Slow" will be the consequence of this. I realised that the title of my OP is probably misleading, but I think it's too late to change it now given the answers already provided. I do appreciate all the answers and the help however <3 $\endgroup$ – Sprout Coder Apr 8 at 8:33
  • $\begingroup$ It' not some long term project that will consume lots and lots of power for no reason. It's an online "game"/challenge that will last only a couple of weeks and "participants" will be asked to decrypt in order to get a reward. The reward must be the result of the decryption itself, in order to make this more "honest". I don't want to fake it, have them decrypt nonsense (i.e. some key), and then send them the reward. The reward must be the encrypted data itself. $\endgroup$ – Sprout Coder Apr 8 at 8:33
  • 1
    $\begingroup$ Why do you even use cryptograhphy? If you are going to use a table you can just safe pairs of (user identifier, timestamp). $\endgroup$ – Nobody Apr 8 at 14:06
  • 1
    $\begingroup$ Low-end phone vs. enthusiast desktop is like 1.5GHz vs. 5GHz these days, and multiply throughput and latency may also vary. (And thus useful work per clock, even once a JavaScript JIT has turned JS into machine code). And if the phone is only running 32-bit code then bigint multiply takes 4x as many 32-bit multiplies as 64-bit multiplies. (Although if this is in JavaScript, probably everything will be done with JS numbers which are IEEE double floating-point (or 32-bit integer if you use certain tricks, but not AFAIK 64-bit integer).) $\endgroup$ – Peter Cordes Apr 8 at 18:43
26
$\begingroup$

I don't know about enforcing browser decryption, but here's an old trick for fast encryption and slow decryption if you understand RSA.

Generate a 2048-bit RSA modulus $N=pq$ and a random exponent $d$. Now solve $de\equiv 1\pmod{(p-1)(q-1)}$ ($e$ has to be secret so don't use 3, or 17, or 65537 or anything like that). Decrypting ciphertexts $c$ using $c^d\pmod N$ takes maybe 0.004 seconds using BearSSL (you might want to do your own benchmarking for some Javascript library), so we'll encrypt 150,000 times and it should take about 10 minutes to decrypt.

Here's the fun bit: we can giant step the encryption process. Compute $g\equiv e^{150000}\pmod{(p-1)(q-1)}$ which should take less than a hundredth of a second. Now take your message $m$ and compute $c_0\equiv m^g\pmod N$ which should less than a hundredth of a second. Now give the end-user $N$, $d$ and $c_0$ and get them to compute $c_{150000}$ where $c_{i+1}\equiv c_i^d\pmod N$. They should not be able to short cut this calculation without factoring $N$.

Promise me that you'll use this wisely; I'm still harrowed by the damage cryptography did to the world's power consumption with Bitcoin.

ETA this idea seems to be similar to the one linked by Mark in the comments.

$\endgroup$
12
  • $\begingroup$ I'm afraid I didn't understand any of this but thank you for taking the time to help. <3 I have no background in cryptography. I was looking for some Javascript-based hints/steps. :-) $\endgroup$ – Sprout Coder Apr 6 at 18:07
  • $\begingroup$ I will take a look at asecuritysite.com/encryption/js05 though, thanks! $\endgroup$ – Sprout Coder Apr 6 at 18:09
  • $\begingroup$ Doesn't the private key owner can speed this with Euler's theorem or your formulation is not correct? $\endgroup$ – kelalaka Apr 6 at 18:18
  • 4
    $\begingroup$ @kelalka. Yes the private key owner can giant step; however in this case the private key owner is the encryptor. Euler's theorem is precisely what is used in the computation of $g$. $\endgroup$ – Daniel Shiu Apr 6 at 18:25
  • 1
    $\begingroup$ @Sprout Coder. Ah. sorry. I'll try and learn some Javascript and see if we can meet in the middle! $\endgroup$ – Daniel Shiu Apr 6 at 18:26
1
$\begingroup$

A suggestion would be to send a "partial" key to the client. This is not too dissimilar, in spirit, to what cryptocurrencies do to ensure that a block is created only every $x$ minutes.

The outer layer might be some kind of asymmetric crypto (such as RSA or ECC) to encrypt a session key and its contents. In a case like this, it's important for the message to have some kind of structure; for instance, the first $b$ bytes are all zero -- this will become clear in a moment.

However, rather than sending the actual session key, here's what you do: zero out the least significant $n$ bits of the session key -- you'll have to calibrate the exact value of $n$ so that it takes 10 minutes on a "reference" platform of your choice. Let's say you perform this calibration and get $n = 32$. So if your (e.g. 128-bit) key were 0x345f60eefc249aa1c6897cd8d82b78fb, you'd send 0x345f60eefc249aa1c6897cd800000000.

The client is then tasked with brute-forcing the last 32 bits of the keys, which would take the claimed 10 minutes. To do this, the client would loop through all 32-bit values, add the current value being tried to the key, and try to decrypt the ciphertext. If it matches the expected pattern (my suggestion was $b$ bytes of zeros), then you found the key, and you can decrypt the remaining ciphertext.

The advantage is that, server-side, this is very fast: just generate the key, perform the encryption once, and you're done. What makes it hard for the client is the missing information on the last $n$ bits of the key.

$\endgroup$
3
  • 4
    $\begingroup$ Brute force exhaustion challenges can be set to take a lot of core hours, but the work is highly parallelisable. If the critical requirement is wall clock time versus proof of work, something inherently serial would be preferable. $\endgroup$ – Daniel Shiu Apr 7 at 13:18
  • $\begingroup$ You're right, and I should have mentioned this. However, given this requirement from the question: "It must happen on the browser (I understand that some might cheat but let's assume I don't care much about these cases even if they happen)", it seems like a reasonable solution. $\endgroup$ – swineone Apr 7 at 14:32
  • 6
    $\begingroup$ It is worth mentioning that the "some might cheat but lets assume I don't care if this happens" trivializes the entire problem. Define decryption by first sleeping for 10 minutes, and then decrypting normally. This is typical of situations where one assumes honest behavior, and is why in cryptography one generally wants to assume honest behavior as little as possible (both because it is unrealistic in real life, and because it trivializes everything --- this is the point of the "ideal vs real" proof paradigm). $\endgroup$ – Mark Apr 8 at 6:23
1
$\begingroup$

There are password hashing libraries whose sole job is to do something like this. Indeed, there have been entire competitions dedicated to identifying good functions for this sort of operation. The winner of the 2015 competition was Argon2. Argon2 is available in many Javascript libraries.

The process would look like:

  • Pick a random key from a reasonable keyspace. The larger the keyspace, the more expensive it will be to decrypt. You will have to tune this.
  • Use Argon2 to hash the key.
  • Encrypt the data using a symmetric encryption like AES, using the hash that came from Argon2. AES is available in javascript
  • Deliver the encrypted data, and the bounds of the keyspace.
  • The user runs random keys out of the keyspace, pass it through Argon2, and then see if the key is right.

The choice of Argon2 supports your desire to run in browser. While there is no way to force users to run in browser, Argon2 is at least known to be difficult to run on a GPU, due to its large memory footprint. This makes it more likely that the end user has to at least run the decryption on a CPU, which will slow it down.

$\endgroup$
1
  • 1
    $\begingroup$ Note that this is roughly the same as Daniel Shiu's answer and therefore has the same disadvantages: #1 power draw is high (environmental damage and on mobile devices the user's battery drains) and #2 very different solution times across devices (cheap phone vs. fast desktop). I do think your solution is simpler and explained better, for what it's worth. $\endgroup$ – Luc Apr 9 at 12:10

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.