Encrypting credit card numbers using Feistel Finite Set Encryption Mode (FFSEM)

Suppose we want to store a credit card number in encrypted form in a database, but we are only allowed to store it in the same format as another credit card number.

Perhaps our database only allows us to store the values in the same "credit card" format, or we have to transmit the encrypted number over a network that only allows values in the same format.

A typical credit card number is 16 decimal digits and so can be represented as an integer between 0 and 9,999,999,999,999,999. This page shows how we can encrypt a given credit card number and end up with an encrypted value in the same range.

Using a standard block cipher

If we just encrypt the 16 bytes directly using a standard block cipher like AES, the ciphertext will be a binary value requiring at least 16 bytes (128 bits) to store it. Except for an infinitesimally small number of cases (a probability in the order of $2^{-74}$) these 128-bit binary values will not look anything like a credit card number.

However, there is a technique that will generate a ciphertext in the same form. This is known as Format Preserving Encryption (FPE) [BONEH-FPE]. We show an example using Feistel Finite Set Encryption Mode (FFSEM) described in [FFSEM].

Format Preserving Encryption

A 16-digit credit card number can have a value between 0 and $N=9\,999\,999\,999\,999\,999$. In the discussion following, when we say $N$ we mean the number $9\,999\,999\,999\,999\,999$. We can store any integer $0\leq i\leq N$ in a bitstring of length $q=54$ bits.

A little theory: for a given maximum integer $n$ the number of bits required is $q=\lfloor\log_2 n\rfloor + 1$. In our case, $\log_2 N = \log N / \log 2 \approx 53.15$.

We will use two techniques here, described below.

1. Cycle following
2. Feistel network

Cycle following

Given an input value $i$ in the range $0 \leq i \leq N$ we use a cipher $E(k,\cdot)$ with a block length of 54 bits to derive a ciphertext $c=E(k,i)$. If $c$ is too big, then we encrypt it again, $c'=E(k,c)$, and repeat until we have a value in the required range $0\leq c\leq N$.

INPUT: i, k, N
c = i
do 
  c = E(k,c)
while c > N
return c

If we use a block cipher with block length 54 bits, we should obtain a valid result within a few cycles. This technique is called cycle following.

The diagram below illustrates cycle following. The outer blue box is the set of all numbers of 54 bits. The inner orange circle is the set of all valid credit card numbers: in our case, all numbers between $0$ and $N$. In this example, the input $i$ when encrypted results in the number $c_1$ which is greater than $N$ and so we repeat. The result $c_2=E(k,C_1)$ is still greater than $N$, so we repeat again. Finally, $c_3 \leq N$ is valid and so we output this as the encrypted value.

This process is reversible. So, to decrypt with input $(c_3, k)$, we just reverse the procedure, decrypting at each step with $D(k,\cdot)$: \[ c_2 = D(k, c_3) > N \Rightarrow \mathtt{repeat} \\ c_1 = D(k, c_2) > N \Rightarrow \mathtt{repeat} \\ i = D(k, c_1) \leq N \Rightarrow \mathtt{stop} \]

But do we have a block cipher with such an obscure block length? Yes, we do.

Feistel network

We can use a standard block cipher like AES to encrypt an arbitrary-length bitstring using a Feistel network. This is named after the cryptographer Horst Feistel who worked at IBM on the original DES cipher.

The input of length $q=54$ bits is split into two halves each of $q/2=27$ bits, the left half $L_0$ and the right half $R_0$. Each round of the Fiestel network does the following with input $(L,R)$ and output $(L',R')$. \[ L' = R \\ R' = L \oplus F(k_j, R) \] where $\oplus$ is the bitwise XOR operation. After a suitable number of rounds ($r\geq 3$), we join up the final left and right halves $L_r$ and $R_r$ to obtain the $q$-bit output.

In our case here, $r=6$ should be sufficient.

The function $F$ needs to be a Pseudo-Random Function (PRF) with a different key $k_j$ on each round. In practice we can use a standard block cipher like AES-128 with a single 128-bit key $k$ and a different tweak for each round, using the round count $j=1,2,\ldots,r$ as the tweak.

To form the 128-bit input block for AES, we pad out the 27-bit input $R$ with zeros to 120 bits and append the 8-bit representation of the round count $j$. We then encrypt this with AES-128 using the key $k$, and truncate the output to 27 bits.

1. B = R || 0..0 || bitstring₈(j)
2. E = AES(k, B)
3. $F(k_j, R)$ = leftmost 27 bits of E.

The encryption algorithm E(k,⋅)

Pulling together the parts above we can describe the cipher $E(k,\cdot)$ used in the cycle following algorithm above.

Example

INPUT: i=7777 7777 7777 7777
KEY=000102030405060708090A0B0C0D0E0F

The decimal number i=7777777777777777 can be represented by the 64-bit QWORD in hex 0x1BA1D901961C71, or in binary

0000000000011011101000011101100100000001100101100001110001110001

We encode this as a 54-bit bitstring by left-shifting as follows:

