2
$\begingroup$

I have this exercise that I found on the Internet. It is originally in French but it says:

Exercise 3: (Feistel scheme). We consider a two-round Feistel cipher defined as follows:

  • The length of the blocks is 8.

  • The key $K = [k_1, ..., k_8]$ is of length 8. The two round keys are $K_1 = [k_1, ..., k_4]$ and $K_2 = [k_5, ..., k_8]$, where the $k_i$ are the bits of the key $K$.

  • The function $V = f (U, U ')$ is defined by writing the bits $v_i$ of $V = [v_1, ..., v_4]$ as functions of $U = [u_1, u_2, u_3, u_4]$ and $U '= [u'_1, u'_2, u'_3, u'_4]$ as follows:

$$\begin{aligned} v_1 &= u_1 u'_4 ⊕ u_2 u'_3 ⊕ u_4 u'_3, \\ v_2 &= u_1 u'_2 ⊕ u_3 u'_1, \\ v_3 &= u_1 u'_4 ⊕ u_1 u'_3, \\ v_4 &= u_3 u'_3 ⊕ u_1 u'_1. \end{aligned}$$

  1. Let the key be $$K = [1,0,1,1,0,0,1,0],$$ and let the message be $$M = [0,1,0,0,0,1,1,1].$$ Calculate the encryption of $M$ using the Feistel scheme above.
  2. Decrypt the message $C = [0,1,1,1,0,0,1,1]$ which was encrypted with the same key.

So my question is: I understood that $U$ is actually the right half of the plaintext and that $U'$ is actually $K_1$ in the first round and $K_2$ in the second. And I solved the exercise based on this understanding. But my teacher said that my understanding is wrong and that $U$ has to be the left half of the plaintext, while $U'$ is the right half of the plaintext. She means that the Feistel cipher is changed in this case. She added that her understanding is more logical and that mine could not even be considered as a possible one in this context. I think that if her understanding is logical and correct, mine is more so.

What do you think? I know this might seem like a trivial question but I really want to read other people's opinions and be convinced by the more logical understanding and explanation.

$\endgroup$
1
$\begingroup$

It seems to me that the exercise is missing some context (which is presumably to be found in the textbook it's taken from). Specifically, it defines a function $$f: \{0,1\}^4 \times \{0,1\}^4 \to \{0,1\}^4,$$ but does not explicitly state what role this function is supposed to play in the Feistel encryption process.

That said, the usual way to define a Feistel encryption round (as given e.g. on Wikipedia) is $$\begin{aligned} L_{i+1} &= R_i, \\ R_{i+1} &= L_i \oplus F(R_i, K_i), \end{aligned}$$ where $L_i$ and $R_i$ are the left and right halves of the input block to encryption round $i$, $K_i$ is the $i$-th round subkey, and $F$ is some nonlinear function.

Presumably, the function $f$ defined in the exercise corresponds to the nonlinear round function that I've denoted by $F$ above. Thus, presumably, one of its arguments is supposed to be the round subkey, while the other one is one of the input half-blocks, just like you say. However, what's not obvious from the given definition is which argument is supposed to be the subkey, or whether the other argument is supposed to be the left or the right half-block (since either convention can be used, and they're essentially equivalent).

Anyway, if the exercise comes with an answer sheet, it should be easy enough to verify this just by doing the encryption is each of the possible ways and comparing the results with the expected answer. Even with the small block size, getting the right answer just by change from the wrong encryption process should be pretty unlikely.

$\endgroup$
  • $\begingroup$ So does this mean that the key was added to the exercise as a trap? and it shouldn't be used in ciphering/decrypting ? and the Feistel scheme should be modified so that no key is used, and both parts of the plain text go into the function, correct? the problem is that i couldn't find the textbook of the exercise, and i don't have an answer sheet. that is why i am asking here. Thank you. $\endgroup$ – M.Noussa Feb 26 '18 at 21:43
  • $\begingroup$ No, that is not what I'm saying at all. I'm saying that your guess is probably right (although, just based on the exercise, there's no way to tell which of $U$ and $U'$ is meant to be the round key), and your teacher's interpretation (as you've reported it above) is almost certainly wrong (since, as you correctly note, it would imply that the key doesn't affect the encryption process at all, which would be silly). Of course, it's also possible that your teacher actually meant to say something other than how you understood their words. $\endgroup$ – Ilmari Karonen Feb 26 '18 at 21:50
  • $\begingroup$ I got it,thank you very much. Also decrypt would be impossible if we consider U and U' as both from the plain text. yeah, maybe i misunderstood what my teacher said. $\endgroup$ – M.Noussa Feb 26 '18 at 21:59
0
$\begingroup$

This is a convention question, but in the absence of a specific convention, since we read English and formulae left to right, and the question is in English, most people would agree with the teacher.

It's best practice to specify the conventions fully, of course.

$\endgroup$
  • $\begingroup$ You yourself focused on left vs right in your question! see Karonen's answer about what you didn't explicitly ask. $\endgroup$ – kodlu Feb 26 '18 at 21:28

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.