Method and apparatus for encrypting data communicated between a client and a server that use an unencrypted data transfer protocol

Techniques for securing data in communications between a client and server using an unencrypted transfer protocol, which does not encrypt a payload defined by the transfer protocol, include selecting a subset from a set of data to be communicated in a particular payload. A secret integer is determined that is unique for the subset. Based on the subset and the secret integer, encrypted data is generated that is practically unintelligible to a device other than the client and the server. A sending device, of the client and the server, sends to a receiving device, in the particular payload, the encrypted data and information to determine, only at the client and the server, the secret integer for decrypting the encrypted data. The present techniques allow a lightweight encryption algorithm to provide authentication and data security for more secure transfer of selective portions of unencrypted payloads transferred by such protocols as the Hypertext Transfer Protocol (HTTP).

FIELD OF THE INVENTION

The present invention generally relates to cryptography in a computer network. The invention relates more specifically to a method and apparatus for encrypting data that is communicated between a client and a server that use an unencrypted transfer protocol for application-layer communications.

BACKGROUND OF THE INVENTION

Hypertext Transfer Protocol (HTTP) is widely used for communication of hypermedia documents, electronic commerce transactions, and various network management software applications. HTTP servers are now widely deployed for the purpose of transiently linking together computers that are widely geographically distributed into a virtual worldwide “web” of computers and networks. Client computers with compatible HTTP or “web” browser software can retrieve documents from HTTP servers and interact with applications that post or return results and screen displays to an HTTP server. The term “client” can refer to a process that sends a request for a service over the network as well as to the computer device that hosts the process. The term “server” can refer to a process that provides the service in response to the request, as well as to the computer device that hosts the process. As used herein, the term “client” refers to the host device for the client process unless otherwise indicated; and the term “server” refers to the host device for the server process, unless otherwise indicated.

An HTTP communication exposes the information that is communicated to many security risks, such as unauthorized access, eavesdropping, and message tampering. Several approaches are currently used to protect against such attacks through use of client passwords, authentication, and various data encryption methods.

In a first approach, HTTP Basic Access Authentication (as defined in Request for Comments 1945 [“RFC 1945”] of the Internet Engineering Task Force, available at the time of this writing at domain ietf.org) is a method that provides client authentication, but not data encryption and server authentication. In this context, “authentication” refers to verifying that a client or server is what its messages indicate it is. A further disadvantage of this approach is that any client password is sent over the network in clear text with no protection.

In another approach, HTTP Digest Access Authentication (as defined in RFC 2069, available at the time of this writing at domain ietf.org) is a method that provides an enhancement over Basic Access Authentication. The secure one-way hash function known as Message Digest 5 (or “MD5”) is used to protect the password sent to a server by generating a fixed-length hash value from the password. Because the original password cannot be recovered from the MD5 hash value, this method does not work well with centralized authentication protocols, such as RADIUS or TACACS+. Use of these protocols generally involves recovering the original password so that it can be forwarded (using another encryption mechanism) to a centralized authentication server for verification.

In yet another approach, secure HTTP (“HTTPS” or HTTP over a Secure Socket Layer, SSL/TLS) is a method that provides data encryption, data integrity, and client/server authentication. HTTPS is a strong and comprehensive solution, but it requires intensive processor usage as well as significant management overhead and technical expertise to install and maintain authentication certificates. Computationally expensive bulk ciphers such as DES, Triple DES, or IDEA are used for encryption of a data stream.

The cost and overhead associated with SSL and HTTPS sometimes are not justified, especially when the data for encryption is relatively short, such as a client password, or encompasses only selected parts of the stream of communication generated by a particular application. HTTPS encryption is done in a lower logical layer than an application, typically in a socket layer; at this layer, an application cannot selectively control whether encryption is applied to data.

Based on the foregoing, there is a clear need in this field for an alternative way to improve HTTP communication security. In particular, there is a need for an approach that provides both authentication and data encryption that is more secure than the HTTP Basic method mentioned above, and that allows the destination server to decrypt the encrypted data in contrast to the Digest Access Authentication method mentioned above. There is also a need for an approach that does not require use of computationally burdensome bulk ciphers to encrypt data as used by the HTTPS method mentioned above.

It would also be desirable to have an approach that is carried out by an application on top of an HTTP transport layer, in order to allow the application to control which data is encrypted and which data is not encrypted.

There is also a specific need for an improved application-layer encryption approach that can efficiently encrypt small or medium amounts of information such as passwords, credit card numbers, user data entry, etc., under control of an application program. There is a further need for an approach that is resistant to attacks in which attackers can eavesdrop on the communication or launch a plaintext attack.

SUMMARY OF THE INVENTION

The foregoing needs, and other needs and objects that will become apparent for the following description, are achieved in the present invention, which comprises, in one aspect, a method for securing data in communications between a client and server using an unencrypted transfer protocol. An unencrypted transfer protocol does not encrypt a payload defined by the transfer protocol. The method includes selecting a subset from a set of data to be communicated in a particular payload. A secret integer is determined that is unique for the subset. Based on the subset and the secret integer, encrypted data is generated that is practically unintelligible to a device other than the client and the server. A sending device sends to a receiving device, in the particular payload, the encrypted data and information to determine, only at the client and the server, the secret integer for decrypting the encrypted data.

