Distributed Source Cryptography
Offers Security for a Distributed Web
Clifton Davis and Christoph F. Eick
Department of Computer Science, University of Houston
Abstract - The barriers to ubiquitous strong cryptography for low volume distributed information applications, as exemplified by many interactive applications on the world wide web, are analyzed. We propose a cryptographic protocol, Emperor, heavily influenced by Diffie-Hellman and El Gamal protocols whose chief virtue is it's inherent failure to violate the laws protecting intellectual property. A simple extension is also discussed which allows for password encrypted signatures, providing authentication and non-repudiation. We make a modest proposal whose successful implementation would allow free use of this protocol on the web without violating either intellectual property laws or laws prohibiting the export of strong cryptographic software.
1. Introduction
Distributed systems, if they are to be secure, must incorporate sufficiently strong encryption. The barriers to ubiquitous cheap secure cryptography are more social than technical. The most effective social barriers are legal ones motivated by concerns of both national security and law enforcement. In many cases these are legitimate concerns. The pursuit of these concerns, however, is limited in most modern democracies by various protections of the rights of individuals. Because of these limitations, the barriers to the free use of strong cryptography in the United States have at times taken such bizarre forms as the classification of cryptographic software as munitions ([14] and [3]), although less bizarre applications of the laws protecting intellectual property have also been used.
In this paper we focus on a distributed information propogation system which is familiar and in some respects, very simple, the World Wide Web, although the issues involved will arise in any widely distributed information system which is international in scope. For the sake of an example problem we hypothosize a small web developer of limited resources who wishes to design web pages from which a browser can send a text string, such as a credit card number, password, or small document, using strong cryptography who's features, including relative strength, can be publicly inspected. We will show that the existing legal barriers are, in fact, insufficient to prevent such usage.
We begin by reviewing the legal and practical difficulties encountered in a straightforward attempt to use strong cryptography across the web. We follow this with a formalized abstraction of information transfer which shows why export limitations are insufficient. This is followed with a brief analysis of a secure cryptographic protocol not protected by patent, the Diffie-Hellman Key Exchange [6]. We propose a somewhat novel public key cryptosystem1 based on this protocol suitable for the exchange of low volume information using web forms. This is followed by an examination of some of its properties. Finally, we will look at a variety of practical issues relating to the implementation of the proposal and its relevance to (internationally) distributed systems in general.
2. The Troubles of Bob
Imagine for the sake of an example the case of a small, but computer literate, business man, Bob (see figure 1), who wishes to receive credit card information from a customer, Alice, on the internet. Further, assume that Bob either does not have access to, does not trust, or simply does not wish to use a commercial secure server. Our hypothetical
1Throughout, for reasons we hope will become apparent, we refer to our cryptographic system as Emperor protocal and our complete proposal as project Emperor, named after the Emperor in the 1837 Hans Christian Anderson tale, "The Emperor's New Clothes".
businessman visits the library and ascertains that RSA [11] is a major cryptographic protocol which is easy to understand. He consults Knuth [9], on the implementation of multi-precision arithmetic. Then he designs his web page.
Figure 1 - Bob and Alice
Figure 2 - Bob's Web Page
Bob designs his new web page to contain a form (such as depicted in figure 2 which would result from HTML code [2]similar to that shown in listing 1) where a text entry area is reserved for entering the credit card number. When Alice clicks on the "encode" button, the contents of the form will be changed to an RSA encrypted form on Alice's computer using a function rsaencrypt which Bob has written in JavaScript [8]. When Alice hits the "send" button, then (as shown in figure 3) the encrypted value is transferred to the CGI program [5] on Bob's machine which stores the encrypted value for later decryption and order processing.
Listing 1: HTML for Bob's Web Page
<html>
<head> <title>Bob's Web Page</title>
<script language="JavaScript">
<!-- hide from other browsers
function rsaencrypt(message) {
//...Omitted body of rsaencrypt function to comply with applicable laws
//...Omitted definition of checkorder to save space
}
// stop hiding from non-JavaScript browsers -->
</script>
</head>
<body>
<h1>BOB'S STUFF</h1>
<form name=ordering
method=post
action="/cgi-bin/bobs.cgi">
<b>Order Form</b>
<br>
<table><tr>
<td> Name, Address, Stuff
<br>ordered, and other
<br>ordering information:
</td>
<td> <textarea name="orderstuff"
rows=5 cols=25>
onChange="checkorder(form.ordering.orderstuff);"
</textarea>
</td>
</tr></table>
<table><tr>
<td>Credit Card Number:</td>
<td>
<input type=text name="cardnum">
</td>
</tr></table>
<p>
<input type=button
value="Encrypt"
onClick="form.ordering.cardnum=rsaencrypt(form.ordering.cardnum);">
<input type=submit value="Send">
<input type=reset value="Clear">
</form>
</body></html>
Figure 3 - Bob's Information and Alice's Information
Unbeknownst to Bob, the message from Alice to Bob is monitored (as shown in figure 4) by the internationally infamous hacker, Helsinki Harry. Harry records Alice's encrypted information. Although Alice's credit card number is securely encrypted using Bob's Public RSA key - Harry cannot decrypt it - Harry proceeds to use the encrypted form of the credit information to order half of Bob's entire stock. Bob, believing that he is having a banner year, thanks to his newfound best customer, borrows from the bank to expand his operations. The process comes to an abrupt halt, however, when Alice receives her credit card bill. Surviving her initial heart attack, Alice declines payment. Not until he receives the charge-backs does Bob realize that he now has problems (as shown in figure 5).
Figure 4 - Bob and Alice and Harry
Bob has taken a loss from being defrauded and must spend money to replenish his stock. The bank, understandably, is concerned about their money which was loaned on a false premise. However, Bob finds that the lawyers representing RSA Incorporated also want money for his unlicensed use of the company's intellectual property. This is rather too bad, because Bob's lawyers will be wanting the money to talk to the gentlemen from the government who are concerned about Harry's unlicensed world wide export of sensitive materials critical to the security of the United States. Bob's situation is grim (see figure 6).
Figure 5 - Bob and Bob's Problems
It is easy to pinpoint the sources of Bob's problems. There are three:
Our goal with project Emperor is to achieve the full functionality of Bob's Web Page without the attendant problems.
Figure 6 - Bob Behind Bars
3. Export Laws: The Workaround
Project Emperor seeks to provide cheap strong cryptography for the World Wide Web in a open inspectable form which can be trusted and is easily accessible. Each of the three problem sources which Bob encountered must be addressed. The most troublesome issue is violation of export laws.
The web, like the internet generally, is international in scope. Cryptographic functionality can be added to the Web by direct inclusion within browsers, by the use of "helper" programs or "plug ins", or by the use of applet code written in Java or JavaScript. The international distribution of each of these is severely crippled by export laws. Where distribution to an anonymous user is made using the internet, as is desirable, the problem is compounded by the existence of top level domains, such as .com, which are international in scope. The problem is also compounded by the requirement that either the cryptographic functionality come from a trusted source or be publicly inspectable, preferably both, but in any case allow potential users such as Alice to determine the relative strength of the keys being used before trusting it with her data.
Formally, software distribution of strong cryptography over the internet may be modeled by a directed graph, G, Such that there is an arrow from node x in G to node y in G, (x,y) if and only if it is legal to distribute strong cryptography from x to y. Given the size of the internet and the potential number of directed graphs, the model would be useless were we not able to make some simplifying assumptions.Assumption 1: We assume that there is a relationship defined on G called country, such that country(x,y) if and only if x and y are in the same country so that country is an equivalence relationship for G.
Assumption 2: We assume that if country(x,y) then (x,y) is in G, so that there are no restrictions on distributing strong cryptography in the same country.
Assumption 3: We further assume that if it is not legal to make one distribution to another country, the distribution to that country cannot be made legal by selecting another source in the same country as the source, or selecting another destination in the same country as the destination. Specifically, if country(x,x') and country(y,y'), then if (x,y) is not in the directed graph, G, then neither is (x,y') or (x',y).
These assumptions are sufficiant to prove a trivial but useful Lemma.
Lemma 1: For x,y,x',y' all in G such that if country(x,x') and country(y,y'), then (x,y) is in G if and only if (x',y') is also in G.
Proof: First we show that if (x,y) is not in G, then (x',y') is not in G. Assume that (x,y) is not in G. Then (x',y) is not in G either by Assumption 3. But then, by the Assumption 3, since (x',y) is not in G, then (x',y') is not in G. If (x'y') is in G then (x,y) must be in G also since if (x,y) were not in G then (x',y') would not be in G. But by Assumption 1 we have country(x',x) and country(y',y) and by a symmetrical argument, if (x,y) is in G then (x',y') must be in G.
The effect of Lemma 1 is that we can concentrate our attention on the equivalence classes of G created by the country relationship (see figure 7). Let H be the collection of all such non-empty equivalence classes. Now, consider the directed graph
G defined over H. For any two equivalence classes, X and Y in H, we let (X,Y) be in the graph G if and only if there is some x in X and y in Y such that (x,y) is in G. From Assumption 2 we have (X,X) in G for every X in H.
Figure 7 - Relation of Directed Graphs
A directed graph,
G , will be said to be complete if there are no import or export restriction, i.e. if for any distinct X and Y in H, (X,Y) is in G . The closure of G , is the directed graph G '*, such that (X,Y) is in G * only if either (X,Y) is in G or there is some Z in H such that (X,Z) is in G while (Z,Y) is in G *. Import restrictions on strong cryptography preventing any distribution from outside a country would result in an isolated country class X such that for any Y in H distinct from X, (X,Y) is not in G . Such an import restriction would effectively isolate that one country without any great effect on the rest of G. On the other hand, export restrictions for X that resulted in a directed graph, G , such that for any Y in H distinct from X, (Y,X) was not in G , could be more troublesome, particularly if X contained many software sources. On the other hand, it might be possible for G to contain many partial export restrictions, while the closure of G , G '*, is a complete graph.The worst case, where
G is totally disconnected by universal export restrictions, is the most challenging. In such a case the only effective option for universal use of strong cryptography would be for each country to have an independent source where each of the individual sources conformed to a common standard. The problems with this approach are extensive. Not every country in H may have a suitable source. Internet distribution which guarantees that the restrictions on G is not violated is difficult, if not impossible, to implement. This would effectively rule out the use of applet based cryptography, and since the browser market is currently dominated by only two ultimate sources, strong cryptography implemented within the browser is effectively eliminated as well. Independent helper programs which are distributed off line in source code meet the requirement for inspectability. Any helper program would have to be carefully crafted to interact with the browser's application. To refer back to our example, only Bob would know that for his application a single text area containing name, address, and all other ordering information was a reasonable thing to do.While helper programs can meet the technical requirements, the combined inconvenience of independent development in each country with independent testing for conformance to the standard, off-line distribution, the requirement for users sophisticated enough to compile and set up helper programs in advance of the need for strong cryptography, and the need for the helper program to interact tightly with the browser, all taken together restrict the promise of cheap universal cryptography.
Fortunately things are not that bad. If
G contains any universal exporter, X in H, for which each Y in H is such that (X,Y) is in G , then any x in X may be lawfully used to distribute strong cryptography universally (as depicted in figure 8). For the sake of an example we will assume Germany in H to be such a universal exporter and www.crypto.de to be a node of G in Germany.
Figure 8 - A Universal Exporter
The existence of a universal exporter does not necessarily make incorporation of strong cryptography into the browser more attractive, particularly if the ultimate source of these browsers is not inside any universal exporter. While the use of helper programs becomes more convenient, the difficulty of providing both convenience and inspectability plus the difficulty of smoothly integrating the cryptographic functionality into the users application, both remain challenges. There is in fact a great deal to be said for Bob's approach of using JavaScript, as it is designed to integrate with HTML code, does not require separate compilation, and can easily be inspected from the browser, making it easy, for example, for a user of comparatively minimal sophistication to verify the key size used for herself. The chief difficulty lies in the fact that Bob and Bob's computer may not reside in a universal exporter.
The World Wide Web is designed to exhibit distributed source functionality. A web page is typically a composite document put together in the browser from multiple segments represented by distinct URLs. There is no restriction that the various segments must come from the same source. A pertinent example is an image maintained at the URL http://www.dcs.ex.ac.uk/~aba/obscura/wrnblack.gif in the UK specifically for the purpose of working around the export restrictions.2 This image contains an implementation of the RSA algorithm in the language Perl [13]. As a non-functional image it violates neither patent restrictions, nor the export laws of the UK. On the other hand, a web page in a country which prohibits such export can effectively provide such an image by providing the information as to where such an image is located. By including the HTML code used in Listing 2, an individual in an export restricted country distributes only that code, yet a browser receiving that code may import the appropriate image from the UK and create a composite document whose functionality is the product of its component parts. A forbidden export has not taken place, because the information has never resided in the country from which its export is forbidden.
Listing 2: Bob's Revenge
<html>
<head> <title>Bob's RSA page</title>
</head>
<body>
<hr>
<h1>Bob's RSA page</h1>
<center>
<img src="http:// www.dcs.ex.ac.uk/~aba/obscura/wrnblack.gif"
alt="[Image of Perl RSA (interpretable) source code]">
</center>
<p>
Note: Image imported from UK courtesy of
<a href="http://dcs.ex.ac.uk/~aba/">Adam Back</a>.
<hr>
</body></html>
2That and selling T-shirts. See http:// www.obscura.com/~shirt/ .
Figure 9 - Project Emperor Avoids Illegal Exports
For project Emperor (see figure 9) we follow exactly the same procedure to obtain strong cryptographic functionality without violating exportation laws. We begin by replacing Bob's initial web page using the HTML code in listing 3. This code establishes a web page consisting of two frames. The first frame, however is unusual in that we assign it no screenspace what-so-ever. The second frame then gets all the display space. The source of the first frame is, as we established earlier for the sake of an example, in Germany. The second frame is simply a local file in the same namespace as Bob's web page. As in the case of the image, the browser will import the component parts to create the combined functionality required, causing them to be exported only where it is legal to do so.
The general form of the first frame is shown in listing 4. Since the frame was assigned no screen space, the actual contents of the page will not be seen unless someone accesses the page directly. The second frame, which is shown in listing 5, follows the general form of Bob's original web page, but with some significant differences. Now the head of Bob's web page no longer defines a cryptographic function, but instead defines public key information. This public key information may be too large to be represented by single integers, as we show here for simplicity, but we will address this later. The unencrypted order information is sent as before. When the card number is encrypted, not only is the card number used but the rest of the order information is appended after two number termination symbols "||". Since the order and card number are encrypted jointly, the unencrypted order information can later be checked for consistency with the encrypted order.3 Finally, note should be taken that rather than using a function "encrypt" Bob's frame uses the function "parent.frame[0].encrypt" which specifies the fact that the encrypt function defined in the 0th frame of the parent web page should be used by the browser.
3Although we specify encrypting an appended version of the order information, in practice encryption with an appended digest of the order information would be sufficiant.
Listing 3: HTML for Bob's New Web Page
<html>
Listing 4: Structure of Frame with Cryptographic Functionality
<html>
Listing 5: Approximate HTML for Bob's Web Frame
<html>
By dividing the functionality of the completed web page into component sections and exporting the components only from locations where such export is legal, we have a complete workaround for achieving strong cryptography without violating export laws. All that remains to make project Emperor feasible then is to provide a form of strong cryptography which does not violate international (or national) intellectual property laws. Bob was fortunate that someone had created exactly the functionality he needed from a country where universal export of strong cryptography is legal. Bob himself could not have placed the cryptographic functionality there as he would have had to export it to do so. We will address the possible motivations of his benefactor in a latter section.
4. Free Security
The Diffie-Hellman key exchange is, as previously remarked, a cryptographic protocol which is not protected by patent. Its cryptographic security depends on the difficulty of finding discrete logarithms.
To use the Diffie-Hellman key exchange protocol, Bob and Alice, or their computer agents, must first agree on two integers, N and g which constitute an agreement to do arithmetic in the multiplicitive group generated by the powers of g in ZN, the integral domain consisting of the integers modulo N. Bob selects a privately held value, x and sends the value of gx to Alice. Alice selects a privately held value, y and sends the value of gy to Bob. Now both can calculate the value of (gx)y = (gy)x. Someone, such as Harry, who monitors their communications so that the values of N, g, gx, and gy are all known, has no apparent way to calculate k = gxy (mod N) without first calculating either x or y, a task which is believed to be difficult where N is sufficiently large and g, x, and y are non-trivial. Although the Diffie-Hellman key exchange protocol is defined for any group with a generator, g, it is customary to take a large prime for N. There is however an argument to be made for selecting N to be the product of two large primes, as it can be shown that g can be chosen so that calculating gxy in that case is at least as hard as factoring N [10], while for prime N and g a generator of Z*N, it is only hypothesized that finding gxy is as hard as finding the discrete log of gx or gy.
The El Gamal [7] system is a cryptosystem closely related to Diffie-Hellman, but is used to exchange messages rather than to simply exchange keys. In the El Gamal system g and N are known and fixed with g relatively prime to N. Bob has a secret key of x and a public key of g-x (which is known to exist since gx is relatively prime to N if g is). Similarly, Alice has a secret key of y and a public key of g-y. If Alice wishes to send the message m to Bob, with 0 <= m < N, then she selects a random value r, and calculates and sends the pair (e1, e2) where e1 = gr(mod N) and e2 = (g-x)r m(mod N). When Bob receives the pair, he can calculate (e1)x e2 = (gr)x (g-x)r m = m (mod N) and thus retrieve the message. Bob can use exactly the same technique, trading y for x to send encrypted values to Alice. Note that not only the fixed values x and y must remain secret, but the random generated values r must also remain secret as a knowledge of r and g-x are sufficient to derive m from e2.
For project Emperor we wish to use a strong cryptosystem which is inherently unprotectable as intellectual property. We do this by a simple juxtaposition of Diffie-Hellman key exchange to produce a key with a single use of that key to perform a very simple encryption, as shown in figure 8. But if the Diffie-Hellman key exchange is unprotectable and can be freely used and the encryption used is not protectable, their simple composition is obvious, or even trivial, and as the two component parts may be used sequentially as desired. At the same time, we shall show the resulting cryptosystem has properties very similar to El Gamal, but also for our purposes, significantly different.
Figure 8 - Emperor as a Simple Composition of Diffie-Hellman and a Shift Transformation
We wish for a simple implementation which does not result in many messages being exchanged, but only a single round. We must also make decisions on how values N, g, x, and y are to be selected. In the Emperor protocal we allow Bob to set both N and g, and require him to communicate, not only these values, but also the value of gx(mod N). It is true that this requires confidence in Bob's selection of these values as well as confidence in Bob's ability to maintain the secrecy of x. On the other hand, we must already have some degree of confidence in Bob, since he receives Alice's information and could, if he wished, publish it to the Web or fail to maintain it's secrecy directly. A prudent Bob will select values of N that are conservatively adequate for the information encrypted, balancing security against processing time. To be compliant with project Emperor, Bob must provide the information in such a way that a knowledgeable Alice can inspect his value of N and decide for herself whether she finds the magnitude sufficiant. While Alice may not be able to detect the presence of sophisticated backdoors built into the values Bob provides, she is taking no greater risk than entrusting Bob with her information to begin with. Once she has decided to take that risk, she needs only to detect an incompetent Bob, not a malevolent one.
Our approach does not place restrictions on how Bob generates the value of x save that x must remain unknown. Bob may maintain a single secret value of x to use with every message received, or he may use a different value of x each time. If a single value is used and discovered it would compromise all messages received. Many multiple values that must be generated in an unpredictable manner and then stored and protected, but retrieved when needed, could actually be a greater risk than a single value. Use of a single x which changes from time to time may be an acceptable compromise.
While it is simple for Bob to select or generate secretly held values of x, it may be more difficult for Alice's software agent acting on standard instructions to generate a unique unpredictable secret value y. The simplest technique is to let the value of y depend on the message m to be conveyed. The simplest function of m that could be used is to simply let y be m. This should not place the security of m at any additional risk as the ability to obtain y from gy in any case would be sufficient to allow the calculation of k = gxy (mod N) from gx.
Given that Bob and Alice share access to the value k = gxy (mod N), this value must then be used as a key in another cryptographic system. The safest use of such a key is as a "one time pad" so that this second system does not compromise the security given by the Diffie-Hellman key exchange. A simple crypto-system for encrypting information using an N element alphabet is to use a shift transformation [4] C = P + k (mod N). This type of cryptosystem was used around 50 BC by Julius Caesar to communicate with Marcus Cicero [12] and as a result we may safely say that it meets any reasonable definition of prior art, and so cannot be protected by patent.
The two component parts taken together provide a solution to the problem of providing secure free communications over the web. Bob's server provides suitable values for N, g, and gx as well as a user friendly form and a frame pointer to JavaScript functions for encryption. Alice's browser allows the input of a message, m, and subsequently uses the legally exported JavaScript functions to calculate and return the two values e1 = gm(mod N) and e2 = m + (gx)m (mod N). The first value fulfills Alice's half of the Diffie-Hellman protocol, while the second value is the encrypted message. Now Bob needs only calculate e2 - (e1)x = m + (gx)m - (gm)x = m (mod N). This one time use of gmx as a key to a shift transformation is effectively a public key trapdoor cryptosystem allowing the secure transmission of m from Alice to Bob.
The close relationship between El Gamal and Emperor is obvious. Both encrypt the message as an ordered pair, the first element of which can be viewed as the concluding half of a Diffie-Hellman exchange, while the second element of the ordered pair is a value which when combined with the Diffie-Hellman value allows the recovery of the original message by a single operation in ZN, multiplication in the case of El Gamal and subtraction in the case of the Emperor. The close relationship can be, however, somewhat misleading. In the El Gamal protocol the values of N, G, x, and y are fixed and the random r is provided by Alice. In the protocol used by project Emperor, y is message dependent, the random but possibly fixed x is provided by Bob as is the possibly transaction unique values of N and g. There is no value of r.
Unlike RSA, our encryption method does not act as a signature. It does not prove to Bob that the message came from Alice and, except by virtue of some special value of the original message, it does not allow Bob to prove to anyone else that the message came from Alice. The signature could be added just as it is in El Gamal. An interesting alternative, however, is for s to be a registered signature value with some trusted signature authority. Now Alice's browser must prompt for s and return a third value e3 = m + s + (gm)s (mod N) where s + gms (mod N) is considered the signature for the message m encrypted using g and N. Only someone who can obtain the value of m, such as Bob, can derive the signature from e3, as s + gms = e3 - m(mod N). Now, if Bob wishes to verify (or prove) that he has a proper signature for the message m, namely s + gms (mod N), the verifier provides the signature authority with the values g, N, m, and putative signature s + (gms) (mod N) and asks if the signature is valid for Alice. The signature authority takes the values given for g, N, and m and also taking the registered secret value s for Alice, first calculates s + (gms) (mod N), and then compares this with the putative value given. If they match, the authority can confirm the authenticity of the signature, and otherwise can reject it. If the authority provides its own web page to provide signature authentication, measures should be incorporated to prevent the authentication server from compromising s to an attack. This should include direct measures such as using the same encryption techniques discussed to encrypt the incoming values of g, N, and m, requiring sufficiently large values of N and non-trivial values of g (g should have a large exponential period), as well as indirect measures such as logging the source of authentication requests, not recording the values of m (or the secret values, x, used for encryption by the signature authority so that m cannot be latter recovered), refusing to test authentication for Alice after an abnormally large number of failed authentications, and possibly requiring an (encrypted) password (or signature) to restrict authentication requests to authorized users. Signature authorities may be as varied as a bank, a credit card company, a government agency, or Bob himself, the last option allowing for signatures by continuing customers.
It is a drawback to the system that the process of authenticating a message must reveal the message to the signature authority. Authentication and non-repudiation are purchased at the cost of some loss of confidentuality. It is possible to take such steps as splitting the message into two parts, m = m1 + m2 (mod N) and signing each half with a different signature registered with a different signature authority. This adds complexity to the protocol and still allows the two message authorities to cooperate to retrieve the message. It is also possible to slightly alter the signature protocol to allow authentication of encrypted messages, but only at the cost of allowing Bob to fake a signature of certain classes of derived messages. For some purposes, it will be natural to sign a digest of a message for authentication while reserving a signature of the message itself for non-repudiation.
5 Project Emperor
We advocate that individuals who are lawfully free to do so make some form of strong cryptography, along the lines we have outlined, available for free use on the web. To support this, a web page whose URL is contained (for reasons of anonimity) at http://clever.net/emperor.html has been set aside to serve as a center and archive of material (other than actual software) supporting this project, including a sign-up for a mailing list. It is our intent that the resulting association of individuals engage in a planned set of activities resulting in the wide-spread availability of such a form of cryptography.
Project Emperor falls naturally into four phases:
Although we canot examine these issues in any detail here, we will touch on some of them and defer other comments for another forum.
Phase 1 - Although patent protection preventing the free use of El Gamel has expired, we prefer the use of the related technique given here. It possesses the advantage of not requiring Alice to generate an independent unpredictable random value. At the same time, should this technique become ubiquitous, the simple extension to support independently verified signatures across many values of N and g may prove quite useful. None-the-less, placing functions in the distributed source export frame to perform El Gamel cryptography does remain a viable option should some unforseen defect in the Emperor protocal become apparent.
Phase 2 - We have implicitly described the message m in terms of an integer value between zero and N. In fact the typical message will be a text string. The function in the export-frame, then, should include the capability of coercing the text string m into a series of messages m0, ... , mn, which is a base N representation of m so that for each mi, where 0 <= i <= n, 0 <= mi <= N and S (miNi) is a numeric representation of m. Each mi, is encrypted separately. The form, then, must be set up to return sufficiently many values for the largest string that the form will legally accept.
In order to achieve a level of security that inspires confidence over an extended period of time, N must be on the order of hundreds of digits. This requires multi-precision arithmetic [9] capable of performing the operations in a reasonable period of time. The results of this multi-precision arithmetic, may, depending on the representation chosen, mean that each large numerical value used is, itself, represented by a series of numerical values. Thus, the public key values set in Listing 5 may in fact require either an entire series of assignments or, preferably, a character string representation of the numbers which are then converted into the internal representation. Similarly the values returned by the form may require a number of individual values that vary both with the size of the text and with the size of N. As a result, it may be advantageous for Bob to use one form to obtain information from Alice and, based on this information, use JavaScript to actually construct a second form during the encryption phase which will have the responsibility of returning the encrypted variables to Bob.
Phase 3 - The following capabilities are needed:
The major implementation challenge will be to be to provide the functions in JavaScript without a significant speed penalty.
The development of a suitable collection of additional support applications will facilitate the use of the proposed encryption technique. Ideally, Bob will have his own software which will decrypt Alice's encrypted information, but failing this, an additional JavaScript application which Bob could use to decrypt individual messages on his machine will help to facilitate widespread usage and can be easily built from the componants required to perform encryption. Bob's task will also be simplified with an application to assist in selecting large primes. An application to help construct appropriate encryption-ready forms to be incorporated into Bob's web-page will also be helpful, although this last function can equally well be implemented as a CGI and should not involve export restrictions.
Phase 4 - Another form of support which is critical is educational material for potential users to help prevent unsound use of the cryptosystem. As an example, Bob and Alice should understand that the number of possible messages places an upper limit on the security; that no matter what the complexity of the encryption process, if there are only a limited number of possible messages, each can be encrypted in turn to detect a match. Educational support is arguably the single most important feature called for by Project Emperor.
A number of features should be inspected when an implementation of Emperor is evaluated. As an example, insuring that implementations of the Emperor Protocal seperate the action that Alice takes to perform the encryption from the action that Alice takes to send her information over the web, insulates the protocal from a wide variety of timing attacks.
6. Conclusions
We have seen that it is possible to provide strong encryption over the World Wide Web without violating export laws by using the inherent distributed source functionality of the web. Further we have shown how to provide the functionality of a public key cryptosystem over the web by utilizing a combination of Diffie-Hellman and a shift-transform, neither of which are protected by intellectual property laws. We advocate implementation of a complete system, project Emperor, to allow free use of strong cryptography on the web for applications whose volume is sufficiently limited that the computation involved is not prohibitive. Although we hold the resulting ability to communicate privately is desirable for many purposes, there is a secondary motive for writing this paper. This paper (and Project Emperor itself) is also an attempt to demonstrate the underlying flaw or absurdity in the regulatory attempts it sidesteps. Such laws demonstrate a fundamental misunderstanding of the technology, both of the nature of the internet and of cryptography. More complex restrictions generated with no underlying understanding of the technology merely require more complex sidesteps and must invariably result in unintended consequences, some of which may be dangerous.4
Strong cryptography has consequences both desirable and undesirable. It is natural to seek to obtain the benefits of change, while avoiding its drawbacks, to maintain a beneficial status quo. The argument that strong cryptography could aid criminals and terrorists, resulting in the loss of human life, is not to be lightly dismissed. It is undeniably true. But we should also note that it is equally true that innumerable children would be saved from being molested if every nook, cranny, and bedroom were open to the government's remote photographic inspection. It does not follow that this is a good idea.
We do not maintain, or attempt to demonstrate, that it is impossible to outlaw the private use of strong cryptography. Such regulation would be exceedingly simple. We maintain, rather, that it is increasingly impossible to outlaw the private use of strong cryptography without severely impacting the laws that insure human rights. As information technology increases, it becomes simpler, on the one hand, to guarantee privacy, and on the other, to create a Orwellian nightmare where privacy from the government does not exist at all. Those who believe that they can simultaneously have, for any length of time, more than two of:
- effective restrictions on strong cryptography,
- a free society,
- and a high level of information technology,
are deceiving themselves just as thoroughly as Hans Christian Anderson's Emperor who wore no clothes.
References
[1] H. Abelson, R. Anderson, S.M. Bellovin, J. Benaloh, M. Blaze, W. Diffie, J. Gilmore, P.G. Neumann, R.L. Rivest, J.I. Schiller, and B. Schneier, "The Risks of Key Recovery, Key Escrow, and Trusted Third-Party Encryption," World Wide Web Journal, V. 2, #3, pp. 241-257, 1997.
[2] T. Berners-Lee and D. Connolly, "Hypertext Markup Language - 2.0," RFC 1866, MIT/W3C, Nov. 1995.
[3] Bureau of Export Administration, Department of Commerce, "Encryption Items Transfered from the U. S. Munitions List to the Commerce List," Federal Register, V. 61, #251, pp. 68572-68587, December 30,1996.
[4] D. M. Burton, Elementary Number Theory, Second Edition, Debiqie, IA: Wm. C. Brown Pub., 1989.
[5] K.A.L. Coar and D.R.T. Robinson, "The WWW Common Gateway Interface Version 1.1", Internet Draft, Work in progress, Revision 00 - May 28, 1998, Expires Nov. 29, 1998, Current status available at http://Web.Golux.Com/coar/cgi/ .
[6] W. Diffie and M. E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, V. IT-22, pp. 644-654, Nov. 1976.
[7] T. El Gamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," IEEE Transactions on Information Theory,V. IT-31, #4, pp496-472, July, 1985.
[8] D. Flanagan and D. Shafer, JavaScript: The Definitive Guide, Third Edition, O'Reilly & Associates, June 1998.
[9] D. Knuth, "Semi-numerical Algorithms," The Art of Computer Programming, Second Edition, Reading, MA: Addison-Wesley, V. 2, pp. 316-336, 1981.
[10] K. McCurley, "A Key Distribution System Equivalent to Factoring," Journal of Cryptology, V 1, pp. 95-105, 1988.
[11] R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, V. 21, pp. 120-126, Feb., 1978.
[12] K. H. Rosen, Elementary Number Theory and Its Applications, Third Edition, Reading, MA: Addison-Wesley, 1992.
[13] R. Schwartz, T. Christiansen and S. Potter, Programming Perl, Second Edition, Ed. L. Wall, O'Reilly & Associates, Oct. 96.
[14] "U. S. International Traffic in Arms Regulations (ITAR),", United States Code, Title 22 - Foreign Relations and Intercourse, Chapter 39 - Arms Export Control, Subchapter III - Military Export Controls, Section 2778 - Control of Arms Exports and Imports. (Text available at http://www.law.cornell.edu/uscode/22/2778.html .)