3 ms·

I 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 go

I 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 ago
Maybe 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 ago
  The 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?
  - MauranKilom 6y ago
    You only need to prove that the other program is possible, you don't need to actually write it (or even know how to write it). In other words, such a proof can even be non-constructive.
hansvm 6y ago
> If it is not needed, flow analysis, tree shaking and const evaluation could get rid of it. That's harder than it sounds. You can construct simple, iterative programs like `while(f(i++)){} return password;` whose behavior depends on hard problems like the Riemann Hypothesis (or easier problems which automated theorem provers still struggle with). Tree-shaking will be unfruitful, but if you can otherwise prove that an equivalent program exists that doesn't leak the password then iO gives an implementation. One interesting additional property is that you don't need to come up with the program which doesn't leak a password; you just need to prove that one exists, which potentially might be substantially easier.

MauranKilom 6y ago

Maybe 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 ago
The 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?
- MauranKilom 6y ago
  You only need to prove that the other program is possible, you don't need to actually write it (or even know how to write it). In other words, such a proof can even be non-constructive.

hansvm 6y ago

> If it is not needed, flow analysis, tree shaking and const evaluation could get rid of it. That's harder than it sounds. You can construct simple, iterative programs like `while(f(i++)){} return password;` whose behavior depends on hard problems like the Riemann Hypothesis (or easier problems which automated theorem provers still struggle with). Tree-shaking will be unfruitful, but if you can otherwise prove that an equivalent program exists that doesn't leak the password then iO gives an implementation. One interesting additional property is that you don't need to come up with the program which doesn't leak a password; you just need to prove that one exists, which potentially might be substantially easier.