Communicating an identity of a group shared secret to a server

• US 9,473,474 B2
• Filed: 07/16/2014
• Issued: 10/18/2016
• 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
• Primary Examiner(s): Williams, Jeffery
• Application Number:
  US14/332,617
• Publication Number:
  US 20140331052A1
• Time in Patent Office: 825 Days
• Field of Search: None
• US Class Current: 1/1
• 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 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}.

2. The method as claimed in claim 1, 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}.

3. The method as claimed in claim 2, 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.

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

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

5. The method as claimed in claim 4, 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}.

6. 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}.

7. The method as claimed in claim 6, 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.

8. 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.

9. The server as claimed in claim 8, 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}.

10. The server as claimed in claim 9, 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.

11. The server as claimed in claim 8, 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}.

12. The server as claimed in claim 11, 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}.

13. 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}.

14. The server as claimed in claim 13, 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.

15. A non-transitory 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.

16. A non-transitory 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}.