Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks

Substitution-Permutation Networks (SPNs) refer to a family
of constructions which build a wn-bit block cipher from n-bit public
permutations (often called S-boxes), which alternate keyless and “local”
substitution steps utilizing such S-boxes, with keyed and “global” permu-
tation steps which are non-cryptographic. Many widely deployed block
ciphers are constructed based on the SPNs, but there are essentially no
provable-security results about SPNs.
In this work, we initiate a comprehensive study of the provable security
of SPNs as (possibly tweakable) wn-bit block ciphers, when the underlying
n-bit permutation is modeled as a public random permutation. When the
permutation step is linear (which is the case for most existing designs),
we show that 3 SPN rounds are necessary and sufficient for security. On
the other hand, even 1-round SPNs can be secure when non-linearity
is allowed. Moreover, 2-round non-linear SPNs can achieve “beyond-
birthday” (up to 2 2n/3 adversarial queries) security, and, as the number
of non-linear rounds increases, our bounds are meaningful for the number
of queries approaching 2 n . Finally, our non-linear SPNs can be made
tweakable by incorporating the tweak into the permutation layer, and
provide good multi-user security.
As an application, our construction can turn two public n-bit permuta-
tions (or fixed-key block ciphers) into a tweakable block cipher working
on wn-bit inputs, 6n-bit key and an n-bit tweak (for any w ≥ 2); the
tweakable block cipher provides security up to 2 2n/3 adversarial queries
in the random permutation model, while only requiring w calls to each
permutation, and 3w field multiplications for each wn-bit input.