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

Improve this question
$\endgroup$
4
  • 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, 2016 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, 2016 at 19:10
  • $\begingroup$ Actual numbers, if they are known. $\endgroup$
    – Demi
    May 21, 2016 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, 2016 at 19:59

1 Answer 1

Reset to default
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...

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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