Slashdot Log In
On the (Im)possibility of Obfuscating Programs
Posted by
timothy
on Fri Mar 01, 2002 03:18 AM
from the bold-words dept.
from the bold-words dept.
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.)
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
I don't know about you... (Score:3, Funny)
sssca (Score:2, Insightful)
proofs (Score:4, Funny)
software protection (Score:4, Informative)
Re:software protection (Score:2, Interesting)
... 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
Re:software protection (Score:2, Interesting)
- 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 portRe:software protection (Score:3, Interesting)
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.
Re:software protection (Score:5, Informative)
Parent
Re:software protection (Score:2)
It would require a dungle with a couple of vital parts of the program to work, and even then, assuming you've one legal copy, you could probably find a way to copy from it.
A useful way would require telling the CPU to fetch the instructions from the dungle, with no way for instructions outside the dungle being able to read into the dungle's adress space, only to jump into it and start executing.
Re:software protection (Score:5, Interesting)
Parent
eh. not good science... (Score:3, Insightful)
Yes you can say that obfuscatable programs can not be
Re:eh. not good science... (Score:4, Insightful)
Of course, mostly the DRM people are interested in making things sufficiently hard to do, not impossible.
They are driven by profit, not purity of outcome, so if a scheme costs more to run than it delivers, it will not be used.
Likewise, tweaking a DRM system to maximise returns involves evaluating the cost of the DRM system itself, and the hassle it gives to legitimate customeers. Just having a 100% success rate means nothing if you only have 2 customers left.
Michael
Parent
Are you sure? (Score:2, Funny)
Re:Are you sure? (Score:2)
Yeah, and they've never read any of my Uncle Nic's perl...
Re:Are you sure? (Score:3, Informative)
Look at page 3 of their paper, they published a slightly adapted version of the IOCCC Contest winner of '98. They of course adapted it to the paper, therefore I suppose it lost most of its obfuscated features
And in the references list on page 37 you can also find a link to http://www.ioccc.org
Yes, this is actually a problem... (Score:5, Insightful)
PLEASE somone start publishing papers on how all digital content can be protected by XORing it with the number 0x42 and will be secure as such for decadeds to come.
Re:Yes, this is actually a problem... (Score:4, Funny)
The correct value should be 0xDEADBEEF.
-
Parent
Re:Yes, this is actually a problem... (Score:2)
Cute, but using 0 and 1 feels like cheezey 31337, though it does give you 0xFEEDFACEC0FFEE.
I preffer the purity of ones like
0xCAFEBABE (Actual magic number for Java classes)
-
Mozart (Score:5, Interesting)
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...
Re:Mozart (Score:2, Informative)
Essentially correct though. I've often wondered if I'm violating copyright by listening to songs and working out the chords on the guitar. I think my playing is so bad that I can get away with it though.
Re:Mozart (Score:5, Informative)
The next famous story concerning the Miserere involves the 12-year-old Mozart. On December 13, 1769, Leopold and Wolfgang left Salzburg and set out for a 15-month tour of Italy where, among other things, Leopold hoped that Wolfgang would have the chance to study with Padre Martini in Bologna, who had also taught Johann Christian Bach several years before. On their circuitous route to Bologna, they passed through Innsbruck, Verona, Milan, and arrived in Rome on April 11, 1770, just in time for Easter. As with any tourist, they visited St. Peter's to celebrate the Wednesday Tenebrae and to hear the famous Miserere sung at the Sistine Chapel. Upon arriving at their lodging that evening, Mozart sat down and wrote out from memory the entire piece. On Good Friday, he returned, with his manuscript rolled up in his hat, to hear the piece again and make a few minor corrections. Leopold told of Wolfgang's accomplishment in a letter to his wife dated April 14, 1770 (Rome):
"...You have often heard of the famous Miserere in Rome, which is so greatly prized that the performers are forbidden on pain of excommunication to take away a single part of it, copy it or to give it to anyone. *But we have it already*. Wolfgang has written it down and we would have sent it to Salzburg in this letter, if it were not necessary for us to be there to perform it. But the manner of performance contributes more to its effect than the composition itself. Moreover, as it is one of the secrets of Rome, we do not wish to let it fall into other hands...."
Wolfgang and his father then traveled on to Naples for a short stay, returning to Rome a few weeks later to attend a papal audience where Wolfgang was made a Knight of the Golden Spur. They left Rome a couple of weeks later to spend the rest of the summer in Bologna, where Wolfgang studied with Padre Martini.
The story does not end here, however. As the Mozarts were sightseeing and traveling back to Rome, the noted biographer and music historian, Dr. Charles Burney, set out from London on a tour of France and Italy to gather material for a book on the state of music in those countries. By August, he arrived in Bologna to meet with Padre Martini. There he also met Mozart. Though little is known about what transpired between Mozart and Burney at this meeting, some facts surrounding the incident lead to interesting conjecture. For one, Mozart's transcription of Allegri's Miserere, important in that it would presumably also reflect the improvised passages performed in 1770 and thus document the style of improvisation employed by the papal choir, has never been found. The second fact is that Burney, upon returning to England near the end of 1771, published an account of his tour as well as a collection of music for the celebration of Holy Week in the Sistine Chapel. This volume included music by Palestrina, Bai, and, for the first time, Allegri's famous Miserere. Subsequently, the Miserere was reprinted many times in England, Leipzig, Paris and Rome, effectively ending the pope's monopoly on the work.
Parent
It was obvious before they proved it. (Score:5, Insightful)
Quick proof:
1)A software-only DRM system attempts to make a product run in cases where it is not a copy.
2)It makes it's decision based on information content of some kind.
3)A copy will perfectly replicate all information content. (If it can't, then you don't need DRM.)
4)If a copy has the same information content as the original, then the DRM cannot distinguish between the copy.
5)Therefore DRM has no way to shut down only the copies.
6)The only way to make DRM work is to have some sort of information that is impossible or very much harder to copy. Thus, the web-activation type scheme, although IP packets could easily be spoofed.
7)God, I should have published this years ago, if it weren't so GODDAMN OBVIOUS!
Not quite (Score:4, Informative)
They proved that not every function is obfuscatable. However for all we know, it might be that most functions are obfuscatable, which is good enough. Also the notion of obfuscation is somewhat contrived (this is because of the lack of a generally well defined notion of what de-obfuscation is, they did the best given what is a new field).
Say, in general proving that a program terminates is impossible. Nevertheless millions of lines of code are put out every day which we are positive they terminate, as we restrict ourselves to designing programs that always do so (even though the occasional bug gets in the way).
Talk about publication delay! (Score:3, Funny)
"Tamper Resistant" (Score:5, Insightful)
So tamper resistant isn't an absolute statement and often refers to the ability to buy time. However many companies (typically the saled dept.) often refer to it as though it buys *complete* piece of mind, yet even physical bank safes are rated by time to resist cracking/breaking.
I think this paper is good because it means that PR claims can be provided with a counter argument from a third party that provides a proof. However I think that anyone using the word tamper resistant is not an imbecile, I think that anyone who uses it in the context of tamper-proof is an imbecile. Resistant has so many contexts.
Could this proof hamper the DMCA? (Score:5, Interesting)
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?
no, it's why the DMCA exists (Score:3, Informative)
Re:no, it's why the DMCA exists (Score:3, Interesting)
If 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.
Re:Could this proof hamper the DMCA? (Score:3, Interesting)
Just food for thought.
An expanded take. The maze analogy. (Score:4, Insightful)
The first time a traveling salesman walks into my living room, I complain to my maze provider. He then releases Labyrinth 2.0. Instead of a maze of brick, the maze is now full of mirrors.
Of course this maze is foiled by crafty salesmen who lay breadcrumbs and place markings on the ground to indicate where they'd been (sure they could have done this before, but lets say they didn't).
So again I complain and the maze provider offers another solution. But this time the maze provider does something new. Labyrinth 3.0 offers support for trolls who live under the maze and can rearrange the markings and discard the breadcrumbs left by the salesmen. You can buy the trolls from the maze provider as well as troll food each month.
Now I've paid for 3 versions of my Labyrinth security product, and am continuing to pay now for trolls and food on a per month basis. My maze provider is now a huge corporation. Should they have to pay if their supposed security system fails?
What if they knew all along that the maze technology was insecure and that no matter the obfuscation there was always a way an intruder could enter your house through supposedly legal means (assume that simply using the maze fairly is not illegal). If it can be shown that the maze provider knew ahead of time that maze tech was inherently insecure and that while the upgrades seemed to fix security holes as they were discovered, that these types of holes would always be present and are indeed unfixable. Should a company be allowed to continue to "upgrade" their technology and make even more money, while they know their product will never be fit for this particular purpose?
Parent
Re:An expanded take. The maze analogy. (Score:3, Insightful)
But a certain software company is advertising that it's latest server software is completely secure, and will run long periods unattended. The default installation turns out to be wide open, and I rather suspect that the servers will have to be rebooted far more often than is true of well-tuned installations of several competing products, two of which are _free_. The problem here is that American courts will generally figure that obfuscated phrasing in the fine print of contracts override public claims like this...
Everything can be cracked (Score:5, Insightful)
If a piece of software (with some kind of copy-protection) runs on a computer, it can be cracked to run without that protection. Tools such as Procdump will start the program, and after the user has clicked yes on a nag box and the program is decryptet, procdump will scan the memory and rebuild the executable.
If a movie or music file is protected by some encryption it still has to be decrypted to be played. There are many ways to crack this. Crack the encryption, intercept the data stream after it has been decrypted or just record the analog stream. A small quality loss, but with no protection at all. I remeber reading an article by Tron Øgrim, where he had interviewed a boss in a publishing corporation or something like that about DeCSS and ways to protect digital data (movies in this case). He asked if they had some way to stop people from just using a camcorder to record the tv, and the boss-guy said no, and I had the impression that they just hadn't thought of it. They can protect their movies and music with super-strong encryption, but people still have to be able to watch the movies or listen to the music. If people can watch or listen to it, they will be able to record it.
Re:Everything can be cracked (Score:5, Informative)
The Image can be tuned to the the sampling rate of your scanner and interference introduced (called moire patterns).
Change the DPI at which you're scanning and the interference will go away. (or find a real girl!)
It's a techniqued used on UK (and other) banknotes too. The engravers make a series of very this, closely spaced lines. When scanned or photocopied they too form moire patterns.
Of course it's just an arms race but like having a locked gate it affords some security. I have access to cheap scanners & colour photocopiers but not to bank note paper or high end engraving equipment.
Parent
Centre for Software Maintenance (Score:3, Informative)
The Centre for Software Maintenance" [uq.edu.au] is hard to beat.
Of particular interest is dcc [uq.edu.au] , the GPL decompiler.
Input ".exe" files, and output high level C code.
dcc != practical (Score:3, Interesting)
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 [backerstreet.com] (reverse-engineering compiler), but it's sort of limited in the kind of input it allows.
IDA [datarescue.com] 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.
In relation to games... (Score:2)
I've worked with Intel's DRM (Score:5, Interesting)
Trivially obvious surely? (Score:4, Insightful)
A perfect example (Score:2)
As many Linux DVD enthusiasts already know, DeCSS was made by looking at the binaries that the Realnetworks DVD software contained and locating the decryption key.
hardware too ! (Score:3, Funny)
Now, if they promote brain-implants, then they might have the users DRM'ed which will be quite different to bypass...
Unless one finds enough red pills.
Its all time, cost & effort based (Score:3, Insightful)
When beowolf clusters came out (obligitory reference) lots of 'unbreakable' encryption was considered suspect (eg DES) Any encryption system is only secure for a limited amount of time. When new hardware/software comes out the limit is shortened.
I remember a hardware 'key' system that plugged into the parallel port, and all the circuitry was encased in a solid block of black plastic. It was broken by sampling the data in & out then wedged itself in and emulated the hard key (software replaced hardware). The real trick is to spend a resonable amount of money to protect your data/programs for what you might get in monetary compensation. Eg don't put a $40,000 dollar lock on a $2 product.
I think the real question is this: what are they trying to protect, and for how long? Could you guarantee that some code would get 5 yrs of time where the encryption is unbreakable? A twisty mind may think up a interesting 'unbreakable' codec, but a differently twisted mind can crack it.
This isn't as big as the poster is making out.... (Score:4, Interesting)
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.
Re:This isn't as big as the poster is making out.. (Score:2, Informative)
http://www.icsi.berkeley.edu/~tschudin/ps/
Church Turing trumps this anyway (Score:2)
So Eisner really does need to outlaw Turing machiens to have his way.
An important point about the paper (Score:5, Informative)
The paper does not say that programs can't be obfuscated. What it does say, is that there can be no generalized "obfuscator" that you run your program through and voila you've got an obfuscated version. Hoever, program obfuscation is possible on a per program basis. Simply put, the more obfuscated a program is, the more difficult it might be for someone to reverse engineer it.
The folks at cloakware [cloakware.com] have done what's supposed to be a bang up job of embedding AES keys in an obfuscated client. What that means is that you can use powerful, yet easy to compute, block ciphers with symmetric keys for "public" key cryptography. The clients will have your key embedded in the program, but in theory they won't be able to recover it. As the paper proves, Cloakware has to do the obfuscation on a program by program basis. They can't have a generalized obfuscating machine because such a machine can't exist.
Now, while I firmly believe that perfect DRM is an impossible goal (assuming no SSSCA), good enough DRM is certainly conceivable. If CSS had been obfuscated, DeCSS might have come out much later than it did. Program obfuscation could easily be used by those want DRM. They'd have to be prepared to be in a digital arms race, but they could probably as least give those who want to crack DRM a run for their money.
All things considered, we'd be better off if content providers were willing to trust software DRM rather than forcing all non copy-compliant hardware out of existence.
Re:An important point about the paper (Score:2)
I've been wanting to use Python for applications that require guarding against malicious users --yes, in effect I am looking for Locked Source, flame away.
I am wondering if you can compile a python interpreter with an embedded public key; you could then encrypt your code with your private key and still be able to ship it to a co-lo or an untrusted client site.
However, I cannot see how this can be generalized without the public key being extractable from the interpreter executable itself or from the code itself in RAM... Thoughts?
Self Evident (Score:2)
In order function the program must be 'interpreted' in someway, since that interpreter could be an engineer, the *best* than can ever be acheived is to make that task more difficult, not impossible.
Since openness is in the interests of all Computing Engineers we need to debunk the urban myth that it's possible.
I wish they hadn't published this thing (Score:3, Funny)
Okay look guys, I know this, you all know this but let's not tell the suits okay.
I like watching them fuck it up
Reverse-engineering of chips, in practice. (Score:3, Insightful)
Want to know what is possible? Want something to think smile about when you hear about the latest and greatest smartcard system? Just curious about how one actually can go about rev-eng'ing a chip?
You owe it to yourself to read the following paper: Design Principles for Tamper-Resistant Smartcard Processors [cam.ac.uk] and check out the slides [cam.ac.uk] for lots of interesting pictures.
Everything from how you use acid to remove the packaging without destroying the chip logic itself, to the actual microprobing to extract information from the circuit.
But it is possible (Score:3, Insightful)
I like to make several points:
- what the "(im)possibility" paper says
- "we all know" does not mean its true
- lots of other published works
- resistance is not an absolute thing
timothy has mis-understood the importance of the "(im)possibility" paper. The breakthrough is that this is the first real theoretical treatment of obfuscation. They show that it is not possible to build a totally automated system that is Really Secure (to vastly over-simplify, they construct program that actively leaks a single bit and then show that no obfuscation program can protect this program against itself). This is really interesting but not directly applicable to what we do - we work with our OEM customers to help design the system, the protocol, the programs so that all the pieces are working together; then we "cloak" the critical pieces. (I spoke to some of the authors before the conference, and many Big Names during Crypto'01; I think it is fair to say that most knowledgable people have this view).
As to the "we all know" truism; it is clearly not true. Real life examples abound - any old, large software system is hard to fix since people don't understand the relations between modules (i.e., the market for reverse-engineering tools). These systems are Tamper-Resistant. The well know IOCC (International Obfuscated C Contest) is another good source of Tamper-Resistant programs. In a manner of speaking, the goal of Cloakware is to achieve this Tamper-Resistance on-demand, for easily maintained code.
The "(im)possiblity" paper is breakthrough on the theory side, but many other people (including us) have published on the practical problems. Some names include Cohen, Collberg, Forest, Wang, Knight. There are many schemes that are reducible to various complexity classes, usually NP-complete and we have one that is PSPACE-hard. All of these papers are correct, there is no conflict.
Lastly, "security" is not binary and has many different attributes. Each application has its unique requirements. For example, diplomatic files are protected for many decades or centuries; a Britney Spear song probably needs only a few months; real-time stock market quotes for 15 minutes. Factors like Usability, Speed, Deployment are often more important than raw security.