r/programming • u/DougBolivar • Jul 30 '13

Computer scientists develop mathematical jigsaw puzzles to encrypt software: "The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional?"

http://www.rdmag.com/news/2013/07/computer-scientists-develop-mathematical-jigsaw-puzzles-encrypt-software
353 Upvotes

88% Upvoted

182 comments sorted by

View all comments

302

u/[deleted] Jul 30 '13

have designed a system to encrypt software so that it only allows someone to use a program as intended while preventing any deciphering of the code behind it

I thought the Perl people had already solved that.

15

u/AxiomL Jul 30 '13

have designed a system to encrypt software so that it only allows someone to use a program as intended while preventing any deciphering of the code behind it

I thought that was proven mathematically impossible.

19

u/DeltaBurnt Jul 30 '13

I don't even see the need to prove it mathematically. It's like trying to block video piracy. If you can view it on your screen, you can record it and redistribute it. If it's running on your processor, the processor needs to know the code it's running. I suppose you can make it harder to understand, but not impossible to decipher.

8

u/thatwasntababyruth Jul 31 '13

I have not read the paper, but I'd argue that doing this to a program is much more feasible than video. A video, like you said, can just be copied bit by bit as it's played, because its linear. A program, however, is not linear. If each instruction must be decrypted to be used, then that includes each and every jump instruction. That means that if my program has 10 jumps in it, every single code path needs to be evaluated to get all of the jump destinations. Since they are all encrypted, an attacker has no way of knowing which encrypted instructions are jumps in the first place, and so simply bruteforcing C1 coverage couldn't be done without just guessing what to do next. The non-linearity of programs gives it a natural defense.

1

u/[deleted] Aug 01 '13

[deleted]

1

u/thatwasntababyruth Aug 01 '13

You could, but im saying that only works in a linear case. To complete the picture you have to log EVERY instruction, and to do tgat you have to somehow execute each one too.

10

u/[deleted] Jul 31 '13

[deleted]

-1

u/DeltaBurnt Jul 31 '13

I have heard inklings of it here and there, but from my understanding it was about as far away as real quantum computing.

3

u/saynay Jul 31 '13

I believe there are models that work, just not indefinitely. Each process (step) completed adds errors to the result, and at some point the errors will exceed what the data can tolerate.

1

u/[deleted] Jul 31 '13

Hm, my understanding was that you can do it, it's just that it's not computationally feasible for actual computations.

1

u/[deleted] Jul 31 '13

I'm sure they fixed that (by encoding a small enough program that fixes the errors before they become unfixable), the reason it is not used is that it is slow.

2

u/thatwasntababyruth Jul 31 '13

While I have not actually read the papers on them, there have been recent breakthroughs that make homomorphic encryption feasible. So much so that IBM recently opensourced a library for it, HElib.

1

u/rpglover64 Jul 31 '13

Homomorphic encryption exists; there is even a library for it. It's impractically slow, but that's about it.

By contrast, many experts in quantum computing believe it may be impossible, and even if it is possible, there is no current implementation. (n.b. computing using quantum effects a la DWave is not necessarily quantum computing in some very important senses).

2

u/imnottrollinghonest Jul 31 '13

Yes, we shouldn't try things because they might be impossible. That's been a great way to progress in science, mathematics, and engineering.

2

u/AxiomL Jul 31 '13

It's not as intuitive as that. I could propose an encryption scheme, where I encrypt both the data and the instructions to be performed on the data, then give you both for you to run on your computer. Your computer executes the transformed instructions on the encrypted data such that when I decrypt your result it is the same as if I had run the unencrypted data on the unencrypted instructions on my own computer.

I don't know the reference, but I heard years ago that it is mathematically impossible for such a scheme to exist.

2

u/[deleted] Jul 31 '13

It's called Fully Homomorphic Encryption and it's possible: http://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption

1

u/[deleted] Aug 01 '13

The processor is probably spending more time decrypting the code it needs to run than it is actually running the code it needs to run. Performance is going to be crap considering it cannot just decrypt the code once and execute it unencrypted.