Mechanism for generating message sequence order numbers

In one embodiment, a mechanism for generating message sequence order numbers is disclosed. In one embodiment, a method includes generating a timestamp value, and calculating a message authentication code (MAC) using as inputs the timestamp value, public information of an intended recipient, and a shared secret key kept between a broadcaster and the intended recipient. In addition, the method includes extracting, according to a pre-determined process agreed to between the broadcaster and the intended recipient, a required number of bits that define a size of an initial sequence number from the MAC. Lastly, the method includes using the extracted result as the initial sequence number.

TECHNICAL FIELD

The embodiments of the invention relate generally to data communications and, more specifically, relate to generating message sequence order numbers in data communications.

BACKGROUND

Data communications suffer from the weakness of intentional invasion by snoopers and other third-party interlopers. Even in cases where data communications are encrypted using some secure mechanism, such as Secure Sockets Layer (SSL), it is still possible for traffic analysis to be conducted where, both endpoints of the communication and how much traffic is passed between them may be determined. This is information that the endpoints may not have wanted to be public. In addition, some data communications may operate in environments where certain types of cryptography and ciphering are not a legal alternative for implementation.

Some conventional techniques for protection of broadcast data communication schemes generally present a few problems with data security. One problem is that the end points of the data communication cannot reliably authenticate who they are speaking with. Another problem is that information within the data communication may be disclosed to parties who the endpoints do not want to see the information.

In addition, conventional techniques for protection of broadcast data communication schemes do not provide for the secure ordering of sequences of messages sent in a randomized order. As a result, any third-party eavesdropper may find out who was supposed to receive which messages and in what order the messages were supposed to be sent. This is especially the case in those broadcast channels where export controls and legal restrictions on cryptographic software exist. Similarly, conventional techniques for protection of broadcast data communications typically have the problem that a broadcaster cannot guarantee that an intended recipient actually receives and processes the messages in a particular sequence in which the broadcaster intended the recipient to receive the messages. In light of the above problems, a way to ensure that broadcast of data communications falling under a sequenced order are not vulnerable to traffic analysis would be beneficial.

In addition, such a solution calls for the reliable and anonymous generation of the initial sequence number and thereby following sequence numbers. A solution that allows for the generation and communication of sequence numbers without having to publish what the initial sequence number (and thereby the following sequence numbers) are without having to reuse the same sequence would be beneficial.

DETAILED DESCRIPTION

Embodiments of the invention provide for generating message sequence order numbers. In one embodiment, a method for generating message sequence order numbers includes generating a timestamp value, and calculating a message authentication code (MAC) using as inputs the timestamp value, public information of an intended recipient, and a shared secret key kept between a broadcaster and the intended recipient. In addition, the method includes extracting, according to a pre-determined process agreed to between the broadcaster and the intended recipient, a required number of bits that define a size of an initial sequence number from the MAC. Lastly, the method includes using the extracted result as the initial sequence number.

FIG. 1is a block diagram of an exemplary network architecture in which embodiments of the invention may be implemented. The network architecture system100includes a broadcaster110and a plurality of recipients130coupled by a network120. Network120may be a public network (e.g., Internet) or a private network (e.g., Ethernet or a Local Area Network (LAN)). In one embodiment, each of the broadcaster110and recipients130is a computing system that engages in data communications. In some embodiments, broadcaster110sends out multicast or simulcast communications to each of the recipients130at the same time. In other embodiments, broadcaster110may communicate with recipients130in a unicast fashion. In yet other embodiments, broadcaster110and recipients130may be participating in a peer-to-peer data communication arrangement.

In addition, broadcaster110includes a sequence number module112and message authentication code (MAC) algorithm module114, while each recipient130also includes a sequence number module132and message authentication code (MAC) algorithm module134. These modules112,114,132,134may be used in conjunction to enable broadcaster110and recipients130to generate sequence numbers for data communications in a reliable, yet anonymous, fashion. The sequence numbers may be utilized by the broadcaster110and recipients130to send fragmented messages of an overall transmission in an anonymous and secure fashion. In particular, the broadcaster110may set up sequence numbers between the broadcaster and the one or more recipients130without having to publish what the initial sequence number (and thereby the following sequence numbers) is and without having to reuse the same sequence.

Embodiments of the invention depend on the cooperating parties to the transaction having a shared secret key, having public published information about the other parties, and each party having a secure time base that is not necessarily shared. Embodiments of the invention further utilize message authentication codes (MACs) to enable the secure, reliable, and anonymous creation and communication of the sequence numbers.