In another aspect of the invention, a method includes receiving, from a sending device of the client and the server, a particular payload of the unencrypted transfer protocol. The particular payload includes encrypted data and information to determine, only at the client and the server, a secret integer unique for the encrypted data in the particular payload. The secret integer is determined based, at least in part, on the information. Based on the secret integer, the encrypted data is decrypted to generate a subset of data to be communicated between client and server.

In other aspects, the invention encompasses a computer apparatus and a computer readable medium, including a carrier wave, configured to carry out the foregoing steps.

Advantages accrue to the disclosed techniques in that existing methods to secure HTTP communication are either weak and inadequate, or strong and comprehensive but have high overhead costs. The solution proposed herein provides a more balanced alternative. It can provide improved security while minimizing overhead costs. It provides good protection against common types of attacks (e.g., unauthorized access, password and data eavesdropping, plain-text attacks, brute-force key search, and reverse engineering attacks). An application can control which data are to be encrypted (or not) to reduce the load on a processor. No authentication certificate is required. The techniques work with existing standard web browsers without the needs of plug-ins or other browser modifications.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

1.0OPERATIONAL CONTEXT2.0STRUCTURAL OVERVIEW3.0FUNCTIONAL OVERVIEW4.0ENCRYPTION APPROACHES FOR HTTP COMMUNICATIONS4.1APPROACH WITH INSECURE CLIENT STATE INFORMA-TION4.2APPROACH WITH SECURE CLIENT STATE INFORMA-TION4.3SECURITY ANALYSIS5.0IMPLEMENTATION MECHANISMS -- HARDWARE OVER-VIEW6.0EXTENSIONS AND ALTERNATIVES
1.0 Operational Context

To illustrate secure data communication using an unencrypted transfer protocol, it is assumed that payloads for the Hypertext Transfer Protocol (HTTP) are generated at a web browser and web server process at an application level and are transmitted over a public network such as the Internet. However, the invention is not limited to this context. For example, the invention may also be applied to protect portions of payloads from other client processes and server processes using HTTP, or for other unencrypted transfer protocols over other insecure networks.

2.0 Structural Overview

FIG. 1is a block diagram of a hypothetical example network context in which embodiments may be implemented. A client100is communicatively coupled through a network110to a server120via links104A,104B. Client100is a network end station device such as a personal computer, workstation, or other processing device that hosts a client process106. Server120is a processing device that hosts a server process126with which client process106interacts; in various embodiments, server120may be implemented as a general purpose data processing system or as a specialized data processor such as a router, switch, gateway, etc. In one example embodiment, server120is a network administration blade that forms a part of the Cisco Catalyst 6000 Switch, from Cisco Systems, Inc., San Jose, Calif.

Communications links104A,104B may be implemented by any medium or mechanism that provides for the exchange of data between client100and server120. Examples of communications links104A,104B include, without limitation, a network such as a Local Area Network (LAN), Wide Area Network (WAN), or the Internet, or one or more terrestrial, satellite or wireless links.

In one embodiment, the client process106is a web application running in a web browser that can communicate using HTTP through network110to the server process126that is hosted by server120. The web browser may be implemented as a commercial Web browser program such as Internet Explorer or Netscape Communicator. Server process126is any software element that provides services to client process106; in one implementation, in which server120forms part of a network device such as a switch, server process126is a network management application for managing the network device through HTTP messages.

Client100includes a data storage device, such as a disk or memory, which can store program instructions and data. A Client Process106, which is executed at client100, stores data in one or more data structures108,109in storage that is accessible to the client process. Server120has a data storage device that includes one or more data structures128,129. According to the illustrated embodiment, client process106may have access to a secure data structure109that cannot be accessed through link104A with the network110, or an insecure data structure108that can be accessed through link104A. An example of an insecure data structure108is a “cookie,” which is a file accessed for reading and writing through HTTP. Similarly, server process126stores some data in a secure data structure129that cannot be accessed through link104B with the network110, and stores some data an insecure data structure128that can be accessed through link104B.

Client100further hosts a selective encryption and decryption process or encryption service107, which is selectively callable by client process106, or by an operating system of client100, to carry out encryption and decryption functions. Although depicted as part of client process106, the encryption service107may be separate from the client process106in other embodiments. Similarly, server120further hosts a selective encryption and decryption process or encryption service127, that is selectively callable by server process126, or by an operating system of server120, to carry out encryption and decryption functions. Although depicted as part of server process126, the encryption service127may be separate from the server process126. Thus, encryption services107,127may comprise one or more software or hardware elements that cooperate to implement the approach that is described computer functionally herein.

3.0 Functional Overview

