1
$\begingroup$

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.)?

$\endgroup$

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Ah. That is basically what my question was asking. So it is neither clear nor unclear whether or not this method actually "optimizes" and whether it becomes insecure. I am using FFX with even split in the middle. $\endgroup$
    – EL_BR_CV
    Aug 15, 2015 at 5:56
  • $\begingroup$ Okay, I tried to prove it and realized that the method is simply not an optimization and in fact slows down the algorithm. $\endgroup$
    – EL_BR_CV
    Aug 15, 2015 at 6:04
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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