Message encryption and decryption utilizing low-entropy keys
View Patent ↗In one embodiment, a first message is obtained and encrypted to produce a ciphertext. The first message is encrypted such that decryption of the ciphertext utilizing a first key yields the first message, and decryption of the ciphertext utilizing a second key different than the first key yields a second message that is distinct from the first message but shares one or more designated characteristics with the first message. Encrypting the first message may more particularly comprise mapping the first key to a first seed, mapping the first message to a second seed, determining an offset between the first and second seeds, and generating the ciphertext based on the determined offset. Such an arrangement prevents an attacker from determining solely from the second message if decryption of the ciphertext has been successful or unsuccessful. Other embodiments include decryption methods, apparatus for encryption and decryption, and associated articles of manufacture.
1. A method comprising:
obtaining a first message; and
encrypting the first message to produce a ciphertext;
wherein encrypting the first message comprises mapping a first key to a first seed, mapping the first message to a second seed, determining an offset between the first and second seeds, and generating the ciphertext based on the determined offset;
wherein the first message is encrypted such that decryption of the ciphertext utilizing the first key yields the first message and decryption of the ciphertext utilizing a second key different than the first key yields a second message that is distinct from the first message but shares one or more designated characteristics with the first message in a manner that prevents an attacker from determining solely from the second message if decryption of the ciphertext has been successful or unsuccessful; and
wherein the obtaining and encrypting are performed by at least one processing device comprising a processor coupled to a memory.
2. The method of claim 1 wherein the first and second keys comprise respective valid and invalid low-entropy keys.
3. The method of claim 1 wherein decryption of the ciphertext utilizing respective ones of a plurality of additional keys different than the first key yields respective additional messages that are distinct from the first message but share designated characteristics with the first message in a manner that prevents an attacker from determining solely from a given one of the additional messages if decryption of the ciphertext has been successful or unsuccessful, and wherein an increase in a maximum number of additional messages does not require any increase in a size of the ciphertext.
4. The method of claim 1 wherein the first message comprises a valid password vault comprising a plurality of passwords, the first key comprises a master password of the password vault and the second message comprises an invalid password vault that is configured to appear valid to an attacker.
5. The method of claim 1 wherein the first message comprises a template utilized to generate multiple invalid password vaults.
6. The method of claim 1 further comprising the steps of:
partitioning a password space into multiple equivalence classes such that each equivalence class comprises passwords having a common password syntax; and
generating keys for respective ones of the equivalence classes;
wherein the ciphertext is generated at least in part utilizing a key generated for a particular one of the equivalence classes.
7. The method of claim 1 wherein the first message comprises a permutation utilized to map passwords to accounts in a password vault, the first key comprises a master password of the password vault and the second message comprises an invalid permutation that is configured to appear valid to an attacker.
8. The method of claim 1 wherein the first message comprises a key utilized to select a password from a password space.
9. A method comprising:
obtaining a first message; and
encrypting the first message to produce a ciphertext;
wherein the ciphertext comprises an offset between a first seed associated with the first message and another seed generated by applying a key-to-seed mapping to a first key;
wherein the first message is encrypted such that decryption of the ciphertext utilizing the first key yields the first message and decryption of the ciphertext utilizing a second key different than the first key yields a second message that is distinct from the first message but shares one or more designated characteristics with the first message in a manner that prevents an attacker from determining solely from the second message if decryption of the ciphertext has been successful or unsuccessful; and
wherein the obtaining and encrypting are performed by at least one processing device comprising a processor coupled to a memory.
10. The method of claim 9 wherein the ciphertext is of the form (δ,x) where δ=ĝ −1 (m)−ƒ x (κ) denotes the offset, m denotes the first message, ĝ −1 (m) denotes a message-to-seed mapping, κ denotes the first key, ƒ x (κ) denotes the key-to-seed mapping and x denotes a supplementary key utilized by the key-to-seed mapping.
11. The method of claim 10 wherein the message-to-seed mapping g −1 (m) is implemented as a function that determines multiple seeds that each map to m and then selects a particular one of the multiple seeds.
12. The method of claim 10 wherein the supplementary key is selected independently from a designated key space for each of a plurality of iterations of said encrypting.
13. The method of claim 10 wherein the key-to-seed mapping comprises at least one of a hash function and a pseudorandom permutation.
14. An article of manufacture comprising a non-transitory processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by at least one processing device cause said at least one processing device:
to obtain a first message; and
to encrypt the first message to produce a ciphertext;
wherein encrypting the first message comprises mapping a first key to a first seed, mapping the first message to a second seed, determining an offset between the first and second seeds, and generating the ciphertext based on the determined offset; and
wherein the first message is encrypted such that decryption of the ciphertext utilizing the first key yields the first message and decryption of the ciphertext utilizing a second key different than the first key yields a second message that is distinct from the first message but shares one or more designated characteristics with the first message in a manner that prevents an attacker from determining solely from the second message if decryption of the ciphertext has been successful or unsuccessful.
15. An apparatus comprising:
at least one processing device comprising a processor coupled to a memory;
wherein said at least one processing device is configured to obtain a first message and to encrypt the first message to produce a ciphertext;
wherein encrypting the first message comprises mapping a first key to a first seed, mapping the first message to a second seed, determining an offset between the first and second seeds, and generating the ciphertext based on the determined offset; and
wherein the first message is encrypted such that decryption of the ciphertext utilizing the first key yields the first message and decryption of the ciphertext utilizing a second key different than the first key yields a second message that is distinct from the first message but shares one or more designated characteristics with the first message in a manner that prevents an attacker from determining solely from the second message if decryption of the ciphertext has been successful or unsuccessful.
16. The apparatus of claim 15 wherein the ciphertext is of the form (δ,x) where δ=ĝ −1 (m)−ƒ x (κ) denotes the offset, m denotes the first message, ĝ −1 (m) denotes a message-to-seed mapping, κ denotes the first key, ƒ x (κ) denotes a key-to-seed mapping and x denotes a supplementary key utilized by the key-to-seed mapping.
17. A method comprising:
obtaining a ciphertext; and
decrypting the ciphertext to produce a first message;
wherein the first message results from decrypting the ciphertext using a first key;
wherein decrypting the ciphertext to produce the first message comprises mapping the first key to a first seed, applying an offset of the ciphertext to the first seed to generate a second seed, and mapping the second seed to the first message;
wherein the ciphertext is configured such that decryption of the ciphertext utilizing a second key different than the first key yields a second message that is distinct from the first message but shares one or more designated characteristics with the first message in a manner that prevents an attacker from determining solely from the second message if decryption of the ciphertext has been successful or unsuccessful; and
wherein the obtaining and decrypting are performed by at least one processing device comprising a processor coupled to a memory.
18. The method of claim 17 wherein decrypting the ciphertext to produce the first message comprises computing m=g(ƒ x (κ)+(δ) where m denotes the first message, δ denotes the offset, g denotes a seed-to-message mapping, κ denotes the first key, ƒ x (κ) denotes a key-to-seed mapping and x denotes a supplementary key utilized by the key-to-seed mapping.
19. An article of manufacture comprising a non-transitory processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by at least one processing device cause said at least one processing device:
to obtain a ciphertext; and
to decrypt the ciphertext to produce a first message;
wherein the first message results from decrypting the ciphertext using a first key;
wherein decrypting the ciphertext to produce the first message comprises mapping the first key to a first seed, applying an offset of the ciphertext to the first seed to generate a second seed, and mapping the second seed to the first message; and
wherein the ciphertext is configured such that decryption of the ciphertext utilizing a second key different than the first key yields a second message that is distinct from the first message but shares one or more designated characteristics with the first message in a manner that prevents an attacker from determining solely from the second message if decryption of the ciphertext has been successful or unsuccessful.
20. The article of manufacture of claim 19 wherein decrypting the ciphertext to produce the first message comprises computing m=g(ƒ x (κ)+δ) where m denotes the first message, δ denotes the offset, g denotes a seed-to-message mapping, κ denotes the first key, ƒ x (κ) denotes a key-to-seed mapping and x denotes a supplementary key utilized by the key-to-seed mapping.