harrisj · January 25, 2014 01:08
diff --git a/toasternet.html b/toasternet.html
 <HEAD>
 </HEAD>
 <BODY>
 <H1 ALIGN=CENTER>Toaster Net:  Design and Feasibility Analysis of a Java-Based Key Search System</h1>
 <H2 ALIGN=CENTER>12/9/96</H2>
 <H2 ALIGN=CENTER>Jake Harris, Katy King, Darrin Jewell</H2>
 <HR> 
 <H2>Abstract</H2>

 <P>As recent RSA factorization efforts have shown
 (FAFNER, RSA-129, others), a virtual Internet computer that leverages
 the computational power of various systems on the Net can be quite
 powerful.  Many past techniques have involved for such a web-based
 computer have been implemented with native C code on a few dedicated
 machines and a significant amount of human involvement and
 coordination.  With the advent of Java, it is possible to create a
 distributed Internet computer without some of the limitations of this
 conventional approach.  Given these advantages, it is not surprising
 that various people have thought about applying such Java-based
 Internet Computers to difficult problems such as RSA factorization or
 DES Challenges.  This paper outlines a Java-based system, Toaster Net,
 for breaking a DES key by brute force, and analyzes the feasibility of
 such a system.  We conclude that the system borders on feasibility in
 the present day, and will be fairly practical in the near future.</P>

 <HR>
 <H2>Table of Contents</H2>
 <UL>
 <LI><a href="#intro">1 Introduction</a>
   <UL>
   <LI><a href="#recent">1.1 Recent Examples</a>
       <UL>
       <LI><a href="#rsa-129">1.1.1 RSA 129</a>
       <LI><a href="#fafner">1.1.2 FAFNER</a>
       <LI><a href="#gimp">1.1.3 The Great Mersenne Prime Search</a>
       <LI><a href="#trei">1.1.4 Peter Trei's DES Key Search</a>
       </UL>
   <LI><a href="#java-intro">1.2 A Java Based Approach</a>
   </UL>
 <LI><a href="#impl">2 Implementation</a>
   <UL>
   <LI><a href="#criteria">2.1 Design Criteria</a>
   <LI><a href="#applet">2.2 The Applet</a>
   <LI><a href="#server">2.3 The Server</a>
       <UL>
       <LI><a href="#server-db">2.3.1 Details of the Server Database</a>
       </UL>
   </UL>
 <LI><a href="#feasibility">3 Feasibility</a>
   <UL>
   <LI><a href="#java-limitations">3.1 Limitations of Java</a>
   <LI><a href="#quant">3.2 A Quantitative Estimate</a>
   </UL>
 <LI><a href="#other">4 Other Issues</a>
   <UL>
   <LI><a href="#scalability">4.1 Scalability</a>
   <LI><a href="#extend">4.2 Extensibility of Ideas</a>
       <UL>
       <LI><a href="#screensave">4.2.1 Screensavers</a>
       <LI><a href="#toaster">4.2.2 Toaster Net</a>
       </UL>
   <LI><a href="#ethics">4.3 Ethical Concerns</a>
   </UL>
 <LI><a href="#concl">5 Conclusion</a>
 </UL>

 <HR>

 <a name="intro"><H2>1 Introduction</H2></a>

 <P>A large part of cryptographic security relies on ``computationally
 secure" algorithms. This security depends on the practical
 impossibility of a brute force attacker solving a difficult problem
 (e.g., a brute force key space search, factorization, discrete logs,
 etc.) whose solution is required to figure out a user's key. Such
 problems demand computational resources far above the power of the
 fastest supercomputers, leading many people to declare absolute
 confidence in the security of the cryptographic protocol. Of course,
 some problems (such as DES key search) can theoretically be solved
 quickly with a specialized computer, but the impracticality or cost of
 such designs made this an unlikely threat in the past. Now that is no
 longer the case; Michael Wiener designed a parallel machine that can
 figure out a DES key by brute force in less that two days for as
 little as $ 100,000. [<a href="#wiener">15</a>] Still, many users feel
 this is merely an expensive toy and not really a threat to DES.</P>

 <P>Recent years have been marked by the explosive growth of the Internet
 and the World Wide Web. If we imagine the World Wide Web as a giant
 parallel computer, with each client as a computational node, we can
 the see the attractiveness of the Web Computer paradigm. [<a
 href="#web-computer>4</a>] Even if we could only harness a small
 fraction (by politely borrowing cycles) of the estimated 10 million
 hosts [<a href="#gen-magic">10</a>] on the Internet for our
 computational problems, we still would have a fairly large number of
 machines at our disposal to attack any parallel problem. Since it
 merely involves borrowing cycles off of various computers, this is
 also one of the cheapest massive parallel machines around. Of course,
 a given node of the Web Computer will perform much slower (due to
 communication overhead, borrowing spare cycles only, and other
 factors) than a node in an actual parallel processer machine. No
 matter, the web computer has the advantage of sheer size; we can
 distribute a parallel program among thousands or tens of thousands of
 nodes at practically no cost, thus making up in number for lack of
 individual processer power.</P>

 <a name="recent"><h3>1.1 Recent Examples</h3></a>

 <P>Several recent examples of massive computational projects have
 illustrated the potential of the Web Computer paradigm. All of these
 have been initiated in the last few years and serve to demonstrate
 examples of some of the various types of problems that can be
 destributed across the web.</P>

 <a name="rsa-129"><H4>1.1.1 RSA 129</H4></a>

 <P>In 1994, a team led by Arjen Lenstra coordinated a world-wide
 effort over the Internet to factor RSA 129.  Hundreds of volunteers
 downloaded code and donated spare cycles on their computers to aid in
 factoring this big number.  They reported results back to the
 coordinating team via email. [<a href="#npac">8</a>] The algorithm
 used was the Multiple Polynomial Quadratic Sieve, an easily
 distributed factoring algorithm developed starting in 1981.  The team
 chose not to use the newest factoring algorithm, the number field
 sieve, because the quadratic sieve was known, well tested, and at that
 time considered better. [<a href="#sieves">9</a>].</P>

 <P>Since then researchers have decided that the quadratic sieve is
 generally better for smaller numbers (less than about 100 digits) and
 the number field sieve is better for large numbers (more than about
 130 digits).  Within this range it depends on the details of the
 implementation and of the hardware used. [<a href="#sieves">9</a></P>

 <P>It is estimated that RSA 129 took about 5000 MIPS-years, or
 10<SUP>17</SUP> elementary cycles.  Based on our feasibility
 estimates, factoring a 129-digit number is computationally much
 simpler than a DES key search.</P>

 <a name="fafner"><H4>1.1.2 FAFNER</H4></a>

 <P>The FAFNER project was an effort conducted in 1995 and 1996 to
 factor RSA 130 over the Internet.  It used the General Number Field
 Sieve algorithm.</P>

 <P>The GNFS begain as the special number field sieve, developed in 1988
 by John Pollard.  As a "special" algorithm, it only helped to factor
 numbers with certain properties.  It was adapted for the general case
 by 1990, and the general number field sieve has been evolving since
 then.  There are several variations being both used for factorization
 and examined for further development.  It was adapted to a distributed
 system for the FAFNER project. [<a href="#sieves">9</a>]</P>

 <P>FAFNER made use of hierarchical servers so as not to overload any
 one server.  Servers would distribute tasks and collect results, and
 report back to the parent server.  Volunteers could help out by
 varying degrees.  They could download and run the sieving code during
 their computer's idle time, reporting the results back by email.  Or
 they could download the more sophistocated GNFSD software, which ran a
 daemon on their machines to automatically sieve and report back to the
 server.  Finally, they could register to be a FAFNER server,
 distributing tasks to other clients and collecting results, processing
 them and reporting back to the parent server. [<a
 href="#fafner">3</a>] FAFNER used a hierarchical server structure, to
 distribute load among servers to handle the costs of communication and
 coordination.</P>

 <P>The final stages of FAFNER were accomplished off the Internet, at
 Bellcore.  The task of factoring RSA 130 was completed in April 1996.
 The team is now looking to factor RSA 155 in a similar manner.</P>

 <P>The difficulty of factoring numbers goes up by approximately an
 order of magnitude with each added digit.  However, because the number
 field sieve is faster than the quadratic sieve for large numbers, RSA
 130 took only as much (as possibly quite a bit less [<a
 href="#sieves">9</a>]) collective computational power as RSA 129.  We
 can expect factoring algorithms can be expected to continue to
 improve; but much larger numbers such as RSA 155 will still require a
 much larger concerted effort to factor.</P>
 
 <a name="gimp"><H4>1.1.3 The Great Mersenne Prime Search</H4></a>

 <P>More people jump on the bandwagon of Internet factoring.  A large
 group of individuals has coordinated efforts to have people help find
 Mersenne primes from the Mersenne numbers. This approach largely
 mirrors that of RSA-129, although it is currently simpler
 computationally. Compiled binaries are available for people to
 download, and users reserve a key space and check it. Once the
 computation is done, they report the results back to the central
 server. They have had one success so far; less than a month ago,
 2<SUP>1398269</SUP>-1 was determined to be the 35th Mersenne prime.
 The search for the 36th largest prime is still going. [<a
 href="#mersenne">5</a>.</P>

 <a name="trei"><h4>1.1.4 Peter Trei's DES key search</h4></a>

 <P>There is one existing project underway to search for DES keys
 by utilizing distributed internet computing power.  This project,
 led by Peter Trei and the [email protected] mailing list members,
 will distribute hightly tuned C code and intel 486/586 assembly
 in an attempt to brute force attack a DES key.  This approach
 is expecting users to volunteer unused cycles on their machines
 via screensaver or background daemon processes.  Their software
 is able to test 220,000 keys/second on a 100 Mhz Pentium
 computer.  Although they are maintaining a database of people's
 results, the choice to use this database or else to randomly search
 the keyspace is up to the user running the client.  This corresponds
 an expected 5,000 cpu years to complete.  They are hoping to
 get 100,000 machines working on the problem which could find
 the key in a month or so. [<a href="#ptrei">13</a>]</P>

 <a name="java-intro"><h3>1.2 A Java-based Approach</h3></a>

 <P>Although these examples illustrate the power of using the Internet for
 distributed computation, they all suffer from similar drawbacks. For
 starters, these efforts usually are very weakly distrbuted with
 usually only on the order of tens to hundreds of participants. This is
 usually due to the double bind of growing administrative cost
 (coordinating the helpers) and platform-specific code (for
 speedups). The administrative overhead stems from distributing code to
 participants, partitioning out the problem to various users, receiving
 the data, and including it into the final solution. Although some
 systems (like FAFNER) boast scripts for helping out with
 administration, a lot of the coordination and communication requires
 human intervention, limiting how much parallelization can be
 achieved. In addition, several of the systems have relied upon
 sometimes highly platform-specific code (Peter Trei wants to even
 distribute in x86 assembly!), limiting the number of users who can
 help out. Both of these factors reduce the potential power of the Web
 Computer by constraining how widely the problem can be parallelized.</P>

 <P>A Java-based Internet computer fixes these problems by drawng upon the
 portability and flexibility of Java. It should be possible (and even
 simple) to implement a Java-based system with the following advantages:
 <UL>
 <LI> Very portable 
 <LI> Can be run by anyone who loads your webpage
 <LI> No human administrative overhead 
 <LI> Low machine coordination costs 
 </UL>
 The portability of Java, combined with its ease of distribution, allow
 the system to support a larger number of hosts. In addition, a good
 system should be able to handle the human administrative duties,
 allowing for faster server lever performance and even more hosts to
 get involved. It is not unreasonable to suppose that a Java-based Web
 Computer should be able to handle in the order of 1000s or 10,000s of
 client programs with ease. We will present an example design of such a
 system.</P>

 <P>Given these advantages, it is not suprising that other people have
 also thought of using Java for solving problems, often with the
 emphasis on stealing rather than borrowing cycles for factorization or
 key searches. There are already a few example applets in existence [<a
 href="#java1">6</a>, <a href="#java2">11</a>, <a
 href="#java3">14</a>]. Most of these seem to be for nothing more than
 amusement value though, without any serious exploration into the issue
 of distributive large-scale computatational efforts. Although
 everybody seems to have investigated whether it is possible to create
 such a Java-based distributed system, no one seems to checked whether
 it is practical. This paper will propose a basic design for such a
 system and demonstrate its feasibility. To avoid mathematical
 complexity, we will examine a Java-based system for a DES key search.</P>

 <a name="impl"><H2>2 Implementation</H2></a>

 <P>This section of the report presents a simple yet effective
 implementation of Toaster Net, the Java-based distributed scheme for
 doing a DES key search. This example demonstrated the simplicity and
 power of the Java-based Web Computer. We have made several implicit
 assumptions and goals in this design that affect the design of the
 applet, the server, and how they communicate. These criteria follow
 directly from the goals of portability and widespread use outlined
 above.<P>

 <a name="criteria"><h3>2.1 Design Criteria</H3></a>
 <OL>
 <LI> <B>Minimal Communication</B>. This is a consequence of our goal
 to have massive numbers of applets running on many hosts
 simultaneously. Frequent communication between the server and the
 various hosts requires a fair amount of overhead, reduces the
 scalability of the server, and limits the effectiveness of our simple
 implementation. Thus, implementations should involve either no or very
 little communication between the server and the applet.
 <LI> <B>Keep It Simple Stupid</B>. In order to get the wide
 distribution of labor we want, we need a very scalable system. Any
 extra complexity should be avoided for this reason.
 <LI> <B>Flexibility</B>. In order to be adapted for a wide variety of
 problems, this system should be flexible and extensible in both its
 internal calculation engines and applet interface. This can be
 accomplished through correct modularity and abstraction.
 <LI> <B>No Assumptions of User Privileges</B>. If we want to increase the
 widespread use of the applet, it should be possible for participating
 users to include the applet call in the HTML of their pages. This
 should make applet use more widespread than having it served off a
 single server. To make this possible, the applet should not depend on
 the user to have special permissions on their web servers (such as
 running CGI scripts or daemons) for successful execution, since very
 few users have such privileges.
 </OL>

 <a name="applet"><H3>2.2 The Applet</H3></a>

 <P>The Java applet is the essential component of the distributed DES
 keysearch algorithm. The basic applet design is quite simple (code
 included with this report), and the code for the DES search extends
 the Java Thread class. This allows the same DES key search algorithm
 to be used in different applets, and possibly for a sophisticated
 applet to run concurrent key searches on a more powerful
 machine.\footnote{This does not really provide any sort of advantage
 on a random DES key search, but might be useful for other distributed
 applications.} This description of how the applet works assumes an
 adequate knowledge of basic Java classes and the applet lifecycle.</P>

 <P>When the applet begins, it reads several parameters provided in the
 <CODE>applet</CODE> tag embedded in the HTML. If these parameters are
 not specified, the default value specified is used.  
 <UL>
 <LI> <B>Port</B> - The port to be used by the applet to communicate
 success back to the server. See complete description of this
 signalling method below. If no port is specified, a default port is
 used.  
 <LI> <B>Startkey</B> - This specifies the the first key to
 test.  Key search will proceed linearly from this key.  The Startkey
 may be based on a database kept by the server, or it may be a random
 number.  
 <LI> <B>Plaintext</B> - The plain text of a message.  
 <LI> <B>Ciphertext</B> - The resulting ciphertext after encryption with the
 desired DES key. 
 </UL>
 The plaintext and ciphertext are both required for correct
 operation. This method of passing parameters to the applet is quite
 simple, requiring no communication for initialization. The downside is
 that in order to have the server assign starting keys to each applet
 on execution, a CGI script needs to be written to generate a HTML page
 just to change one parameter. This seems like an adequate option where
 the applet is called on only a few pages, but becomes impractical if
 the applet is invoked on a large number of pages and we want the
 server to control starter key assignment.</P>

 <P>Once the applet is initialized, it launches a thread to test a range
 of DES keys, starting from its initial search key. Of course, other
 threads (e.g., for displaying progress or allowing the user to play a
 video game) could also be launched at this time, but they are not
 necessary to the basic operation of the system. This key search thread
 is essentially an infinite loop that iterates until it finds the key
 associated with the plaintext-ciphertext pair or the thread is
 terminated. During an iteration of the loop, the thread checks to see
 if the output of encrypting the given plaintext with the given key
 matches the known ciphertext. If it does, the thread terminates and
 alerts the applet by throwing an exception. Otherwise, it increments
 the key and reiterates the loop.</P>

 <P>The applet uses a DES implementation created by Acme.com and
 provided in a package [<a href="#acme">1</a>] of useful cryptographic
 classes. The implementation is relatively simple right now, but
 surprisingly fast for its basic implementation. The author reports the
 ability to encrypt 7000 blocks/sec using DES on a SparcStation 20 and
 a basic Java compiler. Using an optimizing compiler for generating the
 bytecode and a Just-In-Time compiler boosted performance by an order
 of magnitude or so. More efficient implementations could be achieved
 with better compilers and possibly optimizing the bytecode by hand. It
 should be possible to speed Java execution to be comparable to native
 C code. [<a href="#jit">7</a>]</P>

 <P>When the applet is informed by the thread (via an exception) that a
 key has been successfully found, it attempts to communicate the result
 back to the server. There are several different ways to do this,
 depending on the level of complexity we want at the server end. The
 simplest approach is to use open an HTTP connection back to the server
 and invoke a PUT method to post the information back on the
 server. This is simple, because it does not require the server
 maintainer to write anything more than a CGI script, but it assumes
 access to the server configuration, something that is extremely
 unlikely for most situations. Another approach is to have the applet
 connect to a socket on a the server machine and communicate with a
 daemon process of the server. This requires a bit more software coding
 and the ability to run a daemon on a specific port. Finally, the
 simplist way to do this notification is the {\it Chinese lottery}
 method. Simply have the applet pop up a window telling the user
 they've won and to call a phone number and report this number to
 collect their prize. This is simple enough to be a fallback in the
 case network communication fails, although it carries the slight risk
 of the solution not being reported.</P>

 <P>This applet design should be modular. Even in this simple case, all of
 the interface and communication is handled by the applet class, while
 the actual calculation to be distributed is implemented entirely in a
 different class as a thread. This allows either part to be separated
 out and reused in other applications or replaced with different
 tests. For instance, we could write another applet with a graphical
 progress display and have it call the same code for DesThread, or
 perhaps use the applet design with a RSA class instead. This
 modularity is quite simple and effective; it might be possible even to
 write some interfaces to make such modularity simpler.</P>

 <a name="#server"><H3>2.3 The Server</H3></a>

 <P>A brute force DES key search is a very easy problem to parallelize.
 A test of each key can be independantly calculated without any
 loss of performance.  This still requires that the problem be distributed
 onto a set of target machines, in this case WWW clients supporting 
 Java applet execution.  To support this task, we design a key search task
 server which helps distribute to end users running the Java applet on their
 machines.</P>

 <P>This key search server performs a number of separately identifiable tasks:
 <UL>
 <LI> Distribution of the key search applet.
 <LI> Issuing of specific work to be performed.
 <LI> Maintenance of a database of work performed.
 <LI> Keeping user entertained while we use their spare computation cycles.
 </UL>

 To distribute just the key search applet a key space server can be
 very simple.  Any webserver capable of serving ordinary documents can
 fulfill this function.  No special capabilities, such as server
 executed scripts, are needed.  This is clearly an advantage, since the
 number of people who can server the applet along with their particular
 web attraction will increase significantly.</P>

 <P>There are several important issues which must be considered when
 determining how to assign the actual keysearching tasks to applets,
 including: 
 <UL>
 <LI> Efficiency of searching task.
 <LI> Protection from malicious attacks to the key search.
 <LI> Ease of implementation.
 <LI> Ease of maintenance.
 <LI> Availability of communication to searching clients.
 </UL></P>

 <P>There are two major approaches to task assignment.  One way is to
 allow everyone to randomly search the keyspace, until a key is found.
 The other is to linearly search the keyspace by maintaining a
 coordinated database of completed work. [<a href="#coderpunks">12</a>]</P>


 <P>Now, let us examine some of the influencing parameters of a web applet
 distributed search.
 <UL>
 <LI> <B>Communication</B>. Client applet maintains network connection
 for its execution duration.  However, for security reasons, a Java
 applet can only communicate back to the host from which it was
 distributed.
 <LI> <B>Execution</B>.  For many types of applets, they may only be
 executed for a few seconds or minutes at a time.  This is
 significantly different than a lot of other network based distribution
 schemes, where the searching client would be able to search for days
 at a time.
 <LI> <B>Parallelism</B>.  There may be a very large number of
 simultaneous applets executing at any given time.  Initiating a key
 search becomes part of a users's normal interaction with the WWW.
 <LI> <B>Distribution</B>.  Applets should be served along with varying
 documents from varying sources.  Distributing servers should only need
 to serve simple information, and may not be able to perform more
 complicated communication or computation.
 </UL>

 <a name="#server-db"><H4>2.3.1 Details of server database</h4></a>

 <P>A centralized database offers a couple of important advantages.
 Although a linear search will complete on average by searching half of
 the key space, it is guaranteed to complete within a complete search
 of the keyspace.  In contrast, a random search will be expected to
 complete on average with a search of 2<SUP>56</SUP> keys, but may never
 complete.  In fact, it will often complete with a search of size many
 times that of the keyspace.</P>

 <P>Unfortunately, a centralized database also adds many disadvantages.
 Maintaining the integrity of this database requires a large amount of
 computation and communication by the server.  This can be implemented
 in a straightforward manner by using WWW server scripts.  An example
 of this is the the FAFNER project [<a href="#fafner">3</a>].
 Unfortunately, this does require more sophisticated key space server
 administration, which may significantly reduce the number of WWW pages
 serving keysearches along with their information.</P>

 <P>A database also opens the door for many malicious attacks on the
 key search that are not easy to protect against.  Without duplicate
 calculation, it is not possible to protect against someone using
 the client communication interface to fill the database with false
 search information.  Although we can quickly confirm a key discovery,
 the same is not possible for each rejected key.</P>

 <a name="feasibility"><H2>3 Feasibility</H2></a>

 <P>An important consideration in the design of any system is its
 feasibility.  A design for a number-crunching system is useless if it
 cannot be implemented, or if, once implemented, it takes 10000 years
 to produce an answer.  We deem that a reasonable system will finish
 its calculations in under one year.  In this section we will examine
 the limitations inherent in a Java, and make a quantitative estimate
 of whether we will get results in a reasonable period of time.</P>

 <a name="java-limitations"><h3>3.1 Limitations of Java</H3></a>

 <P>Java contributes remarkable flexibility, portability, and power to
 tackling difficult distributed problems. However, as with every other
 engineering design, there are some tradeoffs involved. There are
 several limitations of Java that may hinder or reject its usefulness
 for certain applications.</P>

 <P>One of Java's greatest strengths is also one of its largest
 weaknesses; being an interpreted language provides portability, but
 also slows down basic execution of Java bytecode to be around 10x
 slower than native C code. This can result in the difference between
 taking days and weeks. Luckily, this is a problem being
 solved. Optimizing and Just In Time compilers should be able to
 provide execution performance roughly comparable to compiled C++. In
 addition, the next few years may see the introduction of Java chips
 that will provide blazing fast execution speed; this chips may be
 incorportated in PDAs or products like WebTV [<a href="#jit">7</a>]. One final
 option may be to hand optimize (or even write) the Java bytecode. This
 should improve the execution speed somewhat.</P>

 <P>Another more serious limitation of Java is its variability. That
 is, traditional distributed schemes (like FAFNER) are able to rely on
 having enough time/memory/CPU time/etc. to execute on a distributed
 machine. Java applets are given no such guarantees of execution time,
 machine memory, and other useful constraints. In most cases, this will
 merely be an additional nuisance for the server to deal with, but it
 is possible that this can limit the applications that can be handled
 by the Java supercomputer. For instance, the Number Field Sieve
 requires at least 7 Megabytes of dedicated memory per thread to
 execute in a reasonable time [<a href="#fafner">3</a>]. It might not
 really be possible to allocate this much dedicated memory with a Java
 applet, eliminating an important application that could benefit from
 the distributed Java-based approach. This may not be an actual
 problem, but it should serve to illustrate the concerns.</P>

 <a name="quant"><H3>3.2 A Quantitative Estimate</H3></a>

 <P>We would like to get a quantitative estimate on how long a key search
 will take using our Java system, in order to better judge the
 feasibility of such a system.</P>

 <P>We are searching a key space of 2<SUP>56</SUP> keys.  If we keep a
 database and have a server distribute search spaces, then the expected
 number of keys we need to try before finding the correct one is half
 of the search space, or $2<SUP>55</SUP> keys.  If instead we do away
 with the central server and do a random search, the expectation goes
 up to 2<SUP>56</SUP>.</P>

 <P>For the purposes of this estimate, we assume that we can get very
 widespread distribution, comparable to that of the Altavista web
 search engine, which claims 23 million hits per day [<a
 href="#altavista">2</a>].  The applet will execute while the user
 reads the page, so we assume a connect time of approximately one
 minute.</P>

 <P>In his screensaver-based DES key search, Peter Trei estimates that
 he can test 50,000 keys per second with a tight C implementation on a
 PC with a 100MHz Pentium processor [<a href="#coderpunks">12</a>].
 Although interpreted Java code is considerably slower, Java code that
 is compiled with a Just-In-Time compiler can be comparable in speed to
 C code [<a href="#jit">7</a>].</P>

 <P>That is, the expected time to find a DES key with random search is:
 2<SUP>56</SUP>/[(5*10<SUP>4</SUP> keys/sec)(60
 sec/connection)(20*10<SUP>6</SUP> connections/day)] 
 = 1200 days or approximately 3 years.</P>

 <P>This is a little longer than we would like the key search to take;
 however, it is not completely unreasonable.  And while some of the
 estimates are on the high bound for today, -- currently only very
 large servers will get 20 million hits per day -- the numbers will
 only improve in the future.  The Java language will improve, and
 processor speed will increase, so that a single computer can test more
 keys in the same amound of time.  Network bandwidth will increase,
 resulting in more hits per day.  People will rely more on the Web,
 yielding a longer average connection time.  In short, Toasternet is
 almost feasible now, and will almost certainly be feasible in the near
 future.</P>

 <a name="other"><H2>4 Other Issues</H2></a>

 <a name="scalability"><H3>4.1 Scalability</H3></a>

 <P>With any large distributed system like this, scalability is a major
 concern. As was noted previously, the traditional approaches to such
 distributed computation scale poorly, usually due to administrative or
 communications overhead. The communications overhead in such systems
 is results all the talking between various computational clients and
 servers required to maintain internal databases. As the number of
 participating clients grow, the cost of such communication blows
 up. Another problem with all these systems is that they require a fair
 amount of human involvement. This usually involves such tasks as
 assigning search spaces to various participants and interpreting the
 results. Humans do not scale well; it is far more difficult for
 anybody to coordinate among thousands of machines than tens to
 hundreds. These two factors serve to limit the scope of the
 distributed solutions in the traditional approaches.</P>

 <P>Heeding their example, we have explicitly designed our Java-based
 system to avoid such bottlenecks and scale well. Using the example of
 the DES key search algorithm, there is minimal communication between
 the server and the client. In the simplest case of a fully random
 search, there is even no need for a server at all, and the only
 communication results from success. In addition, there is no necessity
 for human coordination, because such issues should be handled
 intelligently by the server. This allows us to avoid such scalability
 problems and potentially execute our applet on thousands or millions
 of clients without problems. This design philosphy is not just
 specific to our DES search implementation only, but should be
 applicable to implementations of other difficult problems (e.g., RSA
 factorizations).</P>

 <a name="#extend"><H3>4.2 Extensibility of Ideas</H3></a>

 <a name="#screensave"><H4>4.2.1 Screensavers</h4></a>

 <P>The same idea can be implemented in many different ways.  Other
 networked computation efforts have shown this.  An interesting idea is
 that of implementing factoring or key search as a screensaver.  As we
 have discussed elsewhere, Peter Trei is actively researching and
 coding exactly such an application.  Although it will not likely run
 on as many hosts as a Java applet, his application will get a lot more
 performance from each host it does run on.</P>

 <a name="toaster"><H4>4.2.2 Toaster Net</H4></a>

 <P>The name of our Java system originated in a futuristic idea.
 Suppose, a company which sold toasters decided to take advantage of
 their business to solve a computationally difficult problem.  They
 could include in each of their toasters an extra microchip which would
 be dedicated to number-crunching on this problem.  Once it found an
 answer, it would communicate back to the toaster company the result of
 its computation.  It would using the network access that every
 household appliance -- especially toasters -- presumably have at this
 point in the future; hence, Toaster Net.  Another approach for this
 communication would be to have the toaster suddenly stop working when
 a result is found, and keep all toasters sold under lifetime warranty.
 When a customer returned a ``broken" toaster to the company, the
 company would remove the computation chip to find the answer they
 wanted, re-enable the toaster, and return it to the customer.  This is
 of course on the edge of ethical conduct, but who knows?  Maybe
 someday this won't be such a ridiculous idea.  Maybe we <i>will</i>
 have networked toasters.</P>

 <a name="ethics"><H3>4.3 Ethical Concerns</H3></a>

 <P>There are definite ethical concerns in designing a our system.
 Security holes aside, the very nature of Java allows applets to do
 their computation on the host computer, and to communicate back to
 their server, both without informing the client of such actions.  By
 downloading and running an applet, users are agreeing to let the
 applet ``do its stuff."  However, users generally expect that the
 applet is doing nothing more than what it appears to be doing.</P>

 <P>Our goal is to get as much total computation time as we can, to
 improve our chances of breaking the key.  How can we best distribute
 the applet so more people will run it?  We have concluded that a
 single small server will not suffice; we need a much wider
 distribution to finish the computation in a reasonable amount of
 time.</P>

 <P>If we advertise the applet for what it is, there is the chance that
 people will not run it, either because they have no interest in
 donating their machine cycles to factoring, or because they are afraid
 of an applet doing something that they cannot see.  To get around
 this, our applet could easily masquerade as a game -- or as nothing at
 all -- and disguise the fact that it was using the host's resources to
 solve a problem and reporting the results back to the server.  Or it
 could it could claim to be primarily a game, but explicitly tell the
 user that it is doing computations other than for the game.  Our
 design leaves this decision to the implementer incorporating it into
 their web documents.</P>

 <a name="concl"><H2>5 Conclusion</H2></a>

 <P>New web based technologies such as Java allow for the automation of
 distributed computing as a side effect of everyday operations.  This
 opens up the door for a significant increase in the number of machines
 that can share a distributed parallel computing problem.  We are on
 the horizon of being able to factor DES keys by brute force by simply
 sharing a little bit of everyone's computer while they search the net.
 Although not quite possible today, as Java popularity increases,
 solving computationally intense problems using Java applets may become
 entirely feasible and popular.</P>

 
 <HR> 

 <H2>Bibliography</H2>

 <CITE> 
 <P><a name="acme">1</a>. ACME Laboratories.  The Acme.crypto library.<BR
 http://www.acme.com/java/software/Package-Acme.Crypto.html</P>

 <P><a name="altavista">2</a>. Digital Equipment Corporation.  AltaVista
 Search.  http://altavista.digital.com.</P>

 <P><a name="fafner">3</a>. "FAFNER: Factoring via Network-Enabled
 Recursion."  http://cooperate.com/cgi-bin/FAFNER/factor.pl.</P>

 <P><a name="web-computer">4</a>. Fox, Geoffrey C. and Furmanski Wojtek
 "The Use of the National Information Infrastructure and High
 Performance Computers in Industry." July, 1995.
 http://www.npac.syr.edu/users/gcf/sccs732/html/index.html</P>

 <P><a name="mersenne">5</a>. "The GREAT Internet Mersenne Prime
 Search." 
 http://ourworld.compuserve.com/homepages/justforfun/prime.htm.</P>

 <P><a name="java1">6</a>. LaDue, Mark.  "A Collection of Increasingly
 Hostile Applets" 
 http://www.math.gatech.edu/~mladue/HostileApplets.html</P>

 <P><a name="jit">7</a>. McManis, Chuck.  "Just In Time Compilation: A
 look at the technology that turbo charges Java applications."
 September 16, 1996. 
 http://www.javacats.com/us/articles/chuckmcmanis091696.html</P>

 <P><a name="npac">8</a>. Northeast Parallel Architectures Center at
 Syracuse University.  "The RSA Factoring-By-Web project." 
 http://www.npac.syr.edu/factoring.html. </P>

 <P><a name="sieves">9</a>. Pomerance, Carl.  "A Tale of Two Sieves."
 <I>Notices of the American Mathematical Society.</I>  Vol. 43, No. 12.
 December 1996.  pp. 1473-1485.</P>

 <P><a name="gen-magic">10</a>. Rutkowski, Tony "Internet Trends."
 August 1996. http://www.genmagic.com/Internet/Trends/</P>

 <P><a name="java2">11</a>. Southwest Cyberport.
 Digicrime. http://www.digicrime.com/</P>

 <P><a name="coderpunks">12</a>. Trei, Peter. "[DES] Random vs Linear
 Keysearch."  Email from [email protected] to [email protected].
 Thu, 24 Oct 1996 16:29:05 -6</P>

 <P><a name="ptrei">13</a>. Trei, Peter.  Personal email from
 [email protected] to [email protected].  Tue, 10 Dec 1996 10:48:34 -6</P>

 <P><a name="java3">14</a>. Voelker, Geoff and McNamee, Dylan.
 http://www.cs.washington.edu/homes/voelker/classes/FactoringClient.java
 <BR> <I>This source was discovered after the applet code had
 been specified and written.</I></P>

 <P><a name="wiener">15</a>. Wiener, Michael J. "Efficient DES Key
 Search." August 20, 1993.
 http://www.digicrime.com/des\_key\_search.ps.Z</P>
 </CITE>