Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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 2 days ago
    
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 2 days ago
    
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 2 days ago
    
Please, for the love of god do not make custom modifications to AES when there are other solutions that could work perfectly fine. –  pg1989 2 days ago
    
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 2 days ago

3 Answers 3

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.

share|improve this answer
    
am curious which PRF should be used ? What would be the impact on security and performance. doing the above. –  sashank 2 days ago
    
I would recommend using HMAC, since it is presumably a secure PRF. $\:$ I have no idea what the impact on performance would be. $\;\;\;\;$ –  Ricky Demer 2 days ago

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
AddKeys word(0-3), key(0)

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)

AddKeys word(0-3), key(n)
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.

share|improve this answer

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

share|improve this answer
    
Thanks, that looks good. Any comment on how it compares to "FastPRP" by Stefanov and Shi? eprint.iacr.org/2012/254.pdf –  Tim 2 days ago
    
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 2 days ago
    
@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 2 days ago
    
Feistel networks with AES as PRF is the popular and well studied approach for Format Preserving –  sashank 2 days ago
    
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 yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.