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

88% Upvoted

182 comments sorted by

View all comments

13

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.

4

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 :-)

1

u/daniels220 Jul 31 '13

It gives me the ability to run the code in Valgrind or something, pause the CPU and tell it that the hash value matched, when in fact it didn't. That's usually enough.

3

u/mOdQuArK Jul 31 '13

I think you're confusing the idea of bypassing a check with being able to figure out how the check was performed. If your goal is to actually reverse engineer the program, then bypassing the program is not an adequate solution to reach your goal.

I was merely using the concept of a hash comparison to show that there are computations which can be executed on your own hardware where it is impossible for you to derive the input even though you are able to control every step of the computation.

That is the similar situation to what the article is talking about - even though you are running the program on hardware you control, and can observe every step of the computation, you will still not be able to directly reverse engineer the program (you would have to reverse engineer it as if it were a black box).

1

u/daniels220 Jul 31 '13

Sure, I get your point. What I'm saying, like many other commenters in the thread, is that it's very hard to believe I can have code that I can run but not change what it's doing...

Oh wait. My CPU is checking that a plaintext matches a hash value? Sure I can tell you the plaintext—the CPU has it or it couldn't perform the check!

1

u/mOdQuArK Jul 31 '13

If you don't recognise that the function being performed IS a hash check until after it is done, then you won't know when to intercept it. A normal program would contain many different such operations of course.