Lars R. Knudsen and Fauzan Mirza
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
one-time pad and the DES are very weak under this attack.
In this paper, the deletion cryptanalysis of secret-key
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 one-time pad
and the DES block cipher are given.
2 The One-time Pad minus 1 XOR
One-time pad encryption is described by
where the ciphertext C, plaintext P and key K are the same
A deletion attack completely demolishes the security of the one-time
pad. By deleting an XOR from the cipher, notice that
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 16-round iterated cipher, based on the Feistel network. Let
the plaintext be denoted by P = (L0, R0), the ciphertext by C = (R16, L16), and the round subkeys by Ki, for i = 1..16. The round function is
where P, E are bitwise
permutations and S is composed of eight nonlinear S-boxes Si
operating in parallel. The differential attack by Biham-Shamir breaks
the DES using a 13-round characteristic with probability 2-47 and
247 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 224 chosen plaintexts.
Li+1 = Ri, Ri+1 = LiÅP(S(E(Ri) ÅKi)), |
This paper has demonstrated the effectiveness of deletion cryptanalysis
when applied to two well-known cryptosystems. It is shown that deletion
cryptanalysis can sometimes break systems as efficiently as the
chosen-key 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 public-key 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
File translated from TEX by TTH, version 2.00.
On 16 Mar 1999, 15:34.