Cryptographic obfuscation and 'unhackable' software | Hacker News Reader

Cryptographic obfuscation and 'unhackable' software

blog.cryptographyengineering.com

66 pointsclarkm25 comments

I had heard of this paper but reading a summary now makes me link the idea with secure verifiable computing [1]. This is basically the same base idea where A wants to send a program to B so that B can use the program but not know what it does. In the case of the original article, you want B to get back the results by himself (like in a conventional application).

However, there is another approach where B is just an untrusted third party where you want to outsource the computation. In other words, A wants to get back the result and check it, without B knowing anything of it. There is actually a(n almost) generic construction that allows that [2]. In short, you consider the boolean circuit of what you want to compute and transform it so that the inputs are keys necessary to unroll the computation, until getting the encrypted result. More specifically, step 1 gets the input keys and compute some new key (amongst several possible); step 2 use this key for next computation and so on.

On the one hand, this constructions are very neat because they give us a better understanding of what we can do with cryptography. On the other hand, they can be a little frightening because they are the theoretical grail for DRMs and such.

[1] https://en.wikipedia.org/wiki/Verifiable_computing

[2] Part 1 of A Proof of Security of Yao's Protocol for Two-Party Computation, http://eprint.iacr.org/2004/175.pdf

> On the other hand, they can be a little frightening because they are the theoretical grail for DRMs and such.

Definitely. I can't help thinking that the ones who will end up using this sort of technology are corporations who want to control their users, and malware writers. The phrase "Those who give up freedom for security deserve neither" and http://www.gnu.org/philosophy/right-to-read.html also come to mind... it's scary, security is a double-edged sword.

Actually, I think there could be an application in gaming for this. Imagine a game that cannot be beaten with hacking or cheating (reading the code); you would have to play it correctly in order to win.

For example, an adventure game could use this to great extent. There simply wouldn't be a way to know the story until someone would actually managed to go through it and tell you. There could be hidden levels or easter eggs and no one would ever know.

(I came up with this when I was thinking of a Minecraft clone, where you would have to discover the recipes to build stuff on your own. Although I was thinking about simply using hashed input into recipe routine for obfuscation.)

Why is it good to stop people from cheating on a single player game?

You can consider it an "artist's statement", something comparable to Kryptos statue. Nothing evil in that, I believe.

Reading the code doesn't mean you can cheat or hack.

I don't see why you'd engineer out of the game every social element that makes them fun. The only category that would work for is if you procedurally generate every run through of the game and randomise all the mixes so 2 people talking to each other on computers next to each other literally don't have the same game to mix the same items together.

They aren't saying the game would work differently. Rather, things would not be known until at least one person got that far. One couldn't, as soon as the game came out, look at the executable or source file, and determine how it ends, way before anyone else who was playing legitimately.

So people wouldn't be able to spoil the twist until someone actually got to it.

I think this would actually make people more likely to play it together, because there would be real discovery, and people wouldn't know for sure if they REALLY found everything yet.

People could tell each other what they found, but they would only be able to find it by playing, not because one guy looked at the program and just made a complete list.

