This is the code i used to simulate your Sbox (no intelligence, pure application with lots of mask for security).
virtual uint8 apply_s(uint16 input, int numBits) {
uint16 mask = 1;
for (int i = 1; i < numBits; ++i)
{
mask |= mask << 1;
}
uint32 res = input & mask;
res = res * res;
res = (res >> numBits) ^ (res & mask);
return res & mask;
};
And these are the linear and differential results (not all equations are printed but the most probables ones):
Linear Cryptanalysis : 4 bits
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------------
0 | 8 2 2 2 -2 2 -2 2 2 -2 -4 -2
1 | 2 2 2 2 -2 2
2 | -2 4 2 2 -2 2 -2 2 2 -2 2
3 | -2 -2 2 -2 -2 2 2 2 2 4 2
4 | 2 2 -2 -2 -2 -2 2 2 4 4 2 -2
5 | 2 -2 4 4 -4 2 2 2 -2
6 | 2 2 -2 2 2 2 2 -2 -2 2
7 | 2 2 2 6 -2 -2 -2 2 -2 2
8 | 2 -2 2 2 2 -2 4
9 | -2 2 -4 -2 2 2 4 2 2 -2 2 2
10 | 2 4 4 2 -2 -4 2 -4 4 2 -2
11 | 4 2 -2 2 -2 2 2
12 | -4 2 2 2 2 -2 2 4
13 | 4 2 2 2 2 -2 2 -2 2 -2 -2
14 | -4 -4 2 2 2 -2 4 4 2 2
15 | 2 2 -2 4 -2 -2 2 4
X0 ⊕ X1 ⊕ X2 = Y0 ⊕ Y1 ⊕ Y2 : 6
X1 ⊕ X2 ⊕ X3 = Y1 : -4
X1 ⊕ X3 = Y0 ⊕ Y1 ⊕ Y3 : -4
X1 ⊕ X2 ⊕ X3 = Y0 ⊕ Y1 : -4
X0 ⊕ X2 = Y1 ⊕ Y2 : -4
X0 ⊕ X3 = Y2 : -4
X2 ⊕ X3 = Y0 : -4
X1 ⊕ X3 = Y0 ⊕ Y3 : -4
Differential Cryptanalysis : 4 bits
| 0 1 2 3 4 5 6 7 8 9 a b c d e f
---------------------------------------------------------------------
0 | 16
1 | 2 2 2 2 2 2 2 2
2 | 2 2 2 2 2 4 2
3 | 2 2 4 2 2 2 2
4 | 4 2 2 2 2 2 2
5 | 2 4 2 2 4 2
6 | 2 2 2 2 4 2 2
7 | 2 2 4 2 2 4
8 | 2 2 2 2 2 2 2 2
9 | 2 2 2 2 2 4 2
a | 2 2 2 2 2 2 4
b | 4 2 2 2 2 4
c | 2 2 2 2 2 6
d | 2 2 2 2 4 2 2
e | 2 2 4 2 2 2 2
f | 2 2 2 2 2 2 4
1011 => 1110 : 4 / 16
0011 => 0110 : 4 / 16
0110 => 1011 : 4 / 16
0101 => 1101 : 4 / 16
0010 => 1010 : 4 / 16
0100 => 0001 : 4 / 16
0101 => 0110 : 4 / 16
0111 => 1100 : 4 / 16
0111 => 0111 : 4 / 16
1100 => 1100 : 6 / 16
1010 => 1111 : 4 / 16
1011 => 0000 : 4 / 16
1001 => 1010 : 4 / 16
1110 => 0110 : 4 / 16
1111 => 1111 : 4 / 16
1101 => 1000 : 4 / 16
Linear Cryptanalysis : 8 bits
X0 ⊕ X3 ⊕ X5 ⊕ X7 = Y6 : -40
X0 ⊕ X2 ⊕ X3 ⊕ X6 = Y4 : -38
X1 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X6 ⊕ X7 = Y1 ⊕ Y3 ⊕ Y7 : -34
X1 ⊕ X4 ⊕ X7 = Y1 : -34
X0 ⊕ X1 ⊕ X2 ⊕ X3 ⊕ X5 ⊕ X7 = Y2 ⊕ Y3 : -33
X4 ⊕ X6 = Y3 ⊕ Y4 ⊕ Y7 : 32
X1 ⊕ X3 ⊕ X5 ⊕ X7 = Y1 ⊕ Y2 ⊕ Y5 ⊕ Y6 : 32
X0 ⊕ X2 ⊕ X4 ⊕ X6 = Y0 ⊕ Y3 ⊕ Y4 ⊕ Y6 ⊕ Y7 : -32
X1 ⊕ X2 ⊕ X5 ⊕ X6 = Y0 ⊕ Y1 ⊕ Y2 ⊕ Y3 ⊕ Y5 : -32
Differential Cryptanalysis : 8 bits
00000010 => 01001011 : 8 / 256
00000100 => 10010000 : 6 / 256
00000110 => 11010000 : 8 / 256
00000110 => 11010010 : 10 / 256
00000100 => 10100100 : 8 / 256
00011000 => 00111001 : 8 / 256
00000110 => 11010110 : 8 / 256
00000010 => 10001010 : 8 / 256
00000010 => 00101001 : 8 / 256
00000010 => 00101010 : 8 / 256
We can compare these results the S-box analysis of AES :
Linear analysis
X3 ⊕ X6 = Y0 ⊕ Y1 ⊕ Y2 ⊕ Y5 ⊕ Y6 ⊕ Y7 : 16
X1 ⊕ X2 ⊕ X6 = Y1 ⊕ Y6 ⊕ Y7 : 16
X0 ⊕ X2 = Y0 ⊕ Y1 ⊕ Y2 ⊕ Y3 : 16
X0 ⊕ X2 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X6 = Y1 ⊕ Y4 ⊕ Y5 : 16
X1 ⊕ X2 ⊕ X4 ⊕ X5 ⊕ X6 ⊕ X7 = Y0 ⊕ Y1 ⊕ Y4 ⊕ Y5 ⊕ Y6 ⊕ Y7 : 16
X0 ⊕ X2 ⊕ X3 ⊕ X5 = Y0 ⊕ Y1 ⊕ Y4 ⊕ Y5 ⊕ Y6 ⊕ Y7 : 16
X0 ⊕ X5 = Y0 ⊕ Y1 ⊕ Y3 ⊕ Y5 ⊕ Y6 ⊕ Y7 : 16
X0 ⊕ X3 ⊕ X7 = Y0 ⊕ Y2 ⊕ Y3 ⊕ Y5 : 16
X1 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X6 ⊕ X7 = Y0 ⊕ Y1 ⊕ Y3 ⊕ Y4 : 16
X1 ⊕ X2 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X7 = Y2 ⊕ Y5 ⊕ Y6 : 16
Differential Cryptanalysis
01010111 => 00111000 : 4 / 256
01000111 => 11000011 : 4 / 256
00000110 => 00001100 : 4 / 256
00011011 => 11001100 : 4 / 256
01001000 => 00110001 : 4 / 256
01110100 => 11110001 : 4 / 256
11000100 => 01111111 : 4 / 256
10111011 => 10001001 : 4 / 256
00101010 => 10000110 : 4 / 256
01011000 => 00001001 : 4 / 256
TL;DR : In both case (linear & differential), the Sbox of AES is better by a nice margin against cryptanalysis.
I did not pursue the analysis for higher values of $n$ because the RAM required to find the equations increases exponentially...
XORing the high and low bits from a n×n→2n bit multiplication
. What do you understand bycharacteristics
, and this is usually associated with a probability. Could you explain a bit better what you really ask or make a scheme about the functions of which you want the characteristic ? $\endgroup$