Paper 2015/803

Statistical and Algebraic Properties of DES

Stian Fauskanger and Igor Semaev

Abstract

D. Davies and S. Murphy found that there are at most 660 different probability distributions on the output from any three adjacent S-boxes after 16 rounds of DES [1]. In this paper it is shown that there are only 72 different distributions for S-boxes 4, 5 and 6. The distributions from S-box triplets are linearly dependent and the dependencies are described. E.g. there are only 13 linearly independent distributions for S-boxes 4, 5 and 6. A coset representation of DES S-boxes which reveals their hidden linearity is studied. That may be used in algebraic attacks. S-box 4 can be represented by significantly fewer cosets than the other S-boxes and therefore has more linearity. Open cryptanalytic problems are stated. [1] D. Davies and S. Murphy, "Pairs and Triplets of DES S-boxes", Journal of Crypt. vol. 8(1995), pp. 1--25

Note: The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-38898-4_6

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Springer International Publishing
DOI
10.1007/978-3-319-38898-4_6
Keywords
DESS-boxoutput distributionslinear dependenciescoset representation
Contact author(s)
stian @ fauskanger me
History
2016-05-10: last of 2 revisions
2015-08-11: received
See all versions
Short URL
https://ia.cr/2015/803
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/803,
      author = {Stian Fauskanger and Igor Semaev},
      title = {Statistical and Algebraic Properties of DES},
      howpublished = {Cryptology ePrint Archive, Paper 2015/803},
      year = {2015},
      doi = {10.1007/978-3-319-38898-4_6},
      note = {\url{https://eprint.iacr.org/2015/803}},
      url = {https://eprint.iacr.org/2015/803}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.