3 ms·
I'm no crypto expert and trying to follow along, but can't make this leap: > But iO is stronger than it sounds. For example, suppose you have a program that ca
by karmakaze 6y ago
I'm no crypto expert and trying to follow along, but can't make this leap:
> But iO is stronger than it sounds. For example, suppose you have a program that carries out some task related to your bank account, but the program contains your unencrypted password, making you vulnerable to anyone who gets hold of the program. Then — as long as there is some program out there that could perform the same task while keeping your password hidden — an indistinguishability obfuscator will be strong enough to successfully mask the password. After all, if it didn’t, then if you put both programs through the obfuscator, you’d be able to tell which obfuscated version came from your original program.
Why does existence of another mask the secret? Even if you couldn't distinguish the programs, couldn't you just try both possible secrets?
- MauranKilom 6y agoSuppose there exist two programs that do the same task, with the following properties: - Knowing program A allows an attacker to recover your password. - Program B does not contain any information about your password. Eve knows that these programs exist and that they have these properties. Eve is now given two obfuscated programs O1 and O2. They were produced by applying iO to A and B, but Eve knows neither A, B nor how O1 and O2 map to O(A) and O(B). If it were possible for Eve to somehow obtain your password from, say (without loss of generality), O1 in any way, then Eve could deduce that O1 must be O(A). It could not be O(B) because neither O nor B contain information about your password. Since we assert that indistinguishable obfuscation makes it impossible to draw this kind of conclusion, it must be impossible to obtain your password from O(A) if B exists.
- laszlokorte 6y agoI know nothing about the whole topic but could you explain: Why does any of those programs contain the password anyway if it is not needed for achieving the goal? If it is not needed, flow analysis, tree shaking and const evaluation could get rid of it. If it is needed, how would the program not containing it achieve the goal?
- MauranKilom 6y agoMaybe the password is not the best example. I am also not an expert and just took it from the article. As someone explained elsethread: > iO gives you a circuit that is as hard to reverse engineer as the hardest circuit of a given size that computes the same function, but it doesn't give you a guarantee on how hard that actually is https://news.ycombinator.com/item?id=25048220 https://news.ycombinator.com/item?id=25048220 To answer your thoughts though: > If it is not needed, flow analysis, tree shaking and const evaluation coulg get rid of it. Those are methods you could try to apply, but there is no reason why this would be sufficient in the general case. > Why does any of those programs contain the password anyway if it is not needed for achieving the goal? Maybe the problem your program is trying to solve is significantly easier given the knowledge of a secret. As long as you know that it's possible (but potentially harder) to solve the same problem without the secret, with iO you can distribute your obfuscated binary and nobody can recover the secret. For example (if I understand correctly), if your secret program contained an oracle to reverse SHA256 hashes[0], then applying iO to it you could be sure that nobody can recover this secret oracle, because applying iO to a different program that uses brute-force search should yield an indistinguishable obfuscated program. I doubt that's how it actually works (because oracle and brute force are probably not the same "circuit hardness"), but I hope you see the point. [0]before someone complains about lack of bijectivity, read this as "find the smallest integer/bitstring that has the same hash"
- Udik 6y agoThe pre-requisite is that there are at least two possible implementations of the same program- this seems to imply that for every possible input, program A and program B must have the exact same output. Then, it becomes impossible to tell whether the obfuscated code comes from program A or program B. Did I understand this correctly? But this in general seems relevant only for algorithms- two algorithms can produce, provably, the same output for each of their inputs, one being better than the other in terms of performance. Fine. But then the performance of the encrypted version could actually point to the used source code, so unless it's obfuscated away it still can be used to determine the origin of the obfuscated code. But then if the performance is also obfuscated, what reasons are left to encrypt the code?