The most common S-boxes that I've seen are 4-bit and 8-bit (I've seen a 3-bit S-box in PRINTcipher, but I'm pretty sure they only did so due to significant hardware constraints). I understand that anything larger would be difficult to hold in a lookup table, and that 4-bit S-boxes are small enough to exhaustively search for ideal properties (for an 8-bit S-box, that would require checking 256! S-boxes), but what exactly are the tradeoffs made when choosing between the two, or choosing other sizes? I can intuitively understand why small S-boxes are not ideal, but I don't understand much more about the choice of the size.
what exactly are the tradeoffs made when choosing between the two, or choosing other sizes?
The triangle of performance , area and security. Smaller sboxes requires less resouces for implementation but it comes with lesser cryptographic properties (compared to larger size) therefore higher number of rounds to achieve minimum security requirement for the cipher (higher number of rounds , lesser speed performance).
One method used to merge the benefits of smaller and larger boxes sizes by constructing larger s-boxes from smaller s-boxes such as one of Clefia cipher sboxes, skinny etc. This type of construction allows implementation of 4-bit (for example) goes into "mini-cipher" structure to generate 8-bits boxes . The resulted 8-bit sbox has higher cryptographic properties but not as good as AES s-box.
Most of block ciphers come in 64 or 128 bit size which is divisible by 4 or 8 and friendly to software implementation( minimum cpu register size is 8-bit).
However , I have seen other sizes mostly in authenticated encryption , for example , FIDES is the first cipher that uses 5-bit (almost bent) and 6-bit (APN) s-boxes due to their optimal differential and linear probability.moreover , with bitslice implementation of butterfly APN s-box is advantage ref
Ascon uses 5-bit sbox but they claim because of mathematical and threshold-implementation properties.
The most important factors which effects in selecting of SBox size:
Ability to analyze and choose Optimal SBox: up to now,in two well-known papers,(Cryptographic Analysis of All 4 * 4-Bit S-Boxes) and (On the Classification of 4 Bit S-Boxes), cryptographic characteristic of 4-bit SBoxes are thoroughly investigated.As referred in these papers, the aim for choosing 4-bit size SBoxes instead of other different size SBoxes(like 5-bit or 8-bit) is ability to examine all of the bijective SBoxes (16!) in order to examine their cryptanalytic characteristics and finding OPTIMAL SBox between them and use this SBox safely in ciphers. Researches on SBoxes with sizes more than 4-bit has not yet done.
Implementation Constrains: 4-bit SBoxes are more compact in implementing and also by using 4 quantity of 4-bit SBoxes(bitslice implementation), we can build an 8-bit SBox and this structure is more compact and analyzable rather than a unique 8-bit SBox. Nowadays most of the ciphers are designed with low constrain resources like memory and power(Lightweight ciphers) therefore choosing SBoxes with low size is an important issue.
Execution Speed: 8-bit SBoxes are very big look-up tables rather 4-bit ones, therefore it is obvious that execution time of cipher which contains 4-bit SBoxes should be high.