Thumbnail Image

Compression and cryptology

Currently data compression and encryption are carried out as two separate activities. A simpler communication system would result if these two activities could be combined. The security properties of lossless data compression techniques are investigated. It is argued that compression is necessary for security but demonstrated that current compression techniques are not sufficient. Both coding techniques (arithmetic coding and Huffman coding) and modelling techniques (splaying, Ziv-Lempel, and prediction by partial matching—PPM) are examined. It is shown that all these systems have significant security flaws. Explicit attacks are given and descriptions of algorithms to automate the attacks are provided. Chosen plaintext attacks are given for Huffman coding, PPM, and splaying. Known plaintext attacks are given for arithmetic coding, splaying and Ziv-Lempel compressors. A ciphertext only attack is given for the Ziv-Lempel compressors. These results are used to highlight why better models of natural languages have important applications in cryptology. In particular, it is explained how a better model of a source leads naturally to increased resistance from dictionary and ciphertext only attacks. Some of the attacks presented involve novel methods not previously reported in the literature. In particular, it is shown how a backtracking search can be used for known and chosen plaintext attacks against fixed to variable length binary encoders (Huffman coding and splaying). It is shown how a good model of the source (a PPM model) can be used in an automatic ciphertext only attack against simple substitution ciphers and Ziv-Lempel compressors. The attack against simple substitution ciphers is at least comparable to previously published automated approaches. In some cases analytical or asymptotic results concerning the complexity of the attacks are given. It appears that compression leads naturally to increased ciphertext only resistance, but current compressors contain no operations likely to thwart known or chosen plaintext attacks.
Type of thesis
The University of Waikato
All items in Research Commons are provided for private study and research purposes and are protected by copyright with all rights reserved unless otherwise indicated.