Inconsistency in FF1 implementation
Format-Preserving Encryption Library for Java
Brought to you by:
weydstone
Menu
▾
▴
1 Attachments
#4 Inconsistency in FF1 implementation
I have working under the assumption that the FF1 class is equivalent to the FFX class with FF1Parameters; my initial testing confirmed that to be the case (i.e. I was getting the same results from each). However, I have come across a case where the latter fails with the exception below.
The attached source code demonstrates the problem. All the inputs are the same but the FF1 test works and the FFX with FF1Parameters test fails.
Is there something I'm missing? Thanks.
java.lang.IllegalArgumentException: FFX requires a minimum of 12 rounds for method one with imbalanced splits.
at org.fpe4j.FFX.encrypt(FFX.java:684)
at fpe4jtest.FF1Failure.testFFX(FF1Failure.java:34)
Thanks for posting the issue and the source code. I'll take a look at it as soon as I get a chance, but it might be a couple of weeks.
The issue here is a subtle. FF1 is defined to use exactly ten rounds (i.e. iterations of the Feistel structure). FFX relies on the parameters to specify the number of rounds, and the FF1Parameters are hard coded to use ten rounds to match the FF1 specification.
However, FFX also specifies lower bounds on the number of rounds to avoid known attacks. The lower bounds are specified at the bottom of p. 4 in The FFX Mode of Operation for Format-Preserving Encryption with some further discussion in Appendix H. I don't pretend to understand the details of the attacks in Appendix H, but the FFX code should be faithful to the spec as it's written.
It looks like the inputs you're providing to FF1 actually push it out of the specified lower bound for Feistel rounds in FFX. However, the FF1 specification in NIST SP 800-38G implies that ten rounds are sufficient to maintain the security of FF1 for all the permitted inputs.
It would be interesting to see what NIST has to say about using FF1 with parameters that would imply that an FFX implementation should use more than 10 rounds. If you ask them about it, let me know what they say.
As far as the code goes, though, the point has been to implement the algorithms as specified. The code only needs to be corrected if it doesn't match the spec.
Thanks for looking into it. The code that triggered the failure in the first place uses an algorithm that optimizes for the maximum value of the radix and the minimum value of length for the encyrption/decryption process. I modified the code to require a minimum length of 4 (rather than the minimum length of 2 in the spec) and the test case now works. However, other errors have cropped up so I'm going to have to take a deeper look over the next few days.
The other errors are all edge cases with a small radix; I'm getting "radix^minlen must be greater than or equal to 100", which was fine with a smaller minimum text size. I'll stick to the pure FF1 implementation rather than the FFX with FF1Parameters. Thanks for your help, and you may close this.
If you're performing operations that are within the range of the FF1 implementation, then I agree that you should use it rather than the FF1Parameters implementation for FFX. The FF1Parameters implementation demonstrates that it is possible to implement FF1 on FFX, but it's certainly not as well vetted as the NIST-approved FF1 algorithm.
I'll close the ticket as you suggest.
I'm curious what you're using FF1 for, though. FPE generally makes sense when you're forced into using a specific radix and length by external constraints (e.g. legacy systems), but if you're able to dynamically choose your radix and length, maybe a conventional block cipher would be appropriate? Would you be willing to share some of what you're using the FPE algorithms for?
It's a hybrid of a static (legacy) and dynamic system. I can't discuss the project in detail right now, but it's akin to having multiple data fields that need to be encrypted in place. The data fields all have different formats and all are candidates for FPE; rather than create an FPE implementation for each, I've created a library that you can feed a grep-like format for each field into and it comes up with the maximum radix (R) and minimum text length (L) to do the FPE work. Original text is converted to a number in base R across L words, encrypted using FF1, and then converted back to text in the same format as the original.