Abstract:
A system is provided for cycling encryption keys to prevent the guessing of encrypted presence information in a shared information space. The system of the invention prevents malicious publication of presence information and ensures that only valid presence information is published to the shared information space. A malicious subscriber is prevented from knowing that he/she has been detected while a search is underway to determine his/her identity. During such a search, authorized subscribers are shifted to a new source of presence information while the malicious subscriber remains at the previous source.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates generally to communication systems that use shared information spaces such as tuple spaces to exchange data on users, and more particularly to a system for preserving privacy and confidentiality of such user data. 
     2. Background of the Invention 
     As described in our co-pending patent application Ser. Nos. 10/631,789, 10/631,747 and 10/631,834, filed on the same date as this application and respectively entitled “System and Method for Facilitating Communication Using Presence and Communication Services”; “Generation of Availability Indicators from Call Control Policies for Presence Enabled Telephony System”; and “Context Aware Call Handling System”, communication systems are being developed that are characterized by the interpretation of external events to facilitate personalized and customized services. One example of such a new application implemented service requires sharing awareness of a user&#39;s availability. Instead of controlling incoming calls and restricting access as traditional telephony does, this type of service attempts to engender useful communication by advertising the availability of potential collaborators. In order to do so, one or more ubiquitous sensors generate data regarding the user&#39;s location and activities, and apply such data to a context engine. Awareness data (that is raw data relating to the context of the user) is processed by the context engine to generate assertions that are then applied to a policy engine. The policy engine selects a call feature based on the user&#39;s context and policies. For example, a location service may report a user location as the washroom in response to which the context engine makes an ‘Out of Office’ assertion to a tuple space. In response to a call event such as “Incoming Call”, a “Forward to Voice Mail” feature is selected based on the user&#39;s context (that is in the washroom) and policies (that If user is “Out of Office” FORWARD any “Incoming Call” to voice mail). 
     From the foregoing example, it is clear that presence systems operate to share information about users that the users may wish to remain confidential. There are many gradations of privacy and it is anticipated that people will expect to have the ability to share availability information with various degrees of privacy. This leads to an expectation in such systems that the user may wish to politely decline presence requests in a manner that will avoid embarrassment or political problems for the user. 
     A particular problem with respect to the security of presence information results from the fact that presence information has only a few values. Even strongly encrypted presence information is vulnerable since the few possible encrypted values can usually be easily guessed. In addition, malicious attackers can publish presence information that would be embarrassing to the user. 
     Although research has been undertaken in the area of security in tuple spaces, none of such research has directly addressed the problem of using tuple spaces for open presence applications. 
     SUMMARY OF THE INVENTION 
     According to the present invention, a system is provided for cycling encryption keys to prevent the guessing of encrypted presence information. The system of the invention prevents malicious publication of presence information and ensures that only valid presence information is published to the shared information space. A malicious subscriber is prevented from knowing that he/she has been detected while a search is underway to determine his/her identity. During such a search, authorized subscribers are shifted to a new source of presence information while the malicious subscriber remains at the previous source. 
     According to a first aspect of the invention, a cycling key system is provided for protecting presence information, which typically changes slowly and has a restricted set of values. The cycling key operation masks presence information in both its values and its transitioning. It is important that the transitioning of presence values is masked since it is otherwise possible for an attacker to simply observe that presence information has changed and thereby conclude that the user has changed his/her location. For example, if the attacker is a “stalker”, knowing that the victim&#39;s location has changed at a time when the victim usually returns home can be dangerous. Additionally, the system according to the present invention prevents guessing of the encrypted representations of presence information, which is a problem due to the limited number of values it can take, by changing keys at random intervals not coincident with a change in value. This hides both the transitioning and addresses the limited representation problem in a robust manner. 
     According to a second aspect of the invention, multiple sites of presence information are provided which can be used for varying degrees of privacy, creating spoofing presence sites to foil attackers, and politely refusing service. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       A detailed description of the invention is set forth herein below, with reference to the following drawings in which: 
         FIG. 1 , is a block diagram of a privacy and security mechanism for a presence system using tuple spaces in accordance with the present invention; and 
         FIG. 2  is a block diagram of the presentity generating a new cycling key. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Before discussing the invention in detail, a brief introduction is set forth below of the basic structure and operation of a tuple space. 
     A tuple is a set of type/value ordered pairs called ingles. Each ingle consists of a type (e.g. Name) and a value (e.g. John Doe). Thus, a tuple which describes an employee for a company could, for example, be: 
     {:name John Doe :age 37 :employee number 12345 :start_date 810126 :position T12} 
     The tuple space enables coordination by allowing queries based on the matching of tuples by anti-tuples. An anti tuple is a tuple that can be used as a query in the tuple space. In form, it is identical to a tuple except that the value of any one or more fields may be replaced by a ‘?’, which indicates a ‘don&#39;t care’ condition. Tuple spaces are set up to match tuples with anti-tuples that agree in all fields except for the one(s) indicated by the ? query. Thus the anti tuple: 
     {:name ? :age 37 :employee_number ?:start_date ?:position T12} 
     would return the tuples for all employees of position T12 who are 37 years old. 
     Operations on the tuple space include: 
     Poke—place a tuple in the tuple space. Duration may be specified as to how long the tuple should remain in the space. This may be any period up to indefinite. 
     Peek—query the tuple space with an anti-tuple. This query may be specified to last for any period up to indefinite. Copies of matching tuples are returned through the interface and the tuples remain in the tuple space. 
     Pick—query the tuple space with an anti-tuple. This query may be specified to last for any period up to indefinite. Copies of matching tuples are returned through the interface and the tuples are removed from the tuple space. 
     Cancel—with the specified anti-tuple. All matching anti-tuples are removed from the tuple space. Tuples themselves may be removed directly by an appropriate pick request. 
     Additional operations may be provided such as disclosed in applicant&#39;s co-pending UK patent application No. 0200745.8 filed Jan. 14, 2002 entitled ‘Tuple Space Operations for Fine Grained Control’. 
       FIG. 1  shows the system according to the present invention. Presence memory  1  (i.e. tuple space) stores the presence tuples which contain indications of the availability or non-availability of external entities (i.e. persons or devices). It will be understood by a person of ordinary skill in the art that all references to tuple space or presence memory in this specification include any suitable shared information space (for example Java space, etc.) A presentity  3  is the entity that is connected to the external indicators of an entity&#39;s presence. It collects evidence from external sensors  5  and/or from control information sent by the represented entity, and uses this information and some internal polices to determine the entity&#39;s availability and other parameters that indicate its presence. The exact operation of presentity  3  is not pertinent to this disclosure beyond the fact that it stores presence information in an encrypted manner to prevent unauthorized access. 
     Presentity agent  7  is associated with the presentity  3  of an entity and controls access to the presence information. Since this information is encrypted, other entities desiring access to the information must undergo a process of mutual authentication and authorization with the presentity agent  7 . 
     Watcher  9  monitors the presence of an entity for another entity by entering into a cycling encryption protocol, decrypting the received presence information and making this available to the watching entity. Although only one watcher  9  is shown, any number of watchers may be provided for an identical number of subscriptions to presence information by an entity. 
     Watcher agent  11  manages the subscriptions to presence information for a specific entity. One watcher agent  11  is provided per entity. The watcher agent  11 , under direction of the entity, enters into the subscription negotiation for mutual authentication and authorization with the appropriate presentity agent  7 . 
     Public key directory  13  is a directory in which the unique public encryption keys of all watcher agents  11  and presentity agents  7  are kept. 
     Communication between components in this system is accomplished via messaging, as described in greater detail below. 
     First, all entities are provided with unique identifiers for addressing within the system. For example, identifiers may be in the form of URIs (universal resource indicators) in the form of Email addresses. Thus, an example of a unique identifier for the entity (that is person) John Doe whose email address is John_Doe@example.com would be John_Doe.example.com. The Internet naming process ensures that these names are unique and their use in standard operation is security against spoofing. 
     Unique names for other components in the systems associated with an entity may be derived using the familiar dot notation. For example: 
     
       
         
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 Watcher Agent 
                 wa.John_Doe.example.com 
               
               
                   
                 Presentity Agent 
                 pa.John_Doe.example.com 
               
               
                   
                 Presentity 
                 p.John_Doe.example.com 
               
               
                   
                   
               
             
          
         
       
     
     Watchers  9  require more information since a single watcher will be associated with every subscription between a pair of entities. For the example of a subscription for Richard Roe whose unique name is Richard_Roe.acme.com by John Doe whose unique name is John_Doe.example.com, the watcher  9  is w.Richard_Roe.acme.com.John_Doe.example.com or w.{Presentity Unique Name}.{Watcher Unique Name} 
     As indicated above, communication between components is via messages exchanged in the tuple space  1  by publishing and subscribing to information, as is well known in the art. 
     Messages used by components in this disclosure are in tuples of the format: 
                                     &lt;MESSAGE&gt;   &lt;Message Sequence Number&gt;       &lt;TO&gt;   &lt;Unique Name of Receiving Component&gt;       &lt;FROM&gt;   &lt;Unique Name of Sending Component&gt;       &lt;OPERATOR&gt;   &lt;Operator Function Code&gt;       &lt;SECURITY&gt;   &lt;Encypted Unique Name of sender concatenated           with a random word where double encryption is           used in accordance with standard public key           signatures for mutual authentication and           authorization&gt;       &lt;PARAMEMTERS&gt;   &lt;Optional Tuple Containing Parameters Pertinent           to the Operator&gt;                    
