Lars R. Knudsen
Block ciphers - Analysis, Design and Applications.
DAIMI PB--485, Aarhus University, Denmark, 1994.
Abstract.
In this thesis we study cryptanalysis, applications and design
of secret key block ciphers. In particular, the important class of
Feistel ciphers is studied,
which has a number of rounds, where in each round
one applies a cryptographically weak function.
Applications
The main application of block ciphers is that of encryption. We study
the available modes of operation for encryption, introduce a new taxonomy
for attacks on block ciphers and derive a new theoretical upper bound for
attacks on block ciphers.
Also another important application of block ciphers is studied; as building
blocks for cryptographic hash functions.
Finally we examine how to use block ciphers as building blocks in the design of
digital signature schemes. In particular we analyze
Merkle's proposed scheme and show that under
suitable and reasonable conditions, Merkle's scheme is secure and practical.
Cryptanalysis
We study the most important known attacks on block ciphers, linear
cryptanalysis and differential cryptanalysis and introduce a new attack
based on simple relations.
Differential cryptanalysis makes use of so-called differentials
(A,B),
i.e. a pair of plaintexts with difference A, which after a certain number of
rounds result in a difference B with a non-negligible probability. This fact
can be used to derive (parts of) the secret key. Ideas of how to find
the best such differentials are given.
Also it is shown that higher order differentials,
where more than two plaintexts are considered at a time, and partial
differentials, where only a part of (A,B) can be predicted, both have
useful applications.
The above attacks and our new methods of attacks on block ciphers, is applied
to the specific block ciphers, DES, LOKI'91, s^2-DES, xDES^1 and xDES^2.
Attacks on hash functions based on block ciphers are studied and new
attacks on a large class of hash functions based on a block cipher, including
three specific proposed schemes, are given. Also a fourth scheme, the AR Hash
function, belonging to another class of hash functions based on block ciphers
is studied. The scheme
is faster than the known standard ones and was used in practice by German banks.
It is shown that the scheme is completely insecure.
Design
We discuss principles for the design of secure block ciphers. For both
linear and differential cryptanalysis we establish lower bounds on the
complexities of success of attacks. It is furthermore shown that there exist
functions, which can be used to construct block ciphers provable secure
against both linear and differential attacks, the two most important attacks
known to date.
Furthermore we define so-called strong key schedules.
A block cipher with
a strong key schedule is shown to be secure against attacks based on simple
relations and the improved immunity to other attacks is discussed. Also we give
a simple design of a strong key schedule.
A well-known and wide-spread way of improving the security of a block cipher is
by means of multiple encryption, i.e. where a plaintext block is processed
several times using the same (component) block cipher, but with different keys.
We study the methods of multiple encryption and give a new proposal of a scheme,
which is provable as secure as the component block cipher using a minimum number
of component keys.
Some of the work in this thesis has been written as separate articles.