3
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Biv May 21 '16 at 8:45
  • $\begingroup$ 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? $\endgroup$ – e-sushi May 21 '16 at 19:10
  • $\begingroup$ Actual numbers, if they are known. $\endgroup$ – Demi May 21 '16 at 19:33
  • 3
    $\begingroup$ 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)$ $\endgroup$ – poncho May 21 '16 at 19:59
2
$\begingroup$

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...

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.