Format preserving encryption methods for data strings with constraints

• US 8,938,067 B2
• Filed: 10/30/2009
• Issued: 01/20/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.
• Primary Examiner(s): Kim, Tae
• Assistant Examiner(s): Shepperd, Eric W
• Application Number:
  US12/610,221
• Publication Number:
  US 20110103579A1
• Time in Patent Office: 1,908 Days
• Field of Search: 380/28, 380/42, 713150-151, 713/187, 707/687, 707/697, 707/698
• US Class Current: 380/28
• 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 using computing equipment, comprising:

with the computing equipment, obtaining a plaintext version of a string of characters that have a given format, wherein the plaintext version of the string includes a first checksum value computed using a given checksum algorithm;

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, wherein the encrypted version of the string includes a second checksum value;

with the computing equipment, applying the given checksum algorithm to the encrypted version of the string, not including the second checksum value, to produce a third checksum value;

with the computing equipment, determining that the second checksum value is a valid checksum value for the encrypted version of the string by determining that the second checksum value matches the third checksum value;

when the second checksum value is a valid checksum value for the encrypted version of the string, 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 second checksum value is not a valid checksum value for the encrypted version of the string, 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 second checksum value is a valid checksum value for the encrypted version of the string and the encrypted version of the string serves as ciphertext corresponding to the plaintext version of the string.

2. The method defined in claim 1 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.

3. 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, wherein the plaintext version of the string includes a first checksum value computed using a given checksum algorithm;

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, wherein the encrypted version of the string includes a second checksum value;

with the computing equipment, applying the given checksum algorithm to the encrypted version of the string, not including the second checksum value, to produce a third checksum value;

with the computing equipment, determining that the second checksum value is a valid checksum value for the encrypted version of the string by determining that the second checksum value matches the third checksum value;

when the second checksum value is an invalid checksum value for the encrypted version of the string, 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 second checksum value is a valid checksum value for the encrypted version of the string, 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 second checksum value is an invalid checksum value for the encrypted version of the string and the encrypted version of the string serves as ciphertext corresponding to the plaintext version of the string.

4. The method defined in claim 3 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.