Computing device communication with replay protection

[0002] The present invention relates generally to communication between two computing devices. More specifically, the present invention relates to a cryptographic technique for preventing a replay attack during such communication.

[0003] During communication between two computing devices, it is always possible that an unscrupulous third party that is unauthorized may listen to the communication, may tamper with the communication, or may attempt to send spurious communications of its own. One particular attempt at fraud in the communications field is known as a “replay attack.”

[0004] FIG. 1 illustrates a prior art arrangement 100 that illustrates a replay attack. Shown is a client computer 102 communicating with a server computer 104 over any suitable known communication medium 106. In the course of this communication, client 102 sends operation message 108 to server computer 104. Message 108 may or may not be encrypted and may or may not be part of a secure session. In this illustration, an unscrupulous third party 110 uses any suitable means to detect the transmission of operation message 108 from client 102 to server 104. Because third party 110 detects message 108 in its entirety and is not seeking to understand message 108, it is irrelevant to third party 110 whether the message is encrypted or not.

[0005] As part of the replay attack, third party 210 takes message 108 captured earlier and resends it at a later time to server computer 104 which may be unaware that message 108 is coming from a third party. If the replay attack is implemented successfully the server will believe that message 108 is coming from client 102 when actually it is being transmitted by third party 110. Because server 104 is unaware of the origin of the message, it may perform the operation present in the message unaware that the message did not come from client 102. Depending upon the content of operation message 108, the results of server 104 performing this operation again may have disastrous results. For example, message 108 might be a command to delete particular data, modify data, increment a user's balance by particular amount, disgorge funds electronically, release sensitive information, etc.

[0006] Even if client 102 and server 104 had used sophisticated encryption to encrypt message 108 the server will be unaware that the message from the third party is bogus because the third party has replayed message 108 in it entirety and in its encrypted form. The illicit benefit received by third party 110 would not be the understanding of message 108, but the consequences of the operation performed by server 104 when it receives message 108 once again.

[0007] Accordingly, what is desired is a system and technique by which a replay attack during communication between computing devices may be prevented.

[0008] A replay attack prevention technique is disclosed that uses a secret algorithm exchanged between client and servers computers. The algorithm is used to periodically alter a special replay key. The replay key may then be used to alter the message sent or alter the digest appended to the message such that the message and or its digest varies as time progresses. An unscrupulous third party who replays a stolen operation message would be unaware of the replay key and its variation. Any stolen message that is replayed by the third party would not include the time varying aspect as expected by the server computer. The server computer would thus be able to detect the attempted fraud.

[0009] Preferably, the client and server exchange the secret algorithm before communication begins. The secret replay key may be exchanged at the beginning of the communication session in an encrypted form, or may be exchanged earlier. Because the replay key preferably never appears along with the message, and because the digest cannot be used to discover the replay key, the replay key is kept secret from third parties.

[0010] In a system embodiment of the invention, a client computing device and a server computing device communicate over a transmission medium. The client includes a message to be sent to the server over the transmission medium, a cryptographic key, and an alteration algorithm. The alteration algorithm is used to periodically change the cryptographic key, whereby a value to be appended to the message is periodically changed. The server receives the message and the appended value from the client. The server includes the same cryptographic key as in the client, and the same alteration algorithm. Thus, the server may calculate its own version of the value to compare with the received value from the client. A replay attack is prevented because a third party has neither the key or algorithm.

[0011] In a variation on this embodiment, the value is a digest calculated from the message using the cryptographic key. In this variation, the server has its own version of the digest calculated from the received message using the cryptographic key. In another embodiment, any number of alteration algorithms are held by the client and server along with an algorithm identifier that identifies which algorithm to be used for a particular transmission.

[0012] The invention, together with further advantages thereof, may best be understood by reference to the following description taken in conjunction with the accompanying drawings in which:

[0013] FIG. 1 illustrates a prior art arrangement that is subject to a replay attack.

[0014] FIG. 2 illustrates an arrangement for preventing a replay attack according to one embodiment of the invention.

[0015] FIGS. 3A and 3B are a flowchart describing how to implement replay protection according to one embodiment of the invention.

[0016] FIGS. 4 and 5 illustrate a computer system suitable for implementing embodiments of the present invention.

[0017] FIG. 2 illustrates an arrangement 200 for preventing a replay attack according to one embodiment of the invention. As in FIG. 1, a client computer 102 communicates with server computer 104 over communication medium 106. As before, third party 110 is attempting to illicitly detect operation message 108 and replay it to server computer 104. By previously exchanging a secret replay key alternation algorithm 202, client computer 102 and server computer 104 are able to produce a digest 204 which changes periodically. Once server 104 has received and verified message 108 and digest 204 from client 102 it alters its expectation of a received digest value. Even though third party 110 has captured operation message 108 and its appended digest 204, server computer 104 is expecting a different digest than that received via third party 110, and thus realizes that the subsequent replay of a transmission from third party 110 is bogus. In this fashion a replay attack is prevented.

