I'm interested in the property of involution in block ciphers and how one would go about constructing one. Creating a cipher where $E_K(E_K(M))=M$ for any $M$ and $K$ isn't an obvious task and the use of round keys makes it seem like this is an impossible task without undermining the security of the thing. What is my best approach for constructing a reciprocal block cipher? How do Anubis and Khazad do it?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ When you say reciprocal block cipher, do you mean that $Dk$ and $Ek$ are the same function? $\endgroup$– orlpMay 10, 2015 at 4:12
-
$\begingroup$ $D_k(E_k(M))=M$ is pretty much necessary for any encryption method ever, since it's equivalent to "you can decrypt a message." In fact, if $D_k(E_k(M))\ne M$, you don't have a cipher at all. $\endgroup$– cpastMay 10, 2015 at 4:34
-
$\begingroup$ @cpast I messed that up. Fixed now. $\endgroup$– MelabMay 10, 2015 at 5:16
-
$\begingroup$ @orlp Yes, I messed up what I was typing. I've fixed it now. $\endgroup$– MelabMay 10, 2015 at 5:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
9
Anubis (128-bit block) and Khazad (64-bit block) work by using involutional components in sequence. The complete ciphers are not fully involutional, as the key schedules and round constants prevent that from occurring. Decryption requires a different key schedule, but all other operations remain the same. They are SP-network ciphers, which are generally not involutional.
Feistel ciphers also use the same core components for encrypt and decrypt, but work differently, in that they generally do not use components that are involutions. As orlp pointed out, changing the key schedule can make a Feistel cipher into a full involution.
The advantage to involutional components is code reuse; you have a single encrypt/decrypt operation, and most parts of the key scheduling algorithms. It may also be easier to analyze the algorithm. The disadvantage is the components may be suboptimal, which means it usually will require more rounds to provide the same level of non-linearity and diffusion when compared to say, the AES candidates.
For the diffusion component (P) of the cipher, a Cauchy matrix is the go-to operation, since it provides a high branch diffusion, is an involution, and is simple to implement in reference and table-lookup designs. Large matrices can be implemented to provide full diffusion in a single round, but are slow outside of a table-lookup implementation. Khazad uses a large 8x8 matrix operating on the whole 64-bit block, whereas Anubis uses a 4x4 matrix like AES multiple times.
Here is the 8x8 MDS diffusion matrix for Khazad:
\begin{bmatrix} 01_x~~ 03_x~~ 04_x~~ 05_x~~ 06_x~~ 08_x~~ 0B_x~~ 07_x \\ 03_x~~ 01_x~~ 05_x~~ 04_x~~ 08_x~~ 06_x~~ 07_x~~ 0B_x \\ 04_x~~ 05_x~~ 01_x~~ 03_x~~ 0B_x~~ 07_x~~ 06_x~~ 08_x \\ 05_x~~ 04_x~~ 03_x~~ 01_x~~ 07_x~~ 0B_x~~ 08_x~~ 06_x \\ 06_x~~ 08_x~~ 0B_x~~ 07_x~~ 01_x~~ 03_x~~ 04_x~~ 05_x \\ 08_x~~ 06_x~~ 07_x~~ 0B_x~~ 03_x~~ 01_x~~ 05_x~~ 04_x \\ 0B_x~~ 07_x~~ 06_x~~ 08_x~~ 04_x~~ 05_x~~ 01_x~~ 03_x \\ 07_x~~ 0B_x~~ 08_x~~ 06_x~~ 05_x~~ 04_x~~ 03_x~~ 01_x \\ \end{bmatrix}
As you can, see, all 4x4 diagonal corners of the matrix are same, all 2x2 diagonal corners of those matrices are the same, and all 1x1 diagonal corners of those matrices are the same. That is the property that makes the Cauchy matrix an involution. The matrix can be built at runtime from a single row and a recursive algorithm.
For the substitution component (S) of the cipher, using an involutional s-box is not optimal. Even the best involutional s-boxes have inferior properties when compared to modern block ciphers. Anubis and Khazad use the same s-box, here is a comparison to some of its primary properties against the AES s-box:
AES Anubis/Khazad
Nonlinearity: 112 96 higher is better
Differential Uniformity: 4 8 lower is better
Autocorrelation: 32 104 lower is better
Sum of Squares Indicator: 133120 270208 lower is better
AVAL Relative Error: 3.52% 11.72% lower is better
Bit Independence Rel Err: 13.4% 27.6% lower is better
SAC Relative Error: 12.5% 34.4% lower is better
Distance to SAC: 432 620 lower is better
These suboptimal s-box properties are the main reason that Anubis requires more rounds than AES for the same key size, as their diffusion component is essentially the same. The s-box has an iterative period of 2, with every element paired to another.
If you wish to create a cipher that is a full involution, your best bet is a Feistel structure. You can use involutional components but that is not a requirement. If your goal is code reuse and simplicity of description, look at the design principles of Anubis.
You can also use a stream cipher mode such as CTR on any block cipher, as XOR is its own inverse.
answered May 10, 2015 at 8:36
-
$\begingroup$ The question is about block ciphers. How can the key schedule be changed to make a Feistel cipher into an involution? $\endgroup$– MelabMay 11, 2015 at 1:10
-
$\begingroup$ @Melab using a palindromic key schedule as per orlp's answer. I tested it using the AES round as the F-function to build a 256-bit involutional cipher with an 11 rounds and I/O whitening, it works correctly $\endgroup$ May 11, 2015 at 7:11
-
$\begingroup$ W R S R S R S R S R S R S R S R S R S R S R W, where W = whitening, R = a round operation, S = swap $\endgroup$ May 11, 2015 at 7:13
-
$\begingroup$ How does the diffusion matrix or permutation box work here? It does not appear to be a simple mapping of one set of coordinates to another. Are there any alternatives to Feistel and SPN ciphers? $\endgroup$– MelabMay 13, 2015 at 19:47
-
$\begingroup$ @Melab the same way they do in AES, they are not involutions. The key schedule is what makes the Feistel structure an involution, regardless of the F-function used. I used AES because it was convenient and fast. I suppose it could be applied to a Lai Massey cipher, I have none in my code library to modify and test $\endgroup$ May 13, 2015 at 20:01
$\begingroup$
$\endgroup$
2
You can turn any secure $n$-bit pseudorandom function into a secure(?) reciprocal $2n$-bit block cipher by using the former in a Feistel network of at least 4 rounds with a palindromic key schedule.
(?) I'm not certain whether the Feistel construction is weakened by a palindromic key schedule, so I'm hesitating to call it secure.
-
$\begingroup$ I do not think so. I tried it already with some code. The last round in a Feistel cipher doesn't swap halves around. $\endgroup$– MelabMay 10, 2015 at 5:19
-
3$\begingroup$ @Melab That's just silly. You can make it swap the halves after the last round without any loss to security - any attacker can trivially swap halves of the ciphertext as they please. $\endgroup$– orlpMay 10, 2015 at 6:29