Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software | Hacker News Reader

Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software

newsroom.ucla.edu

123 pointsfdb46 comments

It's been interesting seeing this story submitted repeatedly over the past week or so, each time getting no traction, no attention, no comments, and no love. Nice to see it finally hit the front page.

The actual paper is here: http://eprint.iacr.org/2013/451.pdf

Here are some of the submissions of alternate write-ups of this story, in case you want to see if some other source gives more details:

https://news.ycombinator.com/item?id=6125268 (phys.org)

https://news.ycombinator.com/item?id=6126234 (sciencedaily.com)

https://news.ycombinator.com/item?id=6129664 (rdmag.com)

https://news.ycombinator.com/item?id=6132772 (ucla.edu)

You can read other submissions on HN about homomorphic encryption by following this search:

https://www.hnsearch.com/search#request/all&q=title%3A%28hom...

There are lots of them, too.

to save anyone else looking, all the reports seem to be generated from the same press release - there's no significant new info in any (compared to the link here) that i could see.

the paper is a monster :o(

Reads like a marketing junk to be honest. I don't doubt that they have invented something interesting, but this is not a way to announce it.

> This is known in computer science as "software obfuscation," and it is the first time it has been accomplished.

No, of course not. See Fravia, see skype.exe.

> "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"

A mystery? Is this edited for an O magazine? Again, Fravia, Skype, Carberp/bootkit.

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

Uhm, no? Again, see Skype that withstood reverse-engineering attempts for several years with its incremental decrypting loader and other tricks that it was stuffed with to the brim.

They're talking about an obfuscation that's provably strong - i.e. there is no way to de-obfuscate the code, not even in a million years.

You're talking about an obfuscation that's "good enough for the real world" - i.e. it will take a very skilled person several years to de-obfuscate.

Also, their result is very theoretic, and too slow to be deployed in the real world, at least for the next couple of years. See my other comment if you're interested.

BTW - I think by "mystery" they meant "open computational problem". Kind of a mystery if you think about it :-)

"there is no way to de-obfuscate the code, not even in a million years."

Perhaps you're just being hyperbolic, but can you qualify this statement? Is it not possible in a million years given today's technology (this seems unlikely, even the marketing material suggested 100 years)?

Or are you claiming there is mathematical proof that advances in computational power, a growing body of knowledge about de-obfuscation, etc., will not break this approach?

The latter - there is mathematical proof that advances in computational power, a growing body of knowledge about de-obfuscation, etc., will not break this approach.

Also, this is not "marketing material" - nobody is selling this technology, and likely nobody will in the foreseeable future. They're just trying to interest the general public in a major theoretical CS breakthrough.

I wasn't aware such a proof existed, that's very cool.

But it's certainly marketing material. They're selling UCLA's engineering department to potential students, potential sponsors, and the general public. That's not a bad thing. Universities would be stupid not to promote their brand and their professors' achievements.

Minor caveat: the proof says something along the lines of "to de-obfuscate this code, you must be able to find the prime factors of insanely huge numbers, and we assume no one knows how to do that". So it's a bit inaccurate to say that "no advancement will solve this".

My initial reaction was also "....Wtf? No..." This is just a mathematical function equivalent to Skype's RC4 obfuscation. You can reverse engineer it, it just takes a long, long time to undo it all and all the associated protocols.

That being said, having a unique method to encrypt every program so each one required an equivalently long period of reverse engineering would make it very costly to reverse engineer programs. But it would only make sense in terms of protecting new functions.

Protocols and other components that have to survive over multiple versions could not simply be re-obfuscated once they were cracked (or at least, it would serve no purpose). You'd have to change the protocol every time and make the previous one obsolete to new clients while still retaining backwards compatibility with old clients.

Protocols in general cannot be obfuscated directly with this technique. For the sake of simplicity, I will assume we are talking about network protocols. Because this encryption, by definition, does not change behavior, the program would send identical messages over the network, and you can still monitor these and reverse engineer the protocol like before. For the more general, but not formally defined, idea of obfuscation you would also be able to obfuscate the network traffic and other external stuff, because you can change the behavior without actually changing the behavior.

This is a press release written by someone in the university's PR department (essentially; I don't know exactly what UCLA technically calls it). If the faculty involved in the research were at all smart, they had as little to do with this writeup as possible (it's not important at all for their careers and, more important, their heavy involvement probably wouldn't make the release any more accurate).