FIG. 2is a block diagram depicting one exemplary approach to utilize sequence numbers between a broadcaster and recipient according to embodiments of the invention. System200depicts a communication between broadcaster210and recipient220. In one embodiment, broadcaster210may be the same as broadcaster110and recipient220may be the same as recipient130, as described above with respect toFIG. 1. In one embodiment, broadcaster210is sending a message230to recipient220. Message230is part of a sequence of messages of an overall transmission being sent to recipient220. The overall transmission may be broken up into smaller sequence messages due to a variety of reasons, such as communication protocol size requirements, efficiency of communication, security, etc. Each message is assigned a unique sequence number that will be utilized on the receiving end to re-order the messages into the overall transmission.

Broadcaster210creates a MAC255by plugging a variety of inputs into MAC algorithm250. In one embodiment, the MAC algorithm modules114and134ofFIG. 1may be utilized to perform this function. As illustrated, the inputs into the MAC algorithm250include the message itself230, a shared secret key240, and the unique sequence number260assigned to the message. In some embodiments, the MAC algorithm250is an algorithm previously agreed upon between the broadcaster210and recipient220. The shared secret key240is a public-private key pair such that the private key of one actor and the public key of another can be combined to create a key the two actors will share. This shared secret key is unique between the broadcaster/recipient pair and is only known by the pair.

In one embodiment, the shared secret key is created using a Diffie Hellman key exchange protocol. The Diffie Hellman key exchange protocol is a cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher. One skilled in the art should have knowledge of how to establish a shared secret key using Diffie Hellman key exchange protocol. In other embodiments, other cryptographic protocols may be utilized to establish a shared secret key.

The message230and MAC255are then sent to the recipient220. The recipient220guesses the sequence number265of the message230(based upon a previously-agreed upon initial sequence number and sequence order scheme). This guessed sequence number265is incorporated with the message230and shared secret key240as inputs into MAC algorithm250to create a MAC270. The recipient220compares this MAC270with the MAC255sent with the message230to determine if there is a match. If so, then the recipient220is the intended recipient of the message230and the guessed sequence number265is the correct sequence number for the message230. If there is not a match, then the recipient should iteratively step through the possible sequence numbers265in creating MAC270until either a match is found or the possible sequence numbers are exhausted.

In some embodiments, a message may be sent to multiple recipients in a simultaneous fashion. In addition, the broadcaster210has the option of including multiple pseudo-MACs with the message230and sending multiple bogus messages with pseudo-MACs to the recipient220. As a result, the broadcaster210can send messages in such a way that, in addition to not being authenticated by anybody but the intended recipient220, the messages are no longer readable by anybody but the intended recipient220because they are sent in a random order so that no one but the intended recipient220would be able to put them back into order.

The scheme as illustrated inFIG. 2is repeated for each of the messages in the sequence of the overall transaction (which may be sent in a random order). In this way, at the end of all of the broadcasting, the recipient220will be able to put the received messages intended for the recipient back into order to determine the message of the overall transaction. In order for the illustrated approach of utilizing sequence numbers to be successful, the broadcaster210should have a system for creating and communicating an initial sequence number to the intended recipient(s) in a reliable and anonymous fashion. Embodiments of the invention described below provide a means to generate an initial sequence number (and thereby the following sequence numbers) with these goals in mind.

FIG. 3is a flow diagram depicting a method300of generating message sequence order numbers by a broadcaster according to one embodiment of the invention. Method300may be performed by processing logic at a broadcaster that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions run on a processing device), or a combination thereof. In one embodiment, method300is performed by the sequence number module112ofFIG. 1. In one embodiment, the broadcaster of method300may be broadcaster110or broadcaster210communicating with recipient130or recipient220over a network130, as described with respect toFIGS. 1and/or2.

Method300begins at block310where the broadcaster generates a timestamp value. This timestamp value may be an integer value that specifies the number of seconds or microseconds since a particular event (e.g., such as the typical event in many computing systems of midnight of Jan. 1, 1970).

Then, at block320, the broadcaster calculates a message authentication code (MAC) using as inputs the timestamp value, public information of the intended recipient, and a shared secret key kept between the broadcaster and the intended recipient. In some embodiments, the public information of the recipient is a public key, such as the public key utilized to create the shared secret key in the Diffie Hellman key exchange protocol.

At block330, the broadcaster then extracts a required number of bits defining a size of an initial sequence number from the resulting MAC and uses this result as the initial sequence number between the broadcaster and the recipient. In one embodiment, the required number of bits that define the size of the initial sequence number is a pre-determined number agreed to between the broadcaster and the intended recipient.

