How to deal with a cipher with addition and XORs combined together?

I am trying to cryptanalyze a cipher where bitwise XOR and addition mod $2^n$ are combined together. I've been working on it for a long time but with no result - the main difficulty, which I am unable to overcome, is that even though XOR and addition are linear in their own groups, addition mod $2^n$ is non-linear over $\mathbb{F}_2^n$ and vice versa.

Are there any standard methods of dealing with it which I should know about or some fancy theorems that would make things easier?

• This sounds like a sub-class of so-called ARX ciphers. Maybe a search for this term may help you... Jul 1, 2016 at 13:09
• That was exactly what I needed - just knowing what to google for! Thanks!
– Hugo
Jul 1, 2016 at 13:14

Note that, for the least significant bit, addition mod $2^n$ and xor are the same. So if the cipher doesn't include rotation then you can set up a linear equation in the least significant bits of the plaintext, ciphertext, and round keys that holds with probability 1 (if the cipher breaks the state up into two or more distinct parts, like a Feistel cipher, then you need to consider the least significant bits of each part). That means with a single known plaintext you can extract a single bit of information about the least significant bits of the round keys.

This single bit of information narrows down the possibilities for the least significant carry bits, which enables you to gain one more bit of information about the LSBs of the round keys by observing what happens to the least 2 significant bits of the plaintext and ciphertext. That narrows down the possibilities for the LSB carry bits even further, enabling you to gain another bit by looking at the least 3 significant bits of the plaintext and ciphertext, and so on. By progressively narrowing down the possibilities for the round key LSBs, you can gain complete knowledge of those bits (so long as the number of rounds does not exceed the 'part' size of the cipher), and then you can attack the 2nd LSBs using the same techniques.

To illustrate, take this very simple example cipher: $E(x) = ((((x + R_0) \oplus R_1) + R_2) \oplus R_3)$, where the cipher operates on blocks of $n$ bits, "+" is addition over $2^n$, $\oplus$ is xor, and each 'round' key $R_i$ is an $n$-bit independently selected random string. From this, if $X^j$ denotes the $j$th bit of a given word (zero being the least significant bit) and $P$ and $C$ denote the plaintext and ciphertext respectively, given a single known plaintext the following equation gives you a single bit of information about the four round keys: $$P^0 \oplus C^0 = R_0^0 \oplus R_1^0 \oplus R_2^0 \oplus R_3^0.$$ Let us suppose that the result is zero. That means either all four least significant bits of the round keys are zero, or two of them are zero, or none of them are zero - there are eight possible arrangements in total. If you get two known/chosen plaintexts where $P^1$ is fixed to some value and $P^0$ varies, and look at the resulting $C^0$ and $C^1$, you can narrow those 8 possibilities for the LSBs of the round keys down to 4 possibilities. In a similar fashion those four can then be narrowed down to two, and then to one, using a few more known/chosen plaintexts.

With the influence of the least significant carry bits known, you can apply the same technique to determine the four $R^1$ bits. That way you can progressively reveal almost all the bits of the round keys, using relatively few known/chosen plaintexts.

Because of this sort of vulnerability in using only addition and xor, ARX ciphers include rotation (that's the 'R' part of the name).

• That should work, thanks for such a clear explanation!
– Hugo
Jul 1, 2016 at 16:06

For fixed values $z$ the functions $\varphi_z(x) = ((x\oplus z)-x)\oplus z$ and $\varphi'_z(x) = ((x\oplus z)+x)\oplus z$ (where $-$ rsp. $+$ denotes subtraction rsp. addition modulo $2^n$) are linear over the field with two elements. In other words, considered as functions $\varphi_z : GF(2)^n \to GF(2)^n$, they are $GF(2)$-linear: e.g., for each $z$ there exists a $n \times n$ boolean matrix $M$ such that $\varphi_z(x)=Mx$.

This result is due to Louis Goubin. Not sure if it helps.

Louis Goubin. A Sound Method for Switching between Boolean and Arithmetic Masking. CHES 2001. See Theorem 1 and Corollary 1.1.