System, method, and computer program product for zero round trip secure communications based on a noisy secret with a reduced message size
A system, method, and computer program product are provided for implementing zero round trip secure communications based on a noisy secret with a reduced message size. A receiver system receives from a sender system an encrypted message including encrypted message keys and a message MAC that is calculated and added for every sub-key. The receiver system determines if any one of the sub-keys is noiseless based on its corresponding message MAC. If none of the sub-keys are noiseless, the receiver system adjusts bits of the sub-keys until a sub-key with one noisy bit is found and corrected to form a noiseless sub-key. The noiseless sub-key is then processed to obtain a message key to decrypt the encrypted message.
1. A method, comprising:
a) receiving, by a receiver device, an encrypted message including encrypted message keys, and a message authentication code (MAC) that is calculated and added for every sub-key, from a sender system;
b) obtaining, by the receiver device, a number of a plurality of sub-keys from the received encrypted message;
c) obtaining, by the receiver device, a sub-key from the plurality of sub keys associated with the encrypted message;
d) utilizing, by the receiver device, a key derivation function to derive a key encryption key and a key MAC key associated with the sub-key;
e) calculating, by the receiver device, an encrypted message key MAC associated with the sub-key using the derived key MAC key;
f) determining, by the receiver device, whether the calculated encrypted message key MAC matches a received MAC for the sub-key;
g) determining, by the receiver device, that the sub-key does not have any noise if the calculated encrypted message key MAC matches the received MAC for the sub-key;
h) determining, by the receiver device, that the sub-key has noise if the calculated encrypted message key MAC does not match the received MAC for the sub-key;
i) repeating, by the receiver device, steps c though h until a noiseless sub-key is found or all of the plurality of sub-keys are determined to have noise;
j) if all of the plurality of sub-keys are determined to have noise, adjusting, by the receiver device, bits of a selected sub-key one by one, for each of the plurality of sub-keys, until a sub-key with one noisy bit is found and corrected to a noiseless sub-key;
k) deriving, by the receiver device, a key encryption key from the noiseless sub-key;
l) utilizing, by the receiver device, the key encryption key derived from the noiseless sub-key to decrypt a message key associated with the encrypted message; and
m) utilizing, by the receiver device, the message key to decrypt the encrypted message.
2. The method of claim 1 , wherein the receiver device obtains the sub-key from the encrypted message utilizing a same deterministic algorithm utilized by the sender system to select the plurality of sub-keys.
3. The method of claim 1 , wherein the receiver device obtains the sub-key from the encrypted message utilizing a mask that indicates selected bits generated by the sender system from selecting the plurality of sub-keys utilizing random selection.
4. The method of claim 1 , wherein the sender system utilizes a randomly generated message key for encrypting a message to send to the receiver device.
5. The method of claim 4 , wherein the sender system selects a plurality of different sub-keys from a negotiated noisy secret to encrypt the randomly generated message key.
6. The method of claim 5 , wherein the sender system encrypts the message utilizing the randomly generated message key.
7. The method of claim 6 , wherein the sender system sends the encrypted message, the encrypted message keys, and the message MAC that is calculated and added for every sub-key, to the receiver device such that the receiver device is able to perform a MAC-based verification to test sub-key validity of the plurality of different sub-keys.
8. A non-transitory computer readable medium storing computer code executable by a processor to perform a method comprising:
a) receiving, by a receiver device, an encrypted message including encrypted message keys, and a message authentication code (MAC) that is calculated and added for every sub-key, from a sender system;
b) obtaining, by the receiver device, a number of a plurality of sub-keys from the received encrypted message;
c) obtaining, by the receiver device, a sub-key from the plurality of sub keys associated with the encrypted message;
d) utilizing, by the receiver device, a key derivation function to derive a key encryption key and a key MAC key associated with the sub-key;
e) calculating, by the receiver device, an encrypted message key MAC associated with the sub-key using the derived key MAC key;
f) determining, by the receiver device, whether the calculated encrypted message key MAC matches a received MAC for the sub-key;
g) determining, by the receiver device, that the sub-key does not have any noise if the calculated encrypted message key MAC matches the received MAC for the sub-key;
h) determining, by the receiver device, that the sub-key has noise if the calculated encrypted message key MAC does not match the received MAC for the sub-key;
i) repeating, by the receiver device, steps c though h until a noiseless sub-key is found or all of the plurality of sub-keys are determined to have noise;
j) if all of the plurality of sub-keys are determined to have noise, adjusting, by the receiver device, bits of a selected sub-key one by one, for each of the plurality of sub-keys, until a sub-key with one noisy bit is found and corrected to a noiseless sub-key;
k) deriving, by the receiver device, a key encryption key from the noiseless sub-key;
l) utilizing, by the receiver device, the key encryption key derived from the noiseless sub-key to decrypt a message key associated with the encrypted message; and
m) utilizing, by the receiver device, the message key to decrypt the encrypted message.
9. The non-transitory computer readable medium of claim 8 , wherein the receiver device obtains the sub-key from the encrypted message utilizing a same deterministic algorithm utilized by the sender system to select the plurality of sub-keys.
10. The non-transitory computer readable medium of claim 8 , wherein the receiver device obtains the sub-key from the encrypted message utilizing a mask that indicates selected bits generated by the sender system from selecting the plurality of sub-keys utilizing random selection.
11. The non-transitory computer readable medium of claim 8 , wherein the sender system utilizes a randomly generated message key for encrypting a message to send to the receiver device.
12. The non-transitory computer readable medium of claim 11 , wherein the sender system selects a plurality of different sub-keys from a negotiated noisy secret to encrypt the randomly generated message key.
13. The non-transitory computer readable medium of claim 12 , wherein the sender system encrypts the message utilizing the randomly generated message key.
14. The non-transitory computer readable medium of claim 13 , wherein the sender system sends the encrypted message, the encrypted message keys, and the message MAC that is calculated and added for every sub-key, to the receiver device such that the receiver device is able to perform a MAC-based verification to test sub-key validity of the plurality of different sub-keys.
15. A receiver system, comprising:
a memory storing instructions, and
a computer processor executing the instructions for:
a) receiving, by the receiver system, an encrypted message including encrypted message keys, and a message authentication code (MAC) that is calculated and added for every sub-key, from a sender system;
b) obtaining, by the receiver system, a number of a plurality of sub-keys from the received encrypted message;
c) obtaining, by the receiver system, a sub-key from the plurality of sub keys associated with the encrypted message;
d) utilizing, by the receiver system, a key derivation function to derive a key encryption key and a key MAC key associated with the sub-key;
e) calculating, by the receiver system, an encrypted message key MAC associated with the sub-key using the derived key MAC key;
f) determining, by the receiver system, whether the calculated encrypted message key MAC matches a received MAC for the sub-key;
g) determining, by the receiver system, that the sub-key does not have any noise if the calculated encrypted message key MAC matches the received MAC for the sub-key;
h) determining, by the receiver system, that the sub-key has noise if the calculated encrypted message key MAC does not match the received MAC for the sub-key;
i) repeating, by the receiver system, steps c though h until a noiseless sub-key is found or all of the plurality of sub-keys are determined to have noise;
j) if all of the plurality of sub-keys are determined to have noise, adjusting, by the receiver system, bits of a selected sub-key one by one, for each of the plurality of sub-keys, until a sub-key with one noisy bit is found and corrected to a noiseless sub-key;
k) deriving, by the receiver system, a key encryption key from the noiseless sub-key;
l) utilizing, by the receiver system, the key encryption key derived from the noiseless sub-key to decrypt a message key associated with the encrypted message; and
m) utilizing, by the receiver system, the message key to decrypt the encrypted message.
16. The receiver system of claim 15 , wherein the receiver system obtains the sub-key from the encrypted message utilizing a same deterministic algorithm utilized by the sender system to select the plurality of sub-keys.
17. The receiver system of claim 15 , wherein the receiver system obtains the sub-key from the encrypted message utilizing a mask that indicates selected bits generated by the sender system from selecting the plurality of sub-keys utilizing random selection.
18. The receiver system of claim 15 , wherein the sender system utilizes a randomly generated message key for encrypting a message to send to the receiver system.
19. The receiver system of claim 18 , wherein the sender system selects a plurality of different sub-keys from a negotiated noisy secret to encrypt the randomly generated message key.
20. The receiver system of claim 19 , wherein the sender system encrypts the message utilizing the randomly generated message key.