(I have also thought about a similar problem before, but the result ended up being really slow, and I don't know how to make a text adventure actually fun. Mostly it was just really slow though.)

> One couldn't, as soon as the game came out, look at the executable or source file, and determine how it ends, way before anyone else who was playing legitimately.

...or until someone writes a bot to brute-force their way through the game, because computers are really good at trying lots of possibilities really really quickly, many orders of magnitude more quickly than a human player could.

I suppose that's true.

Still an improvement/would take longer.

Also the only way I've tried takes a while to compute, so it might be more efficient to do it based on reasoning instead of based on brute forcs?

But that might be annoying to users, depending on how long it takes to run each thing.

Is there a sweet spot for the computation time is long enough that it is more efficient for a person to reason it out than for a standard home computer to brute force, yet short enough that a human player would not find the delay to be noticeable/annoying?

Isn't that concept also close to homeomorphic encryption?

http://en.wikipedia.org/wiki/Homomorphic_encryption

Homomorphic encryption is one the primitives which is used for this kind of construction, but it is not sufficient per se.

Perhaps this is just my Stack Overflow reflexes, but:

The string argument to SuperSecretPasswordProtectedStuff() should be const (reference, perhaps even) and of course printf() shouldn't be used in C++.

It's ... fun and interesting that such a super-minimal example of source code (from a research professor for crying out at 200 dB(A)) has those kinds of "sloppiness indicators" in it.

Or am I just being grumpy?

Regardless, I'm glad to see someone trying to shed some proper light over the obfuscation research, I too was underwhelmed by Wired's coverage. I'm more or less clueless when it comes to all things security-related, though.

Even grumpy people should be able to distinguish pseudocode from c++, I'd have hoped!

But yeah, great article, imho, in that it clarified these concepts a lot for me, as a non-crypto person.

Whoever writes "printf()" in pseudo-code though, and bothers with newline characters? I would expect "print" or something but of course there's no standard for psuedo-code.

I dunno, but not the author of that piece, as far as I can see; the only printf() in there is in the occc entry, isn't it?

Maybe your stackoverflow neurons put the extra 'f' in the pseudocode print() calls, or maybe the author edited it after seeing your comment :)

Eh, I wouldn't say either of those are universally accepted practices. printf has a much nicer interface than iostream (there's a reason most newer languages have a printf-compatible formatting routine), and marking local variables const (not pointer to const) can be seen as unnecessary verbosity.

I was going to argue with you about printf in C++, (I use it instead of streams, purely because I irrationally hate them); but I have not unwind-protect in my interpreter.

The article leaves me hanging. Long introduction, describes IO and EO, and when it's time to talk about their uses, it just handwaves "lots of exciting stuff coming in future!"

> obfuscating 'symmetric' primitives like pseudorandom functions

So how would be obfuscated and indistinguishable RNGs be useful, if they generate the same numbers? I'm sure there is something there, but the article doesn't tell :-/

Obfuscating a PRF turns a symmetric primitive into an asymmetric one.

You can think of a PRF as a keyed hash. Now, you can turn this into an encryption scheme by running it in counter mode:

    keystream  = PRF(K, 0) || PRF(K, 1) || ...
    ciphertext = plaintext XOR keystream

Now suppose we can obfuscate this PRF with a specific key (i.e. Obf(PRF(K, _))), in a way that makes it impossible to find out what K is. Then you can distribute the encrypted program as a public key, and the private key would simply be K. That's the gist of it.

I don't think you can do it with a stream cipher like that. Rule 1 for a stream cipher is that you never encrypt multiple messages with the same keystream. 'ciphertext = plaintext XOR keystream' means 'keystream = ciphertext XOR plaintext' and the attacker could just encrypt some arbitrary plaintext with the publicly available code and XOR the plaintext back out to obtain the keystream, even if the code itself is a black box.

You could probably manage to do it with a block cipher though.

Yes, you're right, perhaps I oversimplified too much. That is the main hurdle Waters and Sahai have overcome.

They do this by not using a counter, but randomly-selected nonces that feed a keyless stream generator (like AES-CTR with a fixed known key), and use a mechanism (puncturing) to 'blacklist' previously-used nonces so that they reveal nothing about previous keystreams used. Without being able to ask for encryptions of arbitrary messages using a previous nonce, the attacker has little options.

Granted, this is annoying because you have to 'recompile' the obfuscated encryptor for each new nonce, but that is of no concern in the model being used.

>Malware authors and DRM folks

Aren't those largely one and the same?

More precisely, the latter are a subset of the former.

What immediately came to my mind is the attack potential of this methodology. Is there one? Seems to me it makes possible the writing of undetectable malware, no?

Disclaimer: No rhinos were harmed during the writing of this article.

Reply on news.ycombinator.com