The research was announced by the paper and by presentations at seminars and conferences. You are quoting and disputing marketing junk written by one of UCLA's media contacts. (It's still fine for HN to link to it, since most of us won't/can't read the original research).

Exactly. It's promo material to raise the profile of UCLA and its engineering department. Which is fine, but it shouldn't be considered objective, unbiased news.

Often, these releases will play up exciting potential applications, which in reality may still be completely infeasible. They downplay practical limitations and the theoretic nature of the work. This article is not particularly bad, in that regard.

My humble understanding is this is a very theoretical result, unlikely to result in unreversable malware, or improvements in the DRM near you.

Here's a brief summary (obviously, I might be missing a lot of things):

1. "They (researchers in 2001, some of which are authors of this new paper) showed that there exist unobfuscatable functions – a family of functions {f s } such that given any circuit that implements f s , an efficient procedure can extract the secret s; however, any efficient adversary given only black-box access to f s cannot guess even a single bit of s with non-negligible advantage."

That result still holds - one cannot obfuscate any function, and this is proven.

2. "indistinguishability obfuscation: An indistinguishability obfuscator iO for a class of circuits C guarantees that given two equivalent circuits C 1 and C 2 from the class, the two distribution of obfuscations iO(C 1 ) and iO(C 2 ) should be computationally indistinguishable."

Note that this works only for equivalent circuits.

3. "Using indistinguishability obfuscator for NC 1 together with any (leveled) fully homomorphic encryption (FHE) scheme with decryption in NC 1 (e.g. [Gen09b, BV11, BGV12, Bra12, GSW13]), we show how to obtain an indistinguishability obfuscator for all polynomial-size circuits".

Again, this is indistinguishability obfuscator, which works only for equivalent circuits. Also, FHE is very slow nowadays, AFAIK there are no actual deployments of that concept, because of the prohibitive slowness (e.g. a single AES encryption taking days).

4. "Using indistinguishability obfuscator for polynomial-size circuits, together with injective one-way functions, public-key encryption, and a novel variant of Sahai’s simulation-sound non-interactive zero knowledge [Sah99] proofs, we show how to obtain functional encryption schemes supporting all polynomial-size circuits."

This is awesome and sounds like it can obfuscate malware or be used to make actual DRM, but again, the indistinguishability obfuscator is likely so slow as to not be practical these days. Maybe in a few decades?

Obviously I'm not writing this to take anything away from this huge theoretical result - just saying this is likely not what other commenters think it is. And again, my reading of this is very possibly inaccurate.

Deleted comment

I think they can use this for game DRM, if the game can contact the vendor's server, and request a confirmation that this customer account purchased the game.

Nowadays, skilled reverse engineers can modify the game code and "skip over" the calling-home part. With obfuscated code, this isn't possible.

Yes but a non trivial amount of the app would need to be obfuscated. You wouldn't be able to just obfuscate the license validation code as the caller could then be modified to skip over that function call. If this really is as slow as it sounds like it is (still interesting though!) then it wouldn't be practical for game programming. The entire game would run like molasses.

You're right -- this is a great theoretical result, but it is hopelessly impractical for use today (just like FHE).

Also note that the security of the scheme itself is untested. There are a handful of hardness assumptions here that have withstood little scrutiny, including the ones inherited from FHE and multilinear maps.

So their use of FHM is a bit like someone saying - we could colonize Jupiter if we just get enough anti matter.

And how that could be used as a DRM - this is the part I don't get?

This isn't that far-fetched - I wouldn't bet my life that this technology will still be undeployed in, say, 50 years. Academic research is about those discoveries too - even everyday stuff that is now taken for granted, like memory garbage collection, was considered impractical in the beginning.

Regarding DRM: "In Functional Encryption, ciphertexts encrypt inputs x and keys are issued for strings y. The striking feature of this system is that using the key SK y to decrypt a ciphertext CT x = Enc(x), yields the value F(x,y) but does not reveal anything else about x".

You can take x to be the code of the computer game you wrote, and F to be a code simulator. This sounds like the type of DRM game manufacturers want.

Once again I cannot see how it can be used as DRM - what prevents from installing in a VM and sharing it around, writing a wrapper around the executable that intercepts system calls and just gives what it wants etc?

This is too complicated to answer in a forum post.

