Live data from Hacker News

UCLA computer grad constructs “crown jewel of cryptography”

acm.org

121–130 of 145 posts

Re: UCLA computer grad constructs “crown jewel of cryptography”

#121
post #119

Earlier quoted context omitted.

Well, 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…

> 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 !

In 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.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#122
post #89
post #83

Earlier quoted context omitted.

> Just don't trust that code, That's even harder problem to solve

Any program worth obfuscating is not worth trusting.

Among 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?

Re: UCLA computer grad constructs “crown jewel of cryptography”

#123
post #119

Earlier quoted context omitted.

> 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 !

In 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…

Thank you for taking the time to respond so thoroughly :-)

Everything you write makes sense to me -- though I had to lookup and skim Canetti and Holmgren's work to understand the bit about succint garbled RAM.

We live in interesting times!

Re: UCLA computer grad constructs “crown jewel of cryptography”

#125
post #69

The precise mathematical definition of obfuscation and what is considered obfuscation for an average software engineer are two very different things. In fact, the article is only about indistinguishability obfuscation. What is mostly discussed in this thread is the notion of virtual black box obfuscation (VBB). VBB has been proven to be impossible in the general case (see https://www.wisdom.weizmann.ac.il/~oded/PS/ob…

To try to make this concrete, if you have a program A that does bubble sort, and a program B that does selection sort: 1. VBB would be making it so you can't glean information about A or B by running VBB(A) or VBB(B) or examining them, for various definitions of "information". You can't tell A is a bubble sort at all, and you can't tell B is a selection sort at all. VBB is, as mentioned, impossible in the general cas…

[deleted]

Re: UCLA computer grad constructs “crown jewel of cryptography”

#126
post #89

Earlier quoted context omitted.

Any program worth obfuscating is not worth trusting.

Among 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?

Some people do take it that seriously: https://www.gnu.org/software/librejs/

Re: UCLA computer grad constructs “crown jewel of cryptography”

#127
post #69

The precise mathematical definition of obfuscation and what is considered obfuscation for an average software engineer are two very different things. In fact, the article is only about indistinguishability obfuscation. What is mostly discussed in this thread is the notion of virtual black box obfuscation (VBB). VBB has been proven to be impossible in the general case (see https://www.wisdom.weizmann.ac.il/~oded/PS/ob…

To try to make this concrete, if you have a program A that does bubble sort, and a program B that does selection sort: 1. VBB would be making it so you can't glean information about A or B by running VBB(A) or VBB(B) or examining them, for various definitions of "information". You can't tell A is a bubble sort at all, and you can't tell B is a selection sort at all. VBB is, as mentioned, impossible in the general cas…

[deleted]

Re: UCLA computer grad constructs “crown jewel of cryptography”

#128
post #13
post #2

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…

Obfuscation is itself a malware signature.

Sure but it's a very weak signal.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#129
post #84

Earlier quoted context omitted.

I 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)…

> I mean, the same argument has been applied to other cryptographic tools. Intent matters. > Why encrypt your messages, unless you're sending something sketchy? Because I am sending something private, I can't believe people bring this dumbass argument still, and even here. > Why obfuscate programs, unless you're hiding something? Why indeed. This one is the red flag, not message in your e-mail client being encrypted.…

You say the intent is different but don’t show why. What about obfuscation implies malicious intent? How come it doesn’t apply to encryption?

It can’t be about applications, because I can come up with a thousand applications for obfuscation with benign intent. Such as delegating private computation to AWS without Amazon learning my personal information.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#130
post #69

The precise mathematical definition of obfuscation and what is considered obfuscation for an average software engineer are two very different things. In fact, the article is only about indistinguishability obfuscation. What is mostly discussed in this thread is the notion of virtual black box obfuscation (VBB). VBB has been proven to be impossible in the general case (see https://www.wisdom.weizmann.ac.il/~oded/PS/ob…

To try to make this concrete, if you have a program A that does bubble sort, and a program B that does selection sort: 1. VBB would be making it so you can't glean information about A or B by running VBB(A) or VBB(B) or examining them, for various definitions of "information". You can't tell A is a bubble sort at all, and you can't tell B is a selection sort at all. VBB is, as mentioned, impossible in the general cas…

I'm kind of confused. I'm guessing this is a dumb question, but I'm obviously missing something. If a program is running bubble sort, and another is running selection sort... can't you just run them instruction-by-instruction to see which elements they swap? And deduce what they were based on that? Like if you have [4, 3, 2, 1], and the first swap the program does results in [1, 3, 2, 4], then it clearly wasn't bubble sort, right? What am I missing?
Post reply on HN