Slashdot Mirror
On the (Im)possibility of Obfuscating Programs
sl956 writes: "We all know that anybody using the words 'tamper resistant' to describe a software-based solution is incompetent at best. But some of the big players in the DRM field are believing in software-only protection schemes (see Cloakware, Hitachi, IBM or Intel). A mostly unnoticed paper presented to CRYPTO'01 (Santa Barbara, CA, August 19-23, 2001, LNCS vol.2139) *proved* the impossibility of efficiently obfuscating programs. It is the mathematical proof of the impossibility of a software-only DRM system on an untrusted client such as a PC. There are also a lot of interesting theoretical side-effects. You can read the html abstract here, or the postcript full paper here." The paper is from last year, but that doesn't make its conclusion less interesting. (Of course, even hardware isn't always all that secure, either.)
There will always be a Mozart to break the DRM of publically performed (or distributed) works. DRM is a way of controlling the sharing of some piece of work. In reality, the only way to perfectly safeguard the rights is to not share the work -- or trust people. Hmmm...
-- @rjamestaylor on Ello
If I wrote a copywrited piece and then used a form of copy protection that I knew people could break (similar to what some people were doing to "encrypt" song titles on Napster a while back), do I have the right to sue them under the DMCA (and a while back the judge said no)? Maybe so, maybe not, maybe it's a grey area, maybe there are other loopholes I know nothing about. But one thing I think the courts have upheld is that legally there is no degree of separation.
For instance of a judge rules that breaking someone's "lame encryption" does not violate the DMCA, because they knew ahead of time that a person could break it. Then adding to the complexity shouldn't change anything. If you have a proof that shows that software only DRM on an untrusted client is not secure can you or should you be able to claim damages when someone eventually exploits the hole you knew had to exist.
Of course IANAL, and I'm sure this will not cause the DMCA to crumble, but I think it raises some questions. Similarly are you allowed to advertise that such systems baised on obfuscation are secure or should they be clearly labeled as deterants, and not iron clad security?
And they were always very careful to point out that their software is merely tamper *resistant*, not tamper *proof*. This is not just the sales guys, but the engineers too, and even in meetings if I accidentally said, for example, "*blah* will prevent copying", they were quick to correct my mistake.
There's a paper called Protecting Mobile Agents against Malicious Hosts by Tomas Sander and Christian F. Tschudin, which demonstrates it's possible to write a program which can compute a digital signature or other various functions in such a way that it's impossible for the host to hijack the process, i.e., it's cryptographically hard to reverse engineer the program to extract the public key being used, or the function being computed (This paper has been used for various purposes, including proving that it's theoreticaly possible to write computer viruses which have signatures which are impossible to detect).
These papers aren't contradictory, there are important differences between the results.
Ultimately, one paper demonstrates a certain type or program (which would be usefull in implementing a DRM scheme) is impossible, the other paper demonstrates another similar type program (which would also be usefull in implementing DRM schemes) is possible (and demonstrates how to create such a program, and gives a non-trivial example).
Is this the theoretical end of all DRM as the poster is suggesting? Not yet.
... you already know the ending. I cracked it completely in 6 hours and he went back to them with a cracked copy later.
The only protections I know of that indeed have given "breathing space" involved hardware dongles. No one used pirated copies of Cubase on the Atari ST because they didn't work as they should
it's in my head
- The only protections I know of that indeed have given "breathing space" involved hardware dongles. No one used pirated copies of Cubase on the Atari ST because they didn't work as they should
.. but as soon as versions without dongles appeared on other platforms they were cracked completely in an instant.
if you use the hardware dongle for "proof of purchase" - just need to patch the check to the serial portIf it's decided that a company is responsible for it's security holes, can/should they be held liable for damages to a third party? For instance many labels are now using some form of DRM for their online services (PressPlay, MusicNet, Napster, etc). Since there isn't a lot of SDMI compliant hardware out there, these services are forced to use a software based DRM system on untrusted computers.
Should BMG now be able to sue Microsoft for damages when someone figures out the obfuscation being used in Media Player 8? Is this akin to selling a service with a known unpatched security hole? I dunno, but I think it's an interesting question.
people seem to confusing the notions of 'obfuscation' and 'tamper resistance'. given an obfuscated program, one can learn nothing about it beyond its input-output behavior (the paper states this in formal terms). given a tamper-resistant program, one might be able to learn some things beyond its input-output behavior, tamper-resistance means you cannot make meaningful _changes_ to the program without breaking it. this paper deals with obfuscation, not tamper-resistance. obfuscation implies tamper-resistance, but take care to note that tamper-resistance is a weaker requirement.
Many proofs saying that there can be no algorithm that performs X make a fundamental false assumption: there is infinite memory. Just because with infinite memory some algorithm can't exist doesn't mean that it can't be done with finite memory.
Consider the "halting problem". The reason no perfect debugger can exist is because it would necessarily have to get into an infinite loop for certain programs. On real computers, however, an infinite loop will not occur. Program H(K, K) will terminate with the correct answer on any real computer. H will recursively act upon K and H trying to figure out what happens. At some point, program H will see a subinstance of itself running out of memory, a "terminate" answer. This will propagate alternately back to the "root" H, which will return the response. Which response occurs depends on the size of memory and other factors, but it returns the correct answer.
Corollary: No program can truly have itself as a parameter. This is because no program can emulate a memory bigger than its own. Compression is ignored because then some inputs are disallowed (IE, random data that before compression was the maximum input size).
Proof that a perfect debugger for some input size exists: Simply manually create a truth table for all possible inputs, and create a program that returns table[input].
myria
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
dcc isn't practical though, unless you've got a heavily modified version. The offical version is hardwired to only support very small programs, and fixing that would require extensive rewriting of its internal structures.
Not saying that it isn't interesting, only that today, no one (I'll wager) is using dcc for practical reverse-engineering.
There's also rec (reverse-engineering compiler), but it's sort of limited in the kind of input it allows.
IDA on the other hand is the tool of choice for the kind of reverse-engineering you're thinking of. If there were to be a source-generating backend on that one, you'd see a lot of worried faces, I assure you.
Belief is the currency of delusion.
I think this is a very nice analogy, but in all honesty: it proves that you got yourself into this trouble. The company can (and will) argue that, if you were not satisfied by the security-scheme, you shouldn't have bought the product...
The only thing that could come from this is a lawsuit for misleading advertising, and then only if the company advertised the maze as completely secure
And yes, IDA is quite good. Having experienced the fun of IDA, I can vouch for its usefullness. It requires you to use that computer between your ears but with a bit of skill you can do wonders with it. For completeness, Sourcer should be mentioned. It is quite good too, and somewhat orthogonal to IDA. However, I find myself returning to IDA, especially for the "tough" parts.
Was that before or after you spent some time messing with trojans? Yeah you're not going to live that one down. Don't expect me to buy any of your software any time soon.
Quite trivial to crack, since the machine can then easily copy the code. The only uncrackable software is one that runs on its own operating system on its own hardware that is physically secured in a way that prevents tampering.
The illegal we do immediately. The unconstitutional takes a little longer.
--Henry Kissinger
Though the work presented at crypto 2001 may prove that it's not possible to provide program obfuscation in the general case, some other researchers have shown how to do obfuscating in more restrictive, yet powerfull scenarios.
For example, there is a paper that describes a method to do Function Hiding. This allows to compute a function on an untrusted host. A lot of problems can be modeled that way, and though we may never see methods to provide obfuscation in the general case, it does not rule out the possibility of obfuscating special classes of programs.
if you use the hardware dongle for "proof of purchase" - just need to patch the check to the serial port :) but, a more reliable method would be to actually have program code *inside* the dongle that is downloaded at runtime to the memory space of the machine and is vital for the execution of the program :) that's a bit harder to "crack" - but, not impossible.. application needs more modification *g*
Not that much more modification. All you'd need to do here would be to tack the code from the dongle onto the programme and have the downloading routine look at a certain memory address rather than a peripheral port...
The only way of making this moderatly hard is to have the application run completly standalone, in other words in must contain it's own operating system, preferably on unmodifiable hardware, in which case you'd end up with something more like a games consome than a regualr computer.
Check out some of the winning entries from IOCCC competitions and then tell me code can't be completely obfuscated.
Many if not most of the IOCCC entries can be effectively de-obfuscated by running `cpp' (C pre-processor) then GNU `indent' on the code.
Will I retire or break 10K?
Commercial software could then be encrypted.
When you install a new piece of software your public key is read out and you type a product authorization key which is printed on a card in the box, and this is sent via the Internet to the vendor. The vendor checks that the product key hasn't been used before and then encrypts the session key for the software package with your CPU's public key. This encrypted key is sent back to you and stored in a file on your computer's hard drive. When you launch the application, the loader reads the encrypted session key into the CPU and issues a special machine instruction which causes the CPU to decrypt the session key and store it in a CPU register which can't be read out by anyone. But at this point the CPU can start reading the encrypted software code and execute it. The plaintext code is never exposed outside the CPU.
This would not only provide perfect copy protection for software, but also allow DRM in software that can't be cracked.
Expect this soon after the SSSCA passes. Technologically, it wouldn't be hard to implement.
If I can be modded down for being a troll, can I be modded up for being an orc, or a balrog?