1
$\begingroup$

Is there any difference between these two ways to encrypt a string using FPE?

Say the string has the format is specified by this rule First part is in the set $S = \{\text{AA,AB,AC,BA,BB,BC,CA,CB,CC}\} = \{0,1,2,3,4,5,6,7,8,9\}$, second part is in the set $T = \{0,1,2,3,4\} = \{0,1,2,3,4\}$

Example string = $\text{BA2}$

Usage 1. Break the string as parts defined above, determine the integer representing each part as defined by the bijective mapping, and encrypt those integers individually using encryption function $E$.

$\text{BA = 3}$

$2 = 2$

$E(3) \Rightarrow 6 = \text{CA}$

$E(2) \Rightarrow 4 = 4$

Concatenate the parts together to get output

Output string = $\text{CA4}$

Usage 2 Encrypt the entire string by ranking all possible values.

$S=\{\text{AA0, AA1, AA2, AA3, AA4, AB0, AB1 ,AB2 ,AB3, AB4, AC0, AC1, AC2, AC3, AC4,}$ $\text{BA0, BA1, BA2, BA3, BA4, BB0, BB1, BB2, BB3, BB4, BC0, BC1, BC2, BC3, BC4,}$ $\text{CA0, CA1, CA2, CA3, CA4, CB0, CB1, CB2, CB3, CB4, CC0, CC1, CC2, CC3, CC4}\} = \{0,1,2,3...43,44\} $

$E(17) \Rightarrow 8 $

Output string = $\text{AB3}$

Is Usage 1 equally valid as Usage 2? Are there any negative side effects to breaking the string into pieces first compared to encrypting the string as a whole?

$\endgroup$
4
  • 1
    $\begingroup$ Too lazy to write a full answer but here is my intuition : In your first case you have $10! \times 5!$ possible mapping. In the second one you have $45!$ possible mapping. You can consider your second choice as the possibility to change the T mapping for each first combination. $\endgroup$ – Biv Mar 7 '16 at 20:49
  • 2
    $\begingroup$ I've got the strong sense that if there is a mathematical relationship between the two values that you don't want usage 1. For instance, if the sets are the same size you could clearly distinguish when encrypting the same index twice. I.e. information about the plaintext of the one will give you information about the other if you use the same key. But that's just my intuition. $\endgroup$ – Maarten Bodewes Mar 7 '16 at 21:29
  • $\begingroup$ How long is the string? Only 3 bytes, or more than 3 bytes but having a pattern like "BA2AC1CB0" ? Also, what is the output scope of your E() function? In the "Usage 1" , what if the last number is "3"? E(3) => 6 = T(?) $\endgroup$ – Leo.W Mar 8 '16 at 8:46
  • $\begingroup$ @D.W.the string is only 3 bytes composed of characters only from the sets above. The output scope should be the same as the input - the function E puts you back into the same set from which the value came from $\endgroup$ – erotavlas Mar 8 '16 at 16:30
2
$\begingroup$

(1) correct a mistake here:

set S = {AA,AB,AC,BA,BB,BC,CA,CB,CC} = {0,1,2,3,4,5,6,7,8,9}

should be
set S = {AA,AB,AC,BA,BB,BC,CA,CB,CC} = {0,1,2,3,4,5,6,7,8}

(2) According to your example. I would say the "Usage 2" is better than the "Usage 1", since the "Usage 2" has more possible mappings than the "Usage 1" does.
Proof:
Usage 1:
1. E function works for both set S (size = 9) and set T (size = 5).
2. When E function's input is in the {0,1,2,3,4}, its output must also be in the {0,1,2,3,4}. Or, you cannot map "the set T = {0,1,2,3,4} = {0,1,2,3,4}" by the E function.
3. This leads to a problem: the first 5 elements in S ("AA,AB,AC,BA,BB") can only be mapped to a subset of S ("AA,AB,AC,BA,BB"). For example, you will never map "AA0" to "BCX", "CAX", "CBX" or "CCX", where X is in the {0,1,2,3,4}.

"Usage 2":
All possible mappings are here.

(3) According to your two comments:

@D.W.the string is only 3 bytes composed of characters only from the sets above. The output scope should be the same as the input - the function E puts you back into the same set from which the value came from – erotavlas 8 hours ago

In Usage 1, I could encrypt them as separate entities (pass them to an integer FPE with different max value for each) – erotavlas 8 hours ago

I would also say that the "Usage 2" is better than the "Usage 1".
Proof:
A1. the E function now maps S(9) to S(9), T(5) to T(5), S'(45) to S'(45), where S' is the S of your Usage 2 example;
A2. "Usage 1": I will feed your E function 9 inputs to get all possible mappings(S=>S, T=>T). That is, {AA0, AB1, AC2, BA3, BB4, BCx, CAx, CBx, CBx}, where x is a number in the T set.
A3. "Usage 2": I will feed your E function 45 inputs to get all possible mappings(S'=>S'). That is, the whole S' set as specified in A1.
A4. The difference is that by dividing the string into small pieces, the spaces of clear text and cipher text are changed.

$\endgroup$
2
  • $\begingroup$ In Usage 1, I could encrypt them as separate entities (pass them to an integer FPE with different max value for each) $\endgroup$ – erotavlas Mar 8 '16 at 16:27
  • $\begingroup$ I've updated the answer according to your comments. $\endgroup$ – Leo.W Mar 9 '16 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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