Open Collections

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

University of British Columbia

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.

Text

2010-04-20

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/23939

Computer Science

University of British Columbia

Graduate