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

11–20 of 145 posts

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

#11

Post by astrange »

tptacek wrote: post #5
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…

Isn't that where we're already at with ML classifiers?

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

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

#12

Post by Animats »

dataflow wrote: post #3
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…

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, compute an input which yields them) by trying all the input patterns.. There's no undecidability and no halting problem. There's just difficulty. "Difficult" here means there's no way easier than trying all the patterns. This is the same property sound cryptosystems are supposed to have - there's no easier way than trying all the keys.

Whether this result can be extended to programs with iteration I'm not sure. The paper doesn't seem to mention iteration or storage.

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

#13

Post by hgsgm »

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…

Obfuscation is itself a malware signature.

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

#14

Post by Animats »

NoMoreNicksLeft wrote: post #6
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…

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.

> I think Saberhagen's Berserkers actually had this feature.

Yes. Code decoded other code, etc. So if the code wasn't running normally, it couldn't be analyzed. It was handwaving back then, but it may become real.

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

#15

Post by elefanten »

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…

Seems some of those cases (backdoors and classifiers) could be prevented by regulation and/or social convention (eg- don’t use programs/services obfuscated in this way).

The malware seems trickier. Maybe systems will need to require proof of unobfuscated source to run code?

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

#16

Post by sn_master »

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?

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

#17

Post by Hnaomyiph »

hgsgm wrote: post #13
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…

Obfuscation is itself a malware signature.

Until it’s standard practice by all companies to protect up under the guise of consumer protection with all closed sourced software.

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

#18

Post by scarmig »

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…

Can't finite iteration and recursion just be unrolled? And storage just considered another part of the input?

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

#20

Post by y7 »

hgsgm wrote: post #10

Trash title. > established the feasibility of mathematically rigorous software obfuscation from well-studied hardness conjectures

This is not about software obfuscation, this is about cryptographic indistinguishability obfuscation (iO). It's targeting a different problem -- software obfuscation is more about hiding program behavior, whereas iO is more useful for white box cryptography, like hiding an AES key.

Maybe you could obfuscate software eventually, but we don't have practical efficiency even for tiny circuits. It's a bit like saying how fully homomorphic encryption allows you to securely run "software" on someone else's computer: theoretically maybe yes, but in practice it's used within software to run very specific computations.

Post reply on HN