The extraction takes place according to a pre-determined process agreed to between the broadcaster and recipient. Such a process may include extracting the required number of bits from the beginning of the MAC, extracting the required number of bits from the end of the MAC, extracting some subset equal to the required number of bits from the middle of the MAC, or performing some function on the MAC that results in the required number of bits. For example, if a broadcaster is generating 64 bit sequence numbers and is operating under a construct that produces 256 bit MACs, then the broadcaster could extract the 64 bit subset directly from the 256 bit MAC (e.g., from the beginning, end, or middle). In addition, the broadcaster may perform a function on the MAC to produce the 64 bit result, such as dividing the 256 MAC into four 64 bit words and adding them together. One skilled in the art will appreciate that there are a variety of techniques to extract the requisite bits from the MAC to produce the initial sequence number.

At block340, the broadcaster computes a second MAC using the timestamp value, the extracted bits from the first MAC (i.e., the initial sequence number), and the shared secret key as inputs. Then, at block350, the broadcaster sends a message to the intended recipient including the timestamp value and the required number of bits that define the size of the initial sequence number. In addition, the broadcaster attaches the second calculated MAC to the message.

FIG. 4is a flow diagram depicting a method400of generating message sequence order numbers by a recipient according to one embodiment of the invention. Method400may be performed by processing logic at a broadcaster that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions run on a processing device), or a combination thereof. In one embodiment, method400is performed by the sequence number module132ofFIG. 1. In one embodiment, the recipient of method400may be recipient130or recipient220communicating with broadcaster110or broadcaster210over network130, as described with respect toFIGS. 1and/or2.

Method400begins at block410where the recipient receives a message from the broadcaster, the message including a timestamp value and a required number of bits defining a size of an initial sequence number. In addition, a MAC is attached to the message.

Then, at block420, the recipient calculates a first MAC using as inputs the timestamp value from the message, public information (e.g., a public key) of the recipient of the message, and a shared secret key kept between the recipient and the broadcaster. The public information and shared secret key are similar to those discussed above with respect toFIG. 3. At block430the recipient extracts the required number of bits (sent with the original message) from the calculated first MAC and uses this extracted result as the initial sequence number. In one embodiment, the extraction is performed according to a pre-determined process agreed to between the recipient and the broadcaster. Possible implementations of such an extraction process are described above with respect toFIG. 3.

Then, at block440, the recipient calculates a second MAC using as inputs the timestamp value and the extracted initial sequence number, as well as the shared secret key. At decision block450, the recipient determines whether the second MAC matches the MAC sent with the message. In some embodiments, the message may also include one or more pseudo-MACs and other MACs created for other recipients. The recipient should compare the second MAC against all of these other MACs for a match. If there is not match, then at block460, the recipient should discard the message (and attached MAC) and initial sequence number as not intended for the recipient. However, if there is a match, then the method400proceeds to block470where the recipient accepts and processes the message (and attached MAC) and the resulting initial sequence number as intended for the recipient.

In one embodiment, once the initial sequence number has been established between the broadcaster and recipient, they should be able to agree to a system for incrementing the sequence numbers, whether that system is one of linearly increasing the sequence numbers or a system of applying a function to the sequence numbers to create the next sequence number, for example. One skilled in the art will appreciate the variety of techniques that may be utilized to step through the sequence. As a result, the broadcaster and recipient are able to securely and anonymously initialize and communicate a sequence between each other without having to publish what the initial sequence number (and thereby the following sequence numbers) is and without having to reuse the same sequence.

In some embodiments, main memory504, static memory506, and/or data storage device518may be utilized to store public information, such as a public key, of either of the broadcaster or recipient as described above with respect to various embodiments of the invention.

The data storage device518may include a machine-accessible storage medium528on which is stored one or more set of instructions (e.g., software522) embodying any one or more of the methodologies of functions described herein. The software522may also reside, completely or at least partially, within the main memory504and/or within the processing device502during execution thereof by the computer system500; the main memory504and the processing device502also constituting machine-accessible storage media. The software522may further be transmitted or received over a network520via the network interface device508. In one embodiment, the network interface device508is operable to receive messages from either the broadcaster or the recipient described above in various embodiments of the invention.

The machine-readable storage medium528may also be used to store broadcast sequence number logic and/or recipient sequence number logic (e.g., sequence number modules112,132ofFIG. 1), and/or a software library containing methods that call the above applications. While the machine-accessible storage medium528is shown in an exemplary embodiment to be a single medium, the term “machine-accessible storage medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of instructions. The term “machine-accessible storage medium” shall also be taken to include any medium that is capable of storing, encoding or carrying a set of instruction for execution by the machine and that cause the machine to perform any one or more of the methodologies of the present invention. The term “machine-accessible storage medium” shall accordingly be taken to include, but not be limited to, solid-state memories, and optical and magnetic media.