COMMUNICATING AN IDENTITY OF A GROUP SHARED SECRET TO A SERVER

• US 20130227292A1
• Filed: 12/10/2012
• Published: 08/29/2013
• Est. Priority Date: 02/29/2012
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: SUFFLING, David Robert
• Granted Patent: US 8,832,444 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

An identity is communicated by a client device to a server without requiring the identity to be disclosed to eavesdroppers and without requiring the use of symmetric or asymmetric cryptography. In one example, the identity is an identity of the client device, where the identity has been assigned to the client device by the server through the provisioning of a unique subset of client-identifying keys. In another example, the identity is an identity of a group shared secret that has been provisioned by the server to the client device.

Claims

1. A method to be performed by a provisioning server, the method comprising:

assigning to each of L group shared secrets {gss_q} its own unique subset of M_q of N group shared secret identifying keys;

storing information from which it is determinable which unique subset of M_q of the N group shared secret identifying keys was assigned to each group shared secret gss_q;

provisioning one or more client devices {j} by;

assigning to each client device j its own subset of P_j of the L group shared secrets {gss_q};

providing to each client device j the P_j group shared secrets that were assigned thereto; and

for each of the P_j group shared secrets assigned to each client device j, providing to the client device j the M_q group shared secret identifying keys that were assigned to that group shared secret,

wherein L, P_j, N, and M_q are positive integers, P_j is less than L, and M_q is less than N.

2. The method as claimed in claim 1, wherein the assigning of group shared secret identifying keys to group shared secrets {gss_q} is performed in a random or pseudo-random or quasi-random or arbitrary fashion and the stored information comprises records of which M_q of the N group shared secret identifying keys were assigned to each group shared secret gss_q.

3. The method as claimed in claim 1, wherein the assigning of group shared secret identifying keys to group shared secrets {gss_q} is performed according to an algorithm and the stored information comprises the algorithm or an inverse thereof.

4. The method as claimed in claim 1, further comprising:

making the stored information accessible to another server that is configurable to receive a message purporting to identify any of the group shared secrets {gss_q}.

5. The method as claimed in claim 1, wherein the subset of P_j shared secrets is unique to each client device j.

6. A method to be performed by a server, the method comprising:

storing information from which it is determinable which unique subset of M_q of N group shared secret identifying keys was assigned to each of L group shared secrets {gss_q}, where L, N, and M_q are positive integers and M_q is less than N;

when there is a change in a modulating value;

calculating for each of the N group shared secret identifying keys a hash of a combination comprising the group shared secret identifying key and the modulating value;

determining a hash-dependent value for each hash; and

associating each hash-dependent value with the group shared secret identifying key from which the corresponding hash was calculated or with an index of the group shared secret identifying key from which the corresponding hash was calculated;

receiving a message purporting to identify one of the L group shared secrets {gss_q}; and

determining whether the message identifies one of the L group shared secrets {gss_q}.

7. The method as claimed in claim 6, wherein determining whether the message identifies one of the group shared secrets {gss_q} comprises:

extracting from the message M_q components, each of the M_q components purporting to be a hash-dependent value determined from a hash of a combination comprising one of the group shared secret identifying keys and a current instance of the modulating value;

determining for each of the M_q components whether the component is consistent with any of the hash-dependent values;

where each of the M_q components is consistent with one of the hash-dependent values, using the association to determine the group shared secret identifying key that is associated with the consistent hash-dependent value;

using the stored information to determine whether the group shared secret identifying keys associated with the consistent hash-dependent values correspond to any of the unique subsets of group shared secret identifying keys that were assigned to the L group shared secrets {gss_q}; and

where the group shared secret identifying keys correspond to one of the unique subsets of client-identifying keys that was assigned to a particular one of the group shared secrets {gss_q}, determining that the message identifies the particular one of the group shared secrets {gss_q}.

8. The method as claimed in claim 7, wherein determining whether the component is consistent with any of the hash-dependent values comprises determining whether a portion of the component is consistent with a corresponding portion of any of the hash-dependent values.

9. The method as claimed in claim 6, further comprising:

determining whether the message was received from a client device that possesses the particular one of the group shared secrets {gss_q}.

10. The method as claimed in claim 9, wherein determining whether the message was received from a client device that possesses the particular one of the group shared secrets {gss_q} comprises:

extracting from the message a value purporting to be a value r and a value purporting to be a hash of a combination comprising the particular one of the group shared secrets {gss_q} and the value r, wherein r is a positive integer;

