# Format Preserving Encryption for 32 or 64 bit plaintext values

I am looking for a Format Preserving Encryption implementation to apply to either a 32-bit or a 64-bit integer. It looks like AES/FFX mode is just what I need in terms of established security properties. However, it looks like it is patented, and it seems like there might be something equally solid in the public domain for the special case of 32 or 64 bit data, ideally with C source code. I have seen SkipJack or 3DES for the 64-bit case, but I would prefer longer key sizes, as these will be statically configured.

The application is to compartmentalize/anonymize information in a database. I have different kinds of information about users that is not terribly privacy invasive as long as it is kept separate from other kinds of information that is also not invasive on it's own. However, there may be rare cases when I need to connect this data together. So, I was thinking each database would identify users with its own ID, and the key to connect them could be stored separately. The actual application is a little more complicated, but that's the general idea.

• Internally AES operates on 32-bit values when performing mixcolumns, one can modify the algorithm easily to use a 32-bit or 64-bit block size. At 32-bits, rotations may need to be added to break apart the byte oriented structure. I believe this will also allow the use of AESNI instructions, I am curious so I will test this later tonight. – Richie Frame Oct 23 '14 at 3:10
• That sounds interesting if it would retain all of the good properties of AES. I guess these small block sizes are not supported in the standard because they could be misused for more typical block chaining encryption problems? That seems not an issue here. – Tim Oct 23 '14 at 3:51
• Since the competition called for a 128-bit block, they didnt even bother. But AES was based on 64-bit ciphers KHAZAD and SHARK, so it can be reduced to 32-bits the same way it was extended to 128 – Richie Frame Oct 23 '14 at 6:08
• Please, for the love of god do not make custom modifications to AES when there are other solutions that could work perfectly fine. – pg1989 Oct 23 '14 at 7:11
• Also, to the OP: There are plenty of other schemes which achieve FPE that are not patented. Look (for example) at the BPS mode of operation, the spec of which is on the NIST modes development page. – pg1989 Oct 23 '14 at 7:16

I'm not aware of any implementations, but I'm also not aware of any patents on this algorithm.
Furthermore, that algorithm can quite directly be made tweakable,
as that paper describes on pages 10-13.

• am curious which PRF should be used ? What would be the impact on security and performance. doing the above. – sashank Oct 23 '14 at 7:39
• I would recommend using HMAC, since it is presumably a secure PRF. $\:$ I have no idea what the impact on performance would be. $\;\;\;\;$ – user991 Oct 23 '14 at 7:44
• The NIST standard uses AES CBC-MAC. – user124384 Apr 18 '17 at 19:22

DISCLAIMER: any implementation of the following should be reviewed and analyzed before being used in a non-test environment. I have tested an implementation that operates as expected for 32 and 64-bit inputs, but proper round counts have not been determined.

Most modern block ciphers already use building blocks that operate on 32-bit integers as they are designed to be implemented on general purpose hardware. These include Blowfish and AES. Blowfish uses a 32-bit operation in the F function, and AES uses 4 parallel 32-bit MDS matrix multiplications. These building blocks are well studied and provide good diffusion, they are combined with other operations to extend the effective block size past 32-bits.

Since your inputs are multiples of 32-bits, you can build a block cipher from these components in a way that does not require a specialized format preserving mode or algorithm. You essentially need a 32-bit and 64-bit block cipher. The components of AES or Blowfish can provide this.

Since AES instructions are available on both ARM and x86 processors and provide a secure, high speed, timing attack resistant implementation, building a cipher from AES components can be done in a way that can exploit these instructions. AES extends from 32-bits to 128 through the ShiftRows operation, which mixes the bytes of the 32-bit matrix multiplications so that 2 rounds provide full block diffusion.

We can describe a 32-bit cipher in terms of combined AES operations and other operations required to isolate the matrix multiplication from a full round, so an implementation utilizing AESNI instructions can use a similar description. A 64-bit variant requires little modification.

The AESENC instruction performs the ShiftRows and SubBytes operation, followed by MixColumns and AddKeys, as would a single AES round. If we "unshift" the input words prior to the instruction, we cancel out ShiftRows, generating a 4-way parallel operation we can use to build a 32-bit or 64-bit cipher, as below. For 32-bit inputs, proper key scheduling can allow 4-blocks to be encrypted in parallel, allowing fast CTR mode, or processing 4 independent inputs. A 64-bit version can provide 2-wide processing, and would also require an inter-word shift to diffuse the entire block, called prior to the "unshift":