Operator&gt;
 
     The messages used in implementing this invention include, where the operator ‘+’ represents concatenation: 
     Subscribe 
     This message indicates the desire of a watcher agent  11  to subscribe to the presence information of a presentity  3 . As is well known in the art of tuple spaces, in order for the presentity  3  to receive the SUBSCRIBE message, it must first publish an anti-tuple to the shared space  1  with a “?” in the &lt;FROM&gt; field. Preferably, a state machine, as is known in the art performs communication protocol tasks over the tuple space. The SUBSCRIBE tuple is of the form: 
     
       
         
               
               
             
           
               
                   
               
             
             
               
                 &lt;MESSAGE&gt; 
                 &lt;Message Sequence Number&gt; 
               
               
                 &lt;TO&gt; 
                 &lt;Unique Name of Presentity Agent&gt; 
               
               
                 &lt;FROM&gt; 
                 &lt;Unique Name of Watcher Agent&gt; 
               
               
                 &lt;OPERATOR&gt; 
                 &lt;SUBSCRIBE&gt; 
               
               
                 &lt;SECURITY&gt; 
                 &lt;E priv.watcher {E pub.presentity {Unique name of watcher 
               
               
                   
                 agent + random}}&gt; 
               
               
                   
               
             
          
         
       
     
     In this specification, the conventional “E” notation is used before the name of the key used for encryption. Thus, E priv.watcher  expresses the operation of encryption with the private key of the watcher. 
     Subscribe_Reply 
     This message is returned as part of the subscription negotiation process from the presentity agent  7  to a watcher agent  11  which has sent a SUBSCRIBE method to start the process. It indicates whether or not the subscription request has been accepted and the indication of the first cycling key that can be used. The SUBSCRIBE_REPLY message is of the form: 
     
       
         
               
               
             
           
               
                   
               
             
             
               
                 &lt;MESSAGE&gt; 
                 &lt;Message Sequence Number&gt; 
               
               
                 &lt;TO&gt; 
                 &lt;Unique Name of Watcher Agent&gt; 
               
               
                 &lt;FROM&gt; 
                 &lt;Unique Name of Presentity Agent&gt; 
               
               
                 &lt;OPERATOR&gt; 
                 &lt;SUBSCRIBE_REPLY&gt; 
               
               
                 &lt;SECURITY&gt; 
                 &lt;E priv.presentity {E pub.watcher {Unique name of Watcher 
               
               
                   
                 Agent + Random}}&gt; 
               
               
                 &lt;KEY&gt; 
                 &lt;E priv.presentity {E pub.watcher {First Cycling Key&gt;}} 
               
               
                 &lt;IDENT_KEY&gt; 
                 &lt;Epriv.presentity {Unique Name of Presentity Agent + 
               
               
                   
                 Random }&gt; 
               
               
                   
               
             
          
         
       
     
     As described in greater detail below, the &lt;IDENT_KEY&gt; is used to create a hidden unique identifier that can be verified as coming only from the presentity agent  7 . Since only the presentity agent knows its private key, only it can create this key. The use of a random string concatenated with the unique id protects this identifier key from replay attacks. It will be appreciated that there are many other ways that this can be accomplished. One that has been used for digital cash is to encrypt a highly recognizable number. For example if the number has a palindromic binary representation then it will be very difficult for an attacker to guess a key that is the encrypted representation of it and it would be very easy for the intended receiver to verify authenticity and thus prevent spoofing. Thus, a random binary number of sufficient length may be generated, followed by generation of a palindromic number by appending a reversed representation of the binary number with itself (for example for the four-bit randomly generated number 1011, its corresponding palindromic number is 10111101). Such a number has unique properties that can be used to identify a particular sender yet, with encryption, would be very difficult for an attacker to guess. 
     Desubscribe 
     This message indicates the desire of watcher agent  11  to remove a subscription to a presentity  3 . This message does not physically remove the subscription but indicates to the presentity agent  7  that it can remove the watcher agent  11  from its internal lists of authorized watchers. The DESUBSCRIBE message is of the form: 
                                     &lt;MESSAGE&gt;   &lt;Message Sequence Number&gt;       &lt;TO&gt;   &lt;Unique Name of Presentity&gt;       &lt;FROM&gt;   &lt;Unique Name of Watcher&gt;       &lt;OPERATOR&gt;   &lt;UNSUBSCRIBE&gt;       &lt;SECURITY&gt;   &lt;E priv.watcher {E pub.presentity {Unique name of Watcher +           Random}}                    
