Can we replace the XOR operation in DES with some other operation?

Question

Can we replace the XOR operation in the DES algorithm with some other operation? If so, does it work for both encryption and decryption?

Answer 1

Within the DES block cipher itself, the XOR operation is used at two different places:

1. On the input of S-boxes, XOR-ing 48 bits per round: 48 bits from a subkey (extracted from the 56-bit key), and 48 bits that are the output of expansion E. The 48-bit result forms the eight 6-bit inputs of the S-boxes.
2. On the output of S-boxes, XOR-ing 32 bits per round: 32 bits from the former (left) half of the state, and 32 bits formed by the eight 4-bit outputs of the S-boxes. The 32-bit result forms the new (right) half of the state.

If in 1 XOR is replaced by addition modulo 2⁴⁸ (or eight additions modulo 2⁶), in both encryption and decryption, the cipher remains operative, in the sense that decryption remains the reverse of encryption. For something comparable in 2, XOR can be replaced with addition modulo 2³² (or eight additions modulo 2⁴) during encryption, and subtraction during decryption (with the negated input being the output of S-boxes). For interoperability, such changes would need to define unambiguously the limits and ordering of input and output bits.

Any of these changes would remove one notable property of DES: the complementation property, stating that $\operatorname{DES}_\overline K(\overline P)=\overline{\operatorname{DES}_K(P)}$. Depending on context, that could be neutral (e.g. with any bit in plaintext fixed), a benefit (e.g. adding one bit of resistance to brute force), or a disaster (e.g. when the complementation property is part of a strategy against side channel attacks).

These changes would potentially slow down implementations of DES, both in hardware (due to carry propagation) and software (by breaking common optimizations).

The impact on security is debatable. Only one thing is obvious: the S-boxes have been carefully designed in a context with XOR for near-optimal resistance to differential cryptanalysis (and later found fair against other attacks), thus we'd be moving into uncharted territory. Resistance against side-channel attacks could be lessened, even without consideration for the lost complementation property. I would be surprised if practical security was otherwise lessened under the assumption of a single unknown key, but would not bet on related-key attacks, or firmly commit on anything.

All in all, I see no good rationale for such change.