Linear dependencies between non-uniform distributions in DES

Abstract

Davies and Murphy explained some non-uniform distributions of the output from pairs and triplets of S-boxes in DES, and how they are completely dependent on some key bits. There are linear dependencies between these distributions. In this thesis, we describe these linear dependencies. We also describe linear dependencies between the distributions of the output from three adjacent S-boxes after n rounds in DES. We have found all linear dependencies between the distributions of the output from 5 of the S-box triplets in full DES. The dependencies originates from properties common to all S-boxes in DES.