Lars R. Knudsen and Fauzan Mirza
\Title
Deletion Cryptanalysis
Abstract
In this paper the deletion cryptanalysis is considered. The method
deletes certain parts of a cryptosystem before cryptanalysis. All
cryptosystems are susceptible to this attack. It is shown why the
onetime pad and the DES are very weak under this attack.
Keywords. Craptology.
1 Introduction
In this paper, the deletion cryptanalysis of secretkey
systems is considered. By enabling an attacker to selectively delete
crucial operators or functions in a particular cryptosystem, it is
usually possible to break the system much more efficiently than usual.
Even cryptosystems which obtain what Shannon called perfect
secrecy are trivially broken with this new attack.
Two examples of deletion cryptanalysis as applied to the onetime pad
and the DES block cipher are given.
2 The Onetime Pad minus 1 XOR
Onetime pad encryption is described by
where the ciphertext C, plaintext P and key K are the same
length.
A deletion attack completely demolishes the security of the onetime
pad. By deleting an XOR from the cipher, notice that
The
attacker can easily read the plaintext, without knowledge of any part
of the original key. To protect against this devastating attack, one
should always ensure that the key is in fact XORed to the plaintext.
Alternatively, the deletion of the key could be done by the sender
himself, in which case an attacker can never retrieve the secret key.
3 The DES minus 3 XORs
DES is a 16round iterated cipher, based on the Feistel network. Let
the plaintext be denoted by P = (L_{0}, R_{0}), the ciphertext by C = (R_{16}, L_{16}), and the round subkeys by K_{i}, for i = 1..16. The round function is
L_{i+1} = R_{i}, R_{i+1} = L_{i}ÅP(S(E(R_{i}) ÅK_{i})), 

where P, E are bitwise
permutations and S is composed of eight nonlinear Sboxes S_{i}
operating in parallel. The differential attack by BihamShamir breaks
the DES using a 13round characteristic with probability 2^{47} and
2^{47} chosen plaintexts. If in the rounds 3, 5, and 7, the first
XORs in the above round description are removed, the probability of
the characteristic increases to 2^{23.5} and the differential
attack requires only about 2^{24} chosen plaintexts.
4 Conclusion
This paper has demonstrated the effectiveness of deletion cryptanalysis
when applied to two wellknown cryptosystems. It is shown that deletion
cryptanalysis can sometimes break systems as efficiently as the
chosenkey attacks (where the attacker
can choose the key to be used and, optionally, any plaintexts that
they would like to be encrypted).
We expect that many publickey systems can also be broken by selective
deletion of crucial operations or functions and feel that it is
our duty to warn the craptologic community of the threat of deletion
attacks.
File translated from T_{E}X by T_{T}H, version 2.00.
On 16 Mar 1999, 15:34.