calculating a hash of a combination comprising the particular one of the group shared secrets {gss_q} and the extracted value purporting to be the value r;

comparing the calculated hash of the combination to the extracted value purporting to be the hash of the combination; and

where the values are consistent with one another, determining that the message was received from a client device that possesses the particular one of the group shared secrets {gss_q}.

11. A method to be performed by a server, the method comprising:

when there is a change in a modulating value;

calculating for each of L group shared secrets {gss_q} a hash of a combination comprising the group shared secret gss_q and the modulating value, wherein L is a positive integer;

determining a hash-dependent value for each hash; and

associating each hash-dependent value with the group shared secret from which the corresponding hash was calculated or with an index of the group shared secret from which the corresponding hash was calculated;

receiving a message purporting to identify a particular one of the L group shared secrets {gss_q}; and

determining whether the message identifies the particular one of the group shared secrets {gss_q}.

12. The method as claimed in claim 11, wherein determining whether the message identifies the particular one of the group shared secrets {gss_q} comprises:

extracting from the message a value purporting to be a hash-dependent value determined from a hash of a combination comprising the particular one of the group shared secrets {gss_q} and a current instance of the modulating value;

determining whether the extracted value is consistent with any of the hash-dependent values;

where the extracted value is consistent with one of the hash-dependent values, using the association to determine the group shared secret that is associated with the consistent hash-dependent value.

13. A provisioning server operative:

to assign to each of L group shared secrets {gss_q} its own unique subset of M_q of N group shared secret identifying keys;

to store information from which it is determinable which unique subset of M_q of the N group shared secret identifying keys was assigned to each group shared secret gss_q; and

to provision one or more client devices {j} by;

assigning to each client device j its own subset of P_j of the L group shared secrets {gss_q};

providing to each client device j the P_j group shared secrets that were assigned thereto; and

for each of the P_j group shared secrets assigned to each client device j, providing to the client device j the M_q group shared secret identifying keys that were assigned to that group shared secret,

wherein L, P_j, N, and M_q are positive integers, P_j is less than L, and M_q is less than N.

14. The provisioning server as claimed in claim 13, wherein the assigning of group shared secret identifying keys to group shared secrets {gss_q} is performed in a random or pseudo-random or quasi-random or arbitrary fashion and the stored information comprises records of which M_q of the N group shared secret identifying keys were assigned to each group shared secret gss_q.

15. The provisioning server as claimed in claim 13, wherein the assigning of group shared secret identifying keys to group shared secrets {gss_q} is performed according to an algorithm and the stored information comprises the algorithm or an inverse thereof.

16. The provisioning server as claimed in claim 13, wherein the stored information is accessible to another server that is configurable to receive a message purporting to identify any of the client devices {j}.

17. The provisioning server as claimed in claim 13, wherein the subset of P_j group shared secrets is unique to each client device j.

18. A server comprising:

a communication interface through which the server is able to receive a message purporting to identify a particular group shared secret from L group shared secrets {gss_q}; and

a memory storing information from which it is determinable which unique subset of M_q of N group shared secret identifying keys was assigned to each of the L group shared secrets {gss_q}, wherein the server, when there is a change in a modulating value, is operative;

to calculate for each of the N group shared secret identifying keys a hash of a combination comprising the group shared secret identifying key and the modulating value;

to determine a hash-dependent value for each hash; and

to associate each hash-dependent value with the group shared secret identifying key from which the corresponding hash was calculated or an index of the group shared secret identifying key from which the corresponding hash was calculated;

wherein the server is further operative to determine whether the message identifies one of the L group shared secrets {gss_q}, and

wherein L, N, and M_q are positive integers and M_q is less than N.

19. The server as claimed in claim 18, wherein determining whether the message identifies the particular one of the group shared secrets {gss_q} comprises:

extracting from the message M_q components, each of the M_q components purporting to be a hash-dependent value determined from a hash of a combination comprising one of the group shared secret identifying keys and a current instance of the modulating value;

determining for each of the M_q components whether the component is consistent with any of the hash-dependent values;

where each of the M_q components is consistent with one of the hash-dependent values, using the association to determine the group shared secret identifying key that is associated with the consistent hash-dependent value;

using the information to determine whether the group shared secret identifying keys associated with the consistent hash-dependent values correspond to any of the unique subsets of group shared secret identifying keys that were assigned to the L group shared secrets {gss_q}; and