[0018] It should be noted that client 102 and server 104 may each be any suitable computing device and not necessarily a client computer and a server computer. For example, either may be a personal computer, PDA, telephone, or any device capable of carrying out the steps below. In addition, client 102 and server 104 may be two smart cards communicating, or a smart card communicating with a card terminal or other computer.

[0019] FIGS. 3A and 3B are a flowchart describing how to implement replay protection according to one embodiment of the invention. In step 302 client computer 102 and server computer 104 exchange a secret replay key alteration algorithm known only to the two of them. This algorithm may be exchanged in any manner such as by voice, paper, telephone, electronic mail, facsimile, etc. Preferably, the secret algorithm is exchanged outside of the protected communication session to take place in order to preserve the secrecy of the algorithm. It is possible that more then one algorithm be exchanged so that the client and server may chose to use a particular algorithm when modifying a replay key. The algorithm chosen may be any suitable mathematical algorithm for modifying a replay key. Preferably, the algorithm modifies the key each time it is applied. By way of example, the algorithm may increment the key or decrement it by a particular amount.

[0020] In step 304 the client connects to the server over any suitable medium using any suitable protocol. By way of example, the two may communicate over the Internet using TCP/IP protocol, may use X25 protocol, may use PPP, or any other suitable communication protocol. The medium of communication may be any network, LAN, WAN, telephone line, or simple electronic connection between two computing devices.

[0021] In step 306 the client and server establish a secure session between the two of them for communication of commands and information. A secure session may be established in many different ways. By way of example, a secure session may be established using public key encryption, for example, SSL. Alternatively, symmetric cryptography may be used. Establishment of a secure session means that any information exchanged between the parties is encrypted and protected from outside parties.

[0022] In step 310 the client and server exchange a secret replay key within the secure session. Thus, an unscrupulous third party is not able to detect the replay key. Such a key may be any suitable number, for example a 128-byte value. Each party stores this replay key in a secure location. As an optional step 308, if the parties had previously exchanged multiple replay key alteration algorithms in step 302, they may also identify which of the algorithms to use during the session. Step 310 may also occur before this communication session is begun using any suitable medium and technique of exchange.

[0023] Next, the client begins preparation for sending an operation message to the server in order to implement a particular function such as data modification, data deletion, data querying, request for funds transfer, request for balance increment, request for release of information, etc. In step 314 the client generates the particular operation message it desires to send to the server. In step 316 the client uses the secret replay key to generate a digest from the operation message. Generating a digest using a key from a message is a known technique and will be appreciated by those of skill in the art. The digest is a unique sequence of information resulting from a combination of the message and the replay key. Should the replay key be altered, a different digest would be generated from the combination of the message and the altered replay key. In step 318 the client appends the newly generated digest to the operation message.

[0024] At this point in step 320 (although it may occur earlier or later), the client applies the secret replay key alternation algorithm to the replay key to update its value. For example, the alteration algorithm may simply increment the replay key by a certain amount. This alteration of the replay key prevents a third party from succeeding with a replay attack. The reason is that the server also alters its replay key in the same way that the client has done. At a given point in time, the version of the replay key used by the client to create a digest is the same version that the server will used to generate a digest for comparison. Because the replay key and the alteration algorithm are not known to the third party, the third party will not be able to generate the digest that is expected by the server because the replay key changes with every transmission from client to server. In other words, even though the third party may detect the exact sequence of bytes that represent operation message 108 and digest 204, the server computer may very well be expecting a different digest by the time the replayed transmission is received from the third party.

[0025] It should be pointed out that generation of a unique message and appended information may be implemented in another fashion instead of using a digest. Generation of a digest is preferable, however, as it is a faster technique. In the alternative technique, the secret alteration algorithm may be used to alter the replay key in a manner known only to the client and server. The altered replay key is then simply appended to the message. Both are then encrypted under the secure session and transmitted to the server. As above, even though the third party may detect the exact sequence of bytes representing the message and the replay key, it is unaware of the secret algorithm and is unable to alter the replay key over time as the server may be expecting.

[0026] In step 322 operation message 108 and its appended digest 204 are sent to the server. As part of the secure session, these elements may also be encrypted as well. In step 324 the server receives the message and its appended digest. If both have been encrypted under the secure session, the server then decrypts both using the protocol of the secure session. Next, in step 326 the server separates the digest from the message. In step 328 the server then generates its own digest using a combination of the received message and it own replay key. At this point in time, because the replay key used by the client is the same as the replay key held by the server, the digest generated by the server should be equivalent to the digest received from the client.

