9
$\begingroup$

Cryptographic Obfuscation is a technique that allows one to obfuscate source code in a secure way (as opposed to insecurely mangling it into spaghetti code.) For example, here is a way to protect a piece of data with a password:

cipher_text = obfuscate("\key -> if input == SYMETRIC_KEY
then return \"Launch code is 7205872\" else return \"No launch codes for you!\"")

Or here is a public key cryptography scheme:

public_key = obfuscate( "\input -> obfuscate(\" \key -> if key == PRIVATE_KEY
then return " ++ input ++ " else return \\\"You do not have the public key!\\\")" )

My question is, what is the state of this technology? Is it available in any programming languages yet? (I provided my code samples in a haskell-like language, since haskell is very similar to lambda calculus. Indeed, GHC compiles Haskell into lambda calculus as an intermediate step. It is therefore likely that a language like Haskell, or perhaps a lisp, would be the first for which it is available.)

NOTE: I am not talking traditional obfusication of cryptographic programs, but cryptographic obfusication techniques.

$\endgroup$

migrated from security.stackexchange.com Sep 2 '15 at 20:18

This question came from our site for information security professionals.

  • $\begingroup$ "Obfusicated" and "secure" are a little contradictive. $\endgroup$ – John Sep 2 '15 at 1:30
  • 2
    $\begingroup$ @John This is cryptographic obfusication. It isn't about hiding your algorithms but gluing your secrets to them. $\endgroup$ – PyRulez Sep 2 '15 at 1:32
  • $\begingroup$ SYMETRIC_KEY should be replaced with SYMMETRIC_KEY, and "public key!" should be replaced with "private key!". $\endgroup$ – user991 Sep 2 '15 at 14:56
  • $\begingroup$ Intel SGX can provide decent obfuscation, although "only" hardware-enforced. $\endgroup$ – SEJPM Sep 2 '15 at 15:50
  • 2
    $\begingroup$ One "state" of the technology is that DARPA is spending lots of money on it. See SAFEWARE. My guess is that it is changing pretty rapidly. $\endgroup$ – mikeazo Sep 2 '15 at 19:40
7
$\begingroup$

This is really an ongoing area of research in the cryptographic community. So, no, I don't think anything of the sort is available in any programming languages. The DARPA SAFEWARE program suggests that a lot of research money is being put into the area and will give you a feel for some of the topic areas that the community is working on.

Matt Green's post you linked to provides a lot of good background material, but being a year old is outdated somewhat.

A recent survey paper goes over the current state, open problems, etc.

Here are some relevant quotes on the state of the technology:

Scope

Learnable programs, i.e. the source code of which can be reconstructed by just executing it on different inputs, are clearly not interesting for obfuscation, although, most of the interesting programs are not learnable and the range of potential applications is extremely wide.

Efficiency

The most complex function that they (Apon et al., in Implementing Cryptographic Program Obfuscation) obfuscated was a 16-bit point function containing 15 and gates. The process took 9 hours and resulted in an obfuscated program of 31.1 GB size, the evaluation of which on a single input takes around 3.3 hours on a machine with 32 cores and 244 GB RAM.

Dan Bernstein, Andreas Hülsing, Tanja Lange and Ruben Niederhagen broke Apon et al.'s scheme in 19 min on a cluster of 21 PCs. Section 3 of their paper contains some (partially quite obvious) optimizations to get a speed-up of about 50 for running the obfuscated program.

I'm making this a community wiki post so that others can updated it more easily as new results come out. This is a rapidly changing field in cryptography.

$\endgroup$
  • $\begingroup$ Darpa seems a little narrow sighted as to the use of this tech. You can implement a ton of cryptography with little effort once this works (and then you have only one thing that you have to worry about.) All they care about is protecting IP. Not that this detracts from the answer at all, it's just that Darpa is dumb. $\endgroup$ – PyRulez Sep 3 '15 at 1:54
  • 1
    $\begingroup$ @PyRulez the good news is the (academic) researchers involved will be doing general/generic stuff, so all that other cool stuff will be greatly enhanced as an added bonus. $\endgroup$ – mikeazo Sep 3 '15 at 11:46
3
$\begingroup$

Currently there is no programming language (that I know of) having such features. It still seems to be a research topic.

