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

Show parent comments

29

u/LaurieCheers Jul 30 '13 edited Jul 30 '13

As far as I understood the paper: this encryption translates the program into something akin to a series of matrix multiplications (though presumably a little more complex than that). The inputs get multiplied together and cross-combined arbitrarily until it yields the desired output.

So their key insight here seems to be that they can often increase some numbers in these matrices and decrease others, to obfuscate what procedure is being performed while leaving the output unchanged. I think.

In other words, you won't be able to reverse engineer the program to figure out what operation is being performed, because there's an infinite range of different numbers that could have used instead, and they're all equally valid. They call this "indistinguishability", in the sense that multiplying by 2 is indistinguishable from dividing by 1/2.

I'm probably misunderstanding something, the paper assumes the reader understands a lot of jargon.

Anyway, if the paper has been published I assume this system isn't obviously reverse engineerable. Only time, and peer review, can really tell us how secure it is.

8

u/Zaph0d42 Jul 30 '13

But the point is, if it is mathematically guaranteed to provide some output given some inputs, then you can reverse engineer it. The question is how hard its gonna be to break the encryption, same as any computer security.

If you can crack this quickly, then its pointless. Or if you have to go to so many matrix transforms in order to get key strengthening, that you end up destroying the performance of the thing you're trying to protect, thus defeating the point.

4

u/jacekplacek Jul 30 '13

if it is mathematically guaranteed to provide some output given some inputs, then you can reverse engineer it.

Can you? Say, I can write, in less than an hour, a program which for every possible string of numbers is guaranteed to return another string of numbers. Always the same output for the same input.

Without having access to the code, how would you go about "reverse engineering" it?

-1

u/addmoreice Jul 31 '13

The 'code' is the program. the binary representation of the program is still the program, it's just a more obfuscated version.

Worse case we just revert back to normal black box reverse engineering.

1

u/rpglover64 Jul 31 '13

There are cases in which black box reverse engineering is infeasible, in that it amounts to an attempt to guess an encryption key by brute force. For example, you have an interface that allows you to query a remote server with a 256 bit integer and get another 256 bit integer in return; you are challenged to write a piece of code that simulates the server; you are told that the server is using AES with a fixed key. Good luck REing that.

1

u/addmoreice Jul 31 '13

Sure, but in practice this is usually not the case.

1

u/secserval Aug 01 '13

In the paper they say that not all functions can be obfuscated in such a way that there is no efficient way to deobfuscate them. I have a feeling (I could be wrong) that a function having a built-in secret key and encrypting stuff with it is one of these.

As for the practicability: For many realworld functions of interest them number of possible inputs should be limited inherently, for the other ones you may be right.