where the group shared secret identifying keys correspond to one of the unique subsets of client-identifying keys that was assigned to a particular one of the group shared secrets {gss_q}, determining that the message identifies the particular one of the group shared secrets {gss_q}.

20. The server as claimed in claim 19, wherein determining whether the component is consistent with any of the hash-dependent values comprises determining whether a portion of the component is consistent with a corresponding portion of any of the hash-dependent values.

21. The server as claimed in claim 18, wherein the server is further operative to determine whether the message was received from a client device that possesses the particular one of the group shared secrets {gss_q}.

22. The server as claimed in claim 21, wherein determining whether the message was received from a client device that possesses the particular one of the group shared secrets {gss_q} comprises:

extracting from the message a value purporting to be a value r and a value purporting to be a hash of a combination comprising the one of the particular group shared secrets {gss_q} and the value r, wherein r is a positive integer;

calculating a hash of a combination comprising the particular one of the group shared secrets {gss_q} and the extracted value purporting to be the value r;

comparing the calculated hash of the combination to the extracted value purporting to be the hash of the combination; and

where the values are consistent with one another, determining that the message was received from a client device that possesses the particular one of the group shared secrets {gss_q}.

23. A server comprising:

a communication interface through which the server is able to receive a message purporting to identify a particular one of L group shared secrets {gss_q}, wherein L is a positive integer;

wherein the server, when there is a change in a modulating value, is operative;

to calculate for each of the L group shared secrets {gss_q} a hash of a combination comprising the group shared secret gss_q and the modulating value;

to determine a hash-dependent value for each hash; and

to associate each hash-dependent value with the group shared secret from which the corresponding hash was calculated or with an index of the group shared secret from which the corresponding hash was calculated;

wherein the server is further operative to determine whether the message identifies the particular one of the L group shared secrets {gss_q}.

24. The server as claimed in claim 23, wherein determining whether the message identifies the particular one of the group shared secrets {gss_q} comprises:

extracting from the message a value purporting to be a hash-dependent value determined from a hash of a combination comprising the particular one of the group shared secrets and a current instance of the modulating value;

determining whether the extracted value is consistent with any of the hash-dependent values;

where the extracted value is consistent with one of the hash-dependent values, using the association to determine the group shared secret that is associated with the consistent hash-dependent value.

25. A computer-readable medium storing code which, when executed by a processor of a provisioning server, causes the provisioning server:

to assign to each of L group shared secrets {gss_q} its own unique subset of M_q of N group shared secret identifying keys;

to store information from which it is determinable which unique subset of M_q of the N group shared secret identifying keys was assigned to each group shared secret gss_q; and

to provision one or more client devices {j} by;

assigning to each client device j its own subset of P_j of the L group shared secrets {gss_q};

providing to each client device j the P_j group shared secrets that were assigned thereto; and

for each of the P_j group shared secrets assigned to each client device j, providing to the client device j the M_q group shared secret identifying keys that were assigned to that group shared secret,

wherein L, P_j, N, and M_q are positive integers, P_j is less than L, and M_q is less than N.

26. A computer-readable medium storing information from which it is determinable which unique subset of M_q of N group shared secret identifying keys was assigned to each of L group shared secrets {gss_q}, the computer-readable medium further storing code which, when executed by a processor of a server, causes the server, when there is a change in a modulating value:

to calculate for each of the N group shared secret identifying keys a hash of a combination comprising the group shared secret identifying key and the modulating value;

to determine a hash-dependent value for each hash; and

to associate each hash-dependent value with the group shared secret identifying key from which the corresponding hash was calculated or with an index of the group shared secret identifying key from which the corresponding hash was calculated,

wherein the code, when executed by the processor, further results in the server determining whether a message received through a communication interface of the server and purporting to identify a particular group shared secret from the L group shared secrets {gss_q} identifies one of the L group shared secrets {gss_q}, and

wherein L, N, and M_q are positive integers and M_q is less than N.

27. A computer-readable medium storing code which, when executed by a processor of a server, causes the server, when there is a change in a modulating value:

to calculate for each of L group shared secrets {gss_q} a hash of a combination comprising the group shared secret gss_q and the modulating value, wherein L is a positive integer;

to determine a hash-dependent value for each hash; and

to associate each hash-dependent value with the group shared secret from which the corresponding hash was calculated or with an index of the group shared secret from which the corresponding hash was calculated,

wherein the code, when executed by the processor, further results in the server determining whether a message received through a communication interface of the server and purporting to identify a particular one of the L group shared secrets {gss_q} identifies the particular one of the L group shared secrets {gss_q}.