TREE FUNCTIONS AND CIPHER SYSTEMS |
| |
Authors: | Ross J Anderson |
| |
Affiliation: | 4 Old Hall Lane, Worsley, Manchester M28 4GG, UNITED KINGDOM |
| |
Abstract: | A number of encryption systems work by combining each plaintext bit with a hash function of the last n ciphertext bits. Such systems are self-synchronising in that they recover from ciphertext errors with an error extension of n. We show firstly that if the hash function is a tree function, then the system is vulnerable to a chosen ciphertext attack and, under certain circumstances, to a chosen plaintext attack; secondly, that all hash functions are equivalent to some tree function; thirdly, that whether or not this gives a computable attack on a given algorithm depends on the connectivity of a graph associated with the hash function; and, fourthly, the implications for DES, for RSA key selection, and for algorithm design in general. |
| |
Keywords: | Cryptography cryptanalysis self-synchronising algorithms graphs DES RSA |
|
|