6 ms·

Cryptographic obfuscation and 'unhackable' software

66 points by clarkm 13y ago

unwind 13y ago
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.
- ttctciyf 13y ago
  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.
  - unwind 13y ago
    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.
    - ttctciyf 13y ago
      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 :)
- comex 13y ago
  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.
- Shorel 13y ago
  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.
yoha 13y ago
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 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 http://eprint.iacr.org/2004/175.pdf
- userbinator 13y ago
  > 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 http://www.gnu.org/philosophy/right-to-read.html also come to mind... it's scary, security is a double-edged sword.
  - asgard1024 13y ago
    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.)
RaquelCBixler 13y ago
Disclaimer: No rhinos were harmed during the writing of this article.
cuu508 13y ago
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 :-/
- pbsd 13y ago
  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.
  - AnthonyMouse 13y ago
    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.
    - pbsd 13y ago
      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.
blueskin_ 13y ago
>Malware authors and DRM folks Aren't those largely one and the same?
- jessaustin 13y ago
  More precisely, the latter are a subset of the former.
DonGateley 13y ago
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?

66 points by clarkm 13y ago

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.

ttctciyf 13y ago
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.
- unwind 13y ago
  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.
  - ttctciyf 13y ago
    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 :)
comex 13y ago
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.
Shorel 13y ago
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.

yoha 13y ago

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 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 http://eprint.iacr.org/2004/175.pdf

userbinator 13y ago
> 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 http://www.gnu.org/philosophy/right-to-read.html also come to mind... it's scary, security is a double-edged sword.
- asgard1024 13y ago
  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.)

RaquelCBixler 13y ago

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

cuu508 13y ago

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 :-/

pbsd 13y ago
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.
- AnthonyMouse 13y ago
  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.
  - pbsd 13y ago
    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.

blueskin_ 13y ago

>Malware authors and DRM folks Aren't those largely one and the same?

jessaustin 13y ago
More precisely, the latter are a subset of the former.

DonGateley 13y ago

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?