Obfuscated Software
August 14, 2013 When I was in graduate school, one of my fellow students commented to a professor that he would be happy when he got his degree, since he wouldn't need to take any more tests after that. The professor replied that after his Ph.D., every working day as a scientist would be a test. You're always being judged by your peers; and, most importantly, by the funding agencies. As a personal example, at the end of a staff meeting, our research vice president distributed copies of an unsolicited proposal which was routed to him for comment. This was our daily test. We scanned the proposal quickly, and one of the other physicists started to explain that what was proposed violated Heisenberg's uncertainty principle. Actually, he failed his test, since quantum mechanics did not apply. I outlined the problem using classical electrodynamics. As my reward for passing my daily test, I was the one who had to write the report! When at school, your reward for passing a test is a good grade and a slight forward movement towards your degree. Outside of academia, your reward is usually your salary, occasionally the esteem of your colleagues, and sometimes a monetary award. Mathematicians can reap a huge reward by solving one of the Millennium Prize Problems, valued at a million dollars each, and there are large monetary awards in all major fields. Often, competitions are devised whose only award is the recognition of your colleagues. One such competition that I've followed for more than two decades is the International Obfuscated C Code Contest.[1] The goal of this contest is the creation of working programs in the C programming language which are nearly impossible to decipher. I could insert a joke here about my own C programs, but I won't. C is a good language for such a contest, since it's oblivious to whitespace, and it has several language constructs that lend themselves to obfuscation. I'll mention, also, an inherently obfuscating programming language, Whitespace, for which any program looks like a blank page. The language is coded using unique sequences of whitespace characters as its syntax. dorssel.c, written by Frans van Dorsselaer of Bakker Industrial Automation, Leiden, The Netherlands. This short program, which compiles without error using the GNU C compiler (gcc), but with a few warnings, converts ASCII characters to Morse code, and Morse code to ASCII characters. However, it's hard to discern its purpose by looking at the source code. This program won the 1998 Obfuscated C award for "Obsolescent Feature." Although such a program is obfuscated, its decoding is not impossible. After all, an experienced programmer wrote the program, so reverse-engineering by another experienced programmer should be possible. When we do obfuscation by an algorithm, however, things will get harder if the algorithm is unknown to the decoder. PHP is an interpreted language, so the only way its programs can be distributed is by source code. There are obfuscator programs available which are designed to automatically obfuscate your PHP programs to prevent their being modified; and, perhaps redistributed by others claiming the program as their own. These obfuscator programs still produce code that's decipherable, albeit with considerable difficulty. A team of computer scientists from UCLA, IBM Research and the University of Texas at Austin has just developed an obfuscator approach for which reverse-engineering requires the solution of mathematical problems so complex that their solution would take hundreds of years.[3-4] Their approach is described in a 46-page paper scheduled for presentation at the 54th Annual IEEE Symposium on Foundations of Computer Science, October 27-29, 2013, at Berkeley, California.[4] authors liken it to a mathematical jigsaw puzzle, as artistically pictured above.[3] Says coauthor Amit Sahai, who specializes in cryptography at UCLA's Henry Samueli School of Engineering and Applied Science,
"The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional... It's a question that a lot of companies have been interested in for a long time... You write your software in a nice, reasonable, human-understandable way and then feed that software to our system... It will output this mathematically transformed piece of software that would be equivalent in functionality, but when you look at it, you would have no idea what it's doing."[3]
 | Professor Amit Sahai of UCLA. (UCLA Engineering photograph.) |
References:
- International Obfuscated C Code Contest Web Site.
- Brian W. Kernighan and Dennis M. Ritchie , "The C Programming Language," Prentice Hall (Englewood Cliffs, New Jersey), First Edition, 1978, ISBN-10: 0-13-110163-3, paperback: 228 pages.
- Matthew Chin, "Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software," UCLA Press Release, July 29, 2013.
- Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai and Brent Waters, "Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits," July 21, 2013, Paper prepared for the 54th Annual IEEE Symposium on Foundations of Computer Science, October 27-29, 2013, at Berkeley, California.
- Brian W. Kernighan and Dennis M. Ritchie , "The C Programming Language," Prentice Hall (Englewood Cliffs, New Jersey), First Edition, 1978, ISBN-10: 0-13-110163-3, paperback: 228 pages.