Paper 2017/016

Provable Security of Substitution-Permutation Networks

Yevgeniy Dodis, Jonathan Katz, John Steinberger, Aishwarya Thiruvengadam, and Zhe Zhang

Abstract

Many modern block ciphers are constructed based on the paradigm of substitution-permutation networks (SPNs). But, somewhat surprisingly---especially in comparison with Feistel networks, which have been analyzed by dozens of papers going back to the seminal work of Luby and Rackoff---there are essentially no provable-security results about SPNs. In this work, we initiate a comprehensive study of the security of SPNs as strong pseudorandom permutations when the underlying "$S$-box" is modeled as a public random permutation. We show that 3~rounds of S-boxes are necessary and sufficient for secure linear SPNs, but that even 1-round SPNs can be secure when non-linearity is allowed. Additionally, our results imply security in settings where an SPN structure is used for domain extension of a block cipher, even when the attacker has direct access to the small-domain block cipher.

Note: Added (1) attack against 2-round, linear SPNs that works for fields of arbitrary characteristic and (2) remarks on reducing key-length for 3-round linear SPNs.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
SPNsblock ciphers
Contact author(s)
aish @ cs ucsb edu
History
2017-09-27: revised
2017-01-11: received
See all versions
Short URL
https://ia.cr/2017/016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/016,
      author = {Yevgeniy Dodis and Jonathan Katz and John Steinberger and Aishwarya Thiruvengadam and Zhe Zhang},
      title = {Provable Security of Substitution-Permutation Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2017/016},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/016}},
      url = {https://eprint.iacr.org/2017/016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.