The general idea is that no number appears in the code as-is, instead all numbers appear encrypted. You have to have a way to do "encrypted multiplication" - take two encrypted numbers, and get the encryption of their multiplication, without decrypting them in the process. Also for addition. This is called fully homomorphic encryption (finally discovered several years ago, by one of the authors of this paper). This paper builds upon that result.

Edit: also, see here for a simpler technique that seems to work:

https://news.ycombinator.com/item?id=6160742

Maybe I'm being naive (so please correct me if I'm wrong), but isn't this a dream-come-true for malware authors?

How so? Would there be no way to 'fight fire with fire' agains said malware, also, though?

Amazing, an article actually links to a research paper! What the paper is claiming is to have invented a indistinguishably obfuscater. This means that for a program X, you can consider the set of all source codes (of equal size) which generate a program with equivalent behavior to X. The obfuscater can be used to draw a function from this set, without revealing anything about the original source code. As the research paper mentions, although this meets the technical definition of best possible obfuscation, it is not necessarily good obfuscation. For example, if the obfuscater generates the most human-readable version of the input, then it would still qualify, as it reveals nothing about the original source.

The bigger problem with using this encrypt software is that software is over specified. Every external call your system makes, whether or not it actually does anything, is still considered part of the behavior of the program, and would therefore leak information about the structure of your program.

While this is defiantly much stronger than many previous obfuscation techniques, in order for it to be most effective you would need to very strongly keep all side-effect generating code separate as isolated as possible.

EDIT: From the paper: "Now that we have constructed an indistinguishability obfuscator, we are faced with the question: what good is an indistinguishability obfuscator? The definition of indistinguishability obfuscation does not make clear what, if anything, an indistinguishability obfuscator actually hides about a circuit. In particular, if the circuit being obfuscated was already in an obvious canonical form, then we know that the indistinguisha- bility obfuscator would not need to hide anything...we will use indistinguishability obfuscation by constructing circuits that inherently have multiple equivalent forms"

Also, the application to software obfuscation is largely an afterthought in the paper. And I don't see any analysis of the efficiency of software generated by this, so my guess would be that this is infeasible to use for obfuscation.

I quite like this - nothing is going to stop companies wanting to secure their code on customers' machines, and this is at least an elegant way to do it.

I do see problems though, e.g. people trying to make malware could use this very effectively: make a small pointless change, reencrypt, repeat, you then have a pseudo-unique malware signature across as many PCs as you can reach, so antivirus is useless.

Wouldn't this be easily solved by behavioural analysis? I'm not even sure what AVs do these days but I'm sure at least one sandboxes all executables for a while to see if they do anything suspicious before letting them run normally.

The re-encrypted malware would presumably make the same system and library calls in the same order - you don't need to know what the code looks like, just how it behaves.

As far as I can tell this method presents the same problem to signature detection as randomly inserting noise into code caves in the binary. The real target of this obfuscation is making reverse engineers lives difficult.

You don't even need to change the source, you just use a different key.

A different salt might be another way to phrase it.

