Reciprocal block ciphers 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?
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.