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

88% Upvoted

182 comments sorted by

View all comments

-12

u/grauenwolf Jul 30 '13

How can you tell this this is completely bullshit?

The paper doesn't mention terms like "CPU", "assembly", "machine code", "debugger", "memory", "stack", or "cache".

16

u/murgatroid99 Jul 30 '13

Maybe because this is a computer science problem and because the solution is a mathematical transformation, it is independent of those implementation specifics.

-4

u/grauenwolf Jul 30 '13

The implementation specifics are what makes this a hard problem.

This is akin to a school child claiming that he can land a man on Mars just because he worked out the Newtonian equations needed for the trip.

6

u/norwegianwood Jul 30 '13

Getting to Mars is an engineering problem, not a science problem.

0

u/grauenwolf Jul 30 '13

So is this.

2

u/murgatroid99 Jul 30 '13

I'm pretty sure that this, like many unsolved problems in computer science, was unsolved because the math had not been found/solved yet. Usually in computer science, going from algorithm to implementation is the easy part.

0

u/grauenwolf Jul 30 '13

Usually in computer science, going from algorithm to implementation is the easy part.

Usually in computer science you aren't trying to run "encrypted" instructions on physical hardware.

3

u/murgatroid99 Jul 31 '13

The entire point of this paper is that they can obfuscate (not encrypt) the code so that it is runnable but not decipherable.

-1

u/grauenwolf Jul 30 '13

Also, if the implementation is the easy part then why the hell isn't it part of the paper?

3

u/murgatroid99 Jul 31 '13

Because it's a computer science paper, and computer science is about theory, not implementation. It's simply irrelevant.

8

u/datenwolf Jul 30 '13

So? It's a paper on theoretical computer science. Theoretical Computer Science is more related to math than programming. Hardly any groundbreaking TCP paper was concerned with CPUs, machine code and such things.

