# Differential & linear characteristics for integer multiplication

What are the probabilities of differential & linear characteristics for the function that XORs the high and low bits from a $n \times n \rightarrow 2n$ bit multiplication?

I remember reading somewhere that this function (which seems very fast in software) has excellent non-linearity. This suggests applications in (say) a Feistel network (where invertability is not required).

• While I did read a lot about diff. and lin. cryptanalysis I do not understand what you mean by XORing the high and low bits from a n×n→2n bit multiplication. What do you understand by characteristics, 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 ?
– Biv
May 21, 2016 at 8:45
• Just to be sure: when asking for “probabilities”, do you mean “general likeliness/chance of having linear/differential characteristics” or are you fishing for actual numbers of some kind? May 21, 2016 at 19:10
• Actual numbers, if they are known.
– Demi
May 21, 2016 at 19:33
• I suspect 'by XORing the high and low bits' he means the operation $a \otimes b = \lfloor ab / 2^n \rfloor \oplus (ab \bmod 2^n)$ May 21, 2016 at 19:59

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) {
for (int i = 1; i < numBits; ++i)
{
}
uint32 res = input & mask;
res = res * res;
res = (res >> numBits) ^ (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...

• Interesting, but no idea how you managed to implement code for a function based on his crummy description.
– user9070
May 24, 2016 at 11:05
• I assumed the operation was $n \otimes n$ which I implemented.
– Biv
May 24, 2016 at 11:21
• So not great, but possibly usable when combined with other sources of nonlinearity?
– Demi
May 24, 2016 at 13:16