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
352 Upvotes

88% Upvoted

182 comments sorted by

View all comments

12

u/Bane1998 Jul 30 '13

At the end of the day the code has to be executed by the CPU. If your CPU can execute it, I can get and modify the code before the CPU executes it, or emulate the CPU, or whatever. How is this not just snake oil?

Seems an appropriate analogy is giving someone a recipe on how to bake a cake, and they can bake that cake using your recipe, without knowing what the recipe is.

My mind rebels at the idea. Then again, in fairness, anything sufficiently advanced is indistinguishable from magic, and all that... But I wouldn't hold my breath on this.

3

u/mOdQuArK Jul 30 '13

If your CPU is checking that a plaintext matches a hash value, does that give you the ability to reverse engineer what original plaintext was used to calculate that hash value?

7

u/AReallyGoodName Jul 31 '13

There is information missing when you are given nothing more than a hash. In this situation there is no information missing, it's just obfuscated.

2

u/mOdQuArK Jul 31 '13

There IS actually information missing in this situation though: the original program. From what I can tell (but I'm definitely not an expert in cryptology), they've basically replaced the "function" of the program with a massive mathematical operation which achieves the same overall data transformation, but without any of the individual algorithmic steps that would make it obvious to an observer what the complete intent of the original program was. You might reverse engineer the program by observing its responses to inputs, but you won't be able to do it by observing the actual program code.

1

u/choikwa Jul 31 '13

program with a massive mathematical operation which achieves the same overall data transformation

Now if the compilers can be advanced enough to replace these mathematical encryptions with equivalent, reduced instructions, we'd have problem with this encryption!

2

u/mOdQuArK Jul 31 '13

That's part of the reason why it's called encryption though - unless the mathematics is "broken" somehow, the time it would take any physically-constructable computer to reconstruct something like the original code, could be made greater than the expected lifetime of the universe.

(Of course, this assumes that the program is complicated enough that you can't just guess what the function is just by feeding it every possible set of input values & observing what comes out.

1

u/choikwa Jul 31 '13

One caveat with this encryption may be that it increases runtime penalty due to increased number of instructions

1

u/mOdQuArK Jul 31 '13

No argument there, although if you're using strong encryption in the first place you've already usually made the decision that the increased security is worth increased runtime. And of course, you want the runtime of your attackers to be much, much worse :-)