Validate per round rather than cycle-walking in FPE

Question

I was thinking about FPE specifically for numbers, CC, phone, SS #, etc. and I thought of some small "optimization" that could be implemented. Can I validate the string length after each round in the Feistel network, and repeating a round with the same tweak if the data is invalid, and continue until a set # of tweaks/successful rounds have been done.

For decryption, it would be much the same, since any invalid round could simply take the tweak of the preceding successful round.

Is there any downside to this approach (ie. security flaws, does not actually optimize run time, etc.)?

Answer 1

I don't think this would break correctness, but it's possible you might actually slow your algorithm down on average. You'd need a more rigorous combinatorial analysis of the expected number of repeated rounds vs. the expected number of full cycle walks. That really depends on the specific algorithm; are you using FFX?

You'd also need to show that doing this doesn't alter the distribution of ciphertexts in a way that breaks SPRP security. It's possible that it doesn't, but proving it seems nontrivial to me.

Answer 2

Alright, so using per-round validation in almost all cases causes a decrease in performance.

Simple probability tells us that after each round, there is a 1/x chance that the round will fall within the "valid" data set. This means that for any cycle through a Feistel network, the output has this 1/x chance of being correct. Likewise, any Feistel network for FFX with n round specified will tend towards x*n total rounds before completion. This is the same as full-cycle validation.

However, the validation function needs to be called after EVERY round, while the full-cycle validation only needs to validate after every full walk through the cycle. Because validation and all associated functions and called more often for per-round validation, then this method is slower.