1
$\begingroup$

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")

Improve this question
$\endgroup$
4
  • $\begingroup$ Is this cipher even reversible? $\endgroup$
    – bmm6o
    Jul 19 '18 at 15:02
  • $\begingroup$ 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; $\endgroup$
    – Chris Miller
    Jul 19 '18 at 15:03
  • $\begingroup$ Are the P values constant or derived from the key? $\endgroup$
    – conchild
    Jul 19 '18 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – Chris Miller
    Jul 19 '18 at 17:52
1
$\begingroup$

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.

Improve this answer
$\endgroup$
17
  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Jul 19 '18 at 15:58
  • 1
    $\begingroup$ 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... $\endgroup$
    – poncho
    Jul 19 '18 at 16:01
  • 1
    $\begingroup$ 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 $\endgroup$
    – poncho
    Jul 19 '18 at 17:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – user31573
    Jul 19 '18 at 18:36
  • 1
    $\begingroup$ @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. $\endgroup$
    – user31573
    Jul 19 '18 at 18:36

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.