The Open Collections website will be undergoing maintenance on Wednesday December 7th from 9pm to 11pm PST. The site may be temporarily unavailable during this time.

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Bidirectional heuristic search and spectral S-box simplification for the cryptanalysis of the NBS Data Encryption Standard Gullichsen, Eric Alexander


Details of the National Bureau of Standards Data Encryption Standard (DES) are examined, and the strength of the cryptosystem found to lie in its substitution box (S-box) components. An unsuccessful attempt is made to discover symmetries in the S-box functions under permutation and/or complementation of variables. The problem of cryptanalyzing DES is then shown to be equivalent to a problem of tree search. Techniques which can reduce the number of tree nodes which need be visited to effect a cryptanalysis are, investigated. The linearization of the S-box functions by coefficient translations in the Hadamard spectral domain is found to be highly effective in reducing search tree size. For a bidirectional tree search which employs the linearized S-boxes, the number of nodes which need be visited to cryptanalyze DES is shown to be on the order of the key space size. The use of an AND/OR search tree structure with key bit constraints stored at the leaves ensures that each node need be visited only once. Given that the work involved in visiting a node is less than that required for a key trial, this key search method represents an improvement over the cryptanalytic technique of exhaustive key search.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use