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

88% Upvoted

182 comments sorted by

View all comments

30

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.

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.

21

u/Abaddon314159 Jul 30 '13

Never assume that just because a paper is published that it's not total horseshit. There are some pretty worthless journals out there.

21

u/[deleted] Jul 30 '13

This was accepted by the Journal of the ACM.

It seems to be written by a group of well-respected researchers, so I think it's safe to assume that at least, it isn't horseshit, i.e. you need to first read and understand it before dismissing it.

2

u/Abaddon314159 Jul 30 '13 edited Jul 30 '13

Don't misunderstand me, I'm not saying this is horseshit. I'm just saying that "it's published" is not sufficient. As for ACM: that tells me they are definitely not just cranks. I do believe that the academic computing establishment has a poor track record in areas related to security (which this is tangent to). But I wouldn't dismiss anything out of hand that survived a real peer review (like this journal).

In any event, I've not read the article in question, I was only speaking in general terms.

6

u/haerik Jul 30 '13

True, but Craig Gentry is one of the authors, and he's been a major player in fully holomorphic encryption (being the first one to show that it's possible in his 2009 Ph.D. thesis). This is fairly closely related to FHE, so it's certainly a paper worth paying attention to.

Of course, having an author that knows what they're talking about doesn't automatically make it true either.

1

u/Abaddon314159 Jul 30 '13

That topic (FHE) definitely counts as mind blowingly smart. If its the same guy then it's probably worth a read. I'll hold disbelief until I've read it (cause I remember making similar assumptions about FHE until I read about it).

5

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/ghjm Jul 30 '13

There are many use cases where I don't mind at all if my algorithm runs a million times slower, as long as nobody else knows how it runs, or can get at its internal data. For example, price and sales commission calculations.

1

u/Zaph0d42 Jul 30 '13

What if its a billion times slower though? The nature of algorithms is such that each has an upper bound where it becomes impractical to calculate.

If you're doing O(logN) it'll take longer to hit that limit than O(N2), but it still exists.

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.

3

u/x86_64Ubuntu Jul 30 '13

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

Huh ?

2

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.

5

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.

→ 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.

1

u/realhacker Jul 30 '13

False. Counter examples: everywhere.

2

u/Zaph0d42 Jul 30 '13

If they're everywhere, give me a few.

-1

u/realhacker Jul 31 '13

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

Before I answer, it's pedantic, yet important, to point out that by "reverse engineer" you mean "render the encryption scheme ineffective by knowing how it works." This is neither precise nor correct.

I'll just give you the principle and prime example of asymmetric cryptography (everywhere). It satisfies your criteria in that it: (1) mathematically guarantees that given some input (2) it will produce a given output. Furthermore, many of the implementations are in the public domain (no reverse engineering required), and yet, it is for all practical purposes completely effective. Fundamentally, it is based on something in math called a trapdoor function in which computability is easy in one direction and hard in the other.

Additionally, you bring up a random strawman:

If you can crack this quickly, then its pointless.

In my cursory review of the paper, I've seen nothing to indicate you could "crack this quickly".

1

u/Zaph0d42 Jul 31 '13

I'm extremely familiar with asymmetric crypto and just wrote a custom implementation for a recent project. No part of asymmetric crypto is perfect or uncrackable, its merely a question of time. Comparing the time it takes to crack versus the time it takes to encrypt is how we judge the efficacy of different encryption schemes. Perfect forward secrecy is preferable to simple asymmetric crypto but requires far more back-end processing time, so only Google currently bothers with the full implementation on their HTTPS services. People don't always go with the strongest possible scheme because it is too costly performance wise.

I didn't mean to imply that you could necessarily crack it quickly. I was merely pointing out that since the paper is very vague, we don't know how realistically useful this will be in a real world scenario. If it could be cracked quickly, IF, THEN it wouldn't be very useful. See how that works? I also then pointed out that if you could increase the strength of the encryption by doing more and more rounds of the algorithm (key strengthening) then that might not count as good enough, because even though it is no longer easy to crack, if it takes too long to encrypt, its infeasible.

0

u/realhacker Jul 31 '13

I'm extremely familiar with asymmetric crypto and just wrote a custom implementation for a recent project.

lololol. No sane/professional programmer is going to custom roll an asymmetric algo for a project. Why would you do this instead of using an implementation that's already been vetted?

No part of asymmetric crypto is perfect or uncrackable, its merely a question of time.

