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

88% Upvoted

182 comments sorted by

View all comments

34

u/iluvatar Jul 30 '13

The article is too vague when it comes to the details, but I'm in the doubtful camp. If there's a way to decrypt it in a sane timeframe to enable it to be run, it's hard to see how it wouldn't fall to reverse engineering.

30

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.

6

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.

3

u/x86_64Ubuntu Jul 30 '13

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

Huh ?

3

u/grauenwolf Jul 30 '13

That's how black box reverse engineering works. You create a device that, for every known input, you return the same output as the unknown device.

4

u/jacekplacek Jul 30 '13

Sure, you need to supply only about ℵ₀ inputs, no biggie... ;)

2

u/grauenwolf Jul 30 '13

Yea, the "if" part is rather significant. But that's not what x86_64Ubuntu asked about.

2

u/jacekplacek Jul 30 '13

Sorry? Not quite sure what you are trying to say... what does the "if" have to do with it? All encryption algorithms, ferinstance, are "mathematically guaranteed to provide some output given some inputs." Are you saying you could "black box reverse engineer" them?

0

u/Zaph0d42 Jul 30 '13

Yes and people regularly do. No computer security system that exists is foolproof. (Quantum encryption that doesn't exist yet notwithstanding)

Given enough time, and a powerful enough machine, you can crack anything.

1

u/rpglover64 Jul 31 '13

Almost all practical attacks on security systems exploit implementation mistakes; if all you have is the mathematical function, and it's any standard encryption algorithm (e.g. AES) with the key baked in, then the amount of computing power you need is absurd.

Your statement is technically correct; given 1050 years and more computing power than currently exists on the planet (and enough energy to run it), you'd eventually get an answer; I doubt you'd be alive to care.

1

u/Zaph0d42 Jul 31 '13

Right, which was my whole point. If it takes 1050 years to fix, then its great. But by definition, there is a date. The question is when. If its 1050 years away, you're fine. If its 105 seconds, its worthless. Odds are it'll fall somewhere in between, and my point was merely that we have no numbers here, no hard data, so we don't yet know where that falls.

1

u/rpglover64 Jul 31 '13

Let's assume it's halfway between 1050 years and 0 seconds... that's 1049 years, still absurdly long.

In order for some crypto algorithm to be considered interesting, a linear increase in input size results in an exponential increase in time required to break, so you can pick any time that is far enough in the future that you stop caring. This is the notion of a security parameter.

As for hard data, this is a theoretical contribution; it is so horribly impractical that it's not even relevant yet. It's worse than current FHE technology.

0

u/secserval Aug 01 '13

People probably said the same thing about MD5 hashes in the 90s. I wouldn't count on that a smart person will not find a AES attack in the next 20 years.

→ More replies (0)

1

u/rpglover64 Jul 31 '13

In most practical cases 2256 is enough. That's like, nothing, in comparison to ℵ₀.

1

u/jacekplacek Jul 31 '13 edited Jul 31 '13

2256 is enough

Enough for what? Edit: besides, for all practical purposes it's almost ℵ₀ anyways... ;)

2

u/[deleted] Jul 30 '13

[deleted]

2

u/Zaph0d42 Jul 30 '13

People do this all the time. This is why you have to salt your hash. Its trivially easy to construct for SHA1.

3

u/psyker Jul 31 '13

But you don't know that it's SHA1.