# Is this an example of a Feistel cipher?

Have tried to create simplest example. A,B,C,D are 32-bit unsigned, as is k[4]. P is an expansion type p-box of 256 "random" 32-bit values. Assume key-whitening and multiple rounds/keys

#define b0(u) ((u)&0xff)
#define b1(u) (((u)>>8)&0xff)
#define b2(u) (((u)>>16)&0xff)
#define b3(u) (((u)>>24))

// rounds...
A += P[b0(D)^b1(D)^b2(D)^b3(D)] ^k[0];
B += P[b0(A)^b1(A)^b2(A)^b3(A)] ^k[1];
C += P[b0(B)^b1(B)^b2(B)^b3(B)] ^k[2];
D += P[b0(C)^b1(C)^b2(C)^b3(C)] ^k[3];
k+=4
// end rounds


Also, is there a term for this specific method? (besides just "weak")

• Is this cipher even reversible? – bmm6o Jul 19 '18 at 15:02
• Absolutely! Thanks for asking: D -= P[b0(C)^b1(C)^b2(C)^b3(C)] ^k[3]; C -= P[b0(B)^b1(B)^b2(B)^b3(B)] ^k[2]; B -= P[b0(A)^b1(A)^b2(A)^b3(A)] ^k[1]; A -= P[b0(D)^b1(D)^b2(D)^b3(D)] ^k[0]; k-=4; – Chris Miller Jul 19 '18 at 15:03
• Are the P values constant or derived from the key? – conchild Jul 19 '18 at 17:16
• I have two flavors of slightly more complicate variations, and the p-box can be scheduled as part of the key (which slows down scheduling a little) or used static. – Chris Miller Jul 19 '18 at 17:52

This is a simple 128-bit block cipher, reversibly changing a 32-bit word of the state at each of 4 steps shown. It is very similar to an unbalanced Feistel cipher, except that the change of state is with += rather than the conventional ^=. In the context that deviation has three consequences, with the first rather desirable:

1. It creates alternation of ^ and + in the diffusion pattern.
2. Decryption is less similar to encryption than in a Feistel cipher (I guess the decryption code use uses -= ).
3. Hardware implementation would be slightly bigger/more power hungry, perhaps even slightly slower; but 1 more than compensates, and that's a non-issue in software.

To hope for security, there must of course be MUCH more rounds than shown. We have not even reached full diffusion (nothing in B or C influenced the outcome of A ). As a crude reference, AES-128 modifies its full state 10 times (discounting the initial XOR with a subkey); and Speck-128-128 modifies it 16 times. Security will depend a lot on the number of rounds, on a sensible choice of table P, and on the key schedule (producing the array k of subkeys from the actual key).

Note: Implementation in software is likely to suffer from data cache timing dependencies and other cache-related side channels, due to indexing in P at data-dependent indexes.

Note: as pointed by Poncho (correcting my mistakes), this cipher generates an even permutation; but that's not a weakness, since that reveals 1 bit of information only after $2^{128}-2$ input-output pairs are collected.

• As for point (2), the sketched cipher will always be an even permutation, even though it uses +=; that's because at each round, there are bits that do not participate in the transform. – poncho Jul 19 '18 at 15:58
• Also, I do not understand your last point at all; if we replace b0(X)^b1(X)^b2(X)^b3(X) with b0(X), I don't see any right-ward diffusion from the upper 24 bits at all... – poncho Jul 19 '18 at 16:01
• For any round function that includes a bit that is unaffected, and doesn't affect any other bit is, is always an even permutation. It's easy to show; if we consider the permutations that round implements (with a specific key), and the exchanges that implement that permutation, we can pair up the exchanges with that bit=0 with equivalent exchanges with that bit=1. Because we can pair the exchanges up, we always can implement it with an even number of exchanges, which means it's an even permutation – poncho Jul 19 '18 at 17:30
• @fgrieu: This unbalanced Feistel structure with modular addition instead of XOR isn't unheard of in battle-tested ciphers, for example, SHACAL-2 (and thus SHA-2) uses one. – user31573 Jul 19 '18 at 18:36
• @ChrisMiller What you call a "p-box" is usually called an S-box, and rather than use random sequences, they're usually specifically designed to have desirable properties like non-linearity and resistance to differential analysis. – user31573 Jul 19 '18 at 18:36