Does Format Preserving Encryption have significant advantages over a randomly generated lookup table?

Question

I have a need to anonymise phone numbers so that I can carry out testing and analysis work on telecoms data sets and comply with GDPR. I typically receive a batch of a few hundred thousand events containing phone numbers, and need to anonymise all the phone numbers in that batch under the following conditions:

1. A definable prefix of the number should remain the same - I should only transform the right-most n digits. n will typically be between 2 and 6

2. I should always transform the digits in the same way - abcd should always be mapped to efgh

3. The transformation should be one-to-one - efgh should be that output for only one input

4. I should only output digits

If I then receive a further batch of events condition 2 is removed - I can use a new transformation for a new batch.

I've considered two approaches to this requirement:

1. Randomly create a lookup table mapping each n digit string to another n digit string - I will do this for all n digit strings as a one-time exercise prior to encrypting a batch, and generate a new lookup table for a new batch

2. Use one of the Format Preserving Encryption algorithms - e.g. Format-preserving, Feistel-based encryption (FFX) as implemented in the PyFFX or libffx libraries, or FE1 in the botan library

In some cases I may need to reconstruct the original phone numbers in the future in which case I will store the encryption key or lookup table in some secure fashion. In some cases I know I will not need to reconstruct them in which case I will discard the key directly after encryption.

Is there any advantage to using approach 2 over approach 1? I can see the following possibilities:

1. Using a random number generator in 1 may be slightly less robust than using FPE

2. The encryption key for FPE can be substantially smaller than the mapping table in point 1 if there is a need to retain it

3. A publicly available FPE implementation may contain fewer vulnerabilities than a home-grown random lookup implementation

Are there any other considerations I should have in mind?

Answer 1

any other considerations?

Yes.

• In many common use cases the mapping table needs to be retained. That map changes each time a number is added; that's a backup / continuity of service headache.
• The map is security-sensitive: it contains all the clear phone numbers, and information which (combined with other information) allows getting back to users.
• The map can be large (at least about twice as large as the numbers themselves); that's a (perhaps minor) storage issue.
• When the table grows large, there will be collisions in the mapping table, that's a special case which must be handled, and tested.
• Timing attack on the map search code has the potential to leak information (that's also true of some FPE implementations, but proper FPE is less likely to leak something meaningful; in particular FPE won't leak if the creation of the entry was recent, which can happen with a map).
• FPE's performance is predictable, when some map implementation have no specified worst-case performance.
• FPE allows efficient implementation of direct and reverse map, when not all map implementations allow that.

Bottom line: encryption is desirable there. FPE is useful only if size or interoperability is a concern.