According to the illustrated embodiments, a subset of the data to be communicated between client and server is subjected to fast encryption in which the subset is combined with a secret integer to produce encrypted data. The encryption method is selected to provide good protection against common types of attacks including unauthorized access, password and data eavesdropping, plain-text attacks, brute force key searches and reverse engineering. The encryption method is also selected to avoid the intensive computations employed by ciphers such as DES.

To avoid brute force key search attacks, a long secret key is used. For example, a 128-bit key is used. In other embodiments, a shorter key may be used; for example, a 64 bit key may be used. To avoid intensive computations, the subset of data encrypted at one time is limited to a particular size. For example, the subset to be encrypted is limited to 128 bits—sufficient to protect valuable 16-character strings or smaller, such as user passwords. Also to avoid intensive computations, the fixed length subset is combined bit by bit with a secret integer, rather than implementing computer intensive encryption algorithms that cause each bit of the subset to affect most bits of the encrypted data. An exclusive or (“XOR”) operation is performed between each bit of the subset and the corresponding bit of the secret integer to produce the corresponding bit of the encrypted data.

A bit-wise XOR operation is susceptible to a plaintext attack if the same secret integer is used in multiple messages. That is, an attacker who provides or knows the subset for one message can determine the secret integer; and such an attacker can use the secret integer to decrypt subsequent encrypted data to determine subsequent subsets. For example, an attacker who is an authorized user can deduce the secret integer from the encrypted data and the attacker's own password, and then use the secret integer to determine the passwords of other authorized users. To avoid plaintext attacks, the secret integer is changed with each communication in a way that others than the client and server cannot predict. To allow the receiving device to determine the new secret integer, each message includes a clue that only the receiving device can use to determine the new secret integer.

FIG. 2Ais a flow diagram that illustrates a high level overview of one embodiment210of a method for generating selected encrypted data to send using an unencrypted protocol. Although steps are shown inFIG. 2Aand subsequent flow diagrams in a particular order, in other embodiments the steps can be performed in a different order or overlapping in time to produce the same effect.

In step212, a sending device determines a public key for the server, P, that can be used to define a secret key, K, shared by the server and a particular client. The sending device is the device that encrypts and sends data, and it can be either the client or the server.

