  Substitution boxes (S-boxes) are critical nonlinear elements to achieve
cryptanalytic resistance of modern block and stream ciphers. Given their
importance, a rich variety of S-box construction strategies exists. In this
paper, S-boxes generated by using chaotic functions (CF) are analyzed to
measure their actual resistance to linear cryptanalysis. The aforementioned
papers emphasize on the average nonlinearity of the S-box coordinates only,
ignoring the rest of the S-box components in the process. Thus, the majority of
those studies should be re-evaluated. Integrating such S-boxes in a given
cryptosystem should be done with a considerable caution. Furthermore, we show
that in the context of nonlinearity optimization problem the profit of using
chaos structures is negligible. By using two heuristic methods and starting
from pseudo-random S-boxes, we repeatedly reached S-boxes, which significantly
outperform all previously published CF-based S-boxes, in those cryptographic
terms, which the aforementioned papers utilize for comparison. Moreover, we
have linked the multi-armed bandit problem to the problem of maximizing an
S-box average coordinate nonlinearity value, which further allowed us to reach
near-optimal average coordinate nonlinearity values significantly greater than
those known in literature.
