Synchronization of authentication ciphering offset6988197Abstract In a communication system, an authentication ciphering offset (ACO) is generated as a function of one or more parameters, wherein at least one of the one or more parameters is derived from earlier-computed values of the ACO. This enables each device to avoid generating an ACO value that is out of synchronization with a counterpart ACO value generated in another communication device. Claims What is claimed is: Description BACKGROUND
Turning now to FIG. 4, this illustrates an example in which delays in a Bluetooth system, either in transmission or processing, cause the two units A and B to end up with different ACO values, thereby making it impossible to communicate after encryption is turned on. Thus, despite the rule which facilitates communication in a situation like the one depicted in FIG. 3, delays could cause difficulty in communication in a Bluetooth system that uses the same rule. More specifically, at step 401, unit A wants to verify the identity of unit B, and so generates a challenge, denoted AU—RANDA. The challenge is transmitted to unit B. However at step 403, which is prior to receipt of the challenge from unit A, unit B also decides to verify the identity of unit A, and so generates its own challenge, denoted AU—RANDB. At step 405, unit B receives unit A's challenge (transmitted at step 401) and responds by calling E1 to generate the two parameters SRESA and ACOA. (The subscript A in the various parameters indicates that they are associated with unit A's challenge.) Unit B's generated response parameter, SRESA, is then transmitted back to unit A. Unit B generates this response knowing that its authentication request is open, and it will therefore use the ACO value generated by the master, unit A, according to the Bluetooth specification rule. At step 407, unit A receives unit B's response parameter, SRESA, at a time denoted tA, and responds by calling E1 to calculate expected response parameters SRES′A and ACOA. Unit A then can compare the expected signed response, SRES′A with the actual signed response, SRESA, to determine whether unit B is authentic. Unit A performs this calculation without knowing that nearly simultaneous verification events have taken place because unit B's request is received after its response to unit A's request, when unit A's authentication event is already closed. At step 409, unit A receives unit B's challenge and responds by calling E1 to generate the two parameters SRESB and ACOB. (The subscript B in the various parameters indicates that they are associated with unit B's challenge.) Unit A's generated response parameter, SRESB, is then transmitted back to unit B. At step 411, unit B receives unit A's response parameter, SRES B, at a time denoted tB. However, rather than calling E1 to calculate expected response parameters SRES′B and ACOB, unit B calculates SRES′B but retains ACOA from the master unit A in accordance with the rule of the Bluetooth specification. The problem illustrated in FIG. 4 arises because the authentication request from unit B AU—RANDB, generated at step 403 by unit B, is received by unit A (step 409) after receipt of the signed response SRESA, which is generated at step 405 by unit B and received at time tA at step 407 by unit A. Consequently, unit A does not know that the two authentication requests have been generated nearly simultaneously because unit A's authentication request event is closed at time tA before the authentication request generated by unit B is received. Therefore, unit A does not apply the Bluetooth specification rule that requires both units to use the master's ACO value, but instead uses ACOB. However, unit B receives unit A's authentication request, which is generated by unit A at step 401 and received by unit B at step 405 after unit B has generated its authentication request at step 403. Because the authentication request generated by unit A is received after the authentication request generated by unit B but before a response is received from unit A at step 411, unit B realizes that the two authentication requests are nearly simultaneous, and applies the Bluetooth specification rule which requires unit B to use the ACO value of the master unit, or ACOA. As a consequence of this time delay of unit B's authentication request, when the two devices later turn on encryption, unit A utilizes ACOB, as shown at step 413, and unit B utilizes ACOA, as shown at step 415. As a consequence, once encryption is turned on by the two units using different ACO values, communication will be impossible. In the examples described above, it was assumed that each unit generates its expected signed response, SRES′, only after receiving the actual signed response from the other unit. However, this is not a requirement, as a unit could, for example, generate its expected signed result (SRES′) at the same time that it generates the challenge, AU—RAND. Such a determination of when an SRES′ is generated may be dependent on the system in which it is being implemented. The Specification of the Bluetooth System, for example, leaves the particular implementation up to the developer. Because there is no requirement that it be done one way or the other, it is possible that one unit, made by a first manufacturer, will compute SRES′ at the same time that it generates the challenge, while the other unit, made by a different manufacturer, will generate its SRES′ only upon receiving the signed response from the other side. In such a scenario, the two units could again end up with different most-recently-generated values of ACO, which makes it impossible for them to generate the same encryption key when encryption is turned on. There is therefore, a need for a system that avoids the problems associated with the prior art, such as the possibility of ending up with different ACO values, and thereby using incompatible encryption. SUMMARY It should be emphasized that the terms "comprises" and "comprising", when used in this specification, are taken to specify the presence of stated features, integers, steps or components; but the use of these terms does not preclude the presence or addition of one or more other features, integers, steps, components or groups thereof. The foregoing and other objects are achieved by the present invention, which may be used in a communication system. One such system is the Bluetooth system. In accordance with an aspect of the invention, an authentication ciphering offset (ACO) is generated as a function of one or more parameters, wherein at least one of the one or more parameters is derived from earlier-computed values of the ACO. This enables each device to avoid generating an ACO value that is out of synchronization with a counterpart ACO value generated in another communication device thereby avoiding problems caused by uncontrollable delays associated with the prior art systems, for example. BRIEF DESCRIPTION OF THE DRAWINGS The objects and advantages of the invention will be understood by reading the following detailed description in conjunction with the drawings in which: FIG. 1 is a block diagram of two units, each having a link manager, a baseband transmitter and a baseband receiver; FIG. 2 is a timing diagram of authentication signaling in an instance when both units end up with a same value of ACO; FIG. 3 is a timing diagram of authentication signaling in the prior art in an instance when both units end up with different values of ACO; FIG. 4 is a timing diagram of authentication signaling in the prior art in an instance when both units have the potential of using different values of ACO because of a delayed signal; FIG. 5 is a flow diagram of the computation of an ACO value in accordance with one embodiment of the present invention; FIG. 6 is a timing diagram of how the present invention may be implemented in a communications system; and FIG. 7 is a timing diagram of how the present invention may be implemented in a communication system employing certain rules. DETAILED DESCRIPTION The various aspects of the invention will now be described in detail in connection with a number of exemplary embodiments and with respect to the figures, in which like parts are identified with the same reference characters. To facilitate an understanding of the invention, many aspects of the invention are described in terms of sequences of actions to be performed by elements of a computer system. It will be recognized that in each of the embodiments, the various actions could be performed by specialized circuits (e.g., discrete logic gates interconnected to perform a specialized function), by program instructions being executed by one or more processors, or by a combination of both. Moreover, the invention can additionally be considered to be embodied entirely within any form of computer readable storage medium having stored therein an appropriate set of computer instructions that would cause a processor to carry out the techniques described herein. Thus, the various aspects of the invention may be embodied in many different forms, and all such forms are contemplated to be within the scope of the invention. For each of the various aspects of the invention, any such form of embodiment may be referred to herein as "logic configured to" perform a described action. The problems associated with the prior art can be overcome by using a new function that generates the "Authentication Ciphering Offset" (ACO) as a function of all earlier-computed values of ACO, in addition to other possible parameters. As illustrated in FIG. 5, a triggering event (step 501) triggers a particular device or communications unit to calculate an ACO as a function of pre-determined parameters (step 503), at least one of which is derived from earlier computed values of the ACO. The triggering event 501 may be any one of a number of internal or external triggering events. For example, an external triggering event may be an authentication request, or a signed response received from another device. Examples of internal triggering events may include certain timed events, and the like. As to generating a new ACO value, any commutative binary function is sufficient for creating an ACO value based upon previous values, which is not dependent upon order. In an exemplary embodiment, each unit keeps a running sum (bitwise modulo-2) of the ACO values, and combines a most recent value of ACO with a presently generated value of X (produced by calling E1). Thus, after the kth call of E1, the ACO becomes: ##EQU1## where, in this exemplary embodiment, the sum is bitwise modulo-2. This sum may advantageously be generated by employing an exclusive-OR (XOR) function. The value of Xk may be computed in the conventional way, using the function denoted E1. Since the order of the elements in the sum is irrelevant, the two units A and B will have identical ACO values whenever the following result is satisfied:
Techniques other than summing all of the previous ACO values using XOR operations may also be employed. For example, any variety of functions using previous values of ACO may be employed to maintain the same ACO in both units, so long as the selected function or functions satisfy the commutative law. Simple boolean functions such as logical AND, NAND, OR, NOR, addition, subtraction, and multiplication functions could be used. One might, for example, use any commutative binary operations between Xk and ACOk-1, shown in Equation 3. Additionally, more complex functions, such as convolution sums, for example, could also be used. It should be noted, however, that simple binary functions other than XOR functions may not be desirable as they may create an ACO that, after many iterations, tends toward a specific result, thereby generating an ACO that may be predictable. Furthermore, more complex functions may not be desirable as they may increase the computational complexity of the algorithm significantly. However, as processing speeds increase, more complicated algorithms, or combinations of multiple algorithms may be desirable, as they may produce ACO values which are more difficult to predict. FIG. 6 illustrates an example of how the present invention may be employed in a communications system to avoid the problem illustrated in FIG. 3. In FIG. 3, challenges generated by both units nearly simultaneously cause the two units A and B to end up with different ACO values, thereby making it impossible to communicate after encryption is turned on. However, in FIG. 6, using the present invention, each new value of ACO is calculated using the previous ACO values, thereby allowing both units to end up with the same ACO values, and communicate even when encryption is switched on. In the situation illustrated in FIG. 6, unit A and unit B begin with equivalent ACO values. Specifically, unit A begins with ACOm in effect, and unit B begins with ACOn (which is equivalent to ACOm) in effect. At step 601, unit A wants to verify the identity of unit B, and so generates a challenge, denoted AU—RANDA. The challenge is transmitted to unit B. However, at step 603, which is prior to the receipt of the challenge from unit A, unit B also decides to verify the identity of unit A, and so generates its own challenge denoted AU—RANDB. At step 605, unit A receives unit B's challenge (transmitted at step 603) and responds by calling E1 to generate the two parameters SRESB and ACOm+1. In this example, ACOm+1 is derived as a function of AU—RANDB and the previous ACO value. ACOm+1 may be calculated in the manner described in equation 3, or using other suitable commutative binary functions. Unit A's generated response parameter SRESB is then transmitted back to unit B. Similarly, at step 607 unit B receives unit A's challenge (transmitted at step 601) and responds by calling E1 to generate the two parameters SRESA and ACOn+1. ACOn+1 is derived as a function of AU—RANDA and the previous ACO value. ACOn+1 may be generating using any commutative binary algorithm, including the one shown in equation 3, for example. Unit B's generated response parameter SRESA, is then transmitted back to unit A. At step 609, unit B receives unit A's response parameter, SRESB, and responds by calling E1 to calculate the expected response parameter SRES′B and ACOn+2, which is a function of AU—RANDB and ACOn+1. Unit B then can compare the expected signed response, SRES′B with the actual signed response, SRESB, to determine whether unit A is authentic. Similarly, at step 611, unit A receives unit B's response parameter SRESA and responds by calling E1 to calculate the expected response parameters SRES′A and ACOm+2, which is a function of AU—RANDA and ACOm+1. Unit A then can compare the expected signed response SRES′A with the actual signed response SRESA to determine whether unit B is authentic. Sometime later, the units decide to utilize encryption in their communication with one another, either at a predetermined time, or by a start encryption request. Accordingly, at step 613, unit A turns on encryption, using its most recently generated value of ACO to generate the encryption key that it will use. Similarly, at step 615, unit B turns on encryption using its most recently generated value of ACO to generate the encryption key that it will use. In this case, the most recently generated ACO value for unit A is ACOm+2, and the most recently generated ACO value for unit B is ACOn+2. However, these values will be equivalent if the two units begin with equivalent values (i.e., ACOm=ACOn), and if the operations performed at each generation of ACO values are commutative, so that the order of operation does not change the outcome of computation, such as the commutative function shown in Equation 3, for example. Thus, unit A and unit B will end up with equivalent ACO values, and will be able to communicate, even when encryption is switched on. Additionally, equivalent ACO values will be maintained in both units despite unknown delays or simultaneous authentication requests. Thus, the present invention alleviates the problem described in connection with FIG. 3. Turning now to FIG. 7, this illustrates an example in which the problem described in connection with FIG. 4 has been remedied using the present invention. In FIG. 4, delays in transmission or processing of a challenge in a Bluetooth system cause the two units to use different ACO values, making communication impossible once communication is switched on. Both units begin the situation described in FIG. 7 using equivalent ACO values (i.e., ACOm=ACOn). In FIG. 7, unit A generates an authentication request, or challenge, denoted AU—RANDA at step 701, which is then transmitted to unit B. Similarly, unit B transmits a request, or challenge AU—RANDB at step 703, which it transmits to unit A. At step 705, unit B receives the challenge generated by unit A at step 701, and generates the signed response SRESA and ACOn+1. ACOn+1 is computed as a function of AU—RANDA and the previous ACO value, namely ACOn. The signed response SRESA is then sent to unit A, which receives it at time tA shown at step 707. Unit A may then generate ACOm+1, which is a function of AU—RANDA and ACOm, the previous ACO value. Unit A may also generate at this step an expected signed response SRES′A so that it can validate the authenticity of unit B. At step 709, unit A receives the challenge generated by unit B at step 703, and in response, generates a signed response SRESB, and calculates ACOm+2, which is a function of AU—RANDB and ACOm+1. The calculation of each ACO value may be performed using any commutative binary operation, such as the one that is shown in equation 3, for example. Unit A then transmits the signed response to unit B, which receives it at time tB at step 711. Under the rules of the Bluetooth specification, unit B would retain ACOn+1 for future use, as both authentication requests were generated nearly simultaneously, which unit B is aware of due to the fact that it received a challenge from unit A while it had an open event (begun with the challenge generated at step 703). However, in accordance with the present invention, a new value ACOn+2 may instead be calculated at time tB at step 711 as a function of AU—RANDB and ACOn+1. This calculation may be accomplished using any commutative binary operation, such as the one shown in equation 3, for example. Thanks to the use of the present invention, when unit A and unit B decide to turn on encryption at step 713 and step 715, respectively, they will both use their latest ACO values, which are equivalent to one another, to determine an encryption key, and will therefore be able to communicate even when encryption is switched on. It should be noted, that the use and calculation of each ACO value by a particular unit associated with an event initiated by that unit is illustrated as being delayed until the event is closed in FIG. 7. However, this need not be the case, and the ACO value associated with that unit may be calculated at the time a challenge is issued by that unit, or at any other suitable time. However, potential problems may arise if an ACO value associated with a particular challenge event is used before the event is closed, in situations where an event is lost, not returned, or timed out, for example. The invention achieves a number of advantages over, and solves problems associated with, conventional approaches. It eliminates real-time requirements of guaranteed response time. It makes the order of ACO computations insignificant. Real-time issues with different delays between layers are less of a problem. Thus, the present invention allows real-time and non-real-time devices to be used in the same communications system, as it calculates ACO values independent of the order in which they are received. ACO values are also calculated independent of any delays in transmission, receiving, or processing. Moreover, the computational complexity of the invention is negligible. No extra storage is required compared to the old solution. The invention has been described with reference to a particular embodiment. However, it will be readily apparent to those skilled in the art that it is possible to embody the invention in specific forms other than those of the preferred embodiment described above. This may be done without departing from the spirit of the invention. Furthermore, the invention has been described with respect to particular embodiments to overcome the concern that delays in communication will cause the ACO parameters to be unsynchronized between two units. However, the same principle of making a parameter a function, at least in part, of its past values can be applied to any system where delays cause problems with synchronization of any such parameters. Some such systems may include, but are not limited to, any real-time systems in which unpredictable delays may exist, and can cause potential problems. Some examples of such systems may include: wireless systems, such as mobile telephony systems, wireless paging systems, and wireless Internet systems; and wired systems, such as the Internet, landline telephone systems, dial-up networking systems, LANs, WANs, or the like. Any system that has applications at both ends of a communications link that exchange data in which unpredictable delays may cause problems could benefit from using the present invention. Thus, the preferred embodiment is merely illustrative and should not be considered restrictive in any way. The scope of the invention is given by the appended claims, rather than the preceding description, and all variations and equivalents which fall within the range of the claims are intended to be embraced therein.
|
Same subclass Same class Consider this |
||||||||||