There are some reasons why I believe there will likely never be "secure obfuscation" (where obfuscation means the program runs out-of-the-box and no user input such as a key is necessary)

  1. The program needs to be executable. This means that even if somebody had a magic trick at hand to obscure the way the program works, at some point it is analyzable. At this point I'd say your examples are well broken. The key is there in plaintext.

  2. Even with the argument Mr. Green used, not storing the key but rather a hash with salt and pepper, I'd argue that it is not secure. Because secure would imply that we do not get any advance by analyzing it and would have no ability to circumvent it. But we do. Simplest example would be decompile, analyze, modify code, recompile and the password check is gone and the rest is still usable. That is pretty similar to the bad idea of client side user authentication in JavaScript. Now you might argue that I did not in fact learn the secret password, correct I didn't, but that password is not the program, so basically you obfuscated nothing and you still rely on well known cryptography.

  3. This topic is theoretical. There might be a lot of very intelligent ideas and brilliant minds behind this research, but I dare to say that the way Mr. Green presents these ideas they are impractical (regarding his interpretation for obscuring programs). I strongly doubt that "indistinguishability obfuscation" is realistic for the purpose, because either, if it actually works as proposed, would likely kill any performance and thus making it highly unattractive for any company or not applicable on actual computers as there could be more attack vectors and it may not satisfy the security requirements. This is the general notion I get on the topic, as all these proves require a specific model and certain assumptions which may or may not hold on a real machine.

You may be able to obfuscate parts in certain situation, but that does not mean you can protect it from anybody under all circumstances.

Please note that I do not want to state that Mr. Green does not know what he is writing about, but rather take a skeptical look at his article. He likely knows more about the topic than I do.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – mikeazo Sep 4 '15 at 0:51
2
$\begingroup$

I'm not an expert in code obfuscation, but two things jump out at me in reading that article:

  1. They don't seem to have a definition for what "securely obfuscate" means. What they do have is abstract and built on top of assumptions that probably won't hold in the real-world. [*]

  2. Nowhere in that article is anybody proposing a solution. It reads more like "if a secure obfuscator ever exists, it might have some of these properties".

  3. Neither that article, or the source paper by Amit Sahai et. al address the issue that for a program to be executable, it must contain everything that it needs to de-obfuscate itself into machine code, which means that with enough effort, reverse engineers can do the same. So the whole idea of un-reverse-engineerable-yet-executable code seems like a bit questionable. [**]

These points put this research into the early phases of mathematical dreamland, I wouldn't expect to see it in Haskell or Lisp any time soon.


Matthew Green's section starting with "We can obfuscate some things!" basically says that it's possible to architect code such that the secrets can't be retrieved: simply don't put the secrets in the code, put hashes of the secrets instead, or some other trick.

If I paraphrase your question as:

Is there a compiler that will take badly designed code and make it secure?

No, no there is not. And nobody is suggesting that there will be.


Expanding on my thoughts:

  1. [*] The article by Matthew Green defines the problem as:

Alice should not get any more information from seeing the obfuscated program

but quickly admits that:

One thing you may have noticed is that the user Alice who views the obfuscated program truly does learn something more ... the user who got the obfuscated program still has a copy of the obfuscated program.

Similarly, in the abstract of the paper by Amit Sahai et. al they state:

In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible.

  1. [**] It's possible that under some strict conditions we could obtain this un-reverse-engineerability that we want, for example if you ship your software inside a FIPS 140-2 Hardware Crypto Module which will self-destruct if it detects tampering, or if operating systems / motherboards start offering hardware obfuscation support (I have no idea what this would look like, but I won't rule it out). But the idea of a Haskell compiler that will allow your source code to execute but stay obfuscated against an arbitrary attacker on arbitrary hardware seems unlikely.
$\endgroup$
  • 2
    $\begingroup$ A lot of your criticisms of the article are actually result of it being an open area of research. Research is still developing the definition of what "securely obfuscate" means. Researchers have shown how some notions fail (the Barak paper), given some other definitions (indistinguishability obfuscation or IO), exploring how IO can actually be constructed, exploring what IO means in practice, etc. $\endgroup$ – mikeazo Sep 3 '15 at 14:46
  • 2
    $\begingroup$ Also, I don't think the question is "how do you take badly designed code and make it secure". I think the question is "how do you take code with sensitive information embedded in it and make it computationally difficult to extract that sensitive information, yet still run the code". $\endgroup$ – mikeazo Sep 3 '15 at 14:48
  • 1
    $\begingroup$ The question isn't as precise as I'd like, but the line Is it available in any programming languages yet? implies to me that the OP is putting onus on the language to give security, rather than on his own design. The idea of being careful about what crypto material you embed in the executable doesn't require anything special from the language. There's also the question of what strength of secure the OP is intending. I'm assuming they meant "mathematically secure" rather than "time-consuming". $\endgroup$ – Mike Ounsworth Sep 3 '15 at 14:56
  • $\begingroup$ Your point number 3) is exactly the crucial point where I don't see how any of the research are solving this problem. They are of course exploring very interesting areas but as far as I can see they are not practical in the sense of usage OP is asking about. $\endgroup$ – John Sep 3 '15 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.