For example, using Diffie-Hellman key exchange (hereinafter called “D-H”), the server makes public a value of a key dimension, D, which is the maximum number of different keys that can be defined, and the value of a generator, G, used to generate public keys, where G<D. According to D-H, the server then generates a secret random number L (server's private key), and a public key P dependent on L, according to Equation 1.
P=GLmod D  (1)
Where the symbol “mod” indicates the modulus function that provides the remainder when the value of the expression left of the symbol “mod” is divided by the modulus found to the right of the symbol “mod.” When chosen according to the rules of D-H, the value of L cannot be obtained in a practical amount of time from the values of P, G and D.

Any second device, such as client100, may use the public key of the server, P, to generate a secret key, K, which can be shared with the server. According to D-H, the client generates a secret random number M (client private key). Then Equation 2 gives the shared secret key, K.
K=PMmod D  (2).
According to D-H, the client also determines a public key for the client, Q, using Equation 3.
Q=GMmod D  (3).
The server does not know M and cannot compute K using Equation 2. However, the client can inform the public of the value of Q without making public the value of M. When chosen according to the rules of D-H, the value of M cannot be obtained in a practical amount of time from the values of Q, G, D. According to D-H, the server can use the public key of the client, Q, to compute K, using Equation 4.
K=QLmod D  (4)
Since no one else knows the value L, no other party can compute the value of K according to Equation 4, even if given the value of P and Q. Equation 2 and Equation 4, both provide the same value, K, as shown by Equation 5.
K=PMmod D=GLMmod D=GMLmod D=QLmod D  (5).

For example, using at least some of the steps of D-H in step212, the server determines the values of G, D, P. In some embodiments, the client sends an initial message to the server requesting values of G, D, P. In some embodiments, the values of G, D, P are posted to the public so that the client, and any other device that has retrieved the posting, knows these values. In yet other embodiments, the values of G and D are posted, and the client sends an initial message to the server to request the value of P. In this embodiment, upon receiving the request, the server selects a new random value, L, and generates P, and sends the value of P to the client in an initial response.

Additional steps performed in step212for some embodiments, incorporating additional steps of D-H, are described below with reference toFIG. 5A. The additional steps are employed in many embodiments in which the server is both the receiving and the sending device.

In step214, a subset, represented by the symbol T, of the data in the HTTP payload is selected for encryption at the sending device. For example, a script included in a Hypertext Markup Language (HTML) page is communicated to the client by the server via HTTP and is executed by a web browser on the client. The script causes the web browser to prompt a user for a password, among other data, and selects the password for encryption.

In some embodiments, a separate process, such as a Java applet, is provided to the client by the server and is launched by the web browser. The Java applet prompts the user for the password and selects the password for encryption, returning the encrypted data and clue, as described in more detail below, to the web browser for incorporation into the next request from client to server. Thus, using scripts or applets, a web application can select a subset for encryption and employ other processes of the encryption service107without reliance on a browser plug-in module. In other embodiments, a new plug-in module is developed for a web browser or other client process to select the subset for encryption and to invoke the other processes of the encryption services107.

In some embodiments, the server is also the sending device, and the data to be encrypted is selected by a server. For example, the server may generate a password for subsequent use by a client, and select the generated password to be encrypted.

In step216a unique secret integer S, based at least in part on a shared secret key, K, is determined to use for encrypting the subset, T. The shared secret key, K, is based in part on the server's public key P. To avoid plaintext attacks, S is unique for every communication. For example, a different value of S is used for each HTTP payload sent from the sending device.

Additional steps performed in step212for different embodiments are described below with reference toFIG. 4AandFIG. 5B. In the embodiment ofFIG. 4A, for example, a different value of the random number M, generated by the client for each payload, is used to produce a different value of K for each payload, and thus S, derived from K, is different for each payload. In the embodiment ofFIG. 5B, for example, a single value of K is hashed using a one-way hash function a different number of times for each payload, and S is derived from the last output of the hash function.

In step218, the secret integer, S, and the subset, T, are combined to produce encrypted data, E. For example, a bit-wise XOR is performed on the subset, T, and the secret integer, S, to generate the encrypted data E.

In step220the encrypted data E and a clue, represented by the symbol C, for determining the secret integer, S, at the receiving device, are included in the HTTP payload for transmission to the receiving device. Additional steps performed in step220for different embodiments are described below with reference toFIG. 4BandFIG. 5C. For example, in the embodiment ofFIG. 4B, the public key of the client, Q, is included in C. In the embodiment ofFIG. 5C, the number of times the hash function is applied, represented by the symbol N, is included in the clue C.

Control may eventually return to step214to process the next subset or payload to be sent to the same receiving device.

FIG. 3is a block diagram of a data packet300for an HTTP message with encrypted data, according to an embodiment. The illustrated data packet300is a data packet formatted according to the Internet Protocol (IP) in the networking layer used by networking hardware to forward data packets over the Internet and similar networks. For simplicity,FIG. 3illustrates one packet300; however, long HTTP messages may require many more than one packet. Thus, in the description below, references to packet300should be understood to include multiple packets, a packet stream, etc.

The IP packet300includes a destination network address in a destination field302and a source network address in a source field304, among other fields. Within the IP packet300is an HTTP message310for use in communications between the server process126and the client process106at the application layer. The HTTP message includes an HTTP header322and an HTTP payload330. Neither the HTTP header322nor the HTTP payload330is encrypted. In the HTTPS protocol, the entire message310is encrypted.

According to the illustrated embodiment, the HTTP payload330includes a fixed length encrypted data field352for holding E, the encrypted data for a selected subset. The payload330also includes a clue field354for holding data indicating the clue C for determining the secret integer S at the receiving device. For example, in the embodiment described in more detail below with reference toFIG. 4A, the clue field includes data indicating Q, the public key of the client for the unique value of K, the shared secret key, employed for the subset in payload330of a particular data packet. In the embodiment described in more detail below with reference toFIG. 5B, the clue field includes data indicating N, the number of times the hash function is applied for producing the encrypted data in payload330of a particular data packet.

FIG. 2Bis a flow diagram that illustrates a high level overview of embodiment250of a method for processing selected encrypted data that is received using an unencrypted protocol, such as HTTP.

In step252, the receiving device determines a public key for the server P. Step252corresponds, for the receiving device, to step212for the sending device. Additional steps performed in step252for some embodiments, incorporating additional steps of D-H, are described below with respect toFIG. 5A. The additional steps are employed in some embodiments in which the server is the receiving device, and may also be a sending device for a different HTTP payload.

In step254, the receiving device receives E, the encrypted data, and C, the clue for determining the secret integer. For example, the receiving device receives the data packet300that includes the HTTP payload330that includes the encrypted data field352and the clue field354.

In step256, the receiving device determines S, the secret integer unique for the subset encrypted in the payload, based on C, the clue. Additional steps performed in step256for different embodiments are described below with reference toFIG. 4CandFIG. 5D. For example, in the embodiment ofFIG. 4C, the secret integer S is computed based on Q, the public key of the client, included in C, the clue. In the embodiment ofFIG. 5D, the secret integer S is computed based on N, the number of times the hash function is applied to a shared secret key determined in an earlier communication, which number N is included in C, the clue.

In step258, the receiving device combines S, the secret integer, and E, the encrypted data to produce T, the selected subset in plaintext. For example, a bit-wise XOR is performed on S and E to generate T, such as a password.

Control may eventually return to step254to process the next payload received that includes values of E and C from the same sending device.

4.0 Encryption Approaches for Http Communications

Two approaches for encrypting data that is communicated between a client and a server using HTTP for application-layer communications are now described. A first approach is suited to client processes that cannot maintain client state information securely, such as web browsers that store state information in cookies. The second approach is useful in conjunction with client processes that can store state information securely, such as Java applets that can be launched by many current web browsers. The first approach is used for one-way encrypted communications from client to server. The second approach can be used for two-way encrypted communications between the client and server; and consumes fewer computations per payload after an initial payload is communicated.

4.1 Approach with Insecure Client State Information

Embodiments of the first approach support encryption of data in one logical direction, from client to server. Upon the initiation of process212and252ofFIG. 2AandFIG. 2B, respectively, it is assumed that client100and server120each store the generator value G and the modulus value D in data structures108,128, respectively. The embodiments of the first approach described herein do not require storage of generator value G and modulus value D in a secure manner.

In embodiments of step212using the first approach, the client process106on client100sends an initial request to server process126on server120. The initial request may be conveyed from client100to server120in the form of an HTTP request in an IP packet. Encryption process127on server120generates a large secret number L (server's private key), calculates the server's public key value P according to Equation 1, and passes the value of P to the server process126which sends the server's public key value P to the client process106on client100. The encryption process127stores the value of L in secure data structure129for use with subsequent communications from client100. Upon receiving the public key value P, the encryption service107on client100stores P in the insecure data structure108, such as in a browser cookie file.

In embodiments of step214using the first approach, the client process106determines a data subset T to be encrypted, which is a subset of an HTTP payload to be sent to server120. The client process passes the subset T to the encryption service107for encrypting. For purposes of illustration, it is assumed that the client process106selects a user-entered 8-character password as the subset T to encrypt.

In first approach embodiments of step216, the encryption service107on client100determines S, the secret integer unique for the subset T, according to the more detailed steps depicted inFIG. 4A.FIG. 4Ais a flow diagram that illustrates embodiment216aof step216.

In step412, the encryption service107on client100uses a secure random generator to generate the random number M. For example, encryption service107uses the Blum, Blum, Shub (BBS) random bit generator, well known in the art, to generate a value of M that cannot be predicted from a previous value of M.

In step414, the encryption service107on client100determines the shared secret key, K, based on the server's public key, P, and based on the random number M. For example, the encryption service107applies Equation 2 of D-H, shown above.

In step416, the encryption service107applies a secure one-way hash function to K to generate S, the secret integer. With a secure, one-way hash function, the input cannot be determined based on knowledge of the output. Example secure hash functions include the Secure Hash Algorithm (SHA), and compression function called Message Digest 5 (MD5), well known in the art.

It is assumed that the hash function produces an output with s bits (i.e., S<2s) and the modulus D has d bits (i.e., D=2d). Using a one-way hash function, it is not required that s equal d. For the purposes of illustration, it is assumed that the MD5 function is employed with. s=128 while d=64. The value of s is selected as 128 because the MD5 function generates a 128-bit output. The value of d is selected as 64 for performance reasons; larger values may be used for greater security, but require additional computation time. The value of S is therefore computed according to Equation 6.
S=md5(K)  (6),
where the symbol “md5” represents the MD5 hash function. In some embodiments, to generate S that is longer than 128 bits (s>128), MD5 function can be applied multiple times to the original K.

In some embodiments, step416is omitted; and S is set equal to K.

In embodiments of step218using the first approach, the encryption service107performs a bit-wise XOR of the secret integer S and the subset T to obtain encrypted data E, according to Equation 7.
E=T XOR S  (7).
For example, a login password and the secret integer S are combined with a bit-wise XOR operation. The encryption service107passes the value of E to the client process106.

In first approach embodiments of step220, the client100sends a data packet that includes a payload with E, the encrypted data, and C, the clue, according to the more detailed steps depicted inFIG. 4B.FIG. 4Bis a flow diagram that illustrates embodiment220aof step220.

In step422, the encryption service107calculates Q, the client public key according to D-H, using Equation 3, shown above. The value of Q is included in C, the clue, and C is passed to the client process106.

In step424, the client process106stores the value of C, the clue, in the clue field354of the HTTP payload330. The client process106also includes the value of E, the encrypted data, in the encrypted data field352of the HTTP payload330.

In first approach embodiments of step254, the data packet300with the HTTP payload330is received at the server120. In some embodiments of step254, the encryption service127on the server120receives the packet300and extracts the data from the encrypted data field352and the clue field354that indicate the values of E and C. In some embodiments of step254, the server process126receives the HTTP payload330, extracts values of E and C from fields352,354, respectively, and passes those values to the encryption service127.

In first approach embodiments of step256, the encryption service127on server120determines the value of S, the secret integer, based on the value of C, according to the more detailed steps depicted inFIG. 4C.FIG. 4Cis a flow diagram that illustrates embodiment256aof step256.

In step454, the server determines K, the shared secret key, based on Q, the client public key, indicated by C, the clue. For example, the encryption service127sets Q equal to C and computes K according to D-H, using Equation 4, shown above.

In step456, the hash function (which must be the same function as the one that is used in step416) is applied to the value of K to generate the value of S, the secret integer. For example, the encryption service127computes S using Equation 6. In some embodiments, step456is omitted; and S is set equal to K.

In embodiments of step258, the server does a bit-wise XOR of the secret integer S and the encrypted data E to obtain subset, T, according to Equation 8.
T=E XOR S  (8).
For example, the encryption service127on server120combines E, the encrypted data, and the secret integer S, computed in step256a, with a bit-wise XOR operation to produce the login password. In this embodiment, the value of T is then passed from the encryption service127to the server process126. For example, the value of the user's login password is passed to the server process126for further processing.

4.2 Approach with Secure Client State Information

The second approach supports encryption of data in both logical directions, from client to server and from server to client. For multiple payloads, embodiments using the second approach are much faster than the embodiments using the first approach. Embodiments using the second approach have the client maintain secret state information, such as a value of the shared secret key, K, in a secure data structure109. For example, a secure data structure includes a variable in a Java applet, but does not include a cookie file. In the embodiments of the second approach, a single value of K, stored in the secure data structures109,129, is hashed using a one-way hash function a different number of times for each payload, and S is derived from the last output of the hash function.

As in embodiments using the first approach, upon the initiation of process212and252ofFIG. 2AandFIG. 2B, respectively, it is assumed that client100and server120each store the generator value G and the modulus value D in data structures108,128, respectively. The approach herein does not require storage of generator value G and modulus value D in a secure manner, such as in secure data structures109,129.

In embodiments of step212using the second approach, P, the server's public key is determined according to the more detailed steps depicted inFIG. 5A.FIG. 5Ais a flow diagram that illustrates embodiment212aof step212.

In step502, the client and server exchange K, the shared secret key. For example, K is determined according to D-H using the following steps. The client process106on client100sends an initial request to server process126on server120. The initial request may be conveyed from client100to server120in the form of an HTTP request. Encryption process127on server120generates the large secret number L (server's private key), calculates the server's public key value P according to Equation 1, and passes the value of P to the server process126which sends the server's public key value P to the client process106on client100. The encryption service127stores the value of L in secure data structure129for use later to compute the shared secret key K.

Upon receiving the public key value P, the encryption service107on client100stores P in the insecure data structure108, such as in a browser cookie file. The encryption service107on client100determines a random number M, using a random number generator such as the BBS generator, and computes both K, the shared secret key, and Q, the client's public key, using Equation 2 and Equation 3, respectively.

The value of Q is included in at least one subsequent HTTP payload sent to the server120. For example, in some embodiments, the value of Q is included alone in the clue, C, in a payload sent to the server with a particular message, herein called a “follow-up message.” In such embodiments, the server120computes the shared secret key K using equation 4 and stores it in the secure data structure129on server120when the follow-up message is received.

In some embodiments, the value of Q is included in at least one (usually the first) of the payloads sent to the server in step220, described in more detail below with reference toFIG. 5C. In such embodiments, the clue, C, in the clue field354of the particular message that includes the value of Q, also includes other data used to determine the secret key for the subset included in that particular message. Messages other than the particular message may omit the value of Q from the clue, C. When the server120receives the particular message, the server120retrieves the value of Q included in C, retrieves the value of L from secure data structure129, and computes K using Equation 4. For example, server process126passes C to encryption service127, which retrieves the value of Q and computes K.

In some embodiments, the same value of K is used for communications from client to server and for communications from server to client. In other embodiments, one shared secret, K1, is used for communications from client to server, and a different shared secret, K2, is used for communications from server to client. For purposes of describing a simple example, it is assumed that the same value of K is used for communications to and from the client and server.

Embodiment212aincludes additional steps,504,506,508. In step504, a hash function is applied to K, the shared secret key, to generate a first hashed integer, H1. H1is used to generate the secret integer, S, as described in more detail below with reference toFIG. 5B. For example, an encryption service,107,127applies the MD5 hash function to the value of K according to Equation 9.
H1=md5(K)  (9).

In some embodiments, the same hash function is used for communications from client to server and for communications from server to client. In other embodiments, one hash function is used for communications from client to server, and a different hash function is used for communications from server to client. For purposes of describing a simple example, it is assumed that the same hash function is used for communications to and from the client and server.

In step506, the values of K and H1are stored in a secure data structure. For example, the encryption service107on client100stores the values of K and H1in secure data structure109on client100; and the encryption service127on server120stores K and H1in the secure data structure129on server120.

In step508, a counter, represented by the symbol N, is set to the number of times the hash function has been applied. The value of N is used in following steps in C, the clue to indicate the secret integer S to the other communicating party. The value of N can be stored in an insecure data structure. For purposes of illustration, it is assumed to be convenient to store the value of N in the secure data structure109,129, with the value for H1. For example, N is set to 1 by the encryption service107on client100and stored in secure data structure109; and N is set to 1 by the encryption service127on server120and stored in secure data structure129.

In some embodiments, the same counter is used for communications from client to server and for communications from server to client. In other embodiments, one counter is used for communications from client to server, and a different counter is used for communications from server to client. For purposes of illustration, it is assumed that the same counter is used for communications to and from the client and server.

In second approach embodiments of step214, a sending device, of the client100and server120, determines a subset T to be encrypted; the subset is of an HTTP payload to be sent to a receiving device, of the client100and server120. For purposes of illustration, it is assumed that the client is the sending device, and the client process106selects a user-generated 8-character password as the subset T to encrypt. The client process106passes T to the encryption service107.

In step216, the sending device determines S, the secret integer. For example, encryption service107on client100determines S, the secret integer unique for the subset T, according to the more detailed steps depicted inFIG. 5B.FIG. 5Bis a flow diagram that illustrates embodiment216bof step216.

In step512, the hash function is applied to the most recent value of the hashed integer, represented by the symbol HN, where N indicates the current value of the counter N. A value for HN+1is produced. For example, the encryption service107on client100uses the MD5 hash function to generate HN+1according to Equation 10.
HN+1=md5(HN)  (10).
In some embodiments, for purposes of increasing the security of the system, the hash function is applied more than once during step512to generate HN+2or more hashed integers. In some embodiments, each additional hash function applied during step512is a different type of hash function. For purposes of illustration, it is assumed that the particular MD5 hash function is applied only once during step512and no other hash function is applied.

In step514, two values of the hashed integer are combined using a bit-wise XOR operation. Any two values of the hashed integer may be used, provided that the combination is different than used by any previous subset, and provided that the values are available in the secure data structure. For purposes of illustration, it is assumed that only the two most recent values of the hashed integer, HNand HN+1, are stored in the secure data structure. Since HN+1is newly computed, the combination is expected to be unique. For example, the encryption service107on client100computes S according to Equation 11.
S=HNXOR HN+1(11).

Two values of the hashed integer are combined to prevent plaintext attacks. If a single hashed integer, HN, were used, a plaintext attacker could determine the value of HNand could then generate HN+1and subsequent hashed integers using the well known MD5 hash function. By using two hashed integers combined, the plaintext attacker can only recover the combination. Because the combination is not used as input to the MD5 hash function, the attacker cannot compute the next value of the hashed integer and cannot compute the next value of S.

In step516, the value of HN+1is stored in the secure data structure and the counter is incremented. For example, the encryption service107on client100stores the value of HN+1in secure data structure109, dropping the value of HN−1from the data structure109; and the encryption service107also increments the counter N. For purposes of illustration, it is assumed that N=1 at the beginning of step516, but any initial value may be used, as long as the client and the server use the same initial value. H1is already stored in the secure data structure109as a result of step506, above. During step516, H2is stored in secure data structure, N is incremented to 2, and the value of N=2 is stored in the secure data structure109.

In second approach embodiments of step218, the sending device encrypts the text message T based on the secret integer S computed in step514. For example, encryption service107does a bit-wise XOR of the secret integer S and the subset T to obtain encrypted data E, according to Equation 7, as described above for the embodiments of the first approach. In the illustrated example, the login password and the secret integer S are combined with a bit-wise XOR operation.

In second approach embodiments of step220, the sending device sends a data packet that includes a payload with E, the encrypted data, and C, the clue, according to the more detailed steps depicted inFIG. 5C.FIG. 5Cis a flow diagram that illustrates embodiment220bof step220.

In step522, the sending device includes the value of N in the clue C. If the message being generated is the particular message from client to server, which also includes a value of Q, then the value of Q is also included in the clue C. For example, the encryption service107on client100includes the value of N in the clue C. If the value of Q has not yet been sent to the server, the value of Q is also included in C. The value of C is passed to the client process106.

In second approach embodiments of step254, the data packet300with the HTTP payload330is received at the receiving device. In some embodiments of step254, the encryption service107,127on the receiving device receives the packet300and extracts the data from the encrypted data field352and the clue field354that indicate the values of E and C, respectively. In some embodiments of step254, the process106,126receives the HTTP payload330, extracts values of E and C from fields352,354, respectively, and passes those values to the encryption services107,127, respectively.

In embodiments of step256for the second approach, the encryption service107,127on the receiving device determines the value of S, the secret integer, based on the value of C, according to the more detailed steps depicted inFIG. 5D.FIG. 5Dis a flow diagram that illustrates embodiment256bof step256.

In step552, the receiving device determines, from C, the value of NS, the counter on the sending device. For example, the encryption service127on server120retrieves the value of NS from C. It is assumed for purposes of illustration that NS has a value of 2, while the counter N on the receiving server has a value of 1.

In step554, it is determined whether NS is greater than N. If so, the hashed integer on the receiving device should be hashed one or more times to bring the counters on the communicating devices into synchronization. If not, then some problem is indicated. For example, the sending device might have incorrectly reset its counter. As an alternative example, the sending device might have missed some previous response messages from the receiving device. If NS is less than or equal to N, the hashed integers for computing the value of S that was used by the sending device have already been computed on the receiving device and might be stored in the secure data structure. If NS is too small, the hashed integers used in computing S might no longer be stored in the secure data structure.

If it is determined in step554that NS is greater than N, control passes to step556. In step556, the hash function is applied to the current value of HNto compute HN+1; HN+1is stored in the secure data structure. In some embodiments, the value of HN−1is removed from the secure data structure. Then N is incremented. Control passes back to step554to determine whether the hash function should be applied again to achieve synchronization.

For example, when NS=2 and N=1, control passes to step556and the encryption service127on the receiving server120computes H2by applying the hash function to H1and then increments N to N=2. Control passes back to step554to see if the hash function should be applied again to achieve synchronization. This time NS=N and control passes to step558.

If it is determined in step554that NS=N, or NS<N, control passes to step558. In step558, the values of HNSand HNS−1are determined. If those values are in the secure data structure, the values are retrieved. If not, the values are recomputed by retrieving the value of the secret key, K, and hashing it NS times; re-computing from the value of K is undesirable because it consumes more computational resources than retrieving values already computed. Control then passes to step560. Alternatively, in some embodiments, if NS<N, the receiver can choose to abort the communication session as this indicates some problematic condition.

In step560, the value of the secret integer S used by the sending device is determined according to Equation 12.
S=HNS−1XOR HNS(12).
For example, when NS=2, the encryption service127on the receiving server120determines that the value of S is H1XOR H2.

In an embodiment of step258in the second approach, the server does a bit-wise XOR of the secret integer S and the encrypted data E to obtain subset T, according to Equation 8, above. For example, the encryption service127on server120combines E, the encrypted data, and the secret integer S, computed in step256b, with a bit-wise XOR operation to produce the login password. In this embodiment, the value of T is then passed from the encryption service127to the server process126. For example, the value of the user's login password is passed to the server process126for further processing.

4.3 Security Analysis

This section is provided to help a reader understand and benefit from the steps taken in the above embodiments. However, the invention is not limited by this analysis or by the features of the mechanisms proposed to explain the steps or by any theories expressed.

In both approaches, D-H is relied upon to establish one or more common secret keys, K, between client and server. D-H is vulnerable to active attacks, such as a man-in-the-middle attack, well known in the art. However, to passive attackers, which can only sniff network traffic but cannot alter the contents and directions of the packet streams, the only known way to determine the secret key is exhaustive search. Even with a relatively small key size (64 bits), an exhaustive search is expected to take a very long time.

Both methods use XOR to encrypt text T. Therefore, some mechanism to prevent plaintext attacks is appropriate. If an attacker has knowledge about one plaintext message (e.g., the attacker's own password), the attacker can use the known plaintext, T, and the encrypted data, E, to figure out the encryption integer, S. For example:
E=T XOR SS=T XOR E.

In the first approach, a new secret key K is used for each encryption, and a different value for S=md5(K) is obtained for each payload. Therefore, even if a plaintext attacker can get the secret S of one message, the attacker cannot use the captured secret to decrypt other messages. In the second approach, a single shared secret key K is used for the whole session; but the use of two hashed integers effectively prevents plaintext attacks. If an attacker knows T and E (T XOR HNXOR HN+1), then the attacker can determine (HNXOR HN+1), but not HNor HN+1individually. Thus, the attacker cannot figure out the future hashed integers. For example, although the attacker may also know that HN+1=md5(HN), that information does not help much, because currently there is no known way to find a value x given the quantity (x XOR md5(x)) except to perform a brute-force search.

The first approach stores the server's public key P in a browser cookie. This is not a security risk because P is not a secret. The second approach relies on the secret key K and HN, HN+1being stored in some secure place, such as inside an applet or some client storage that is not accessible from the public network.

FIG. 6is a block diagram that illustrates a computer system600upon which an embodiment of the invention may be implemented. Computer system600includes a bus602or other communication mechanism for communicating information, and a processor604coupled with bus602for processing information. Computer system600also includes a main memory606, such as a random access memory (“RAM”) or other dynamic storage device, coupled to bus602for storing information and instructions to be executed by processor604. Main memory606also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor604. Computer system600further includes a read only memory (“ROM”)608or other static storage device coupled to bus602for storing static information and instructions for processor604. A storage device610, such as a magnetic disk or optical disk, is provided and coupled to bus602for storing information and instructions.

The invention is related to the use of computer system600for encrypting data that is communicated between a client and a server that uses hypertext transfer protocol for application-layer communications. According to one embodiment of the invention, encrypting data that is communicated between a client and a server that uses hypertext transfer protocol for application-layer communications is provided by computer system600in response to processor604executing one or more sequences of one or more instructions contained in main memory606. Such instructions may be read into main memory606from another computer-readable medium, such as storage device610. Execution of the sequences of instructions contained in main memory606causes processor604to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

Computer system600also includes a communication interface618coupled to bus602. Communication interface618provides a two-way data communication coupling to a network link620that is connected to a local network622. For example, communication interface618may be an integrated services digital network (“ISDN”) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface618may be a local area network (“LAN”) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface618sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

The received code may be executed by processor604as it is received, and/or stored in storage device610, or other non-volatile storage for later execution. In this manner, computer system600may obtain application code in the form of a carrier wave.

6.0 EXTENSIONS AND ALTERNATIVES