  We investigate S-boxes defined by pairs of Orthogonal Cellular Automata
(OCA), motivated by the fact that such CA always define bijective vectorial
Boolean functions, and could thus be interesting for the design of block
ciphers. In particular, we perform an exhaustive search of all nonlinear OCA
pairs of diameter $d=4$ and $d=5$, which generate S-boxes of size $6\times 6$
and $8\times 8$, respectively. Surprisingly, all these S-boxes turn out to be
linear, and thus they are not useful for the design of confusion layers in
block ciphers. However, a closer inspection of these S-boxes reveals a very
interesting structure. Indeed, we remark that the linear components space of
the OCA-based S-boxes found by our exhaustive search are themselves the kernels
of linear CA, or, equivalently, \emph{polynomial codes}. We finally classify
the polynomial codes of the S-boxes obtained in our exhaustive search and
observe that, in most cases, they actually correspond to the cyclic code with
generator polynomial $X^{b}+1$, where $b=d-1$. Although these findings rule out
the possibility of using OCA to design good S-boxes in block ciphers, they give
nonetheless some interesting insights for a theoretical characterization of
nonlinear OCA pairs, which is still an open question in general.
