17
$\begingroup$

I got the idea from Eve Online's BPCs (Blueprint Copy). The in-game explanation is that the license to manufacture a copy of a starship is limited to X times, and afterwards the BPC is automatically corrupted.

I understand that the resulting plaintext can be copied after decryption any number of times, rendering the limit moot, I was just wondering if its possible.

$\endgroup$
  • 5
    $\begingroup$ I'm voting to close this question as off-topic because I find it unrelated to cryptography. The general problem here is to limit the number of execution of some program (here, the one that decrypts). Cryptography (at least, non-quantum) is of no help towards that. $\endgroup$ – fgrieu Jun 20 '18 at 11:15
  • 1
    $\begingroup$ But you could have a certain limited number of different keys that all decrypt the ciphertext. Not sure it helps though. And not sure you can do better. $\endgroup$ – Florian Bourse Jun 20 '18 at 15:07
  • 4
    $\begingroup$ @fgrieu I find the fact that cryptography is no help in this vein to make it tremendously applicable here on this site. Any reasonable study of cryptography would include the limits of cryptography, and this one turns out to be a rather interesting limit with substantial implications for design an implementation of systems. $\endgroup$ – Cort Ammon - Reinstate Monica Jun 20 '18 at 22:49
  • $\begingroup$ Couldn't you do it with a blockchain like solution? $\endgroup$ – JDL Jun 21 '18 at 11:10
  • $\begingroup$ Just to be clear, are you asking whether, given n computers, each of which are running the same algorithm, it is possible for those computers running that algorithm to cause all other computers to be unable to run that algorithm? $\endgroup$ – Acccumulation Jun 21 '18 at 15:39
35
$\begingroup$

Cryptography itself cannot solve this problem. This problem has long been studied in the field of copyright management to prevent piracy.

The main issue is that it is difficult to keep a state in the ciphertext that records how many times the ciphertext has been decrypted. Even if you can, there is no way in practice to prevent someone reverting the state. I.e. you decrypt, then throw away the new ciphertext, then decrypt using the old ciphertext again.

There have been some interactive protocols designed in the past that use an external trusted server to track the number of decryption. This may work but add some other problems such as privacy (you are essentially tracking the user).

$\endgroup$
  • 9
    $\begingroup$ Amongst those "other problems" comes a lack of robustness - if you can't see the trusted server (for whatever reason), you're locked out of the data. $\endgroup$ – Toby Speight Jun 20 '18 at 13:57
  • 2
    $\begingroup$ Good answer. I wonder if a blockchain approach could work without a trusted third party, in much the same way that bitcoin's blockchain prevents double-spending. $\endgroup$ – John Coleman Jun 20 '18 at 14:26
  • 7
    $\begingroup$ @JohnColeman I'd doubt how much a blockchain can help. Essentially, the interactive solutions work by letting the server keep the decryption key and count the number of decryption requests. Currently, blockchain cannot keep a secret because it is difficult (if not impossible) for the miners who do not know the secret to verify the process involving the secret. $\endgroup$ – Changyu Dong Jun 20 '18 at 15:05
  • 27
    $\begingroup$ “difficult to keep a state in the ciphertext” – I would rather say it is fundamentally impossible. A ciphertext is an abstract mathematical entity. Mathematical objects don't care about time or other implementation details in our universe. If you modify some bit in a concrete physical storage of that ciphertext, then what you've actually done is created a new, different ciphertext (and possibly lost access to the old one, if it was the only existing copy). Where the discussion gets interesting if you go quantum, because then it might be fundametally impossible to make a copy... $\endgroup$ – leftaroundabout Jun 20 '18 at 15:14
  • 1
    $\begingroup$ @JohnColeman then what prevents them from throwing away the new blockchain and using the old blockchain to decrypt? $\endgroup$ – user253751 Jun 21 '18 at 0:43
4
$\begingroup$

At first, I tended to agree with @fgrieu that this is not really a "cryptography" question.

If, it would belong more into the general information security corner, because – generally – the problem could be somewhat solved in software as well as in physical hardware. Yet, both software solutions as well as dedicated hardware solutions would still be subject to attackers using reverse engineering techniques which aim at gaining the ability to issue forced counter resets. Attacks like this will always be feasible; especially when the target is valuable from the perspective of an attacker.

