UCLA computer grad constructs “crown jewel of cryptography” • Hacker News Board

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

#111

Post by e12e » Thu, May 25, 2023, 2:53 PM UTC

DannyBee wrote: post #97

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

Ed: redundant - asked and answered in thread.

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

#112

Post by DannyBee » Thu, May 25, 2023, 3:23 PM UTC

e12e wrote: post #111

DannyBee wrote: post #97

Earlier quoted context omitted.

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…

Ed: redundant - asked and answered in thread.

Yeah, I probably should have collected an the pieces into a single reply. Right now the number of comments is small enough that it’s not hard to find though.

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

#113

Post by pxc » Thu, May 25, 2023, 3:25 PM UTC

Brotkrumen wrote: post #64

yjftsjthsd-h wrote: post #53

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? It's easy to argue that everyone has legitimate interest in hiding some things in data, but what would be a legitimate case for hiding things in code?

"This is a trade secret. We have not patented it, because it's so clever and valuable that it needs to be protected longer than a patent lasts"

That remains a fundamentally anti-social motivation...

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

#114

Post by KMag » Thu, May 25, 2023, 3:30 PM UTC

dmix wrote: post #31

Animats wrote: post #12

Earlier quoted context omitted.

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…

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

There are more efficient ways to hide malware from current scanners, and on the flip-side, the scanners that use heuristics/ML to classify the sequence of system calls made by the binary wouldn't be affected by this sort of obfuscation.

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

#115

Post by joelfried » Thu, May 25, 2023, 3:54 PM UTC

yjftsjthsd-h wrote: post #53

Vervious wrote: post #34

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. Why encrypt your messages, unless you're sending something sketchy? Why obfuscate programs, unless you're hiding something? It's easy to argue that everyone has legitimate interest in hiding some things in data, but what would be a legitimate case for hiding things in code?

Making it harder for bad actors to create malware would seem like one legitimate case.

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

#116

Post by Tangurena2 » Thu, May 25, 2023, 3:59 PM UTC

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…

We already have code that obfuscates itself. And runs differently based on whether it is running in a debugger or not. This has been the cat & mouse game played by:

virus writers vs anti-virus code.

game hackers vs anti-cheat software.

license checking code vs cheapskates.

Stuxnet.

> Code where no one can tell if it has a backdoor.

Back in 1984, Ken Thompson wrote Reflections on Trusting Trust [0]. The short answer is "no, you can never ever tell if it has a backdoor. Ever."

> The moral is obvious. You can't trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code. In demonstrating the possibility of this kind of attack, I picked on the C compiler. I could have picked on any program-handling program such as an assembler, a loader, or even hardware microcode.

Back in the 90s, I was interested in hacking. The sort of hacking that starts with "this is the disassembler. Step one, hack the trial version of IDA Pro." It was fascinating at the time (and bores me now, my punishment for growing up, I guess) so I read & did lots of stuff like that.

0 - https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...

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

#117

Post by Tangurena2 » Thu, May 25, 2023, 4:03 PM UTC

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.

This was the point behind Reflections on Trusting Trust - you can't trust it. Unless you build the entire compiler/linker tool chain from source that you've already inspected.

https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...

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

#118

Post by Tangurena2 » Thu, May 25, 2023, 4:07 PM UTC

Animats wrote: post #14

NoMoreNicksLeft wrote: post #6

Earlier quoted context omitted.

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.

It was standard coding practices if you were selling games - to prevent people from hacking the license key stuff. Or by cheating software to prevent detection by anti-cheat software. One of the hooks built into Windows is "is a debugger connected" helps the virus/cheat code determine if it is "safe" to run or not.

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

#119

Post by cs702 » Thu, May 25, 2023, 4:37 PM UTC

DannyBee wrote: post #95

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…

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!

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

#120

Post by s3p » Thu, May 25, 2023, 4:42 PM UTC

eru wrote: post #73

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…

Just don't trust that code, and don't run it? You should require positive proof that code does what you want. Similar to how eg Haskell's type systems doesn't have to solve the halting problem [0]: it just rejects some programs that would be ok, but don't conform to the type system. See also proof-carrying code. https://en.wikipedia.org/wiki/Proof-carrying_code [0] Ok, unless you use undecidable instances or somethin…

Yes great so let's not use any software at all on our machines! only things we can program ourselves or are open-source. what a dystopia we live in...