FORMAT PRESERVING ENCRYPTION SYSTEMS FOR DATA STRINGS WITH CONSTRAINTS

• US 20150134972A1
• Filed: 01/16/2015
• Published: 05/14/2015
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: entIT Software LLC (Open Text Corporation)
• Original Assignee: Voltage Security Incorporated (HP Inc.)
• Inventors: Martin, Luther W., Spies, Terence, Pauker, Matthew J.
• Granted Patent: US 9,489,521 B2
• Time in Patent Office: Days
• US Class Current: 713/189
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H03M 13/096 Checksums
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

Format preserving encryption (FPE) cryptographic engines are provided for performing encryption and decryption on strings. A plaintext string may be converted to ciphertext by repeated application of a format preserving encryption cryptographic algorithm. Following each application of the format preserving cryptographic algorithm, the resulting version of the string may be analyzed to determine whether desired string constraints have been satisfied. If the string constraints have not been satisfied, further applications of the format preserving cryptographic algorithm may be performed. If the string constraints have been satisfied, the current version of the string may be used as an output for the cryptographic engine.

Claims

1. A method for performing cryptographic operations at computing equipment, comprising:

with the computing equipment, obtaining a plaintext version of a string of characters that have a given format;

computing a checksum value for the plaintext version of the string; and

with the computing equipment, repeatedly applying a format preserving encryption algorithm to the string until an encrypted version of the string is produced that complies with the given format and has a checksum value that matches the checksum value that was computed for the plaintext version of the string.

2. The method defined in claim 1 further comprising:

with the computing equipment, modifying the checksum value that matches the checksum value for the plaintext version of the string so that the modified version of the checksum value does not match the checksum value for the plaintext version of the string.

3. The method defined in claim 2 further comprising storing the modified version of the checksum value in a data item that contains the encrypted version of the string.

4. The method defined in claim 2 wherein modifying the checksum value comprises applying a mapping to the checksum value of the plaintext version of the string.

5. The method defined in claim 2 wherein modifying the checksum value comprises applying an offset to the checksum value of the plaintext version of the string.

6. The method defined in claim 2 wherein modifying the checksum value comprises adding a number to the checksum value of the plaintext version of the string.

7. The method defined in claim 6 wherein adding the number to the checksum value of the plaintext version of the string comprises adding a digit in the range of 1 to 9 to the checksum value mod 10.

8. A method for decrypting a string of ciphertext that complies with a given format by containing characters that have values selected from at least one set of valid character values, the method comprising:

applying a format preserving encryption (FPE) cryptographic algorithm to the string multiple times with computing equipment to produce plaintext corresponding to the ciphertext, wherein each time the FPE cryptographic algorithm is applied to the string, the string is altered while continuing to comply with the given format; and

after each application of the FPE cryptographic algorithm, using a decryption engine implemented on the computing equipment to determine whether the string satisfies string constraints.

9. The method defined in claim 8 wherein the string constraints comprise internal string constraints that specify interrelationships that must be satisfied between characters in the string and wherein using the decryption engine comprises using the decryption engine to determine whether the interrelationships have been satisfied.

10. The method defined in claim 9 further comprising:

halting application of the FPE cryptographic algorithm when it is determined that the interrelationships have been satisfied.

11. The method defined in claim 10 wherein each application of the FPE cryptographic algorithm to the string involves multiple applications of a block cipher to an encoded binary value.

12. A method for performing cryptographic operations using computing equipment, comprising:

with the computing equipment, obtaining a plaintext version of a string of characters that have a given format;

with the computing equipment, applying a format preserving encryption algorithm to the string to produce an encrypted version of the string that complies with the given format;

with the computing equipment, determining whether the encrypted version of the string to which the format preserving encryption algorithm has been applied satisfies given string constraints; and

when the encrypted version of the string is determined to satisfy the given string constraints, halting further application of the format preserving encryption algorithm with the computing equipment and using the encrypted string as ciphertext corresponding to the plaintext version of the string; and

when the encrypted version of the string is determined to not satisfy the given string constraints, applying the format preserving encryption algorithm to the encrypted version of the string with the computing equipment at least one additional time to alter the encrypted version of the string until the encrypted version of the string satisfies the given string constraints and serves as ciphertext corresponding to the plaintext version of the string.

13. The method defined in claim 12 wherein applying the format preserving encryption operation to the string to produce the encrypted version of the string involves multiple applications of a block cipher to an encoded binary value that represents the plaintext version of the string.

14. The method defined in claim 12 further comprising:

with the computing equipment, applying a format preserving encryption (FPE) decryption algorithm to the ciphertext until the ciphertext satisfies the given string constraints.

15. The method defined in claim 12 wherein the given string constraints comprise internal string constraints that specify a required interrelationship between characters in the string.

16. The method defined in claim 12 wherein the given string constraints comprise external string constraints that specify a required relationship between characters in the string and data external to the string.

17. The method defined in claim 16 wherein the data external to the string comprises a checksum value.

18. The method defined in claim 12 wherein the given string constraints comprise a valid checksum constraint requiring that the ciphertext have a checksum that matches a checksum value for the plaintext version of the string.

19. The method defined in claim 12 wherein the string constraints comprise an invalid checksum constraint requiring that the ciphertext have a checksum that does not match a checksum value for the plaintext version of the string.