Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

UCLA computer grad constructs “crown jewel of cryptography”

acm.org

Post reply on HN
Print view View original

41–50 of 145 posts

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

#41

Post by x-complexity »

Animats wrote: post #12
dataflow wrote: post #3

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…

IMO: Paranoid about the implications, slightly less worried about it applying in practice.

As shown by the DRM schemes used in modern games, this type of obfuscation comes at the cost of performance: Unless you want to compute a sensitive function at the user's end in an obfuscated manner, it'd be much simpler to just run that function on your end and optimize it in terms of running costs & performance.

Such a design would also runs counter to the everything-as-a-service model that companies are trending towards, as it places more power back at the user's end, even if the user can't decipher the obfuscated function's inner mechanisms. Such a design would reduce the need to phone home, and thus the need for EaaS.

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

#42

Post by [deleted] »

Animats wrote: 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…

[deleted]

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

#43

Post by whitemary »

whatshisface wrote: post #36
dmix wrote: post #31

Earlier quoted context omitted.

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

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

> people already cannot tell whether code has backdoors

I was feeling crazy after reading that.

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

#44

Post by jhanschoo »

Animats wrote: post #12
dataflow wrote: post #3

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…

A (polynomial-sized) circuit in this context is a sequence of DAGs whose nodes are binary logic gates where the nth DAG infers 1 output bit from n input bits, such that some polynomial bounds the size of the graphs of the sequence. See https://en.wikipedia.org/wiki/Circuit_complexity

The class of circuits in question is P/poly which includes BPP (which includes P, the class of polynomial-time programs). So the result is quite general, since most practical programs are in P.

For an introduction to complexity theory, see Arora, Barak (2009) (Draft available here https://theory.cs.princeton.edu/complexity/book.pdf ); same Barak that did the presentation "On the (Im)Possibility of Obfuscating Programs" (2001) mentioned in the abstract.

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

#45

Post by astrange »

tptacek wrote: post #22
astrange wrote: post #11

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

Think it'd be a bit dangerous to let them make any though, unless you were single stepping.

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

#46

Post by arsome »

sn_master wrote: post #16
vlovich123 wrote: post #7

If I’m reading Wikipedia [1] correctly, a program that does an AND of 32 booleans when obfuscated is 32 GiB. No indication of runtime overhead but something tells me it’s a large constant overhead (if I skimmed the paper correctly, the complexity class must be the same). [1] https://en.wikipedia.org/wiki/Indistinguishability_obfuscati...

But can it be compressed with something like UPX?

And can you tell where an operation begins and ends, for example, determine inputs and outputs?

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

#47

Post by m463 »

Animats wrote: 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…

Could you steal source code, obfuscate it, and sell it as your own?

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

#48

Post by foota »

I wonder how this compares to homomorphic encryption? If I understand correctly, I could give someone a computation with an embedded key that operates over encrypted data, and they wouldn't be able to decrypt the data other than for the computation I gave them, right?

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

#49

Post by noam_k »

foota wrote: post #48

I wonder how this compares to homomorphic encryption? If I understand correctly, I could give someone a computation with an embedded key that operates over encrypted data, and they wouldn't be able to decrypt the data other than for the computation I gave them, right?

I think it compares more to a One Time Program or Functional Encryption.

Homomorphic Encryption won't prevent you from decrypting other outputs (if you have a decryption key), and with Functional Encryption it's assumed both parties know the function being evaluated, so OTP is really the closest.

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

#50

Post by quickthrower2 »

m463 wrote: post #47
Animats wrote: 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…

Could you steal source code, obfuscate it, and sell it as your own?

Does it run at the same speed as the original?
Post reply on HN