5
$\begingroup$

After swapping random indexes of trivial involution $S[x] = ¬x$, I found the following involution S-Box with a non-linearity of $98$ and a differential uniformity of $6$.

Is there an upper limit to maximum non-linearity attainable for an involution S-Box?

For example: the Anubis cipher S-Box has a non-linearity of $96$ and a differential uniformity of $8$. Will the Anubis cipher become stronger if I use the S-Box I found?

byte[] S = new byte[256]
{
    0xde,0x32,0x10,0xc3,0x9e,0x52,0x89,0x6a,0xe8,0x97,0x29,0x6d,0x35,0xcb,0xb5,0xc7,
    0x02,0xc0,0xba,0x1a,0xda,0x62,0x60,0x47,0xed,0xcd,0x13,0x7b,0x88,0x4b,0x21,0x87,
    0xa1,0x1e,0x82,0x70,0xa9,0xd1,0xa3,0x79,0x30,0x0a,0xd6,0xdc,0xce,0x5e,0x6c,0xc2,
    0x28,0x64,0x01,0xa0,0xe1,0x0c,0xfa,0x42,0x48,0xc8,0x44,0x6f,0x50,0xbb,0xb6,0xbd,
    0xfd,0xc5,0x37,0xab,0x3a,0x49,0xf5,0x17,0x38,0x45,0xf6,0x1d,0x77,0xef,0xaa,0xdf,
    0x3c,0xb7,0x05,0xa8,0xac,0x8f,0x66,0xf2,0x85,0x9b,0x5d,0xe3,0x7c,0x5a,0x2d,0x69,
    0x16,0x75,0x15,0xd3,0x31,0xf7,0x56,0xc1,0x84,0x5f,0x07,0xb0,0x2e,0x0b,0xe7,0x3b,
    0x23,0x7f,0x7d,0xee,0xf3,0x61,0xe9,0x4c,0xd5,0x27,0xd0,0x1b,0x5c,0x72,0x81,0x71,
    0x83,0x7e,0x22,0x80,0x68,0x58,0xbe,0x1f,0x1c,0x06,0x8e,0x92,0xa6,0xf1,0x8a,0x55,
    0x96,0xa4,0x8b,0xec,0xd8,0xb3,0x90,0x09,0xd9,0xf0,0x9f,0x59,0xf9,0xb8,0x04,0x9a,
    0x33,0x20,0xb9,0x26,0x91,0xaf,0x8c,0xdd,0x53,0x24,0x4e,0x43,0x54,0xff,0xcf,0xa5,
    0x6b,0xe0,0xc6,0x95,0xdb,0x0e,0x3e,0x51,0x9d,0xa2,0x12,0x3d,0xd4,0x3f,0x86,0xf8,
    0x11,0x67,0x2f,0x03,0xc9,0x41,0xb2,0x0f,0x39,0xc4,0xe4,0x0d,0xeb,0x19,0x2c,0xae,
    0x7a,0x25,0xfe,0x63,0xbc,0x78,0x2a,0xea,0x94,0x98,0x14,0xb4,0x2b,0xa7,0x00,0x4f,
    0xb1,0x34,0xf4,0x5b,0xca,0xfb,0xfc,0x6e,0x08,0x76,0xd7,0xcc,0x93,0x18,0x73,0x4d,
    0x99,0x8d,0x57,0x74,0xe2,0x46,0x4a,0x65,0xbf,0x9c,0x36,0xe5,0xe6,0x40,0xd2,0xad
};
$\endgroup$
  • $\begingroup$ are you sure the nonlinearity of the Anubis s-box is 96? my test says it is 94 $\endgroup$ – Richie Frame Jun 4 '16 at 9:51
  • $\begingroup$ Should consider trying the original Anubis s-box. The current S-box is the product of 2 4-bit s-boxes, to make hardware implementations easier. Presumably the first s-box would be more secure as there is a limit to security of a random 4-bit s-box as opposed to a random 8-bit s-box. $\endgroup$ – user3201068 Nov 24 '16 at 4:53
4
$\begingroup$

Assuming your differential uniformity and non-linearity figures are correct, then yes, your s-box is slightly stronger against basic differential and linear cryptanalysis. Although Anubis already was essentially immune to basic differential and linear cryptanalysis. However your s-box would need to be evaluated against other forms of cryptanalysis (e.g. interpolation, invariant subspace, etc) in order to determine if it was "better" in a more general sense. It may also be less efficient in terms of hardware implementation than the current Anubis s-box (to invoke another, no-less crucial sense of "better").

Note: The AES s-box is affine-equivalent to an involution (as will be obvious if you think about the multiplicative inversion function), and has a higher non-linearity and lower differential uniformity. Non-linearity and differential uniformity are the same for all affine-equivalent permutations. So that should help address your question about the maximum non-linearity of an involution.

| improve this answer | |
$\endgroup$
  • $\begingroup$ His figures are correct. Autocorrelation is 96, SSI is 251392, SAC and 2nd order SAC relative error is 21.9%, AVAL rel error is 4.69%, 2nd order AVAL rel error is 7.42%, BIC is 0.2288, 2nd order BIC is 0.28139 $\endgroup$ – Richie Frame May 31 '16 at 20:22
  • $\begingroup$ "SSI is 251392". what do you mean by SSI. $\endgroup$ – vinu Jun 1 '16 at 4:05
  • $\begingroup$ @vinu - you need to include an "@Richie Frame" at the start of your comment to ensure he sees it. $\endgroup$ – J.D. Jun 1 '16 at 9:26
  • 1
    $\begingroup$ @EllaRose - I don't have a link, but the intuition is this - if two functions $f(x)$ and $g(x)$ are affine equivalent to each other, that means $f(x) = a(g(b(x)))$ where $a(x)$ and $b(x)$ are affine functions. In other words $f(x)$ and $g(x)$ are the same s-box except one is composed with some affine functions. Differences propagate through affine functions with probability 1, so those affine functions cannot change the differential probabilities of the core 'shared' s-box. Hence the two functions will have the same max differential probability (same uniformity). $\endgroup$ – J.D. Mar 3 '17 at 0:42
  • 1
    $\begingroup$ @EllaRose - P.S. if that short explanation doesn't suffice I think the topic of how affine equivalence affects differential uniformity could make for a good question . . . $\endgroup$ – J.D. Mar 3 '17 at 0:53

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.