Techniques for key ratcheting with multiple step sizes

• US 10,735,384 B2
• Filed: 07/14/2017
• Issued: 08/04/2020
• Est. Priority Date: 02/17/2017
• Status: Active Grant

• Current Assignee: WhatsApp LLC (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Original Assignee: WhatsApp LLC (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Konigsberg, Derek Alan, Nachman, George, Yuen, Chun Wing, Kret, Ehren Andrew
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): Ahmed, Mahabub S
• Application Number:
  US15/649,929
• Publication Number:
  US 20180241725A1
• Time in Patent Office: 1,117 Days
• Field of Search: 713155
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• 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/065 for group communications cryptographic mechanisms or cryptographic arrangements for key management involving conference or group key H04L9/0833
• CPC Class Codes: H04L 63/0869 for achieving mutual authentication cryptographic mechanisms or cryptographic arrangements for mutual authentication H04L9/3273
• CPC Class Codes: H04L 63/126 the source of the received data
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/32 including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
• CPC Class Codes: H04W 12/033 of the user plane, e.g. user's traffic

Abstract

Techniques for key ratcheting with multiple step sizes are described. For example, an apparatus may be configured to receive two or more encrypted messages, where the encrypted messages are encrypted according to a multi-dimensional ratcheting encryption scheme. Moreover, the apparatus may be configured to determine which of the encrypted messages was most-recently received and extract a message iteration count from the most-recent encrypted message, generate a decrypted message by decrypting the encrypted message based on a decryption key, decompose the message iteration count into a plurality of message chain key iteration counts, and determine the decryption key based on the plurality of message chain key iteration counts.

Claims

1. A computer-implemented method, comprising:

receiving a first encrypted message and a second encrypted message, the first and second encrypted messages encrypted according to a multi-dimensional ratcheting encryption scheme;

determining, via at least one processor, which of the first encrypted message or the second encrypted message is a most-recent message;

discarding, via the at least one processor, the first encrypted message and skipping decryption of the first encrypted message based at least in part on the determination that the second encrypted message is the most-recent message;

extracting, via the at least one processor, a message iteration count for the second encrypted message;

decomposing, via the at least one processor, the message iteration count into a plurality of message chain key iteration counts;

determining, by the at least one processor, a decryption key based on the plurality of message chain key iteration counts; and

generating, by the at least one processor, a decrypted message by decrypting the second encrypted message based on the decryption key.

2. The method of claim 1, the decryption key based on a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, wherein the plurality of dimensions empowers variable-step advancement of the plurality of client chain keys.

3. The method of claim 2, wherein variable-step advancement of the plurality of client chain keys corresponds to discarding one or more encrypted messages, the one or more encrypted messages including the first encrypted message.

4. The method of claim 1, further comprising:

retrieving a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, the plurality of client chain keys corresponding to a plurality of client chain key iteration counts;

determining that the plurality of client chain key iteration counts equals the plurality of message chain key iteration counts;

determining the decryption key as a highest-dimension client chain key of the plurality of client chain keys; and

advancing two or more client chain keys of the plurality of client chain keys in response to decrypting the second encrypted message where a highest-dimension client chain key iteration count corresponding to the highest-dimension client chain key is equal to a maximum chain key iteration value.

5. The method of claim 1, further comprising:

retrieving a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, the plurality of client chain keys corresponding to a plurality of client chain key iteration counts;

determining that a client iteration count is less than the message iteration count, the client iteration count corresponding to a composition of the plurality of client chain key iteration counts;

generating a plurality of ratcheted client chain keys by advancing the plurality of client chain keys based on a iteration distance between the client iteration count and the message iteration count; and

determining the decryption key as a highest-dimension ratcheted client chain key of the plurality of ratcheted client chain keys.

6. The method of claim 5, wherein advancing the plurality of client chain keys comprises regenerating a higher-dimension client chain key based on advancing a lower-dimension client chain key, wherein regenerating the higher-dimension client chain key skips over one or more allowed iteration counts of the higher-dimension client chain key.

7. An apparatus, comprising:

at least one processor for executing stored instructions to;

receive a first encrypted message and a second encrypted message, the first and second encrypted messages encrypted according to a multi-dimensional ratcheting encryption scheme;

determine which of the first encrypted message or the second encrypted message is a most-recent message;

discard the first encrypted message and skip decryption of the first encrypted message based at least in part on the determination that the second encrypted message is the most-recent message;

extract a message iteration count for the second encrypted message;

decompose the message iteration count into a plurality of message chain key iteration counts; and

determine the decryption key based on the plurality of message chain key iteration counts; and

generate a decrypted message by decrypting the second encrypted message based on a decryption key.

8. The apparatus of claim 7, the decryption key based on a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, wherein the plurality of dimensions empowers variable-step advancement of the plurality of client chain keys.

9. The apparatus of claim 8, wherein variable-step advancement of the plurality of client chain keys corresponds to discarding one or more encrypted messages, the one or more encrypted messages including the first encrypted message.

10. The apparatus of claim 7, further comprising:

the key management component operative to retrieve a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, the plurality of client chain keys corresponding to a plurality of client chain key iteration counts;

determine that the plurality of client chain key iteration counts equals the plurality of message chain key iteration counts;

determine the decryption key as a highest-dimension client chain key of the plurality of client chain keys; and

advance two or more client chain keys of the plurality of client chain keys in response to decrypting the second encrypted message where a highest-dimension client chain key iteration count corresponding to the highest-dimension client chain key is equal to a maximum chain key iteration value.

11. The apparatus of claim 7, further comprising:

the key management component operative to retrieve a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, the plurality of client chain keys corresponding to a plurality of client chain key iteration counts;

determine that a client iteration count is less than the message iteration count, the client iteration count corresponding to a composition of the plurality of client chain key iteration counts;

generate a plurality of ratcheted client chain keys by advancing the plurality of client chain keys based on a iteration distance between the client iteration count and the message iteration count; and

determine the decryption key as a highest-dimension ratcheted client chain key of the plurality of ratcheted client chain keys.

12. The apparatus of claim 11, wherein advancing the plurality of client chain keys comprises regenerating a higher-dimension client chain key based on advancing a lower-dimension client chain key, wherein regenerating the higher-dimension client chain key skips over one or more allowed iteration counts of the higher-dimension client chain key.

13. At least one non-transitory computer-readable storage medium comprising instructions that, when executed by at least one processor, cause a system to:

receive a first encrypted message and a second encrypted message, the first and second encrypted messages encrypted according to a multi-dimensional ratcheting encryption scheme;

determine which of the first encrypted message or the second encrypted message is a most-recent message;

discard the first encrypted message and skip decryption of the first encrypted message based at least in part on the determination that the second encrypted message is the most-recent message;

extract a message iteration count for the second encrypted message;

decompose the message iteration count into a plurality of message chain key iteration counts;

determine a decryption key based on the plurality of message chain key iteration counts;

generate a decrypted message by decrypting the second encrypted message based on the decryption key.

14. The non-transitory computer-readable storage medium of claim 13, the decryption key based on a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, wherein the plurality of dimensions empowers variable-step advancement of the plurality of client chain keys.

15. The non-transitory computer-readable storage medium of claim 14, wherein variable-step advancement of the plurality of client chain keys corresponds to discarding one or more encrypted messages, the one or more encrypted messages including the first encrypted message.

16. The non-transitory computer-readable storage medium of claim 13, comprising further instructions that, when executed by the at least one processor, cause the system to:

retrieve a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, the plurality of client chain keys corresponding to a plurality of client chain key iteration counts;

determine that the plurality of client chain key iteration counts equals the plurality of message chain key iteration counts; and

determine the decryption key as a highest-dimension client chain key of the plurality of client chain keys.

17. The non-transitory computer-readable storage medium of claim 16, comprising further instructions that, when executed by the at least one processor, cause the system to:

advance the highest-dimension client chain key by one step in response to decrypting the second encrypted message where a highest-dimension client chain key iteration count corresponding to the highest-dimension client chain key is less than a maximum chain key iteration value.

18. The non-transitory computer-readable storage medium of claim 16, comprising further instructions that, when executed by the at least one processor, cause the system to:

advance two or more client chain keys of the plurality of client chain keys in response to decrypting the second encrypted message where a highest-dimension client chain key iteration count corresponding to the highest-dimension client chain key is equal to a maximum chain key iteration value.

19. The non-transitory computer-readable storage medium of claim 13, comprising further instructions that, when executed by the at least one processor, cause the system to:

retrieve a plurality of client chain keys, the plurality of client chain keys corresponding to a plurality of dimensions of the multi-dimensional ratcheting encryption scheme, the plurality of client chain keys corresponding to a plurality of client chain key iteration counts;

determine that a client iteration count is less than the message iteration count, the client iteration count corresponding to a composition of the plurality of client chain key iteration counts;

generate a plurality of ratcheted client chain keys by advancing the plurality of client chain keys based on an iteration distance between the client iteration count and the message iteration count; and

determine the decryption key as a highest-dimension ratcheted client chain key of the plurality of ratcheted client chain keys.

20. The non-transitory computer-readable storage medium of claim 13, wherein advancing the plurality of client chain keys comprises regenerating a higher-dimension client chain key based on advancing a lower-dimension client chain key, wherein regenerating the higher-dimension client chain key skips over one or more allowed iteration counts of the higher-dimension client chain key.