Differential and Linear Cryptanalysis on Random Sbox

Question

Assume that we use the key to perform a uniform permutation to generate a sbox. The literature is rich supporting the statement that a random Sbox can make any cryptographic scheme weaker. I have tested and found the randomly permuted sboxes possess weak nonlinearity and high differential probability. We know that to perform differential and linear attack the DDT and LAT should be handy. If we make the sbox key-dependent and every distinct key results a distinct sbox(best case). Now if someone tries to perform a differential/ linear cryptanalysis then will it be logical to consider the Bruteforce complexity of guessing the proper sbox? If it is logical then what should be the approach to such an attack?

Answer 1

Typical attacks on Secret SPNs (i.e. with secret uniform S-Boxes) are integrals, see e.g. [1].

Even for AES: the S-Box is too good against differential/linear attacks (strong mixing in MixColumns is also necessary), so best attacks are of another kinds. (Not counting related-key attacks, which allow to deactivate many S-Boxes).

More to the question: in some special cases it may be indeed useful to consider differential cryptanalysis with ``random'' difference. See for example [2], where the output of the Feistel function is very small so that it does not matter which difference to choose - the differential will be sufficiently strong anyway.

[1] Biryukov, A., Khovratovich, D., & Perrin, L. (2017). Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs. IACR Transactions on Symmetric Cryptology, 2016(2), 226-247. https://doi.org/10.13154/tosc.v2016.i2.226-247

[2] Orr Dunkelman, Abhishek Kumar, Eran Lambooij, Somitra Kumar Sanadhya: Cryptanalysis of Feistel-Based Format-Preserving Encryption. IACR Cryptol. ePrint Arch. 2020: 1311 https://eprint.iacr.org/2020/1311

Answer 2

It is correct that

The literature is rich supporting the statement that a random Sbox can make any cryptographic scheme weaker

But in general such statements apply to fixed public S-boxes (and as an aside, typically not to sizable ones, especially when they are permutations). But the question is about a secret key-dependent S-box (and a permutation on top of that), which is a very different matter.

Sizable key-dependent S-boxes are often considered a fine component for the non-linearity and key schedule/injection of a cipher (except perhaps from the prospect of timing attacks), and a few ciphers use them, including Blowfish.

---

Now if someone tries to perform a differential/ linear cryptanalysis then will it be logical to consider the Bruteforce complexity of guessing the proper sbox?

Yes, especially as a higher bound of the complexity of an attack if the S-boxes are the only key-dependent transformation. But for proper design that likely won't be enough for attack.

---

What should be the approach to such an attack?

Tentative: one approach is to consider some class of differential/linear property of the S-box(es) that has a sizable probability to hold for random key, show that an attack is then possible, and thus conclude that an attack is possible for a sizable portion of the keys.