Cryptology ePrint Archive: Report 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

Category / Keywords: DES, S-box, output distributions, linear dependencies, coset representation

Original Publication (in the same form): Springer International Publishing

Date: received 11 Aug 2015, last revised 9 May 2016

Contact author: stian at fauskanger me

Available format(s): PDF | BibTeX Citation

Note: The final publication is available at Springer via

Version: 20160510:053235 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]