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.)

Comments

Yes, this is actually a problem...

[gnovos]

...because it means that the ONLY recourse for these money hungry bastards in the "content industry" (is legal prostitution considered and "industry"?) is legislation. As long as they can be fooled into thinking that Mr. Wizbang's new ROT-14 encryption scheme is uncrackable by all but the most devious of minds, they will relax and let themselves sink slowly into the mire of contentment that will someday be thier graves. But when people come around spouting off how impossible it is to have DRM on "untrusted" machines, the only solution is legislate trust into all the machines in the most draconian and Brotherly way possible.

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.

Mozart

[rjamestaylor]

In my Music Appreciation (Apprehension?) class I learned that as a young boy Mozart broke a vaulted DRM of his day by simply attending a concert in an Italian church. The mass that day was kept under lock and key and would only be played once a year; all copies of the music were kept secret. What Mozart did is hear the mass (once) and then went home and wrote the entire score as if he was copying the original documents yet only assisted by his memory. His scoring was so good he was accused of stealing the score from the church. (Forgive my poor recollection of Mozart's superb recollection ancedote...)

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

[Oink.NET]

Here's an exerpt from this article (I like the "effectively ending the pope's monopoly" part):

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.

It was obvious before they proved it.

[Henry V .009]

It was already obvious that this was true.
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!

"Tamper Resistant"

[JohnBE]

I don't want to be a pedant, but resistant doesn't mean immune in all contexts, it also means "the attempt to prevent something by action or argument" [or something to that effect - I don't have a dictionary within reach].

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?

[CptnKirk]

Now with this proof being published, software companies now have no expectation that their software only copy protection or DRM system is secure. What does this mean?

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?

Everything can be cracked

[neonstz]

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

[DrSkwid]

I tried to scan in a picture from a girlie calender the other day and it came out with an array of dots over the picture, it looked terrible. I was told that it was a relatively old form of copy protection. I looked at the source picture but it looked perfect in real life, I wondered how they did it.

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.

I've worked with Intel's DRM

[KNicolson]

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.

An important point about the paper

[cube_mudd]

I attended the 2002 IPAM Crypto conference at UCLA where Steven Rudich gave a presentation on this. There is an important point that, from reading the comments thus far, is not being appreciated.

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 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:software protection

[uebernewby]

I think you'll find dongle-protected apps such as CuBase, 3D Studio Max (up to v.3) et al have been available cracked for a long time.

Re:software protection

[CaptainSuperBoy]

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.