[0027] In step 330, the server compares the received digest to the digest it has generated on it own. If the digests are equivalent in step 332 then in step 334 the server performs operation message 108 received from the client. In step 336 the server then applies the alternation algorithm to its own replay key in order to update the key as the client had done in step 320. Thus, the client and server are synchronized in their alteration of the replay key. Step 336 is performed in a similar manner as had been performed by the client computer in step 320. At this point in time, the replay key of the server is equivalent to that of the client. Next, control returns to step 312 where preparation for another operation message to be exchanged between the client and the server is begun.

[0028] It should be apparent at this point that if an unscrupulous third party had detected the operation message and its appended digest and replayed it to the server such an attack would be unsuccessful. Because the server has altered its replay key in step 336 it will generate a different digest from that received from the unscrupulous third party. Should the digest not be equivalent, in step 338 the server simply rejects the operation message and prepares for another incoming message from the client computer.

[0029] Thus, it will be apparent that the replay key changes in a predictable manner according to the alternation algorithm and in a fashion previously agreed upon by the client and the server. In one embodiment of the invention, the replay key changes after ever operation message sent to the client from the server. The alternation algorithm may also be applied to the replay key at any other times and with different frequencies as long as the replay key used to generate a digest by the client for a particular message is the same replay key used by the server to generate its own digest for the same message. Because the third party is not aware of the changing replay key, it will attempt to send a detected operation message along with a digest that is out of date. Even though a server computer may receive a valid string of information encrypted appropriately under the secure session, it will generate a different digest then that received from the third party because the server computer has altered its replay key in the expectation of another operation message to be received from a valid client.

[0030] FIGS. 4 and 5 illustrate a computer system 900 suitable for implementing embodiments of the present invention. FIG. 4 shows one possible physical form of the computer system. Of course, the computer system may have many physical forms ranging from an integrated circuit, a smart card, a printed circuit board and a small handheld device up to a huge super computer. Computer system 900 includes a monitor 902, a display 904, a housing 906, a disk drive 908, a keyboard 910 and a mouse 912. Disk 914 is a computer-readable medium used to transfer data to and from computer system 900.

[0031] FIG. 5 is an example of a block diagram for computer system 900. Attached to system bus 920 are a wide variety of subsystems. Processor(s) 922 (also referred to as central processing units, or CPUs) are coupled to storage devices including memory 924. Memory 924 includes random access memory (RAM) and read-only memory (ROM). As is well known in the art, ROM acts to transfer data and instructions uni-directionally to the CPU and RAM is used typically to transfer data and instructions in a bi-directional manner. Both of these types of memories may include any suitable of the computer-readable media described below. A fixed disk 926 is also coupled bi-directionally to CPU 922; it provides additional data storage capacity and may also include any of the computer-readable media described below. Fixed disk 926 may be used to store programs, data and the like and is typically a secondary storage medium (such as a hard disk) that is slower than primary storage. It will be appreciated that the information retained within fixed disk 926, may, in appropriate cases, be incorporated in standard fashion as virtual memory in memory 924. Removable disk 914 may take the form of any of the computer-readable media described below.

[0032] CPU 922 is also coupled to a variety of input/output devices such as display 904, keyboard 910, mouse 912 and speakers 930. In general, an input/output device may be any of: video displays, track balls, mice, keyboards, microphones, touch-sensitive displays, transducer card readers, magnetic or paper tape readers, tablets, styluses, voice or handwriting recognizers, biometrics readers, or other computers. CPU 922 optionally may be coupled to another computer or telecommunications network using network interface 940. With such a network interface, it is contemplated that the CPU might receive information from the network, or might output information to the network in the course of performing the above-described method steps. Furthermore, method embodiments of the present invention may execute solely upon CPU 922 or may execute over a network such as the Internet in conjunction with a remote CPU that shares a portion of the processing.

[0033] In addition, embodiments of the present invention further relate to computer storage products with a computer-readable medium that have computer code thereon for performing various computer-implemented operations. The media and computer code may be those specially designed and constructed for the purposes of the present invention, or they may be of the kind well known and available to those having skill in the computer software arts. Examples of computer-readable media include, but are not limited to: magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD-ROMs and holographic devices; magneto-optical media such as floptical disks; and hardware devices that are specially configured to store and execute program code, such as application-specific integrated circuits (ASICs), programmable logic devices (PLDs) and ROM and RAM devices. Examples of computer code include machine code, such as produced by a compiler, and files containing higher level code that are executed by a computer using an interpreter.

[0034] Although the foregoing invention has been described in some detail for purposes of clarity of understanding, it will be apparent that certain changes and modifications may be practiced within the scope of the appended claims. For instance, the two computing devices may be the same or be quite different. The replay key and alteration algorithm may be exchanged well before a communication session, or during that session. The replay key may change after each transmission, or at other frequencies. A digest may be calculated or the key may be appended to the message directly and then encrypted. Therefore, the described embodiments should be taken as illustrative and not restrictive, and the invention should not be limited to the details given herein but should be defined by the following claims and their full scope of equivalents.