Differential attacks: using alternative operations

Is it possible that a block cipher apparently immune to classical differential cryptanalysis can be attacked considering a different operation on the message space? Recently Calderini and Sala showed how to effectively compute alternative operations on a vector space which can serve as message space for a block cipher such that the resulting structure is still a vector space. The latter were used to mount a linearisation attack against a toy cipher. Here we investigate how alternative operations interact with the layers of a substitution–permutation network and show how they influence the differential probabilities, when the difference taken into consideration is different from the usual bit-wise addition modulo two. Furthermore, we design a block cipher which appears to be secure with respect to classical differential cryptanalysis, but weaker with respect to our attack which makes use of alternative operations.