Earlier quoted context omitted.
Is it just an existence proof or is it actually constructive? (I haven't read the dissertation.)
I'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, co…
UCLA computer grad constructs “crown jewel of cryptography”
31–40 of 145 posts
Re: UCLA computer grad constructs “crown jewel of cryptography”
#32If mankind can't stomach 10% overhead to check array bounds and collect unused memory, what makes anybody think they can sell 1,000,000% overhead to make your DRM driver (and viruses) harder to reverse?
Re: UCLA computer grad constructs “crown jewel of cryptography”
#33That 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…
Even 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.
Re: UCLA computer grad constructs “crown jewel of cryptography”
#34That 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…
Obfuscation is itself a malware signature.
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.
Re: UCLA computer grad constructs “crown jewel of cryptography”
#35Earlier quoted context omitted.
Well, 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".
You'd still know what syscalls a cryptographically obfuscated userland program was making.
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?
Re: UCLA computer grad constructs “crown jewel of cryptography”
#36Earlier quoted context omitted.
I'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, co…
The 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
Unfortunately, the biggest industrial use case is making wi-fi routers that are absolutely impossible to install OpenWRT on, etc...
Re: UCLA computer grad constructs “crown jewel of cryptography”
#37> Program obfuscation would enable a host of useful applications: For instance, you could use an obfuscated program to delegate particular tasks within your bank or email accounts to other individuals, without worrying that someone could use the program in a way it wasn’t intended for or read off your account passwords (unless the program was designed to output them).
I relate this to cracking; run a program and watch the memory, see where the password is checked and edit the binary at that location to bypass. So this level obfuscation would make that impossible? Seems like magic honestly.
Re: UCLA computer grad constructs “crown jewel of cryptography”
#38Re: UCLA computer grad constructs “crown jewel of cryptography”
#39Re: UCLA computer grad constructs “crown jewel of cryptography”
#40DRM implementations already use code obfuscation heavily. Can someone with knowledge of the math clarify why this is a big deal? Why would it matter that there is mathematical proof that someone cannot figure out what the code is doing? How does it apply to crypto?
This work, on the other hand, shows a provably secure construction for obfuscation (assuming that some assumptions about the hardness of various well-studied mathematical problems are true). In other words, extracting a bitcoin secret key from an obfuscated algorithm is as hard as insert math problem here. (This is how all cryptography works; e.g. breaking RSA encryption is as hard as factoring large products of primes.) This paper is special because, for the first time, the hard math problem they use (to build the obfuscation) is "reasonable": they've been studied for decades, and no one knows how to break them. (Indeed, a lot of cryptography is built on top of the same assumptions/problems.)
Thus, we would be surprised if someone extracted our bitcoin secret key from our obfuscated program, because it means they solved some "thought-to-be-unsolvable" mathematical problem. This is a much nicer guarantee than the alternative, e.g. with current obfuscation, where we say "oh, it looks pretty random, let's stick my key in" and then trusting that no one will break it. (That's a lot of trust, when you might have a 100,000 Bitcoin at stake.)
Of course, none of this is really feasible; at best, we can securely obfuscate tiny circuits (in the present time). So the main utility is probably to hide keys and the such, not to obfuscate entire programs. This might enable better secure MPC schemes, NIZKs, etc. So I guess, per your question, it's also targeted towards a different use case.
Now, as to why theoretical cryptographers care about obfuscation in general: it's not so much about the direct application of obfuscating programs. (It's not obvious why obfuscation is more interesting than encryption, etc, from an applied point of view.) Instead, from a theoretical point of view, if we can build indistinguishability obfuscation, we can directly build public key encryption, non-interactive zero knowledge proofs, Multiparty computation, etc. etc. (assuming one-way functions). So really, this is a primitive that somehow connects all of the other primitives, which is why theoreticians think it is a big deal.