# Achieving non-linearity in a block cipher using only rotations, shifts, AND, OR, and XOR

It is supposedly difficult to introduce enough non-linearity in block ciphers based on modular addition, data-independent bitwise rotations, and XOR to make them secure against certain kinds of cryptanalysis even though addition is used because it introduces non-linearity into the design that XOR does not have. But what if we also use bitwise AND, bitwise OR, and bitwise shifts (a left bitwise shift fills a fixed-length bit string with zeroes on its left-hand side)? And let's toss modular addition into the flames since that actually does not run in constant time on some processors.

I figure that bitwise AND and bitwise OR can be used to introduce more non-linearity than modular addition. Additionally, though I'm not familiar with the details rotational cryptanalysis, I figured that bitwise shifts can help to thwart it since the for some inputs, the outputs of a function using rotations might be made equal with a rotation applied to one of them. Bitwise shifts would not suffer from this problem. As an example, consider that for inputs $x_0 = 0101$ and $x_1 = 1010$ the function $f(x) = (x \ggg 1) \oplus x$ will return $111$ in both instances. But, if $f(x) = (x \gg 1) \oplus x$, then the outputs will be $0111$ and $1111$, respectively.

• The circuit for an adder incorporates bitwise AND/OR and shifts. Commented Nov 6, 2017 at 22:48
• @EllaRose I am aware of that, but I did away with addition. Commented Nov 7, 2017 at 15:29

The brief answer is: Yes, you can!

You may wish to study NORX, an AEAD scheme submitted to the CAESAR competition, whose essential thesis is that you can simultaneously attain high security, high software performance, and high hardware performance by the same design principles as ARX, but replacing $a + b$, which is slow in hardware, by the approximation $a \oplus b \oplus (a \wedge b) \ll 1$.

• "You may wish to study GIMlI, a permutation accepted at CHES2017, whose essential thesis is that you can simultaneously attain high security, high software performance, and high hardware performance by the same design principles as NORX, Ascon and Keccak, but replacing a+b, which is slow in hardware, by the approximation simliar to a⊕b⊕(a∧b)≪1." :D
– Biv
Commented Nov 7, 2017 at 11:36
• I'd edit my answer to mention Gimli too, but I don't think I can do any better than you just did! Commented Nov 7, 2017 at 14:43
• I do not know if I want to approximate addition. Commented Nov 7, 2017 at 15:29
• @Melab The point of addition is to add non linearity. The result does not matters. The propagation of non linearity by addition and $a \oplus b \oplus (a \land b) \ll 1$ are equivalent.
– Biv
Commented Nov 7, 2017 at 15:30
• @Biv That's fine. I'm just interested in trying it without addition. Commented Nov 7, 2017 at 17:02

Notice applying xor against the constant 1 is the not gate. And adding either Or gates or And gates is sufficient to create any function. Xoring, shift and rotation alone are not sufficient.