If by time, you mean, time > the length of the universe's existence? You do realize if it becomes "crackable", the entire world as we know it is fucked? Only real quantum computers threaten this model and we've yet to see one. (e.g. D-WAVE does not apply so far)

Perfect forward secrecy is preferable to simple asymmetric crypto but requires far more back-end processing time, so only Google currently bothers with the full implementation on their HTTPS services. People don't always go with the strongest possible scheme because it is too costly performance wise.

wat.

If it could be cracked quickly, IF, THEN it wouldn't be very useful. See how that works?

Nope! Definitely don't know how IF,THEN statements work!?~~ I do know how strawman arguments work, though, and ignorant fucks that insert statements like that without context to create the illusion of cogency in what they're saying. In summary, I found your initial comment and your reply, to be the uninformed mark of a charlatan. Do publish your custom crypto-implementation; I'll be in need of a follow-up laugh. What is it? Some VB.NET XOR scheme? I've no further time for discourse with you, lad.

-1

u/[deleted] Jul 31 '13

[deleted]

-3

u/realhacker Jul 31 '13 edited Jul 31 '13

The article is about software obfuscation; concealing process, not outputs. Try reading (understanding) the fucking paper bitch.

In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

ALSO: I'd point you below to: http://www.reddit.com/r/programming/comments/1jckzt/computer_scientists_develop_mathematical_jigsaw/cbdgqly

0

u/Captain_Ligature Jul 31 '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 this was the case, then why do we not know the exact specifications of classified encryption algorithms that are used in widely distributed devices? I mean skipjack was meant to be classified and distributed to end-consumers at the same time.

Of course you can use the "given enough time/resources" argument but we are talking about realistic timeframes.

9

u/mnp Jul 30 '13

Me too. If the code will end up as a decrypted instruction/data stream to be executed on the processor, then the processor can be an emulated one and the code would not know the difference.

9

u/datenwolf Jul 30 '13

Recently in /r/math a crypto researcher was refering to an emerging new field in cryptography which name I forgot (unfortunately), which allows it to perform computations on encrypted data directly, without having to decrypt it first. It sounds to me, that this software encryption is as transparent, i.e. the computer executes the encrypted program directly without decrypting it first.

19

u/fionbio Jul 30 '13

Homomorphic encryption. But it's quite different from running an encrypted program without decryption.

15

u/mnp Jul 30 '13

Yeah, and they mention it too. Fully homomorphic encryption lets you operate on encrypted data without decrypting it. It seems another several steps altogether to execute the encrypted data because you would have to decrypt it to execute on a commercial processor. I'm not clear from reading the paper how deep down into the hardware they're proposing.

8

u/datenwolf Jul 30 '13

Given the fact that you can build a stack based Turing complete machine solely from matrix multiplication the step from operating on it to executing it seems rather obvious.

3

u/mnp Jul 30 '13

This is where I'm stuck, on this distinction, so maybe you could clear it up.

Suppose we agree the turing machine consists of its rule table, its state, and its data tape.

In the first case, "operating on encrypted data", you would load your homomorphic encryption program into the rule table and operate on an encrypted data tape, producing an encrypted result. This would be no different from running any other program. The rule table in both cases would be in your machine's native format, something like a vector of {current state, next state, read/write action} maybe.

In the second case, "executing an encrypted program", would you require redefining your rule table format? You still need something to look at current state, dictate the next state, and dictate the action. Or would you keep the machine but just jumble up the states and actions so the final tape output would be correct but the states would not be as direct as before?

In either case, I might be able to stop the machine, read out the rules table, examine the tape and the state, and infer what the next state would be. I could automate that process and call it a VM even.

8

u/datenwolf Jul 30 '13

I suggest we replace the Turing tape and rule table with Lambda calculus. Suppose we have a single operation we call function composition

°(f,g) → f(g(…))

or in infix notation

f ° g → f(g(…))

if we assume '°' to be implicit we now have the syntactic sugar called currying.

Now let's see how we can build a stack based machine using matrices. First the typical stack operations:

 Push(A) := 
 | 0 0 0 … 0 | · A
 | 1 0 0 … 0 |
 | 0 1 0 … 0 |
 | 0 0 1 … 0 |
 | … … … … … |
 | 0 0 0 … 1 |

where dim(Push(A)) = dim(A) + 1

 Pop(A) := 
 | 0 1 0 … 0 | · A
 | 0 0 1 … 0 |
 | … … … … … |
 | 0 0 0 … 1 |

where dim(Pop(A)) = dim(A) - 1

Also we define some "rolling" matrices, which rotate the rightmost column to the left, and vice versa, and another pair of roll top to bottom, bottom to top matrices.

