5 ms·
That is a fascinating result. A remarkable mathematical achievement. And a nightmare. This thesis says that it's possible to obfuscate code in such a way that
by Animats 3y ago
That is a fascinating result. A remarkable mathematical achievement. And a nightmare.
This thesis says that it's possible to obfuscate code in such a way that there is a lower bound on the level of effort needed to de-obfuscate it. That lower bound can apparently be comparable to the level of effort required to break a cryptosystem.
So, coming soon, viruses and worms nobody can figure out. Code where no one can tell if it has a backdoor. ML classifiers where no one can be sure what they really do.
- dataflow 3y agoIs it just an existence proof or is it actually constructive? (I haven't read the dissertation.)
- vlovich123 3y agoLooks like constructive but my math knowledge is probably equivalent to a freshman’s at best.
- matthewdgreen 3y agoIt is not efficient enough that you need to worry about exciting developments using this scheme. But it’s a step towards more reasonable mathematical assumptions than previous constructions, assumptions that may actually be true. Give it a few more years and we might be able to use this stuff.
- Animats 3y agoI'm not sure. It seems to be applied to "circuits", which in this context seems to mean a one-way set of logic gates (such as AND, OR, NOT, NAND) which map a set of boolean inputs to a set of boolean outputs. In theory you can construct any finite digital function that way. It's a useful abstraction, like a Turing machine. Unlike a Turing machine, a circuit is finite. All circuits are "solveable" (given a outputs, compute an input which yields them) by trying all the input patterns.. There's no undecidability and no halting problem. There's just difficulty. "Difficult" here means there's no way easier than trying all the patterns. This is the same property sound cryptosystems are supposed to have - there's no easier way than trying all the keys. Whether this result can be extended to programs with iteration I'm not sure. The paper doesn't seem to mention iteration or storage.
- scarmig 3y agoCan't finite iteration and recursion just be unrolled? And storage just considered another part of the input?
- grayhatter 3y agoIn theory? Absolutely; unrolling a loop is exactly what it sounds like. Recursion is just a fancy loop. But there's a reason no one does that, and why no compilers emit that as code.
- User23 3y agoFancy in the sense of being a loop with an implicit stack. Or maybe just some registers if TCO. And yet the machines we can actually build are far closer to LBAs than TMs.
- jahewson 3y agoThis is how SMT solvers deal with bounded quantifiers.
- dmix 3y agoThe next question is why didn’t the high end shops spending a ton of money and recruiting effort on crypto and state malware like NSA .. or Russia(?) figure this out already or did they
- whatshisface 3y agoBecause figuring out what a worm does doesn't help if it has already done it, and for that matter they're supposed to remain undetected. Furthermore people already cannot tell whether code has backdoors, or what ML classifiers do for that matter. Unfortunately, the biggest industrial use case is making wi-fi routers that are absolutely impossible to install OpenWRT on, etc...
- whitemary 3y ago
- deleted 3y ago[deleted]
- Cyph0n 3y agoI’m sure DRM companies like Denuvo are having a field day.
- tptacek 3y agoIsn't that where we're already at with ML classifiers?
- astrange 3y agoWell, we know they're ML classifiers and they're not making syscalls. So there's obviously a limit to "we don't know what they do".
- tptacek 3y agoYou'd still know what syscalls a cryptographically obfuscated userland program was making.
- sbierwagen 3y agoIf it's a total black box, wouldn't the NOBUS thing to do would be to have some large key that it's watching input for that flips it into a malicious mode? If BB(6) took years to execute, how long would you have to spend feeding random input to a suspected-hostile 10000 symbol Turing machine (whose source code and state you can't examine) in a sandbox before you decided it was safe?
- rini17 3y agoEasy, have all executable segments read-only with none (or fixed) syscall instructions.
- astrange 3y agoThink it'd be a bit dangerous to let them make any though, unless you were single stepping.
- NoMoreNicksLeft 3y agoEven if the vendor is willing to provide source, you can't be sure that the binary matches. Nice. I think Saberhagen's Berserkers actually had this feature.
- Animats 3y ago> I think Saberhagen's Berserkers actually had this feature. Yes. Code decoded other code, etc. So if the code wasn't running normally, it couldn't be analyzed. It was handwaving back then, but it may become real.
- Tangurena2 3y agoIt was standard coding practices if you were selling games - to prevent people from hacking the license key stuff. Or by cheating software to prevent detection by anti-cheat software. One of the hooks built into Windows is "is a debugger connected" helps the virus/cheat code determine if it is "safe" to run or not.
- schoen 3y agoYou can be sure that it matches if the vendor (1) doesn't use an obfuscated binary, or (2) provides exact details of how the obfuscated binary was constructed (presumably including some kind of seed for the obfuscator).
- Tangurena2 3y agoThis was the point behind Reflections on Trusting Trust - you can't trust it. Unless you build the entire compiler/linker tool chain from source that you've already inspected. https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
- hgsgm 3y agoObfuscation is itself a malware signature.
- Hnaomyiph 3y agoUntil it’s standard practice by all companies to protect up under the guise of consumer protection with all closed sourced software.
- hulahoof 3y agolike that time sony gave everyone a rootkit: https://en.wikipedia.org/wiki/Sony_BMG_copy_protection_rootkit_scandal https://en.wikipedia.org/wiki/Sony_BMG_copy_protection_rootk...
- RockRobotRock 3y agosimilar to starforce for those that don't know: https://www.youtube.com/watch?v=p-wyIalhdPU https://www.youtube.com/watch?v=p-wyIalhdPU
- Vervious 3y agoI mean, the same argument has been applied to other cryptographic tools. Why encrypt your messages, unless you're sending something sketchy? Why obfuscate programs, unless you're hiding something? Yet I think the utility of encryption is well-demonstrated, and not just theoretical. It can be used by good people to defend against adversarial intent. And it may well be that obfuscation (in its most direct application) has the same effect. (e.g. companies sharing proprietary algorithms for you to run at home, without revealing the secret sauce; or me delegating computation to AWS without revealing secrets) Note that this is not why indistinguishability obfuscation (iO) is a crown jewel, here. Practically, iO is nowhere close to obfuscating anything larger than a tiny circuit. But it can still be useful to do things like obfuscate secret keys when designing cryptographic protocols. Theoretically, iO allows us to derive essentially every cryptographic primitive, which is why this paper is interesting, and why iO is called a crown jewel. And now, we can build iO for the first time from well-studied hardness assumptions.
- elefanten 3y agoSeems some of those cases (backdoors and classifiers) could be prevented by regulation and/or social convention (eg- don’t use programs/services obfuscated in this way). The malware seems trickier. Maybe systems will need to require proof of unobfuscated source to run code?
- deleted 3y ago[deleted]
- m463 3y agoCould you steal source code, obfuscate it, and sell it as your own?
- quickthrower2 3y agoDoes it run at the same speed as the original?
- omgwtfbyobbq 3y agoAcross the same universe of discourse.
- godelski 3y agoWouldn't this also be a field day for encryption maximalists? I'd imagine if all code were to be perfectly obscured then to the public it wouldn't matter, but many would demand for more open source and that'd be the only way to trust.
- amoss 3y agoAh, "code is law". Good luck with that.
- blurbleblurble 3y agoJust wait until the legislators catch wind of this.
- eru 3y agoJust don't trust that code, and don't run it? You should require positive proof that code does what you want. Similar to how eg Haskell's type systems doesn't have to solve the halting problem [0]: it just rejects some programs that would be ok, but don't conform to the type system. See also proof-carrying code. https://en.wikipedia.org/wiki/Proof-carrying_code https://en.wikipedia.org/wiki/Proof-carrying_code [0] Ok, unless you use undecidable instances or something like that.
- Attrecomet 3y ago> You should require positive proof that code does what you want. That's just saying you should only ever solve simple problems with your computer.
- eru 3y agoWhy? People have eg written proven-correct C compilers. And those things ain't 'simple'.
- ilyt 3y ago> Just don't trust that code, That's even harder problem to solve
- zamalek 3y agoAny program worth obfuscating is not worth trusting.
- twelve40 3y agoAmong other things, tons of desktop software and most mobile apps and even javascript you run from most websites is obfuscated. How is it possible to avoid that? Do you run 100% open source for everything with javascript disabled?
- bentcorner 3y ago
- krageon 3y ago> viruses and worms nobody can figure out Sandboxing and modeling interaction are still possible and useful, and is a large part of figuring out viruses and worms. That's not going away
- deleted 3y ago[deleted]
- stuckkeys 3y agoYeah pretty much. It is only going to get wilder in the ransomware scene. Good times ahead.
- DannyBee 3y agoWell, no. What you are worried about is VBB (roughly can i take a program a and obfuscate it in a way that you get no information about the original from the obfuscated version), which has been proven impossible. This is about indistinguishability, which is a form of obfuscation, but not the kind you are thinking about. This is really something like "If you have two programs a and b that compute the same function, it's possible to obfuscate them in a way that the resulting programs are indistinguishable from each other" So if program a is "bubble sort" and program b is "selection sort" (function here is the mathematical sense, so these compute the same function), obfuscation can make it so you can't tell them from each other, and you can't tell if the original program of what you are holding was bubble or selection . Roughly: VBB is the ability to take any program and make it indistinguishable from random. IO is the ability to take two programs that compute the same function and make them indistinguishable from each other. "compute the same function" is actually what makes it feasible :) The original use case was really trying to turn secret key systems into public key systems by hardwiring the secret key into the program and then obfuscating it. So an example use case today would be "every DVD decoding program has a different key but computes the same function, can you make them all indinguishtable and thus hide the key" or something like that.
- cs702 3y ago> The original use case was really trying to turn secret key systems into public key systems by hardwiring the secret key into the program and then obfuscating it. Wow, that definitely qualifies as a "crown jewel." I, for one, would not look forward to a future in which software running on my hardware is able to hide secrets, like one-off media encryption keys, from me!
- DannyBee 3y agoIn practice, as the thesis proves, you can use iO to generate a lot of things people care about in cryptography. I will go out on a limb and say you can use it to build almost everything interesting :) Now, it happens for a lot of those we don't need iO and iO may be impractical, but as a theoretical building block, it's quite nice. As for your concern, yes, this is now possible, at least in the sense that you do as good as is possible to do in making them computationally indistinguishable. This does not prevent you from attacking it in other ways :) Two things, good or bad depending on how you look at it: 1. You can prove iO is as least as good as the best possible obfuscation scheme that can ever exist. So whatever that enables you to do or not, it's the limit. 2. It also means you can get away with handing over less secrets, ensure better isolation, etc. The following things are possible with iO (trivially so), due to this paper: Adaptively secure succinct garbled RAM - which would let you hand secure databases to untrusted providers and not worry about it. Sender deniable encryption where you can't prove what the original plaintext was and various options are equally likely. Fully deniable interactive encryption where secrecy of communication is protected even if the parties are later coerced (or willingly bribed) to expose their entire internal states: plaintexts, keys and randomness. etc These are just some examples. Now, some of this, as I said, we know how to do already, some we don't. But this paper gives you iO as a building block that can do them without having to separately prove that it is as sound and secure as existing crypto systems are. Again, iO only provides computational indistinguishability, not other things, but it is a nice primitive.
- Tangurena2 3y agoWe already have code that obfuscates itself. And runs differently based on whether it is running in a debugger or not. This has been the cat & mouse game played by: virus writers vs anti-virus code. game hackers vs anti-cheat software. license checking code vs cheapskates. Stuxnet. > Code where no one can tell if it has a backdoor. Back in 1984, Ken Thompson wrote Reflections on Trusting Trust [0]. The short answer is "no, you can never ever tell if it has a backdoor. Ever." > The moral is obvious. You can't trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code. In demonstrating the possibility of this kind of attack, I picked on the C compiler. I could have picked on any program-handling program such as an assembler, a loader, or even hardware microcode. Back in the 90s, I was interested in hacking. The sort of hacking that starts with "this is the disassembler. Step one, hack the trial version of IDA Pro." It was fascinating at the time (and bores me now, my punishment for growing up, I guess) so I read & did lots of stuff like that. 0 - https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
- sacnoradhq 3y agoAutonomous, polymorphic malware utilizing secure computation to perform operations that aren't revealed to systems they infect. Seems like there is an opportunity for bot nets to perform computations, say BTC mining, in a completely sealed and zero-knowledge environment, which now may not even need a backdoor or are able to hide it perfectly.