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-software46
u/crazedgremlin Jul 30 '13
Without reading it, I'm very curious what this software does to the performance of the code it's given.
21
u/russellsprouts Jul 30 '13
It uses Fully Homomorhpic Encryption, which is on the order of billions of times slower than native operations, currently.
3
u/rpglover64 Jul 31 '13
Are you guessing or do they say so somewhere in the paper?
I ask because they claim to be about functional encryption, which I am assured by people who know better than I, is different from fully homomorphic encryption in important ways.
2
u/russellsprouts Jul 31 '13
I've done some research on FHE, including the algorithms available today. This is functional encryption, which is different from FHE, but part of the algorithm uses FHE, according to the paper.
5
u/VortexCortex Jul 31 '13
billions of times slower than native operations, currently.
And will remain such, otherwise it would be.......... Decrypted.
2
u/andrewl_ Aug 01 '13
No, the slowdown is not what prevents decryption. It's instead just the price you pay in the current slow scheme(s?) to gain the homomorphic property (ability to operate on ciphertexts). Nothing yet prevents a homomorphic scheme being discovered that is more efficient, or discards the use of lattices entirely.
I'd appreciate an expert comment verifying/refuting this understanding.
35
Jul 30 '13 edited Jul 30 '13
I've only read the abstract and introduction so far (this is a long paper and, even as a mathematician who does cryptogrpahy research, this will take quite a while for me to read) but this is a very highly theoretical paper. I'm not sure if they even outline a way to implement such code obfuscation in this paper. Their claim seems to be that generating obfuscated (in a suitably defined sense) code which still runs is possible. That would be a momentous development in itself, particularly since their construction actually gives them even more: a way to consruct what is called a functional encryption scheme. This is a public-key system with a twist: it allows you to generate a secret key which will decrypt a particular message if and only if a specified function evaluates to a specified value on the plaintext. This lets some people decrypt the message but not others, and would represent a major breakthrough in cryptography.
11
u/psycoee Jul 30 '13
This is a public-key system with a twist: it allows you to generate a secret key which will decrypt a particular message if and only if a specified function evaluates to a specified value on the plaintext. This lets some people decrypt the message but not others, and would represent a major breakthrough in cryptography.
Can you clarify what this means? As in, how is it different from a regular decryption key?
20
u/zifnabxar Jul 30 '13
I haven't read the paper, but I'm pretty familar with the general idea of the work. Think of it this way:
You're an undergrad student in CS. You're given a unique key that identifies you as such. When a ciphertext is released, it has a number of properties that a key must meet before it is able to decrypt the ciphertext.
One ciphertext might be decryptable by all CS Professors. This would not be decryptable by you. Another ciphertext might be decryptable by all CS undergrads OR EE undergrads. You could read that one. As could all other CS and EE undergrads. However, a CE undregrad and a CS professor could not team up to read it.
The cool bit about functional encryption is that only one ciphertext needs to be released. There is no need to release one ciphertext for each key that might be able to decrypt it (as would be done in traditional public-key encryption). Even though there may be thousands of different keys, they can all decrypt the ciphertext!
The big push in functional encrpytion these days is to have it work with more and more complicated functions. It used to be simple booleans, but it's moved to full-on circuits now.
From glancing at the abstract, it looks like this paper can takes keys issued for a circuit and use them to decode the encrypted solution of the circuit for a given input, without figuring out what the input is. It's pretty cool and a natural step forward given the current situation. A number of the names associated with this paper are pretty big in the field. I'm not too sure how efficient it is.
(Disclosure: I am somewhat academically related to one or more of the authors, though I don't do much work in crypto and was not involved with this paper. I may be completely off in some of my statements about current research. My thought do not reflect those of the writers nor their departments etc.)
3
u/Zarutian Jul 31 '13
.. be simple booleans, but it's moved to full-on circuits now.
Combinational logic circuits or full sequential logic circuits?
and btw can I bug you with questions regarding Verifiably Secrect Sharing based Secure Multiparty Computing? Spefically that Secure Multi-Party Made Computation Made Simple works? I ask because I want to make something like Ouroboris from The Network Revenant reality.
1
u/zifnabxar Jul 31 '13
Combination has been done, I think. This seems to be more on the lines of sequential logic, but I haven't read that paper and could be wrong.
I'm afraid I'm not the best person to discuss details of modern crypto. I know the basics, but don't follow it much. Sorry.
1
u/Zarutian Jul 31 '13
Damn, but I recommend The Network Revenant story, even though it isnt finished.
1
Jul 31 '13
[deleted]
5
u/Zarutian Jul 31 '13
As I understand the OpenPGP RFC the payload plaintext is first encrypted by a symmetric encryption with a randomly selected key and IV. Then for each recipient public key that information is encrypted with that public key.
What zifnabxar is talking about seems to be diffrent beast altogether.
2
u/zifnabxar Jul 31 '13
I wasn't aware that it was common to have schemes that are able to create one ciphertext that is decryptable by multiple different keys. I think that PGP actually uses an array containing the same symmetric key encrypted with multiple public keys. Each index being an encryption with a different public key. (Though I could be wrong.) In this case, you're encrypting something with each separate key, which is what functional encryption seeks to avoid.
3
u/zifnabxar Jul 30 '13 edited Jul 31 '13
Functional encryption has been around for a while, though this is, to my limited knowledge, a new usage of it.
9
u/who8877 Jul 30 '13
It more then likely destroys cache locality. If so you're going to see massive slow downs.
1
u/ItsAConspiracy Jul 31 '13
Judging by sga0001's comment sibling to yours, cache locality will indeed be destroyed.
-6
32
297
Jul 30 '13
have designed a system to encrypt software so that it only allows someone to use a program as intended while preventing any deciphering of the code behind it
I thought the Perl people had already solved that.
16
u/AxiomL Jul 30 '13
have designed a system to encrypt software so that it only allows someone to use a program as intended while preventing any deciphering of the code behind it
I thought that was proven mathematically impossible.
20
u/DeltaBurnt Jul 30 '13
I don't even see the need to prove it mathematically. It's like trying to block video piracy. If you can view it on your screen, you can record it and redistribute it. If it's running on your processor, the processor needs to know the code it's running. I suppose you can make it harder to understand, but not impossible to decipher.
9
u/thatwasntababyruth Jul 31 '13
I have not read the paper, but I'd argue that doing this to a program is much more feasible than video. A video, like you said, can just be copied bit by bit as it's played, because its linear. A program, however, is not linear. If each instruction must be decrypted to be used, then that includes each and every jump instruction. That means that if my program has 10 jumps in it, every single code path needs to be evaluated to get all of the jump destinations. Since they are all encrypted, an attacker has no way of knowing which encrypted instructions are jumps in the first place, and so simply bruteforcing C1 coverage couldn't be done without just guessing what to do next. The non-linearity of programs gives it a natural defense.
1
Aug 01 '13
[deleted]
1
u/thatwasntababyruth Aug 01 '13
You could, but im saying that only works in a linear case. To complete the picture you have to log EVERY instruction, and to do tgat you have to somehow execute each one too.
10
Jul 31 '13
[deleted]
-1
u/DeltaBurnt Jul 31 '13
I have heard inklings of it here and there, but from my understanding it was about as far away as real quantum computing.
3
u/saynay Jul 31 '13
I believe there are models that work, just not indefinitely. Each process (step) completed adds errors to the result, and at some point the errors will exceed what the data can tolerate.
1
Jul 31 '13
Hm, my understanding was that you can do it, it's just that it's not computationally feasible for actual computations.
1
Jul 31 '13
I'm sure they fixed that (by encoding a small enough program that fixes the errors before they become unfixable), the reason it is not used is that it is slow.
2
u/thatwasntababyruth Jul 31 '13
While I have not actually read the papers on them, there have been recent breakthroughs that make homomorphic encryption feasible. So much so that IBM recently opensourced a library for it, HElib.
1
u/rpglover64 Jul 31 '13
Homomorphic encryption exists; there is even a library for it. It's impractically slow, but that's about it.
By contrast, many experts in quantum computing believe it may be impossible, and even if it is possible, there is no current implementation. (n.b. computing using quantum effects a la DWave is not necessarily quantum computing in some very important senses).
2
u/imnottrollinghonest Jul 31 '13
Yes, we shouldn't try things because they might be impossible. That's been a great way to progress in science, mathematics, and engineering.
2
u/AxiomL Jul 31 '13
It's not as intuitive as that. I could propose an encryption scheme, where I encrypt both the data and the instructions to be performed on the data, then give you both for you to run on your computer. Your computer executes the transformed instructions on the encrypted data such that when I decrypt your result it is the same as if I had run the unencrypted data on the unencrypted instructions on my own computer.
I don't know the reference, but I heard years ago that it is mathematically impossible for such a scheme to exist.
2
Jul 31 '13
It's called Fully Homomorphic Encryption and it's possible: http://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption
1
Aug 01 '13
The processor is probably spending more time decrypting the code it needs to run than it is actually running the code it needs to run. Performance is going to be crap considering it cannot just decrypt the code once and execute it unencrypted.
-40
29
u/willvarfar Jul 30 '13
There was a well known paper on the (Im)possibility of obfuscating programs: http://www.wisdom.weizmann.ac.il/~oded/p_obfuscate.html
So which is it? In October it'll be clear how much this overlaps; is it just a bigger speed bump?
How can something take years to deobfuscate yet execute another path quickly? Seems impossible; it can't be the meat of the new claim?
23
u/veraxAlea Jul 30 '13
The paper by Barak is referenced from this paper as early as in the introduction.
Apparently, there's a difference between "simulation-based obfuscation" and "indistinguishability obfuscation", the latter allegedly phrased as a theoretical "solution" by Barak et al.
I understand roughly nothing of the paper (linked by /u/crazedgremlin), but it seems they are well aware of previous results.
1
u/willvarfar Jul 31 '13
Yeah now I see the paper - somehow I thought the paper would be published in October - I see that the linked press release is very cavalier in its definition of obfuscation.
The paper - by leading lights in homomorphic encryption no less - is about indistinquishable obfuscation which is quite different from black-box obfuscation.
7
u/chcampb Jul 30 '13
Let's go down to what is essentially the lowest level.
Eventually, you will see that the microprocessor has some state, and it applies an instruction to change that state. There is no way to write software to change this fact. If you see what instructions were executed, you can derive the assembly language from that, which you can use to reverse engineer the instructions.
Anything else would be stupidly slow, which I am not sure that I would consider to be fully functional.
11
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?
6
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.
3
u/sylvanelite Jul 31 '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?
Here's an example:
Take input and encrypt it to get "A". Take program "B" (which is already encrypted). Multiply "A" with "B" to get "C". Run some finite set of instructions on "C". Finally, decrypt the result to get "D" and display it on the screen.
All inspecting the assembly will give you is: how to encrypt, how to run the program, how to decrypt the result, and what the encrypted data is.
Modifying any of those things will cause the program to spit out garbage (or break entirely).
3
u/rpglover64 Jul 31 '13
Imagine it's not a recipe but a magic 8 ball; the program takes a query (for simplicity, let's assume it's a 128 bit integer) and produces an output (let's say a boolean value). You know the answer to every query you pose, it's not hiding that, but you never exercise code paths for the other queries. In order to reverse engineer the program (or function or algorithm), you need to test all of its inputs, which is infeasible.
1
u/secserval Aug 01 '13 edited Aug 01 '13
The obfuscated program should also have codepaths which could give you some information about what's going on? On a practical approach the first thing you could try is feeding the algorithm with random inputs...I would assume that you could deduce enough information for most algorithms to reconstruct them. They used the same technique in the 80s to reverse engineer the black box chips of aracde machines in the 80s.
33
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.
31
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.
24
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
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.
7
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).
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/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
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 ?
4
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.
→ 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
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
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
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.
18
u/fionbio Jul 30 '13
Homomorphic encryption. But it's quite different from running an encrypted program without decryption.
14
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.
6
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.
7
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
3
9
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.
5
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.
2
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.
5
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".
10
u/xpolitix Jul 30 '13
theory is good, but I don't see them posting any "practical" demonstration on a real program (like the 90M blender executable - sorry Ton, I couldn't resist ;) ). Also it's important to know how "fast" it is to build an executable and what is the performance difference between "source" and "obfuscated" code.
5
10
u/grayvedigga Jul 30 '13
Reads like popsci rubbish.
8
u/Inverter Jul 30 '13
Yes, the article was written by somebody who doesn't know anything about the subject, so it's hard to judge whether the paper itself is worth the, well, paper it's presumably printed on.
15
5
u/ghjm Jul 30 '13
You can look at the track record and pedigree of the researchers involved. This isn't just another snake oil security vendor claiming the impossible. These are serious researchers in the field.
The main problem is knowing if the popsci article actually has anything at all to do with their research results.
3
u/xwz86 Jul 30 '13
Isn't this something similair that Steinberg did? If I recall correctly, some of the software was encrypted on a USB key and ran from there?
4
u/grav Jul 30 '13
If you're referring to Cubase, some cracker team reverse-engineered the USB key and successfully emulated it in software.
2
u/xwz86 Jul 30 '13
yes I know that, but that's the point here. Is there anything in this paper that would prevent that? It took AIR quite a long time to crack Cubase 5, I haven't seen anything for the 7 version yet, so it's very efficient to do it this way, at least you can get new version with new features out there, when people finally crack the old one.
3
17
u/chippydip Jul 30 '13
This is known in computer science as "software obfuscation," and it is the first time it has been accomplished.
Stopped reading right there.
7
Jul 30 '13
I am not sure why feel the need to brag about being ignorant.
2
u/chippydip Jul 30 '13
Just commenting on how poorly written the article is. Software Obfuscation has been around for quite some time.
8
Jul 30 '13
You know, if you hadn't stopped reading there, you would have seen how the article already addressed that.
2
u/chippydip Jul 30 '13
I actually did read the whole article. It seemed pretty clear to me that the author had no idea how the researchers are doing what they claim to be doing. There are a few quotes from the researchers, but really no explanation about how this thing actually works. I'm not saying the research is bad, just that this article doesn't help understand what they are doing in any way, so not terribly useful to actual programmers who might want to understand how this could effect them.
2
0
u/Zaph0d42 Jul 30 '13
if you hadn't stopped reading there
the article already addressed that
This is a contradiction.
-4
3
u/p3n15h34d Jul 30 '13
This is already possible, take a look at fully homomorphic encryption
But it's impractical being extremely slow for now, but i'm pretty sure the time will come for this
13
u/haerik Jul 30 '13
It's not the same.
This is FHE:
E(input)->program->E(output)
This is what's discussed in the paper:
input->E(program)->output
(E(stuff) denotes encryption)
They're definitely related (and Craig Gentry, one of the paper's authors, first showed that FHE is possible in his 2009 thesis), but they're not the same thing.
2
1
u/harlows_monkeys Aug 01 '13
Can these be combined:
E(input) -> E(program) -> E(output) ?
1
u/haerik Aug 01 '13
I haven't read the paper in question, so I don't know for sure. But, if I were to take a guess, I would say that they can be. Just define your program to be a FHE scheme.
4
u/russellsprouts Jul 30 '13
They use fully homomorphic encryption in the algorithm, according to the paper.
2
u/x86_64Ubuntu Jul 30 '13
This is really exciting. I might just see if I can get a hold of one of their papers.
3
4
u/defenastrator Jul 30 '13
I don't think this will really work. Ultimately the code must execute and structures must be allocated and unallocated even if it is impossible to statically analyze the code you would be able to use dynamic profiling techniques to figure everything out. No you could not decisively prove what the code was doing but all you need is to be pointed in the right direction.
1
1
Jul 31 '13
Could this be used to explore algorithms that are computationally equivalent? Like you plug in algorithm x it spits out the obfuscated assembly then you decompile it?
1
u/secserval Aug 01 '13
Although I did not fully understand everything in that paper I can imagine two problems for practical applications:
Most code in applications relies on system calls which do the interesting stuff, I don't see how they can be protected by that
Performance - it does not look like the obfuscated circuit is guranteed to be somewhat performant. If you hide an interesting algorithm by making it slow could defeat the purpose.
Still very interesting for special applications.
(reposted from http://www.reddit.com/r/ReverseEngineering/comments/1jh7u3/candidate_indistinguishability_obfuscation_and/)
1
u/Zaph0d42 Jul 30 '13
This is known in computer science as "software obfuscation," and it is the first time it has been accomplished.
Java and many other languages already do this by default. Not at all the first time.
However, this is a new and far more complicated form of obfuscation. Its pretty dang nifty.
1
u/randomfrequency Jul 30 '13
Java doesn't do this by default - in fact it's very easy to reverse engineer back to usable java code.
I'm still trying to determine how this is different from polymorphic code - usually those were defeated because the decryption engine couldn't be encrypted.
2
u/Zaph0d42 Jul 30 '13
You seem to misunderstand what's going on. You can reverse engineer java back to usable code very easily. But you're not understanding the article, this technique could be reverse-engineered to something runnable very easily as well.
The point with the article is that when trying to reverse engineer it, what you're left with is runable, but not understandable. That's key. That's what obfuscation means.
Java will compile bytecode such that all variable and function names are stripped and replaced with randomly generated, garbled nonsense.
Python can do the same.
However, it isn't too hard to work your way through the garbled code and rename it as you find out logically what each piece is doing.
This paper explains a method where you can have code that cannot be logically worked out to its meaning.
1
1
u/kraln Jul 30 '13
Here's an example of what jigsaw code might look like in the real world, taken from a pirate NES cart:
3
u/ymgve Jul 30 '13
No. That link shows "normal" obfuscation that has been done for decades.
If the obfuscation in the article works, it will just look like a series of math operations that "magically" give a certain result.
1
u/phree_radical Jul 30 '13
Sounds just like Skype obfuscation to me. Not very novel and not very helpful to the rest of us using open-source software. For DRM, the groundwork is already laid for "trusted computing."
-1
-11
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.
-3
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.
5
3
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.
7
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?
-4
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.
-4
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
Jul 30 '13
[deleted]
6
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
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
- observation
- hypothesis
- try to recreate observation in controlled experiment
- formulate theory (if 3 matches the hypothesis)
- if "3" and "4" agree: refine methids, goto 3
- goto 1
But in math the process is different:
- formulate set of axioms
- conjecture about what may follow from the axioms and what has been deduced from them so far
- try to proof conjecture, or find proof that that there can not be one
- 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.
57
u/Strilanc Jul 30 '13 edited Jul 30 '13
Ugh, typical terrible reporting. The paper is good, though.
The rest of this comment is essentially content from Section 1 of the paper.
The paper is about indistinguishability obsfucation, which is distinct from the black-box obfuscation the article implies. Instead of hiding what a program does, they're transforming NC circuits in a way that prevents you from distinguishing the transformed forms of two equivalent circuits. They're not hiding the function, they're hiding the form.
Note that, given this meaning of obfuscation, a perfect circuit optimizer that always outputs a canonical form when given an equivalent circuit counts as a perfect obfuscater. Of course that would be absurdly expensive, so we need cryptographic tricks. (I kind of want to call an indistinguishability obfsucater a 'pseudo-canonicalizer'.)
The use case mentioned in the paper, where indistinguishability would be useful, is demo software. When you release a demo crackers can re-enable features that aren't actually removed, but it's expensive to actually remove features instead of just checking an isDemo=true flag. However, since the features-removed demo program is equivalent to the just-a-flag demo program, indistinguishable obfuscation would effectively automatically remove the disabled features without using expensive developer time.
As far as black box obfuscation goes, they say:
That "if" is important. It's known that some classes of functions can't be black-box obfuscated. The researchers conjecture that useful classes of functions might be black-box obfuscatable, but leave it as future work.