5 ms·
Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software
- 6d0debc071 13y agoDid this just effectively mission-kill all copyrights on algorithms?
- VMG 13y agoPDF: http://eprint.iacr.org/2013/451.pdf http://eprint.iacr.org/2013/451.pdf
- MarcScott 13y agoMaybe I'm being naive (so please correct me if I'm wrong), but isn't this a dream-come-true for malware authors?
- sarreph 13y agoHow so? Would there be no way to 'fight fire with fire' agains said malware, also, though?
- ColinWright 13y agoIt'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 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 https://news.ycombinator.com/item?id=6125268 (phys.org) https://news.ycombinator.com/item?id=6126234 https://news.ycombinator.com/item?id=6126234 (sciencedaily.com) https://news.ycombinator.com/item?id=6129664 https://news.ycombinator.com/item?id=6129664 (rdmag.com) https://news.ycombinator.com/item?id=6132772 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%28homomorphic+encryption%29&sortby=create_ts+desc&start=0 https://www.hnsearch.com/search#request/all&q=title%3A%28hom... There are lots of them, too.
- andrewcooke 13y agoto 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(
- tehwalrus 13y agoI 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.
- VMG 13y agoYou don't even need to change the source, you just use a different key.
- tehwalrus 13y agoI 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.
- VLM 13y agoA different salt might be another way to phrase it.
- rainforest 13y agoWouldn'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.
- rainforest 13y agoMy 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-Deobfuscator-A-DARPA-Cyber-Fast-Track-Funded-Effort-Slides.pdf https://media.blackhat.com/us-13/US-13-Raber-Virtual-Deobfus...
- jonahx 13y agodoes this mean that unbreakable DRM will now be possible?
- pornel 13y agoIs there anything that prevents running such program in a VM?
- VLM 13y agoNo, 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 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 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.
- farseer 13y agoI wonder if this would hit software performance?
- mistercow 13y agoIt'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?
- pornel 13y agoDo 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 http://en.wikipedia.org/wiki/Malbolge
- norswap 13y agoI 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?
- tenfingers 13y agoThe 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.
- norswap 13y agoOkay, 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.
- tjaerv 13y agoRead up on homomorphic encryption: http://en.wikipedia.org/wiki/Homomorphic_encryption http://en.wikipedia.org/wiki/Homomorphic_encryption
- huhtenberg 13y agoReads 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.
- peterwwillis 13y agoMy 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.
- gizmo686 13y agoProtocols 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.
- VLM 13y agoAn 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.
- Nimi 13y agoMy 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.
- venomsnake 13y agoSo 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?
- gizmo686 13y agoAmazing, 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.
- deleted 13y ago[deleted]
- anologwintermut 13y agoThe 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.
- kunai 13y agoYeah, 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.