Abstract:
In order to provide a secure measurement of Round Trip Time (RTT), the calculation of RTT and the authentication data are separated. A device A sends a message to device B to start the method. Both devices generate a random number and device A waits for device B to finish. Device A sends its random number to B, which answers with its own random number, and device A calculates the RTT. If the RTT is below a certain limit, device A then requires authentication data, which is calculated by device B and sent to device A that verifies the authentication data. The RTT can thus be securely calculated regardless of the calculating resources of device B. Alternate embodiments, a system and devices are also provided.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to communication networks, and in particular to security in such networks. 
       BACKGROUND OF THE INVENTION 
       [0002]    Time-based distance is often used in the network field and is measured as the duration of a packet transmission between two devices. A standard Internet protocol, Internet Control Message Protocol (RFC 792; http://www.ietf.org/rfc/rfc792.txt), exists and permits the computation of a distance in milliseconds between two hosts. The associated command is called “ping” and the time-base distance is named Round Trip Time (RTT). This time-based distance is for instance used to decide whether two devices are in a local proximity. 
         [0003]      FIG. 1  illustrates the concept of local proximity in a network  100 . The network  100  comprises two Local Area Networks (LANs), LAN L 1   110  and LAN L 2   120 , interconnected by the Internet  130 . LAN L 1   110  comprises device A  112  and device C  114 , both within a circle  116  that illustrates local proximity, i.e. devices within the circle are considered close to a reference point, in this case device A. LAN L 2   120  comprises device B  122 , which is located outside of the circle  116 , which means that it is not considered close to device A. 
         [0004]    In the prior art, a usual method for device A to determine if device B is in its close proximity is based on time-based duration. Device A sends a series of ping commands to device B and measures the associated RTTs. As soon as device A obtains a RTT lower than a given limit (e.g. 7 ms), it considers that device B is in its local proximity. If not, after a number—typically 50 or 100—of RTTs greater than this limit, it considers that device B is not in its local proximity. 
         [0005]    Other methods exist where device A does not directly determine whether device B is near to it or not. For instance, device A may send messages to the device such that only devices in its local proximity receive it. A typical method is to send messages with a low Time-To-Live (TTL). These messages can only pass through a limited number (namely TTL) network nodes. 
         [0006]    However, the “ping” solution provides a low level of security. Device A has no means to ensure that the response to its ping command comes from device B and thus that the time-distance it measures relates to B. An attacker (located in LAN L 1 ) can block all pings to devices outside LAN L 1  and answer on their behalf. A would then consider that all those devices are in its local proximity. This failure is due to the lack of security in the prior art. 
         [0007]    A basic solution to that problem would be to authenticate ping responses using standard cryptographic means: device A sends a challenge (in its ping command to device B) and waits for the response. When receiving it, it can check that only device B could have computed the response. For example, device A can send a random number to device B and device B authenticates it e.g. by signing it. Device A then verifies the authentication code. In a second example, device A encrypts a challenge and sends it to device B that replies with the decrypted challenge. 
         [0008]    To prove that the ping response originates from it, device B has to perform cryptographic computations before answering device A. The time necessary for the computations may vary from one device to another and be very important on low-resource devices. The computation time may lead A to consider that low-resource devices are not in its local proximity, when this on the contrary is the case. This is clearly not always desirable. Naturally, device A could increase the limit so that low-resource devices have the time to perform the calculations and respond. However, doing so would often mean that high-resources devices outside the local proximity will be regarded as being inside, which usually is undesirable. 
         [0009]    WO 2004/014037 describes a method for secure authenticated distance measurement between a first and a second device. The first device authenticates the second device, exchanges a secret with it, and transmits a signal for distance measurement to it. The second device then modifies the received signal according to the secret and returns the modified signal. Upon reception of the modified signal, the first device measures the roundtrip time and verifies that the received signal was modified according to the exchanged secret. As will be appreciated, WO 2004/014037 may be seen as an implementation of the basic solution hereinbefore and suffers from at least some of its drawbacks. 
         [0010]    It can therefore be appreciated that there is a need for a method of calculating time based distance that is secure and independent of the resources of devices. This invention provides such a method. 
       SUMMARY OF THE INVENTION 
       [0011]    In a first aspect, the invention is directed to a method of secure calculation at a first device of time based distance to a second device in a network. The first device sends a first message to the second device and receives a second message in response, and calculates the time distance based on the time of transmission of the first message and the time of reception of the second message. The first device also receives a further message that comprises authentication data cryptographically linked to least the first message or at least the second message or at least the first message and the second message, and verifies the authentication data. 
         [0012]    In a preferred embodiment, the first device further sends a message to request the further message comprising authentication data if the calculated time based distance is below a predetermined limit. 
         [0013]    In a further preferred embodiment, the first message comprises a first cryptographic element and the second message comprises a second cryptographic element, and the authentication data is calculated based on the first and the second cryptographic elements. 
         [0014]    It is advantageous that the cryptographic elements are random numbers and the authentication data is a result of a function calculated using the random numbers, the function being dependent on a secret. It is also advantageous that the first device sends a fourth message to the second device to let it know that the method has been initiated, and generates the first cryptographic element. It is further advantageous that the first device waits a predetermined time so as to give the second device time to finish the generation of the second cryptographic element. 
         [0015]    In an alternative embodiment, the first device calculates authentication data, and wherein the message, sent to the second device to request the further message comprising authentication data of the second device, comprises the authentication data of the first device. 
         [0016]    In a further preferred embodiment, the first device further validates the calculation of the time based distance to the second device upon successful verification of the authentication data. 
         [0017]    In a second aspect, the invention is directed to a method of responding at a second device in a network to a protocol for secure calculation at a first device of time based distance to the second device. The second device receives, from the first device, a first message requesting a response for time based distance calculation. In response to the first message, it sends a second message. The second device then calculates authentication data, cryptographically linked to one of: at least the first message, at least the second message, and at least the first message and the second message, and sends, to the first device, a third message comprising the authentication data. 
         [0018]    In a third aspect, the invention is directed to a first device adapted for secure calculation of time based distance to a second device in a network. The first device comprises an input/output unit adapted to send a first message to the second device and receive from the second device a second message sent in response to the first message. The first device further comprises a processor adapted to calculate the time distance based on the time of transmission of the first message and the time of reception of the second message. The input/output unit is further adapted to receive a further message comprising authentication data cryptographically linked to one of: at least the first message, at least the second message, and at least the first message and the second message, and the processor is further adapted to verify the authentication data. 
         [0019]    In a preferred embodiment, the input/output unit is further adapted to send a message to request the further message comprising authentication data only if the calculated time based distance is below a predetermined limit. 
         [0020]    It may be advantageous that the processor is further adapted to calculate authentication data of the first device, and the input/output unit is further adapted to include the authentication data of the first device in the message sent to the second device to request the further message comprising authentication data of the second device. 
         [0021]    In a further preferred embodiment, the processor is further adapted to generate a first cryptographic element and to verify the authentication data, cryptographically linked by being based on the first cryptographic element and a second cryptographic element, and the input/output unit is further adapted to include the first cryptographic element in the first message, and to receive the second cryptographic element in the second message. 
         [0022]    In a fourth aspect, the invention is directed to a second device in a network adapted to respond to a protocol, launched at a first device, for secure calculation of time based distance to the second device. The second device comprises a processor adapted to calculate authentication data, cryptographically linked to one of: at least a first message, at least the second message, and at least the first message and the second message, and an input/output unit adapted to receive, from the first device, the first message, in response to the first message, send the second message to the first device, and send, to the first device, a third message comprising the authentication data. 
         [0023]    In a preferred embodiment, the input/output unit is further adapted to receive a message from the first device, the message comprising authentication data calculated by the first device. The processor is further adapted to verify the received authentication data and calculate its own authentication data only if the received authentication data is successfully verified. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0024]    Preferred features of the present invention will now be described, by way of example, with reference to the accompanying drawings, in which: 
           [0025]      FIG. 1 , discussed hereinbefore, is an illustration of a network and the concept of local proximity; 
           [0026]      FIG. 2  illustrates a flow chart of a preferred embodiment of the method according to the invention; 
           [0027]      FIG. 3  illustrates a flow chart of an alternative embodiment of the method according to the invention; and 
           [0028]      FIG. 4  illustrates a flow chart of a further alternative embodiment of the method according to the invention. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0029]      FIG. 2  illustrates a flow chart of a preferred embodiment of the method according to the invention. The method has three general phases:
       1. A pre-computation phase in which the method is initiated and first cryptographic computations are made.   2. A phase of time-based measurement of the distance between two devices, exchanging results of the pre-computation phase in a “ping”-like command.   3. A cryptographic verification phase, in which additional authentication data, cryptographically linked to the results exchanged in the “ping” messages, are computed and exchanged, as needed, and authentication is verified. In other words, it is verified that the sender of the response to the “ping” command is the sender of the authentication data, and the identity of the answering device is further verified.         
         [0033]    In the description hereinafter, it is assumed that device A  212  requires a secure measurement of the RTT to device B  216 . In other words, device A launches the protocol and device B responds to it. 
         [0034]    In one embodiment, device A and device B each has a X.509 certificate, certified by a common trusted entity, and an associated RSA private key. Before the start of the method, each device has knowledge of the certificate and the public key of the other device. A preferred embodiment, however, is described hereinafter. 
         [0035]    Device A  212  comprises a processor  213  for calculations and an input/output unit  214  for communication. Device B  216  also comprises a processor  217  for calculations and an input/output unit  218  for communication. 
         [0036]    The pre-computation phase begins when device A  212  sends a new measurement message  222  to device B  216 . The message  222  indicates that device A wishes to make a new RTT measurement. Upon reception of this message  222 , device B computes  224  a cryptographic element, preferably a random number (Random_B) that is new for each computation. Device A calculates  226  an independent cryptographic element, preferably a random number (Random_A) that is new for each computation, and waits  228  a predetermined time to give device B the time necessary for the computation. In a preferred embodiment, device A knows the maximum time necessary for B&#39;s computation, but it is also possible to use a pre-determined, general time value, e.g. if the maximum time is unknown to device A. 
         [0037]    The measurement phase begins when device A sends a message  242  comprising its cryptographic element to device B, and also notes  244  the time of transmission. Upon reception of A&#39;s message  242 , device B responds with a message  246  comprising its cryptographic element. Device A receives the message  246  and notes  248  the time of reception. With the time of transmission and the time of reception, device A then calculates  250  the RTT to device B. It should be noted, however, that at this point, device A has no means of knowing that the message  246  purportedly from device B in fact came from that device. 
         [0038]    In a preferred embodiment, when calculating  250  the RTT, device A also verifies if the RTT is below the given limit, i.e. if device B is in the local proximity. If this is not the case, i.e. if device B is not close, then there is no point in verifying that device B was the sender of message  246  and the method either stops or recommences—it has been mentioned hereinbefore that it is common to send a series of up to 50 or 100 ping messages to calculate the RTT to a device and stop as soon as one RTT is below a certain value. It is also possible for device A to restart the method without having received a response from device B, if the limit has been exceeded. However, if device A considers that device B is in the local proximity, then requires authentication data by sending a message  252  that indicates that the RTT is good, but that authentication data is needed. In an alternative embodiment, no “RTT is good” message  252  is sent and the rest of the method is performed automatically. 
         [0039]    The cryptographic verification phase then begins when device B, either automatically or in response to the “RTT is good” message  252 , then calculates  262  the required authentication data—cryptographically linked to the “ping” messages  242 ,  246 , in this case based on both A&#39;s and B&#39;s cryptographic elements—that it was the sender of the message  246  it sent to device A. The authentication data is preferably a concatenation of the two cryptographic elements signed with device B&#39;s private key. The preferred way of calculating the proof uses public key cryptography, but other ways, such as e.g. using secret key cryptography, are also possible. Device B then sends a message  264  comprising the authentication data to device A. In a preferred embodiment, the authentication data message  264  further comprises the certificate of device B. 
         [0040]    Upon reception of this message  264 , device A verifies  266  the authentication data. A successful verification means that the message  246  from device B indeed came from device B in response to the message  242  sent to it by device A. The verification is preferably performed by verifying that device B&#39;s certificate is a compliant certificate, i.e. by verifying the X.509 chain of trust; decrypting the signature; and checking that the result matches the concatenation of the cryptographic elements, Random_A and Random_B. Upon successful verification, device A validates the calculation of the time based distance to device B. Device A is now assured that it pinged device B and, if the RTT is good, that device B is in its local proximity. 
         [0041]    Consider  FIG. 1  where device B is not close to device A, and where an attacker C (located in LAN L 1 ) is able to block all pings to devices outside LAN L 1  and answer on their behalf. When device A uses the present invention, device C has no means of calculating B&#39;s authentication data, since he does not possess B&#39;s private key. Device C could obtain authentication data from device B beforehand by launching the protocol, passing himself off as device A. But, it this case, C would have to predict the cryptographic element generated by A, which is not possible. Else, the authentication data obtained from device B will not be valid if device C sends it to device A, which then will consider that B device is not in its local proximity. The method according to the invention is thus more secure than the prior art methods. 
         [0042]      FIG. 3  illustrates a flow chart of an alternative embodiment of the method according to the invention. The embodiment illustrated in  FIG. 3  is similar to the preferred embodiment, and the same steps will be denoted by the same reference numbers. 
         [0043]    Before the method starts, device B has calculated and stores at least one cryptographic element, preferably a random number. 
         [0044]    Device A starts the method by calculating  226  a cryptographic element, which is sent to device B in message  242 . Device A also notes  244  the time of transmission. Upon reception of the message  242 , device B uses  345  its stored cryptographic element and sends it in a message  246  to device A. Device A notes  248  the time of reception and calculates  250  the Round Trip Time (RTT). 
         [0045]    If the RTT is below a certain threshold, device A sends a message  252  to device B to let it know that the RTT is acceptable and that it requires authentication data. Device B then calculates the authentication data as described hereinbefore and sends the authentication data to device A in message  264 . Device A then verifies  266  the authentication data, and thereby the origin of the received “ping” message  246  the identity of device B. 
         [0046]    After having sent the message  264  comprising the authentication data, if device B only had one cryptographic element stored, it calculates  368  a new cryptographic element. 
         [0047]      FIG. 4  illustrates a flow chart of a further alternative embodiment of the method according to the invention. The embodiment illustrated in  FIG. 4  is similar to the preferred embodiment, and the same steps will be denoted by the same reference numbers. 
         [0048]    Device A starts the method by sending to device B a new measurement message  442 , preferably comprising the certificate of device A. Device A and device B calculate  226 ,  228  a cryptographic element each, and device A waits  228  to give B the time to finish the calculation. 
         [0049]    Device A sends a message  242  comprising its cryptographic element to device B and notes  244  the time of transmission. Upon reception of the message  242 , device B uses its calculated cryptographic element and sends it in a message  246  to device A. Device A notes  248  the time of reception and calculates  250  the Round Trip Time (RTT). 
         [0050]    If the RTT is below a certain threshold, device A calculates  451  authentication data (auth. data_A) to prove its identity and sends to device B a message  452  comprising the authentication data. The message  452  also lets device B know that the RTT is acceptable and that device A requires authentication data (auth. data_B) from device B. Upon reception of the message  452 , device B then verifies  454  the authentication data received from device A, which means that the message  242  from device A indeed came from device A. If device B is assured that it was pinged by device A, it calculates  262  the required authentication data as described hereinbefore and sends the authentication data to device A in message  264 . Device A then verifies  266  the authentication data, and thereby the origin of the “ping” response  246  and the identity of device B. 
         [0051]    This invention can for example be used in video diffusion on a network to ensure that only device in local proximity of a source receive the video. 
         [0052]    It can thus be appreciated that the present invention improves upon the prior art by providing a method of calculating time based distance that is secure and independent of the resources of devices. 
         [0053]    It will be understood that the present invention has been described purely by way of example, and modifications of detail can be made without departing from the scope of the invention. 
         [0054]    Each feature disclosed in the description and (where appropriate) the claims and drawings may be provided independently or in any appropriate combination. Features may, where appropriate be implemented in hardware, software, or a combination of the two. Connections may, where applicable, be implemented as wireless connections or wired, not necessarily direct or dedicated, connections. 
         [0055]    Reference numerals appearing in the claims are by way of illustration only and shall have no limiting effect on the scope of the claims.