2
$\begingroup$

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$:

Algorithm

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
$\endgroup$
3
  • $\begingroup$ I tend to think this is off-topic, because we don't do code review; but will let others decide, for mods don't really vote on these things (they decide, and here I hesitate). That said, hint: the input + key + round at the input of the Feistel round function introduces a major regularity, and would I believe be enough to allow a slide-like attack when the block size is not too large. I see no other striking issue. $\endgroup$ – fgrieu Nov 26 '20 at 15:44
  • $\begingroup$ @fgrieu, as per the topic link on your comment, «[...] using a minimal amount of code to illustrate an algorithm you have a theoretical question about is fine, a good indicator for that case being that you could have written that code in any language to bring the point across» $\endgroup$ – 0x2b3bfa0 Nov 26 '20 at 17:33
  • $\begingroup$ Python was just a sensible compromise between expressivity and clarity, though, if you deem it opportune, I can remove the boilerplate code and express the encryption and decryption routines with the LaTeX algorithmicx package or a similar notation. $\endgroup$ – 0x2b3bfa0 Nov 26 '20 at 18:07
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ The hash function takes as its only argument the addition of the input variables instead of its concatenation because they inputs are numbers and not binary strings. $\endgroup$ – 0x2b3bfa0 Nov 26 '20 at 21:10
  • $\begingroup$ What would be the advantage of calculating the concatenation of the finite fields $hash(data * rounds + key * rounds * first + round)$ over the current $hash(data + key + round)$? $\endgroup$ – 0x2b3bfa0 Nov 26 '20 at 21:13
  • 1
    $\begingroup$ @0x2b3bfa0: I proposed an alternative with numbers only, and have better explained the rationale. This should address both comments. $\endgroup$ – fgrieu Nov 26 '20 at 21:36
  • 1
    $\begingroup$ «We can do this with just numbers, as $return$ $hash(data + (key ⋅ rounds + round) ⋅ first ⋅ second)$» As the $data$ passed to $function$ is always a number from a finite field with length $first$, wouldn't be the multiplication by $second$ an unnecessary precaution? $\endgroup$ – 0x2b3bfa0 Nov 27 '20 at 0:09
  • 1
    $\begingroup$ @0x2b3bfa0: indeed $\cdot\mathit{first}\cdot\mathit{second}$ was more than needed. But we can't change that to $\cdot\mathit{first}$ as suggested, for $\mathit{data}$ has been reduced modulo $\mathit{second}$, and it can be that $\mathit{first}<\mathit{second}$ unless I missed something. I've thought more about the slide attack. I'm quite positive about the related-key attack, and optimistic about the other, which would qualify as a break by modern standards. $\endgroup$ – fgrieu Nov 27 '20 at 6:24

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.