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.)
as a developer myself, i spent a bit of time messing around with protection schemes for applications i wrote for the Palm OS platform. i wrote a paper on it, which was made available at PalmSource 2000 and is available here. i enjoyed understanding the inner workings of how they did it - so, i documented it. however, i knew that there was no beating them - the question remained.. how long would it take for them to crack it? does it give me some selling breathing space? (more time = more sales) :P
I read the article last year when it came out. The results are not as far reaching as they sound from a first reading of the abstract.
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).
The Centre for Software Maintenance" is hard to beat.
Of particular interest is dcc , the GPL decompiler.
Input ".exe" files, and output high level C code.
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.
Not quite correct. Indeed, the Vatican did keep the score of the Allegri Miserere secret. Mozart didn't quite get it right on the first listening though - it was three.
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.
"Under the iron bridge, we fist" - The Smiths, Still Ill
The result is not particularly surprising. In some sense, the DMCA exists precisely because people can break these schemes: where technology can't enforce the behavior, you need the power of the state to enforce the behavior.
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.
For those interested, the paper is available here:m a-secur ity.ps.gz
http://www.icsi.berkeley.edu/~tschudin/ps/
Oh no, you're wrong, they've heard of it! :-)
:).
...
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
Is there any way of hacking that besides duplicating the actual device?
Yes, tinkering on the assembler code in the software that checks for the hardware certifacte so it reports okay even if it's not there.
--
Karma 50, and all I got was this lousy T-Shirt.
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.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
Have you read the paper? What you say is clearly obvious, but that's not what the paper is about. They are not proving that you can't run a copy of a software, they talk about retrieving an encryption key hidden inside a program.
-- Slef
I'm going to have to give this another go, because moderators didn't quite catch on. Your point number (2) is where you made a mistake. The DRM can not only make its decision based on the information content but on the DRM's execution environment. If it is able to find _any_ information that is unique to a particular machine (quite easy actually), then it can enforce copy protection through public key cryptography. When the transaction that grants a user a copy of the product in question, the producer can insert a watermark including this unique information and (unforgeably) digitally sign it. The DRM can then check that the signature is correct and matches the unique identifying information. So yes, DRMs can enforce copy protection--through cryptography.
Now, having said that, if the DRM itself is under attack, then it can be altered to not enforce signatures, or (as someone already suggested) run in a sandbox where all unique identifying information can be forged. This is a different problem.
From what I read of the paper, it stopped short of making claims about copy protection, and basically stated that it is impossible to obfuscate a program, not that it was impossible to sign data or verify its source. So, no, it's not obvious, and you are over simplifying an erroneous proof of a claim they didn't make.
120 characters isn't enough to explain it.