Unbalanced numeric Feistel network implementation

Question

After reading a comprehensive paper ^[1] covering various kinds of generalized Feistel networks, I've tried to implement the Unbalanced Numeric Feistel variant, which relies on modular arithmetic for splitting and joining an integer in two smaller parts.

Given the scarcity of example implementations for this kind of cipher, I had to figure out some inexplicit details on my own in order to come up with the algorithm below. Therefore, I would like to pose some questions to clarify my remaining doubts:

• Does the implementation below follow accurately the described network generalization? If not, what operations are wrong and what would be the right way of performing them?

• Is there any way of reversing the modulus addition ⊞ on the encryption function other than by using modulus subtraction ⊟ on the decryption function? Given two integers $a$ and $b$ from a finite field of length $x$, the operation $(-a-b) \bmod x$ would be reversible in a similar way to the bitwise exclusive-or, but (obviously) the ciphertext would not be the same as the one obtained with the current operations.

• What would be the implications of dynamically computing $first$ and $second$ so the $first \cdot second$ finite field is strictly equal to the input $data$?

Algorithm

Given two finite fields of lengths $first$ and $second$ greater than $2$, a number of $rounds$ greater than $2$, a positive integer $data$ on the finite field of length $first \cdot second$ and a positive integer $key$:

Please note that the LaTeX code above was inserted as an image due to the technical limitations of the MathJax formatting. The markdown source of this question contains a commented-out block with the code used to render it.

Tests

(Python implementation that can be used to test the described algorithm).

import random


class NumericFeistel:

    def __init__(self, key: int, rounds: int, first: int, second: int):
        assert all(number >= 2 for number in (rounds, first, second))
        self.first, self.second = first, second
        self.key, self.rounds = key, rounds

    def function(self, data: int, round: int) -> int:
        globals().update(self.__dict__)
        random.seed(data + key + round)
        return random.choice(range(first))

    def encrypt(self, data: int) -> int:
        globals().update(self.__dict__)
        assert data < first * second
        for round in range(rounds):
            left, right = data // second, data % second
            left += self.function(right, round)
            data = first * (right % second) + (left % first)
        return data

    def decrypt(self, data: int) -> int:
        globals().update(self.__dict__)
        assert data < first * second
        for round in reversed(range(rounds)):
            left, right = data % first, data // first
            left -= self.function(right, round)
            data = second * (left % first) + (right % second)
        return data


for test in range(1000):
    random.seed()
    feistel = NumericFeistel(
        rounds = 2 + random.choice(range(1000)),
        first = 2 + random.choice(range(1000)),
        second = 2 + random.choice(range(1000)),
        key = 42
        )
    data = random.choice(range(feistel.first * feistel.second))
    assert feistel.decrypt(feistel.encrypt(data)) == data

Weaknesses

Using and abusing the random module for producing pseudorandom numbers and implementing the one-way round function may be a really bad idea, but this code is intended to be as readable as possible, and its hypothetical insecurity is a minor concern.

Please note that this only is a recreational exercise and nobody plans to use it for anything but demonstrative purposes. This is not another rolling out my own crypto question.

Bibliography

1. Hoang V.T., Rogaway P. (2010) On Generalized Feistel Networks. In: Rabin T. (eds) Advances in Cryptology – CRYPTO 2010. CRYPTO 2010. Lecture Notes in Computer Science, vol 6223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14623-7_33

Answer 1

Does the implementation follow accurately the described network generalization?

No. The Feistel network analyzed in the paper assumes independent round functions, but the code does not give that.

The issue is where the code reads random.seed(input + key + round). The corresponding pseudocode either has the same issue, or is at at least ambiguous with $$\text{return }\mathit{hash}(\mathit{data}+\mathit{key}+\mathit{round})$$ when perhaps it means $$\text{return }\mathit{hash}(\widehat{\mathit{data}}\mathbin\|\widehat{\mathit{key}}\mathbin\|\widehat{\mathit{round}})$$ where $\widehat x$ is a representation of integer $x$ per (say) big-endian binary, over a fixed-width bitstring chosen large enough for the maximum possible value.

If we use the same hash at each round, it is desirable that the input of $\mathit{hash}$ is unique for any triple $(\mathit{data},\mathit{key},\mathit{round})$. We can do this with just numbers, as $$\text{return }\mathit{hash}(\mathit{data}+(\mathit{key}\cdot\mathit{nbrounds}+\mathit{round})\cdot\mathit{second})$$

Problem with the current proposition is: there is very little difference in the round functions for the different rounds. For a fixed $\mathit{key}$, if we note $F$ the function $x\mapsto\mathit{hash}(\mathit{key}+x)$, then the Feistel round function $F_i$ at round $i$ is $x\mapsto F_i(x)=F(i+x)$, which is very far from independent functions.

This is a good context for slide attack when $\mathit{first}=\mathit{second}$ and these are small (that is, $2^\mathit{first}$ is enumerable). At least a related-key attack works: no mater how many rounds, we can query two black boxes that implement the cipher and tell if they have their keys offset by one or not. And because the round function's result is added, which is associative with the $i+x$ operation at the input of $F$, I think it extends to a distinguishing attack in the single random key setup; perhaps even a way to tabulate the $F$ function and recover the functional equivalent of the key in sizably less than $4^\mathit{first}$ queries.

---

Is there any way of reversing the modulus addition ⊞ on the encryption function other than by using modulus subtraction ⊟ on the decryption function?

I see nothing simpler that works.

---

What would be the security implications of dynamically computing $\mathit{first}$ and $\mathit{second}$ as the $\mathit{first}\cdot\mathit{second}$ finite field is strictly equal to the input $\mathit{data}$?

As is, with $\mathit{data}$ the input block, that's not functional. This would mean the maximum value of the ciphertext is $\mathit{data}$. Thus, by induction, either the cipher is identity (which it won't be in all likelyhood), or it is not injective thus is not decipherable.

Therefore, we can't do without at least another input, which is the $\mathit{top}$ of the range $[0,\mathit{top})$ for $\mathit{data}$. And then we have a serious problem when $\mathit{top}$ is prime.

In Format Preserving Encryption (the academic name of what the question studies), one standard solution to this is cycle walking, which essentially increases $\mathit{top}$ a little until finding $\mathit{top'}=\mathit{first}\cdot\mathit{second}$ with $\min(\mathit{first},\mathit{second})$ above some reasonableness thresold, then fixes encryption by encrypting again when the ciphertext is in range $[\mathit{top},\mathit{top'})$. That's compensated at decryption by decrypting again when the decrypted plaintext is in range $[\mathit{top},\mathit{top'})$.

---

I have not touched side channel attacks, which are heavily language-dependent anyway.