New software obfuscation method - possible end to need for SW patents?

[40hz]

Here's an interesting announcement from UCLA.

Seems a researcher has developed a new complex software obfuscation method that goes beyond the way it's been done previously. Supposedly, this new methodology allows obscured code to be run just as easily as native code, but still remains extremely difficult or impossible to reverse engineer or analyse.

Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software
Software remains completely functional but impervious to reverse-engineering
By Matthew Chin July 29, 2013

UCLA computer science professor Amit Sahai and a team of researchers 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. This is known in computer science as "software obfuscation," and it is the first time it has been accomplished.

Sahai, who specializes in cryptography at UCLA's Henry Samueli School of Engineering and Applied Science, collaborated with Sanjam Garg, who recently earned his doctorate at UCLA and is now at IBM Research; Craig Gentry, Shai Halevi and Mariana Raykova of IBM Research; and Brent Waters, an assistant professor of computer science at the University of Texas at Austin. Garg worked with Sahai as a student when the research was done.  

Their peer-reviewed paper will be formally presented in October at the 54th annual IEEE Symposium on Foundations of Computer Science, one of the two most prominent conferences in the field of theoretical computer science. Sahai has also presented this research in recent invited talks at Stanford University and the Massachusetts Institute of Technology.

"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," Sahai said. "It's a question that a lot of companies have been interested in for a long time."  

According to Sahai, previously developed techniques for obfuscation presented only a "speed bump," forcing an attacker to spend some effort, perhaps a few days, trying to reverse-engineer the software. The new system, he said, puts up an "iron wall," making it impossible for an adversary to reverse-engineer the software without solving mathematical problems that take hundreds of years to work out on today's computers — a game-change in the field of cryptography.

The researchers said their mathematical obfuscation mechanism can be used to protect intellectual property by preventing the theft of new algorithms and by hiding the vulnerability a software patch is designed to repair when the patch is distributed.

"You write your software in a nice, reasonable, human-understandable way and then feed that software to our system," Sahai said. "It will output this mathematically transformed piece of software that would be equivalent in functionality, but when you look at it, you would have no idea what it's doing."

The key to this successful obfuscation mechanism is a new type of "multilinear jigsaw puzzle." Through this mechanism, attempts to find out why and how the software works will be thwarted with only a nonsensical jumble of numbers. <more>

I can't help but wonder if something like this could provide a strong argument for no longer granting patents on software? The expression of an idea (as opposed to the idea itself) is the only thing that is eligible for protection under a US patent. Might the fact you could completely mask and protect the expression of an idea (i.e the underlying code and functional design) be the proverbial "cheap technical fix" that finally eliminates the supposed justification to allow patenting computer code? Hard to say somebody stole your code when there's no way they could have seen it to begin with. All code becomes a "trade secret" in this scenario should this new methodology actually do what it claims it can.

[attach]

[Tinman57]

  First thing I thought about was how this was going to affect your computers performance.  I would think this would eat up a lot more CPU cycles, but then again, I'm no programmer. 

[Renegade]

They seem to be using language differently than the rest of the world. "Obfuscation" is not encryption. Software obfuscation, if you ask anyone else, is simple symbol replacement e.g.:

Code: (csharp)

int years, months, days;

And obfuscated:

Code: (csharp)

int a, b, c;

However, it does sound really good.

[40hz]

They seem to be using language differently than the rest of the world. "Obfuscation" is not encryption.

Actually, from the sound of it, it sounds like something new is being tried. Possibly it's a hybrid approach...so maybe it doesn't matter whether you call it either encryption or obfuscation at this point?

I'm gonna have to wait to see Sahai's paper. (And hope I understand some of it when I do. )

@Ren - I saw this in an abstract about software obfuscation (emphasis added):

Program obfuscation is a semantic-preserving transformation aimed at bringing a program into such a form, which impedes the understanding of its algorithm and data structures or prevents extracting of some valuable information from the text of a program. Since obfuscation could find wide use in computer security, information hiding and cryptography, security requirements to program obfuscators became a major focus of interests for pioneers of theory of software obfuscation. In this paper we also address the issue of defining security of program obfuscation. We argue that requirements to obfuscation may be different and dependent on potential applications. Therefore, it makes sense to deal with a broad spectrum of security definitions for program obfuscation. In this paper we analyze five models for studying various aspects of obfuscation: “black box” model of total obfuscation, “grey box” model of total obfuscation, obfuscation for software protection, constant hiding, and predicate obfuscation.

Looks like there's a far from uniform definition of what constitutes software obfuscation between the security academic's and the programmer's worldview. (Never knew there were 5 defined models to accomplish it either - did you?) And that word 'transformation' is slippery since it could mean either a straight-up substitution or a more complex encryption process.

I often wish I had the time and mathematical background to really understand the subtleties found within this topic. Because this is one field where the "little details" seem to be everything.

[Renegade]