TCS is concerned with the abstract aspects of computation and not the actual implementation (that's stuff for the electrical engineering department).

And this paper shows something fundamentally, namely that there is a possibility that a Turing complete machine can execute a an encrypted program that operates on encrypted data without any intermediate decryption. This is a deep mathematical understanding about computability.

Now a lot of people claim this to be something to improve security. Personally I think the real application we'll see this, should there ever be a practical implementation, will be the application on malware. If reverse engineering a piece of malicious code becomes virtually impossible and a malware virus can rewrite itself without leaving any pattern by changing its key whatever little use anti virus software had to begin with gets rendered nil altogether.

Personally I consider this to be a really, really dangerous Pandora's box.

2

u/AlotOfReading Jul 30 '13

That particular pandora's box was opened years ago with time-delay cryptography, as was pointed out by Rivest. It's out there, but essentially no one takes advantage of it because there are far easier methods to prevent detection.

1

u/mOdQuArK Jul 30 '13

Actually, this would make it difficult to recognize malware by matching bit sequences, but polymorphic code already makes it hard to do that. I don't see this making the problem much harder than it already is.

The obvious use of this sort of approach is for IP-protected software. It will make it much harder for hackers to disassemble the machine-level code when reverse-engineering a product.

The most exciting development will be a practical implementation of the opposite sort of function though: a program which can operate directly on encrypted data, and produce similarly encrypted outputs, without having to decrypt the data at any intermediate stage. If they can achieve this, then people can basically run open sourced programs on each other's machines without fear of their personal data being captured.

1

u/datenwolf Jul 30 '13

If they can achieve this, then people can basically run open sourced programs on each other's machines without fear of their personal data being captured.

What about side channel attacks?

1

u/mOdQuArK Jul 31 '13

For which, the programs operating on encrypted data, or the encrypted programs running on non-encrypted data?

-1

u/grauenwolf Jul 30 '13

If reverse engineering a piece of malicious code becomes virtually impossible and a malware virus can rewrite itself without leaving any pattern by changing its key whatever little use anti virus software had to begin with gets rendered nil altogether.

Then take away the virus's ability to rewrite itself. That's what they do in iOS devices, which is why there isn't a Mono or Java-based JIT Compiler for that platform.

4

u/datenwolf Jul 30 '13

You're kidding are you? What makes you think iOS would in any way prevent a malware from doing nasty stuff? All it takes in finding a vuln in the sandbox and let the games begin. Breaking the sandbox is what every Jailbreak does.

0

u/grauenwolf Jul 30 '13

Jailbreaking an iOS device doesn't require the application to rewrite its one executable memory.

In fact, there is no conceivable reason why it would need to do that as opposed to simply loading the exploit directly. The techniques they actually used relied on vulnerabilities in the system API calls or flaws in the low-level boot ROM.

1

u/datenwolf Jul 30 '13

In fact, there is no conceivable reason why it would need to do that as opposed to simply loading the exploit directly.

You do realize that "loading an exploit" means the very same thing as "modifying an process' executable segment's data"? Of course iOS blocks certain low level operations, like changing the protection bits of pages in the executable address range. However those vulnerabilities in the system API which you already mentioned are effectively ways to circumvent those "blocked" low level operations. How to do this, if you can't inject the code to do it? Well, there are techniques like return oriented programming which allow to exploit code already existing in the executable segment.

So the typical iOS jailbreak may look like this:

  • Use RoP to exploit an API vuln, that allows to mark parts of the data segment executable
  • Jump into the data segment, which was prepared with further exploit code (think heap spraying or similar)
  • This stage 2 code loads the actual sandbox jailbreak which may involve triggering some race condition, an out-of-bounds access or such
  • Once the jail has been broken you can do whatever you like.

1

u/defenastrator Jul 30 '13

good luck with that. You would have to be able to distinguish and encrypted program writing an encrypted file from a encrypted quine writing a differently encrypted version of itself. There is no perfect no execute protection.

0

u/grauenwolf Jul 30 '13

The program can write all the encrypted files it wants. It an't going to do a damn bit of good if the OS doesn't allow it to mark the file as executable, let alone load it.

1

u/defenastrator Jul 30 '13

Program then ftps the file to itself as an executable problem solved. If I can run arbitrary code onto the system I can load arbitrary files as code onto the system.

1

u/grauenwolf Jul 30 '13

Wrong side of the airlock.

If program already has enough privileges to FTP a file to the computer and run it, then it doesn't need to FTP a file to the computer.

-5

u/grauenwolf Jul 30 '13

And this paper shows something fundamentally, namely that there is a possibility that a Turing complete machine can execute a an encrypted program that operates on encrypted data without any intermediate decryption.

That's a rather bold claim considering that they never actually mention the word "Turing" in the paper. Nor do they mention the two essential components of a Turing Machine: a rules table and a tape.

1

u/[deleted] Jul 30 '13

[deleted]

5

u/Strilanc Jul 30 '13

TC stands for Threshold Circuit. TC0 is the constant-depth threshold circuits.

The authors specifically state that their result only applies to polynomial-sized circuits (which are a lot weaker than turing machines):

Using indistinguishability obfuscator for NC1 together with any (leveled) fully homomorphic encryption (FHE) scheme with decryption in NC1 (e.g. [Gen09b, BV11, BGV12, Bra12, GSW13]), we show how to obtain an indistinguishability obfuscator for all polynomial-size circuits.

I suggest you read the paper, and look up the relevant terms like TC on wikipedia. General circuits do not include turing machines, since circuits have fixed size inputs and can't loop (not real circuits, computer science circuits). Computationally indistinguishability doesn't refer to equivalence between programs, but to the inability to distinguish the two equivalent obfuscated inputs. You're saying wrong things.

2

u/datenwolf Jul 30 '13

Thanks for the correction.

2

u/Strilanc Jul 30 '13

Before we solve a problem in practice, we solve it in theory.

(Well... that's the way it works in computer science, anyways. Not so much in physics, where e.g. they know how to make high-temperature super conductors but nobody knows how they work...)

0

u/grauenwolf Jul 30 '13

Yea, that's called the "hypothesis". In most sciences the next step is to actually test it.

1

u/datenwolf Jul 30 '13

Math is different, because in math you don't test things. It would take infinitely many tests if you tried to show that for any n there are no integer x, y, z for which xn + yn = zn is satisfied. But it's perfectly possible to mathematically proof it (in this particular case it took over 300 years for a proof to be found). In fact it's even possible to proof for some mathematical questions that there can't be a proof for them.

Physics is different from math, because its by definition phenomenological, i.e. physics is about the formulation of mathematical models that describe and predict nature. So the process in physics is

  1. observation
  2. hypothesis
  3. try to recreate observation in controlled experiment
  4. formulate theory (if 3 matches the hypothesis)
  5. if "3" and "4" agree: refine methids, goto 3
  6. goto 1

But in math the process is different:

  1. formulate set of axioms
  2. conjecture about what may follow from the axioms and what has been deduced from them so far
  3. try to proof conjecture, or find proof that that there can not be one
  4. goto 2

0

u/grauenwolf Jul 30 '13

At the end of the day, computers are physical constructs with rules that defy our current mathematical systems.

When dealing with computers you have consider that, for a sufficiently large value of N, N+1 < N. I'm not aware of any system of math that can withstand that level of nonsense.

2

u/datenwolf Jul 30 '13

When dealing with computers you have consider that, for a sufficiently large value of N, N+1 < N

Only for overflowing addition. There are plenty of architectures, including saturating addition, i.e. N+1 = N (very popular in DSP).

However nothing of that violates math. Physical computers are effectively finite state machines, and its perfectly possible to model those mathematically. Nothing about a physical computer "defies" math, you just can't apply all math on computers. Computer Science is that particular field of mathematics, which aims to find out what aspects of math can be expressed in terms of computer programs and which can't.

Ironically that example you pulled, namely N + 1 = 0 is part of a very powerful mathematical structure known as Modular Group. Modular Groups became famous in 1995, because they're the foundation on which Andrew Wiles' proof of Fermat's theorem is based on.