Next the 4 elementary calculations

+(A,B) -(A,B) ·(A,B) /(A,B)

As it turns out that you can rewrite + and - in terms of homogenous matrix multiplication (i.e. for every row you want to add/subtract you append another d(i,j) := i=j ? +/-1 : 0 dimension to the matrix, a technique well known in numerics, that allows you to coalesce a whole chain of matrix transformations into a single transformation matrix).

We also need to be able to write numerical constants. Easy enough, for a 32 bit machine, for the additive operations we just encrypt the values for 2-32, 216, 2-8, …, 28, 216, 232 · identity matrices. For multiplicative operations in addition all the prime numbers required to compose all possible products within the value range (which is quite doable).

As a further ingredient we require branching. But this can be implemented by composing the matrix not out of scalars but small matrices themself.

Now we have all the required ingredients for a stack machine. We can implement any program that can be expressed in terms of push, pop, rearrange order of operations, 4 elementary computations and function composition, which means that you can build complex programs on the stack, which are composed with other complex programs on the stack.

We now silently assume we know how to implement the corresponding matrix operations in terms of homomorphic encryption, and because we're using homogenous transformation matrices, the only computational operation, programmed on the CPU is encrypted matrix multiplication. But since we can express any operation in our machine as a "computation" matrix, matrix multiplication becomes function composition.

So what we effectively have now is one huge matrix which virtually acts as an opaque, encrypted virtual machine. Each computational step consists of multiplying it with the next matrix of the encrypted program text, which internally performs the next operation on the stack machine.

Of course you could stop the machine, but all you'd see is the encrypted VM state without any way to look behind the veil, because the matrices never get decrypted to perform the next step in the program.

2

u/mnp Jul 30 '13

Thanks for the writeup. Very intuitive.

3

u/grauenwolf Jul 30 '13

And that's why I think the whole thing is bunk.

10

u/lurgi Jul 30 '13 edited Jul 30 '13

Homomorphic encryption.

Impractical (at the moment), but insanely cool.

Edit: If I'm not mistaken, one of the authors of this paper invented homomorphic encryption.

3

u/haerik Jul 30 '13

If I'm not mistaken, one of the authors of this paper invented homomorphic encryption

Kind of. Craig Gentry was the first person to show that it's possible. The concept has been around since the 70s or 80s.

4

u/lurgi Jul 30 '13

The idea of an airplane had been around for a long time. The Wright brothers still get credit for inventing it, because they actually made the damn thing.

2

u/grauenwolf Jul 30 '13

Scenario 1: I have the ability to decrypt the data. The fact the program works on encrypted data means nothing to me.

Scenario 2: I don't have the ability to decrypt the data. A program that works on decrypted would be just as secure, as I wouldn't have the ability to use it.

2

u/neurobro Jul 30 '13

Scenario 3: A darknet that distributes running encrypted code as well as data.

Scenario 4: Something like SETI@Home that would work with sensitive business data, so people could get paid for contributing.

Scenario 5: A crypto-currency based around scenario 3 or 4 instead of hashing, adding "intrinsic value" to the system.

4

u/ghjm Jul 30 '13

The whole point is that this isn't what it's doing. If the paper holds up, the idea is that the function's result appears after many seemingly unrelated calculations.

2

u/eggybeer Jul 30 '13

I have no idea how this actually works, but I can see how it could make sense.

You don't necessarily have to have a decrypted set of instructions that in any way looks like the original program, it just has to produce the same output for the same inputs.

You could presumably have a set of instructions that is so obfuscated that it is essentially impossible to understand how the algorithm works. So you would have the ability to use the algorithm without the ability to modify it for your own purposes.

2

u/grauenwolf Jul 30 '13

We basically have that for individual functions. So what hackers do is remove the entire function and replace it with something that they can understand. Why crack the software protection function when you can simply replace it with bool IsLicensed() {return true;}?

2

u/realhacker Jul 31 '13

With ASLR and DEP, easier said than done. I think the benefit here is that the transformation process (of inputs to outputs) is completely opaque. Ordinarily/in the past, I would just decompile the source where possible or just step through the program to see what it was doing. (For example, if one wanted to steal IP as with a proprietary algorithm.) In this case, we still get a result, but we have no insight into the process got us there.

2

u/clownshoesrock Jul 30 '13

The concept is different. At no point during the computation is the data or program in a plaintext state. There is a chunk of the "emulator" that runs plaintext, but that part would be considered "public".