Monday, April 25, 2016

Format Preserving Encryption in Encrypting Credit Cards

Every time we swipe out credit cards in a point of sale device, our credit card number is read. And, no doubt we need to encrypt it for maintaining security. Format Preserving Encryption or FPE is an encryption technology in which the format of the ciphertext output remains same as format of the plaintext input. So, that would mean if we encrypt a 16 digit credit card number using FPE, the encrypted output will be another 16 digit number.

But, why do we need that ? Let's understand it in more details.

Challenges of encrypting credit card numbers

We can use a block cipher to encrypt credit card numbers. But, there are certain challenges with that approach.

  • If we encrypt a 16 digit credit card number using a block cipher, the output will be 34 bytes long. This may break existing applications that expect the credit card number to be a 16 digit number only.
  • The 34 byte ciphertext of a 16 digit credit card number obtained using block cipher will contain hexadecimal values containing alphanumeric and special characters. The ciphertext output may not be another credit card number. And, that may break existing applications.
  • If the ciphertext is decrypted and encrypted again, it should retain its value. It should not depend on any random seed value to initialize the encryption as it is done in a block cipher.

FPE is an encryption using which credit card numbers can be encrypted in such a way that field length and data type of the plaintext credit card number is preserved across encryption, which would mean, the encrypted output of a 16 digit credit card number will be another 16 digit number which can integrate well with the existing applications.

So, we can say, FPE is like a random permutation which, in this case, takes a 16 digit number as input and gives another 16 digit number as output. But, for a large domain, it is infeasible to precompute a truly random permutation and remember it. FPE uses a secret key to generate pseudorandom permutation of a number in such a way that the computation time for a single value is less and computationally feasible.

How is Format Preserving Encryption done

Format Preserving Encryption uses a block cipher like AES as a primitive. So, if the block cipher algorithm is secure, FPE will be unbreakable.

There are a number of algorithms for Format Preserving Encryption. Some of them are mentioned below :

FPE using Prefix Cipher :

Let's say, there are N numbers from 0 to N-1. First, a block cipher is applied on each of these integers. As a result, we would get another set of integers called weights of those N integers. Next, we can sort the integers as per their weights.

For example,

Let's assume, N is 4.

weight(0) = 0x52786875875878765253865433328645
weight(1) = 0x23868574647366539533289686858585
weight(2) = 0x85375765765765757657312321735711
weight(3) = 0x76353535355535535544429394745455


FPE(0) = 1
FPE(1) = 0
FPE(2) = 3
FPE(3) = 2

FPE using Cycle Walking :

Let's say, S be the set of allowed values for the inputs. In this algorithm, first a block cipher will be applied to each of the inputs. If the output is not in S, block cipher will be applied again on that input, until the output ciphertext is in S.

As this pseudorandom permutation is one-to-one and the domain is finite, the iteration is guaranteed to stop.

FPE using Feistel Network

In this algorithm, the input is first split into two halves L1 and R1 and the following operations are performed on each half :

L2 = R1
R2 = L1 XOR F(ki, R1)

Here, a single key k is used with a different tweak in each round, using the round count as the tweak.

Acceptance of FPE

National Institute of Standards and Technology has recommended Format Preserving Encryption for encrypting sensitive data like credit card numbers, Social Security Numbers etc.

This was an introductory article on Format Preserving Encryption just to give some basic information. Hope it solved its purpose.

1 comment: