Richard De Moliner
On the Statistical Testing of Block Ciphers
This doctoral thesis was done by Richard J. De Moliner from 1990 to 1999 with Professor James L. Massey at the Signal and Information Processing Laboratory of the Swiss Federal Institute of Technology at Zürich.
Tests that are capable of analyzing any practical block cipher, no matter what the internal structure of the block cipher may be, are the subject of this work. It is argued that such tests must be statistical.
A discrete memoryless source producing a fixed-length sequence of output digits from a finite alphabet is considered. The problem of deciding whether the single letter probability distribution of the discrete memoryless source is equal to a given probability distribution or not is analyzed in detail. For this problem of statistical hypothesis testing the Pearson statistic is used. What can validly be concluded from statistical hypothesis testing is carefully considered.
We show that if a cryptanalyst cannot solve at least one of two basic problems for a given block cipher, then he cannot "break" this block cipher. These two basic problems are (1) to find an algorithm that is distinguishing for the given block cipher and (2) to find an algorithm that is key-subset distinguishing for the given block cipher and for a given decomposition of the key space.
An approach to finding an algorithm that is distinguishing for a given block cipher as well as an approach to finding an algorithm that is key-subset distinguishing for a given block cipher and for a given decomposition of the key space are described. These two approaches form the framework for the statistical testing of block ciphers.
A family of tests called bit-dependency tests is presented. The aim of a bit-dependency test is to say as much as possible about the quality of a block cipher when only a given subset of bits of the plaintext blocks and a given subset of bits of the corresponding ciphertext blocks are observed.
cryptography, cryptanalysis, block ciphers, bit-dependency tests, statistical hypothesis testing, statistical tests, Pearson statistic.
Richard J. De Moliner. On the Statistical Testing of Block Ciphers, volume 14 of ETH Series in Information Processing (Ed. J.L.Massey). Hartung-Gorre Verlag Konstanz, 1999. ISBN 3-89649-489-9.
Electronic versions of this doctoral thesis can be downloaded from this home page (PDF, 5755 KB) or from the library of the Swiss Federal Institute of Technology at Zurich (http://e-collection.ethbib.ethz.ch/show?type=diss&nr=13106).