Theoretical computer science teaches that some computational problems are much more difficult than others. Very hard problems scale exponentially. Other problems are solvable in Polynomial time, but only using an oracle that can correctly decide which path to follow each time a choice is encountered. The second set of problems is termed NP. One of the most perplexing problems in computer science was introduced in 1977 by three cryptography researchers named Rivest, Shamir, and Adelman. They invented a sophisticated encryption algorithm called RSA, (after their initials). The only known Achilles Heel of the RSA cryptosystem rests on the ability (or rather, inability) to factor a very large integer into a product of prime numbers in a reasonable length of time. The exact complexity of prime factoring is not known, but it is expected to be difficult and has proven to be so thus far.
One particular instance of the RSA problem involves factoring a specific 129-digit number into its prime factors. Using theoretical computer science as a guide, Rivest, Shamir, and Adelman estimated that it would take 4 x 1016 years to factor RSA-129. However, applying the quadratic sieve algorithm along with the collaboration of thousands of volunteers (who donated CPU time on their workstations), researchers solved RSA-129 in 1994 after less than a year of work. The key to the solution was using thousands of computers at the same time to attack the factoring problem. To prove that they had discovered the proper solution, the distributed-factoring researchers used their solution to break a secret coded message that Rivest, Shamir, and Adelman had created in 1977 as a test. The message read, "The magic words are squeamish ossifrage."
Java offers a unique opportunity for use in cooperative projects such as factoring RSA-129. Some of the researchers involved in factoring RSA-129 recently announced they had also factored RSA-130-in a fraction of the time. Java would make cooperative efforts much easier through platform independence.
So what does this have to do with malicious applets? One critical feature of the RSA efforts was the voluntary participation. That is what made them cooperative efforts. The same sort of factoring could be accomplished using a malicious applet. Such an applet would surreptitiously steal CPU cycles from the machine of any Web user who hit its Web page. The applet would spin a thread on the remote machine to run part of a factoring solution on that machine's CPU. After a sufficient amount of work, a partial solution could be mailed back to a collection site for collation with similar results from elsewhere.
There is no reason a CPU-cycle-stealing applet needs to work on factoring. It can perform any work. Using such an applet, a Web miscreant could instantly upgrade his or her 486-DX2/66 into a huge collective machine with the combined power of hundreds of workstations. Workstations around the world could be automatically pressed into service. Imagine the dismay of a CEO who discovers that her new Whiz-bang 4200+ has been helping compute results for a competitor. Or imagine the legal ramifications in store for the owner of a government machine that inadvertently helps a foreign national break an encryption algorithm. Or imagine a computer hardware manufacturer who specs out a competitor's machine using a stealthy benchmark applet. The possibilities are many.
Chapter... Preface -- 1 -- 2 -- 3 -- 4 -- 5 -- 6 -- 7 -- 8 -- 9 -- A -- B -- C -- Refs
Copyright ©1999 Gary McGraw and Edward Felten.