Xrhrft

In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.

• What does "Canonical representative of S-Box is 0123468A5BCF79DE" mean? And,


• How can I calculate it for an individual S-Box?

Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set ${0,1}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits. Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF.

A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order. Thus, for example, the string 0123468A5BCF79DE represents the permutation:

0123456789ABCDEF

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

0123468A5BCF79DE

(See e.g. this answer for examples.) While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.

The story doesn't end here, though. The article you've linked does not discuss individual S-boxes, but equivalence classes of them. One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):

Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ mathrm{LE}(S)$.

Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices. (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)

The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.

Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them. One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it. But which one? The author describes their choice in definition 6:

Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.

For example, the S-boxes 0123468A5BCF79DE and 5BCF79DE0123468A are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8 in hex) before applying the S-box. But the string 0123468A5BCF79DE sorts before 5BCF79DE0123468A in lexicographic order (since 0 < 5), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.

As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.