I was imagining a random unused string somewhere in the code / random uncalled function. If you use an encryption key to actually generate the obfuscated program (I wasn't sure the article was saying you did,) this is clearly not required.

My naive understanding is this approach is that there will be clear units that do small bits of work. With a tracing framework and some analysis, like that recently presented at BH [1], I wonder if blocks of code could be extracted to remove some of the obfuscation - if the blocks are meaningful (or can be simplified).

Does anyone have any ideas if this sort of analysis looks feasible in response to this kind of obfuscation?

[1] : [PDF] - https://media.blackhat.com/us-13/US-13-Raber-Virtual-Deobfus...

The abstract of the paper is far more informative that then article. Functional encryption allows to decrypt a ciphertext c with a function (there can be many) f and get F(c), without revealing anything else about c.

This was previously doable where F was public in a way that could be plausibly efficient. This was an interesting result because it might lead to things like efficient searchable encryption without using very slow fully homomorphic encryption(FHE). A lot of these applications, however required F to be obfuscated.

This paper achieves hiding f, for a somewhat weak notion of obfuscation, and more crucially, by using fully homomorphic encryption(FHE). Given that FHE is effectively (very really but very inefficient) cryptographic pixie dust, it's not too surprising you can do this. However, for a lot of the applications for functional encryption, you could do int with FHE in other ways.

I have a hard time figuring this out. If the code executes, then it means the processor reads instructions. Surely there is some way to access those instructions?

The same results can be derived from different instructions. By simplifying; you can perform multiplication by repeated addition, or combinations of both, or even more clever tricks which would hardly make the original intent of simply making a multiplication obvious.

Running the code in a simulator would give you the final output, but would do very little to explain how the code itself is working, which is what you usually are after.

Okay, so this is simply an advanced form of obfuscation. An hypothetical uberman can still reverse engineer it. I don't expect anyone to, but the article seems to claim that there is some mathematical impossibility to do so.

Read up on homomorphic encryption: http://en.wikipedia.org/wiki/Homomorphic_encryption

I wonder if this would hit software performance?

It's really hard for me to imagine that it wouldn't. No matter how you look at it, at the end of the day, it can't be putting the same machine code into memory, or an attacker would just look at that and disassemble it.

But cryptography is full of things that I wouldn't have imagined, so maybe?

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

Did this just effectively mission-kill all copyrights on algorithms?

An entertaining way to spend time on HN articles about theoretical work might be to provide a "practical" example.

My interpretation of the paper and the "state of the art" is that its previously possible to submit "bunchadata" "iamakey34335" and "clearance=T OR NOT fired=F" (edited) to a decryption algo and your key and boolean stuff mix together to decrypt the data. The point of the paper is its now possible to submit a more complicated program than just the boolean like "clearance_level+seniority_years>0x10".

The entertaining part of the discussion would be if I got the basic concepts right or wrong, not so entertaining to debate if the greater-than symbol was proven or other tiny details like that.

Do I understand that correctly that it allows writing Malbolge[1]-like programs easily for the owner of the key?

[1] http://en.wikipedia.org/wiki/Malbolge

Yeah, well, OS X has been using this system to encrypt loginwindow, Finder.app, Dock.app, and iTunes.app, so this doesn't seem like much to write home about.

does this mean that unbreakable DRM will now be possible?

Is there anything that prevents running such program in a VM?

No. This result says nothing about DRM.

No, but it does mean you could technically create a ridiculously more complicated scheme, which means they'll probably be more ways than ever to break it, dumb system design choices, etc. Also more patents will tie things up and create more artificial limits. (If I were more of a jerk, I'd probably be filing an internet era/style patent along the lines of "I now patent the XOR... in functional encryption") The net effect is probably slightly weaker DRM.

I read some of the paper. Maybe an intro before you even read the paper's intro would be a wikipedia article like this:

http://en.wikipedia.org/wiki/Functional_encryption

And a blog post about a similar problem that doesn't work from about a decade ago like this:

http://www.cs.princeton.edu/~boaz/Papers/obf_informal.html

The 2001 paper TLDR is something like, there exists at least some hash functions that can't be obfuscated. Don't flame me too hard, there's a reason the paper is longer than eleven words.

That probably gives enough background to understand the intro to the paper?

As you can see by list list of authors in the paper Boaz coauthored, Sahai has been involved in this for a long time and this has been researched and pondered for a long time.

Maybe this is way too gross of a summary of the paper, but if you think of how unix filesystem permission bit masks work, you can already do something of that complexity with crypto keys (basic boolean stuff) but the paper proves you can run more complicated "programs" in the crypto key (not just basic boolean, but access_level >= 5 or whatever).

Another relatively ancient crypto concept that you probably need as a background is at least an understanding of what SSSS can do. Maybe not how it works, but the idea that keys can be screwed around with other than just one unitary thing.

Being stuck with the analogy in head that a crypto key maps 1:1 with the idea of a physical tumbler lock key isn't helping too much... well maybe unless you start thinking about master keys and stuff like that.

Maybe another awful TLDR analogy, this time of the 2013 paper, is I can make at a system level a powered smartcard that executes arbitrary code to do all kinds of stuff with and around a key .... as per the paper at the algorithm level (not the system level) you could execute arbitrary code in the key.

Which brings us back to the original DRM topic that smartcards have not been all that successful in the crypto world (insert debate here) so being able to "do computin'" in an algorithm rather than a chunk of slightly tamper resistant hardware probably isn't going to be much different for the endusers. And it'll be a lovely tasty new patent minefield. So I wouldn't expect much if any DRM impact.

Reply on news.ycombinator.com