TE
TechEcho
Home24h TopNewestBestAskShowJobs
GitHubTwitter
Home

TechEcho

A tech news platform built with Next.js, providing global tech news and discussions.

GitHubTwitter

Home

HomeNewestBestAskShowJobs

Resources

HackerNews APIOriginal HackerNewsNext.js

© 2025 TechEcho. All rights reserved.

Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software

123 pointsby fdbalmost 12 years ago

16 comments

ColinWrightalmost 12 years ago
It&#x27;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.<p>The actual paper is here: <a href="http://eprint.iacr.org/2013/451.pdf" rel="nofollow">http:&#x2F;&#x2F;eprint.iacr.org&#x2F;2013&#x2F;451.pdf</a><p>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:<p><a href="https://news.ycombinator.com/item?id=6125268" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=6125268</a> (phys.org)<p><a href="https://news.ycombinator.com/item?id=6126234" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=6126234</a> (sciencedaily.com)<p><a href="https://news.ycombinator.com/item?id=6129664" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=6129664</a> (rdmag.com)<p><a href="https://news.ycombinator.com/item?id=6132772" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=6132772</a> (ucla.edu)<p>You can read other submissions on HN about homomorphic encryption by following this search:<p><a href="https://www.hnsearch.com/search#request/all&amp;q=title%3A%28homomorphic+encryption%29&amp;sortby=create_ts+desc&amp;start=0" rel="nofollow">https:&#x2F;&#x2F;www.hnsearch.com&#x2F;search#request&#x2F;all&amp;q=title%3A%28hom...</a><p>There are lots of them, too.
评论 #6159935 未加载
huhtenbergalmost 12 years ago
Reads like a marketing junk to be honest. I don&#x27;t doubt that they have invented something interesting, but this is <i>not</i> a way to announce it.<p>&gt; <i>This is known in computer science as &quot;software obfuscation,&quot; and it is the first time it has been accomplished.</i><p>No, of course not. See Fravia, see skype.exe.<p>&gt; <i>&quot;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&quot;</i><p>A mystery? Is this edited for an O magazine? Again, Fravia, Skype, Carberp&#x2F;bootkit.<p>&gt; <i>According to Sahai, previously developed techniques for obfuscation presented only a &quot;speed bump,&quot; forcing an attacker to spend some effort, perhaps a few days, trying to reverse-engineer the software.</i><p>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.
评论 #6160115 未加载
评论 #6159862 未加载
评论 #6160676 未加载
评论 #6160757 未加载
Nimialmost 12 years ago
My humble understanding is this is a very theoretical result, unlikely to result in unreversable malware, or improvements in the DRM near you.<p>Here&#x27;s a brief summary (obviously, I might be missing a lot of things):<p>1. &quot;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.&quot;<p>That result still holds - one cannot obfuscate any function, and this is proven.<p>2. &quot;indistinguishability obfuscation: An indistinguishability obfuscator iO for a class of circuits C guarantees that given two <i>equivalent</i> 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.&quot;<p>Note that this works <i>only for equivalent circuits</i>.<p>3. &quot;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&quot;.<p>Again, this is indistinguishability obfuscator, which works only for equivalent circuits. Also, FHE is <i>very</i> slow nowadays, AFAIK there are no actual deployments of that concept, because of the prohibitive slowness (e.g. a single AES encryption taking days).<p>4. &quot;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.&quot;<p>This is awesome and sounds like it <i>can</i> 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?<p>Obviously I&#x27;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.
评论 #6160700 未加载
评论 #6160481 未加载
评论 #6160382 未加载
MarcScottalmost 12 years ago
Maybe I&#x27;m being naive (so please correct me if I&#x27;m wrong), but isn&#x27;t this a dream-come-true for malware authors?
评论 #6161712 未加载
gizmo686almost 12 years ago
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.<p>The bigger problem with using this encrypt software is that software is over specified. Every external call your system makes, whether or not it <i>actually</i> does anything, is still considered part of the behavior of the program, and would therefore leak information about the structure of your program.<p>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.<p>EDIT: From the paper: &quot;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&quot;<p>Also, the application to software obfuscation is largely an afterthought in the paper. And I don&#x27;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.
tehwalrusalmost 12 years ago
I quite like this - nothing is going to stop companies wanting to secure their code on customers&#x27; machines, and this is at least an elegant way to do it.<p>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.
评论 #6159369 未加载
评论 #6159318 未加载
rainforestalmost 12 years ago
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).<p>Does anyone have any ideas if this sort of analysis looks feasible in response to this kind of obfuscation?<p>[1] : [PDF] - <a href="https://media.blackhat.com/us-13/US-13-Raber-Virtual-Deobfuscator-A-DARPA-Cyber-Fast-Track-Funded-Effort-Slides.pdf" rel="nofollow">https:&#x2F;&#x2F;media.blackhat.com&#x2F;us-13&#x2F;US-13-Raber-Virtual-Deobfus...</a>
anologwintermutalmost 12 years ago
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.<p>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.<p>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&#x27;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.
norswapalmost 12 years ago
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?
评论 #6159733 未加载
farseeralmost 12 years ago
I wonder if this would hit software performance?
评论 #6160539 未加载
VMGalmost 12 years ago
PDF: <a href="http://eprint.iacr.org/2013/451.pdf" rel="nofollow">http:&#x2F;&#x2F;eprint.iacr.org&#x2F;2013&#x2F;451.pdf</a>
6d0debc071almost 12 years ago
Did this just effectively mission-kill all copyrights on algorithms?
VLMalmost 12 years ago
An entertaining way to spend time on HN articles about theoretical work might be to provide a &quot;practical&quot; example.<p>My interpretation of the paper and the &quot;state of the art&quot; is that its previously possible to submit &quot;bunchadata&quot; &quot;iamakey34335&quot; and &quot;clearance=T OR NOT fired=F&quot; (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 &quot;clearance_level+seniority_years&gt;0x10&quot;.<p>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.
pornelalmost 12 years ago
Do I understand that correctly that it allows writing Malbolge[1]-like programs easily for the owner of the key?<p>[1] <a href="http://en.wikipedia.org/wiki/Malbolge" rel="nofollow">http:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Malbolge</a>
kunaialmost 12 years ago
Yeah, well, OS X has been using this system to encrypt loginwindow, Finder.app, Dock.app, and iTunes.app, so this doesn&#x27;t seem like much to write home about.
jonahxalmost 12 years ago
does this mean that unbreakable DRM will now be possible?
评论 #6159539 未加载
评论 #6160135 未加载
评论 #6159778 未加载