Forced_Desubscribe
 
     This message is sent from the presentity agent  7  to the subscribed watcher agents  11  to inform them that their subscription to presence information has been removed. This message is of the form: 
     
       
         
               
               
             
           
               
                   
               
             
             
               
                 &lt;MESSAGE&gt; 
                 &lt;Message Sequence Number&gt; 
               
               
                 &lt;TO&gt; 
                 &lt;Unique Name of Watcher Agent&gt; 
               
               
                 &lt;FROM&gt; 
                 &lt;Unique Name of Presentity Agent&gt; 
               
               
                 &lt;OPERATOR&gt; 
                 &lt;FORCED_DESUBSCRIBE&gt; 
               
               
                 &lt;SECURITY&gt; 
                 &lt;E priv.presentity {E pub.watcher {Unique Name of Watcher 
               
               
                   
                 Agent + Random}}&gt; 
               
               
                   
               
             
          
         
       
     
     Since presence information is of a sensitive nature, there will be times when the subscription of a malicious user will be terminated involuntarily. In this case the sharing of the cycling key information with all subscribers in the normal manner (as described later) will have to be terminated. This is accomplished as noted below by removing all current subscriptions and the setting up of a new site of presence information in the presence memory. All subscribers are then notified of this and in response initiate re-subscriptions. The malicious subscriber need not be notified and the breached presence location may be maintained if desired conveying spurious information. 
     This message may also be used as an acknowledgement of a requested de-subscription. 
     The basic format of presence information may be changed according to user needs and in response to system evolution. However for this disclosure presence information is restricted to the single field that contains availability information. The other fields in the tuple, specifically IDENT_KEY, TOGGLE, NEXT_KEY, are keys used specifically to provide the privacy and security protection offered by the invention set forth in this disclosure. 
     Presence information is published or poked to the tuple space  1  by a presentity  3  in the form of a tuple: 
     
       
         
               
               
             
           
               
                   
               
             
             
               
                 &lt;IDENT_KEY&gt; 
                 &lt;E priv.presentity {Unique Name of Presentity Agent + 
               
               
                   
                 Random}:&gt; 
               
               
                 &lt;TOGGLE&gt; 
                 &lt;One of two or more unique values known to senders 
               
               
                   
                 and receivers that will be used to indicate a newly 
               
               
                   
                 entered tuple&gt; 
               
               
                 &lt;Availability&gt; 
                 &lt;E CURRENT     —     CYCLING     —     KEY {Available or 
               
               
                   
                 Non-Available)&gt; 
               
               
                 &lt;Next Key&gt; 
                 &lt;E CURRENT     —     CYCLING     —     KEY {Next_Cycling_Key}) 
               
               
                   
               
             
          
         
       
     
     Subscription information is protected according to the present invention using the well-known public key system. This provides for the capability of mutual authentication in the negotiation system and in the operation of the presence tuples, notably the IDENT_KEY that may be used to provide opaque multiple presence sites, as discussed in greater detail below. 
     The same public key system is used in the well-known way to insure that only a particular agent (i.e. watcher  9  or presentity  3 ) can create a specific value in a presence tuple or message, thereby providing user authentication. It also addresses the issue of non-repudiation of presence tuples and the prevention of presence tuple spoofing in a well-known way. 
     It will be appreciated by a person of skill in the art that the use of public key directory  13  implies that public keys are available for all presentity agents  7  and watcher agents  11 , which may be accessed using their unique identities. The directory  13  is used to the retrieve these public keys. 
     The cycling key system of the present invention addresses the problem that presence information can be observed in the outside world and consists of only a few values. Because of this paucity of unique values, even an encrypted presence value can reasonably be guessed because it changes slowly between only a small number of values. A malicious observer could observe an entity&#39;s behavior surreptitiously in the real world, guess its availability and watch the presence memory  1  for a presence tuple that is changing in synchrony with this observed behavior. The fact that the presence information is encrypted is not a hindrance to such a malicious watcher  9  since it would have only a few discrete values which, encrypted or not, serve as markers for presence. 
     To overcome this security flaw, the system of the present invention uses cycling keys generated by a presentity  3  to its authorized watchers  9  in the presence tuple and in the SUBSCRIBE_REPLY message. 
     The cycling key is a shared secret key that performs encryption by simply XORing with the target value. 
     An example of the method of operation of the present invention will now be described. 
     Subscription negotiation begins with a watcher agent  11  sending a SUBSCRIBE message to the agent  7  of the desired presentity  3 . The presentity agent  7  considers the request and replies with a SUBSCRIBE_REPLY message which contains the site to be used for storing presence information for a predetermined desired degree of privacy protection and an encrypted value of the first cycling key to be expected. 
     Upon receipt of the SUBSCRIBE_REPLY message, the watcher agent  11  creates a watcher  9  to handle the subscription. The watcher  9  subscribes to the indicated site and waits for the first presence tuple to be poked. 
     In this process the presentity agent  7  waits a reasonable amount of time (for example a few hundredths of a second) after sending a presence tuple before issuing a new tuple with the cycling key that it has given to the watcher agent  11  in the SUBSCIBE_REPLY message. 
     The watcher  9  receives this tuple and enters into the cycling key process described below. 
     However, in the event that the watcher  9  does not receive an initial tuple with the expected cycling key, it will detect invalid values when it decrypts the availability information. It then knows that it is out of sequence with the cycling key and in response requests synchronization by de-subscribing and re-subscribing. 
     The authorized watchers  9  subscribe to the presence site by issuing a subscription for the value of the IDENT KEY field that they have been given in the subscription process. At random intervals, the presentity  3  generates a new cycling key and provides it to the watchers  9  within the presence tuple. In particular, the presentity takes the current cycling key (i.e. the value it last generated and shared as a cycling key) and encrypts the presence (availability) information with it. The presentity  3  also encrypts the new cycling key with the current cycling key and then publishes this information as a tuple to the presence memory  1  for publication to all authorized watchers. The authorized watchers  9  then use the received key to decrypt both the availability information and the new key. The new key is then stored for use on the next presence tuple and the availability is used for whatever purpose needed. 
     In the event that the presence information changes (that is the user moves locations), the same procedure takes place. A new cycling key is generated, and a presence tuple with the new presence information is generated in the same manner as described above. Thus, changes in presence information are indistinguishable from random cycling key changes to a malicious watcher. 
     It is possible in some circumstances for a presence tuple to be missed with the result that a watcher  9  loses synchronization with the cycling key. In such a case, the watcher  9  will recognize that this is the case by seeing invalid values when it decrypts the presence information. In response, the watcher  9  notifies the watcher agent  11  of the problem. The watcher agent  11  then obtains resynchronization by de-subscribing and re-subscribing to the presentity  3  to obtain a valid cycling key through subscription negotiation. 
     Some important applications are possible resulting from the publishing of and subscription to presence tuples according to the system of the present invention. 
     Site of Presence Tuple 
     Presence information is shared by watchers  9  subscribing to tuples published by the presentities  3 . The IDENT_KEY field is the prime field used for the subscription. Informally, this can be considered to be a location within the presence memory  1  and therefore is referred to herein as the site of the presence tuple. Since this field is opaque, it allows a presentity  3  to have many sites of presence information without an unauthorized watcher  9  being aware of it. This ability for opaqueness and multiple sites has many uses, which are detailed as follows: 
     Prevention of Spoofing of Presence Tuple by Malicious Publisher 
     To prevent malicious users from entering false information into the system that would falsely represent an entity&#39;s presence, the IDENT_KEY is created as a secret value by each presentity  3 . As discussed above the presentity  3  creates this value by encoding its unique id with a random value. This creates a value that is very difficult for an attacker to guess. 
     Ensuring that a Tuple is from a Valid Publisher 
     Although an attacker will experience difficulty in trying to guess the IDENT_KEY value, a valid watcher  9  can confirm that a valid presentity  3  has created an IDENT_KEY by decoding it with the presentity&#39;s public key and observing the presentity&#39;s unique id within it. 
     Spoofing Presence to Deter Malicious and Undesired Watchers 
     The creation of an opaque site for the presence tuple also permits identification of malicious and undesired watchers by the creation of spoofing presence tuples. An example is when a subscription request arrives from an entity that a presentity  3  does not wish to have observe its presence. Circumstances may be such that a refusal to supply presence information would be impolite or politically unwise. In such a circumstance, the presentity  3  creates a spoofing site in which it can place false presence information. The presence negotiation is carried out normally as set forth above except that the undesired watcher  9  is provided with a site in which the presentity  3  can place false information that could appear to be reasonable. 
     In a similar manner as above, a presentity  3  may at times wish to rid itself of an undesired watcher  9  without the political problems incurred by forcing it to de-subscribe. This can be accomplished by de-subscribing all of its watchers except the undesired one. The de-subscribed watchers can then immediately re-subscribe and are directed to a newly created site. The undesired watcher remains at the previous site where it can be given false information. 
     Each of the above scenarios is analogous to trapping as used in the telephony case of trapping a malicious or obscene caller by causing the system to ignore his requests of disconnect by hanging up. However, according to the present invention trapping is done by subterfuge. The malicious watcher will be unaware of the action taken against it. 
     Various Levels of Privacy 
     The strategy of using opaque sites for presence information also allows for a presentity  3  to have multiple sites with presence information. As indicated above, this can be used to foil undesired watchers  9 . However it can also be used to provide different grades of presence information to various classes of watchers. Thus an entity can graduate the amount of private information it wishes to share with various classes of watchers such as work colleagues, personal friends, family and so on. 
     Modifications and variations of the invention are possible. All such modifications and variations are believed to be within the sphere and scope of the invention as defined by the claims appended hereto.