Then again, this could very well be answered from a cryptographic point of view.

Is it possible for a cryptographic algorithm to limit the number of times a package/ciphertext can be decrypted?

No cryptographic (or non-cryptographic) algorithm is able to do that all by itself.

But…

Let’s look at the facts:

  • Unless there is a trusted party which controls the decryption counter, it is not possible to limit the number of times something is decrypted. (think: reverse engineering attacks.)
  • Unless there is a trusted party which controls the data and data handling process, it is not possible to limit the data usage or even its destruction after a number of decryption counts. (think: attacks by repetition of the same decryption process using copies of data.)

So, yes this is possible if – and only if – we assume there is a trusted party. All we need to do is to add a trusted party to the mix (for example: you, or a trusted 3rd party) which controls the data – incl. decryption process, decryption counter, data storage, data handling, as well as the data destruction. The security of this solution would the rely on (a) the security of the cryptographic algorithm you use for encryption/decryption, and (b) the security of the trusted party who controls the data and its processing.In the end, it depends on the specific real world scenario (which you didn’t specify) how this could be implemented safest and most feasible.

$\endgroup$
  • 1
    $\begingroup$ If one can a trusted party to control the data and its processing, then cryptography is often not necessay. In fact, traditional access control would be sufficient and perhaps more efficient (assuming a trusted party). $\endgroup$ – Changyu Dong Jun 21 '18 at 6:19
  • $\begingroup$ @changyu-dong Indeed... which is why I'ld personally (from a non-moderator point of view) would put this question (as I wrote) more into the general information security corner. $\endgroup$ – e-sushi Jun 21 '18 at 18:41
3
$\begingroup$

When you are building commercial software, you have to do your best to create schemes like this.

While it's true that Cryptography alone can't come up with a solution to this that lacks certain weaknesses; it is absolutely true that you can use some basic cryptography plus protocols to build in enough deterrence that enough people find it easier to follow the rules (which is what you really want). This is particularly true if you can reliably identify violators. You can do some reasonably effective enforcement if there is an online server that you control involved in the protocol.

As an example, a lot of schemes involve hashing and secrets. If you encrypt a ciphertext under $H_k$, you can provide a sequence of keys $H_{0 \cdots k}$ that lead to it. Each $H_n$ is unique, knowing any $H_n$ means that you can find $H_k$, and knowing $H_n$ does not mean that you know $H_{n-1}$, etc....

$$ \begin{align} H_0 &= H(k_{random}) \\ H_1 &= H(H_0) \\ H_2 &= H(H_1) \\ \cdots &= \cdots \\ H_k &= H(H_{k-1}) \end{align} $$

You can use more game-theoretic measures; one that we considered to stop real-world license violations. Presume that your license is encoded into an X509 client certificate. Users don't want to post their secret keys to the world; because that would both identify them to the vendor and have bad security consequences. So users would need to choose between being compliant and being insecure.

$\endgroup$
  • 4
    $\begingroup$ I'm not clear how your example hashing scheme provides the protection required: once you've generated this sequence, what do you do with it that limits how the recipient can use it? The X509 example appears to address multiple people using the same key, but that's a subtly different problem from the same person using the key multiple times, sequentially, which is what the question asks for. $\endgroup$ – IMSoP Jun 20 '18 at 15:48
  • 1
    $\begingroup$ the simple crypto-only approach that the OP asks for is impossible without assuming hardware support; but that's a useless answer. companies have to build in enough deterrence that people buy licenses, and easily implementing this in a way that doesn't bother legitimate users generally involves cryptography. The x509 problem addresses customers getting one license and installing it multiple times in their org. Sysadmins concerned about security will tell the installers to stop sharing the certs between machines, due to it being a security hazard. $\endgroup$ – Rob Jun 20 '18 at 16:00
  • 4
    $\begingroup$ The cost of cheap microcontrollers has fallen to the point that dongles could be produced for under $1. The bigger difficulty is that most computers don't have any nice means of interfacing with dongles that wouldn't expose security risks (e.g. USB ports, requiring that software be able to access a camera that can see the dongle or a microphone that can hear it, etc.) $\endgroup$ – supercat Jun 20 '18 at 16:27

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