bit_encode[54]=6E8764065871C4  011011101000011101100100000001100101100001110001110001

Notation: We represent a $\ell$-bit bitstring as the leftmost $\ell$ bits of a big-endian byte array of length at least $\lceil\ell/8\rceil$ bytes with all other bits to the right being set to zero. For example, the 10-bit bitstring "0101101010" is represented as 0x5A80 (or 0x5A8000 or 0x5A800000, etc).

The first round of the Fiestel network gives:

Round 1:
input=  6E8764065871C4
L=6E876400	011011101000011101100100000
R=32C38E20	001100101100001110001110001
B=      32C38E20000000000000000000000001
E(k,B)= D3C677C4DE006B4AFD72E8D0D912DB63
F=      D3C677C0
L=      6E876400
L XOR F=BD4113C0
L'=32C38E20	001100101100001110001110001
R'=BD4113C0	101111010100000100010011110
001100101100001110001110001101111010100000100010011110
output= 32C38E37A82278

Note that E(k,B) is the result of using AES-128 to encrypt the 128-bit input block B=32C38E20000000000000000000000001 with the 128-bit key k=000102030405060708090A0B0C0D0E0F: see CryptoSys API Testbed Example.

The second round gives:

Round 2:
input=  32C38E37A82278
L=32C38E20	001100101100001110001110001
R=BD4113C0	101111010100000100010011110
B=      BD4113C0000000000000000000000002
E(k,B)= FC2E12E84F0608A791910998CCFE37D6
F=      FC2E12E0
L=      32C38E20
L XOR F=CEED9CC0
L'=BD4113C0	101111010100000100010011110
R'=CEED9CC0	110011101110110110011100110
101111010100000100010011110110011101110110110011100110
output= BD4113D9DDB398

After 6 rounds (see full details) we have

L'=D1E42E80	110100011110010000101110100
R'=4C82D860	010011001000001011011000011
110100011110010000101110100010011001000001011011000011
output= D1E42E89905B0C

Decoding this back to a 64-bit QWORD by right-shifting, we obtain

c=0x0034790ba26416c3
0000000000110100011110010000101110100010011001000001011011000011

In decimal, this value is c=14769789665023683 > 9999999999999999, so we repeat the cycle and compute $c' = E(k, c)$.

After another 6 rounds (details) we obtain

L'=81F9D5C0	100000011111100111010101110
R'=43EF01E0	010000111110111100000001111
100000011111100111010101110010000111110111100000001111
output= 81F9D5C87DE03C

Decoding this back to a 64-bit QWORD by right-shifting, we obtain

c=0x00207e75721f780f
0000000000110100011110010000101110100010011001000001011011000011

Thus the final encrypted value is 9146 2421 4567 9375. This can be stored in a database as a "valid" credit card number (yes, we know there are check digits and certain expected prefixes for a given card-issuing company, but you get the idea.)

Decrypting

To decrypt a given value $c$ with key $k$, note that the output $(L',R')$ for the reverse Feistel round with input $(L,R)$ is given by $R'=L, \; L'= R \oplus F(k_j,L)$ for $j=r,r-1,\ldots,1$.

The full decryption details of our example above are listed here. This shows that the ciphertext c=9146242145679375 with key k=0x000102030405060708090A0B0C0D0E0F decrypts uniquely to c=7777777777777777.

Source code

Download a simple C program feistel_bits.zip (9 kB) to demonstrate this (use at your own risk). The source code files are:

• feistel_bits.c
• bitarray.c
• bitarray.h

The bitstring manipulation functions in bitarray.c are basic and perhaps inelegant, but should do the job they are required to do.

This uses our CryptoSys API library to do the AES-128 encryption. You can always substitute your own favourite AES library: just replace the internals of encrypt_128().

A sample MSVC project file is in feistel_bits_msvc9.zip. You need to install CryptoSys API on your system which you can download from the latest Trial Edition of CryptoSys API.

Security considerations

The security of a Feistel network depends on the number of rounds. At least 3 rounds are required. The more rounds the better, at the cost of more computations. For our example here with a block size of 54 bits, six rounds should be more than sufficient. The shorter the block, the more rounds you need.

Matthew Green describes this method of Format Preserving Encryption very well at his blog [GREEN11] along with some security issues.

References

• [BONEH-FPE] Boneh, Dan. "Format preserving encryption (FPE)." Coursera Stanford Cryptography I Online Cryptography Course. 08-odds-and-ends-v2-annotated.pdf (accessed January 2013)
• [FFSEM] Spies, Terence. "Feistel finite set encryption mode." NIST Proposed Encryption Mode. Available online at ffsem-spec.pdf (2008).
• [GREEN11] Green, Matthew. "Format Preserving Encryption, or, how to encrypt a credit card number with AES", A Few Thoughts on Cryptographic Engineering (accessed February 2013)

Contact us

To comment on this page or to tell us about a mistake, please send us a message.

This page first published 15 February 2013. Last updated 30 June 2020.