Input to AES instruction is 4-word array, word(0 to 3)
variable n defines current round
key(n) defines a group of 4 32-bit identical subkeys for round n, or all 0 for n=empty

word(0) = 32-bit plaintext

iShift word(0-3)
AESENC word(0-3), key(1)
iShift word(0-3)
AESENC word(0-3), key(2)
...
iShift word(0-3)
AESENC word(0-3), key(n-1)
iShift word(0-3)
AESENCLAST word(0-3), key(empty)

32-bit ciphertext = word(0)


The 64-bit version would be mostly the same, except the size of the subkeys and plaintext spans 2-words, and the addition of a mixing operation prior to each iShift (inverse shiftrows) operation. This can be done by swapping bytes between each word. [ 0x00112233, 0xaabbccdd ] becomes [ 0xaa11cc33, 0x00bb22dd ], for example, which can be done in in a single SSE3 instruction without a branch.

For decryption the equivalent inverse is used, with InverseMixColumns (AESIMC instruction) used to generate decryption subkeys 1 through n-1. The keys are then placed in reverse order. ShiftRows is called in place of its inverse at the same step.

For either version the AES key schedule can be used, but the generated subkeys would need to be split into the size of the plaintext. Since less subkey material is mixed per round, the round count should be appropriate to diffuse the key material and resist attacks. The round count needs to be at least as many as AES for a given key size. I would suggest a minimum of 19 rounds for the 32-bit version, and 15 for the 64-bit version.

Nothing about this should be patented, or even patentable, as the basic building blocks are a cornerstone of modern cipher design, and this is simply a derivative of a public domain standard. As such it can be implemented on a variety of platforms from 8 to 64-bit, with a small codebase, and use specialized instructions for secure implementation.

With a proper round count, it should be as secure as the key size would provide, within the obvious limits placed on security by the block size. A different key schedule may provide better nonlinearity to the round subkeys, which may allow a similar security level with a lower round count, or a higher security level with the determined round count.

• This looks great if I had the time to educate myself and convince myself it was valid. My security requirements are of my own invention anyway, so I could use something experimental, as long as not foolish. The reason I asked for FPE rather than small "block cipher" is I think "block" suggests some longer plaintext is being chopped up, which raises question of why small blocks. – Tim Oct 25 '14 at 14:40

We have designed FNR encryption scheme for this very purpose of preserving lengths and formats of small input fields ( $32 <= x < 128$ bits). It uses Naor and Reingold's PWIP extensions to classic fiestel networks. They have proved it to be more secure than classic Feistels. We have made it practical by using invertible matrices rather than working in $GF(2^n)$ which is difficult for arbitrary lengths. Our key size is 128 assuming we internally use AES-128 , supporting 256 key sizes is trivial by changing internal code to AES-256 if needed.

This is released under LGPL-v2 and not patented. Currently supports preserving formats of IP Addresses other formats could easily be supported.

Feel free to refer below

Motivation and applications could be found here

Source code here and java bindings here

The spec is here

The slides are here

• Thanks, that looks good. Any comment on how it compares to "FastPRP" by Stefanov and Shi? eprint.iacr.org/2012/254.pdf – Tim Oct 23 '14 at 3:41
• Ah, though I see this is still experimental (which would surely also be the case if I wrote the implementation for any of these other methods!). I am not really constrained by legacy requirements, so still trying to think if I can solve my problem with more standard building blocks. – Tim Oct 23 '14 at 4:00
• @Tim, To best of our knowledge there aren't any standards apart from NIST's FFX modes which are patented. Yes we did analyze FastPRP, these techniques work on very tiny spaces less than 16 bits , they tend to be expensive for 32 bits and above although we dont have bench marked results – sashank Oct 23 '14 at 7:26
• Feistel networks with AES as PRF is the popular and well studied approach for Format Preserving – sashank Oct 23 '14 at 8:07
• I also saw mention of VPFE by Visa being patented. Come to think of it, a license fee would be fine, if it is was one time purchase. But, don't want to end up with database held hostage. – Tim Oct 23 '14 at 14:28