I've been using software obfuscation and encryption for about a decade, and this is the first time I've ever heard of "obfuscation" being used that way. Pretty much every single software protection program/solution out there makes a very hard distinction between obfuscation and encryption. They can be used together, but they are by no means similar in anything that they do - well, that is what I get from every vendor that I've ever looked at. (I'm over-simplifying, but other aspects of obfuscation are not significantly different in the abstract - they are all replacements.)

Many software obfuscators out there create an obfuscation map. It's a simple file that maps the obfuscated values to what the programmer wrote. So, you end up going from a, b, c back to year, month, day. It's a flat, linear transformation.

Here's a partial example of a map from a 1-off program that I wrote to do some data cleaning and normalization:

Code: (xml)

<map>
  <field>
      <signature>System.Windows.Forms.Label</signature>
      <name>lblEfwYear</name>
      <newname>k</newname>
  </field>
  <field>
      <signature>char[]</signature>
      <name>split</name>
      <newname>a</newname>
  </field>
  <field>
      <signature>System.Windows.Forms.TextBox</signature>
      <name>txtCountries</name>
      <newname>c</newname>
  </field>
  <field>
      <signature>System.Windows.Forms.TextBox</signature>
      <name>txtEfwYear</name>
      <newname>l</newname>
  </field>
  <field>
      <signature>System.Windows.Forms.TextBox</signature>
      <name>txtOriginal</name>
      <newname>e</newname>
  </field>
  <field>
      <signature>System.Windows.Forms.TextBox</signature>
      <name>txtTransformation</name>
      <newname>f</newname>
  </field>
  <field>
      <signature>System.Windows.Forms.TextBox</signature>
      <name>txtYears</name>
      <newname>d</newname>
  </field>
  <otherstuff />
  <method>
      <signature>void(object, System.EventArgs)</signature>
      <name>btnInsurance_Click</name>
      <newname>h</newname>
  </method>
  <method>
      <signature>void(object, System.EventArgs)</signature>
      <name>btnInsurance2_Click</name>
      <newname>c</newname>
  </method>
  <method>
      <signature>void(object, System.EventArgs)</signature>
      <name>btnSchool_Click</name>
      <newname>i</newname>
  </method>
  <method>
      <signature>void(object, System.EventArgs)</signature>
      <name>btnSchool2_Click</name>
      <newname>d</newname>
  </method>
  <method>
      <signature>void(bool)</signature>
      <name>Dispose</name>
  </method>
  <method>
      <signature>void(object, System.EventArgs)</signature>
      <name>Form1_Load</name>
      <newname>k</newname>
  </method>
  <method>
      <signature>void()</signature>
      <name>InitializeComponent</name>
      <newname>a</newname>
  </method>
</map>

Here's the abstract:

http://eprint.iacr.org/2013/451

Abstract: In this work, we study indistinguishability obfuscation and functional encryption for general circuits:

Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.

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.

Sigh... Looks like yet another case of reporters not knowing about what they're reporting on and not understanding the terminology. The researchers are using the language normally.

Some friends and people I know (mISVs) actually roll their own solutions. But they're really damn good at it. They've found that most commercial solutions were simply too easy to crack (they cracked them), and it was simply better to do it themselves. (Ballsy.) One fellow wrote up a portion of his approach called "partial key verification". It's interesting, but not what these guys are doing.

I do wonder how they get around the dumping problem though... Maybe I'll read on it later after I finish some work. (I'm goofing off at the moment. )

[Vurbal]

Wouldn't the need for those patents have to start before it could end?

Besides this wouldn't work for any of the patents I've read (and that's quite a few). "A bunch of vague stuff that's not new... do it with a computer " isn't code. Well it's code for bend over and grab your ankles but it's not computer code.

[xtabber]

"You write your software in a nice, reasonable, human-understandable way and then feed that software to our system," Sahai said. "It will output this mathematically transformed piece of software that would be equivalent in functionality, but when you look at it, you would have no idea what it's doing."

If the system works, this just means that the code is not retrievable from the program itself, but, the computer must still be able to follow the instructions in the code, or the program won't be of much use.  That means that the functionality of an "obfuscated" program can still be recreated by capturing what it does when it is executed or interpreted.

A bigger speed bump perhaps, but still just a speed bump.

[Renegade]

"You write your software in a nice, reasonable, human-understandable way and then feed that software to our system," Sahai said. "It will output this mathematically transformed piece of software that would be equivalent in functionality, but when you look at it, you would have no idea what it's doing."

Obfuscation is the lowest form of software protection. It's akin to the kind of cipher that you used to solve in grade 2 with simple letter substitution.

If the system works, this just means that the code is not retrievable from the program itself, but, the computer must still be able to follow the instructions in the code, or the program won't be of much use.  That means that the functionality of an "obfuscated" program can still be recreated by capturing what it does when it is executed or interpreted.

A bigger speed bump perhaps, but still just a speed bump.

It sounds like you're asking about the dumping problem for decrypted code. Is that right?

[xtabber]

It sounds like you're asking about the dumping problem for decrypted code. Is that right?

I don't believe static approaches like dump analysis are as effective for reverse-engineering as dynamic approaches like tracing program execution steps.  A program's gotta do what a program's gotta do.