16-bit entry in a S-Box of a SPN block cipher: Would it have the same speed/performance than a 8-bit entry?

Question

I learned that in Substitution–permutation block ciphers, the maximum size of S-Box set to receive an entry from a data is the max numeric count of the data, for example, if the entry is 8-bits the S-Box set to be used is 256-bytes as 2^8=256.

Would 16-bits entries in a S-Box set of 65536-bytes (2^16) deliver the same speed/performance (cycles per byte) to the cipher as well as if was used 8-bits entries in a 256-byte S-Box set?

16-bits entries require a larger S-Box set (65536 bytes), would it be 256 times slower that if it was used a 8-bits entry? (as 65536/256=256).

Answer 1

Firstly note that a $2^{16}$-long look up table of 16-bit=2-byte entries takes up 131,072 bytes of space.

Your question is very architecture dependent. For speedy encryption you would want the S-loaded into the fastest bit of memory cache (L1 cache is a frequently used term). Now the Pentium III for example had 32KB of L1 cache which could easily cope with a 256B S-box, but would not be able to cope with your S-Box. It would be swapping sections of the table in and out and taking a performance hit. More modern processors such as the Xeon series have 1-2MB of L1 cache and might be able to cope. If you want to encrypt stuff in resource constrained environments such as mobile phones and and IoT sensors (and this is the focus of a great deal of block cipher design these days), note that for example the ARM Cortex A L1 cache is typically 32 kB or 64 kB and would not cope well.

The overall effect is probably much less than a factor of 256 (but again architecture dependent bus speeds will affect this). However the variation in time produced by cache swapping increases the danger of timing side channel attacks (Bernstein "Cache timing attacks on AES" showed that cache timing effects can cause vulnerabilities in AES implementations). This now becomes a question not just of performance degradation but also security degradation.