A Chosen Plaintext Attack of the 16-round Khufu Cryptosystem

In 1990, Merkle proposed two fast software encryption functions, Khafre and Khufu, as possible replacements for DES [1]. In 1991, Biham and Shamir applied their differential cryptanalysis technique to Khafre [2], and obtained an efficient attack of the 16-round version and some bounds on the 24-round version. However, these attacks take advantage of the fact that the S-boxes used for Khafre are public; they cannot be applied to Khufu, which uses secret S-boxes, and no attack of Khufu has been proposed so far. In this paper, we present a chosen plaintext attack of the 16-round version of Khufu, which is based on differential properties of this algorithm. The derivation of first information concerning the secret key requires about 231 chosen plaintexts and 231 operations. Our estimate of the resources required for breaking the entire scheme is about 243 chosen plaintexts and about 243 operations.