Khufu and Khafre
Encyclopedia
In cryptography
, Khufu and Khafre are two block cipher
s designed by Ralph Merkle
in 1989 while working at Xerox
's Palo Alto Research Center. Along with Snefru
, a cryptographic hash function
, the ciphers were named after the Egyptian Pharaoh
s Khufu, Khafre
and Sneferu
.
Under a voluntary scheme, Xerox submitted Khufu and Khafre to the National Security Agency
(NSA) prior to publication. NSA requested that Xerox not publish the algorithms, citing concerns about national security. Xerox, a large government contractor, complied. However, a reviewer of the paper passed a copy to John Gilmore, who made it available via the sci.crypt newsgroup
. It would appear this was against Merkle's wishes. The scheme was subsequently published at the 1990 CRYPTO
conference (Merkle, 1990).
Khufu and Khafre were patented by Xerox; issued on March 26, 1991.
cipher which, unusually, uses key
s of size
512 bits; block ciphers typically have much smaller keys, rarely exceeding 256 bits. Most of the key material is used to construct the cipher's S-boxes. Because the key-setup time is quite time consuming, Khufu is not well suited to situations in which many small messages are handled. It is better suited to bulk encryption of large amounts of data.
Khufu is a Feistel cipher
with 16 rounds by default (other multiples of eight between 8 and 64 are allowed). Each set of eight rounds is termed an octet; a different S-box is used in each octet. In a round, the least significant byte of half of the block is passed into the 8×32-bit S-box. The S-box output is then combined (using XOR) with the other 32-bit half. The left half is rotated to bring a new byte into position, and the halves are swapped. At the start and end of the algorithm, extra key material is XORed with the block (key whitening
). Other than this, all the key is contained in the S-boxes.
There is a differential attack on 16 rounds of Khufu which can recover the secret key. It requires 243 chosen plaintexts and has a 243 time complexity (Gilbert and Chauvaud, 1994). 232 plaintexts and complexity are required to merely distinguish the cipher from random. A boomerang attack
(Wagner, 1999) can be used in an adaptive chosen plaintext / chosen ciphertext scenario with 218 queries and a similar time complexity. Khufu is also susceptible to an impossible differential attack
, which can break up to 18 rounds of the cipher (Biham et al., 1999).
Schneier
and Kelsey (1996) categorise Khafre and Khufu as "even incomplete heterogeneous target-heavy Unbalanced Feistel Networks".
, used as a source of "nothing up my sleeve number
s".) An advantage is that Khafre can encrypt a small amount of data very rapidly — it has good key agility. However, Khafre probably requires a greater number of rounds to achieve a similar level of security as Khufu, making it slower at bulk encryption. Khafre uses a key whose size is a multiple of 64 bits. Because the S-boxes are not key-dependent, Khafre XORs subkeys every eight rounds.
Differential cryptanalysis is effective against Khafre: 16 rounds can be broken using either 1500 chosen plaintexts or 238 known plaintexts. Similarly, 24 rounds can be attacked using 253 chosen plaintexts or 259 known plaintexts.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, Khufu and Khafre are two block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s designed by Ralph Merkle
Ralph Merkle
Ralph C. Merkle is a researcher in public key cryptography, and more recently a researcher and speaker on molecular nanotechnology and cryonics...
in 1989 while working at Xerox
Xerox
Xerox Corporation is an American multinational document management corporation that produced and sells a range of color and black-and-white printers, multifunction systems, photo copiers, digital production printing presses, and related consulting services and supplies...
's Palo Alto Research Center. Along with Snefru
Snefru
Snefru is a cryptographic hash function invented by Ralph Merklein 1990which supports 128-bit and 256-bit output. It was named after the Egyptian Pharaoh Sneferu, continuing the tradition of the Khufu and Khafre block ciphers....
, a cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
, the ciphers were named after the Egyptian Pharaoh
Pharaoh
Pharaoh is a title used in many modern discussions of the ancient Egyptian rulers of all periods. The title originates in the term "pr-aa" which means "great house" and describes the royal palace...
s Khufu, Khafre
Khafra
Khafra — also Khafre — was an Egyptian pharaoh of the Fourth dynasty, who had his capital at Memphis. According to some authors he was the son and successor of Khufu, but it is more commonly accepted that Djedefre was Khufu's successor and Khafra was Djedefre's...
and Sneferu
Sneferu
Sneferu, also spelled as Snephru, Snefru or Snofru , was the founder of the Fourth dynasty of Egypt. Estimates of his reign vary, with for instance The Oxford History of Ancient Egypt suggesting a reign from around 2613 BC to 2589 BC, a reign of 24 years, while Rolf Krauss suggests a 30-year reign...
.
Under a voluntary scheme, Xerox submitted Khufu and Khafre to the National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
(NSA) prior to publication. NSA requested that Xerox not publish the algorithms, citing concerns about national security. Xerox, a large government contractor, complied. However, a reviewer of the paper passed a copy to John Gilmore, who made it available via the sci.crypt newsgroup
Newsgroup
A usenet newsgroup is a repository usually within the Usenet system, for messages posted from many users in different locations. The term may be confusing to some, because it is usually a discussion group. Newsgroups are technically distinct from, but functionally similar to, discussion forums on...
. It would appear this was against Merkle's wishes. The scheme was subsequently published at the 1990 CRYPTO
Crypto
-Cryptography and cryptanalysis:* Cryptography, the practice and study of hiding information* Cryptanalysis, the study of methods for obtaining the meaning of encrypted information* CRYPTO , an annual cryptographical and cryptoanalytic conference...
conference (Merkle, 1990).
Khufu and Khafre were patented by Xerox; issued on March 26, 1991.
Khufu
Khufu is a 64-bit blockBlock size (cryptography)
In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size...
cipher which, unusually, uses key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
s of size
Key size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...
512 bits; block ciphers typically have much smaller keys, rarely exceeding 256 bits. Most of the key material is used to construct the cipher's S-boxes. Because the key-setup time is quite time consuming, Khufu is not well suited to situations in which many small messages are handled. It is better suited to bulk encryption of large amounts of data.
Khufu is a Feistel cipher
Feistel cipher
In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel who did pioneering research while working for IBM ; it is also commonly known as a Feistel network. A large proportion of block...
with 16 rounds by default (other multiples of eight between 8 and 64 are allowed). Each set of eight rounds is termed an octet; a different S-box is used in each octet. In a round, the least significant byte of half of the block is passed into the 8×32-bit S-box. The S-box output is then combined (using XOR) with the other 32-bit half. The left half is rotated to bring a new byte into position, and the halves are swapped. At the start and end of the algorithm, extra key material is XORed with the block (key whitening
Key whitening
In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key before the first round and after the last round of encryption.The first block cipher to use a form of key whitening is...
). Other than this, all the key is contained in the S-boxes.
There is a differential attack on 16 rounds of Khufu which can recover the secret key. It requires 243 chosen plaintexts and has a 243 time complexity (Gilbert and Chauvaud, 1994). 232 plaintexts and complexity are required to merely distinguish the cipher from random. A boomerang attack
Boomerang attack
In cryptography, the boomerang attack is a method for the cryptanalysis of block ciphers based on differential cryptanalysis. The attack was published in 1999 by David Wagner, who used it to break the COCONUT98 cipher....
(Wagner, 1999) can be used in an adaptive chosen plaintext / chosen ciphertext scenario with 218 queries and a similar time complexity. Khufu is also susceptible to an impossible differential attack
Impossible differential cryptanalysis
In cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected probability, impossible differential cryptanalysis exploits...
, which can break up to 18 rounds of the cipher (Biham et al., 1999).
Schneier
Bruce Schneier
Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
and Kelsey (1996) categorise Khafre and Khufu as "even incomplete heterogeneous target-heavy Unbalanced Feistel Networks".
Khafre
Khafre is similar to Khufu, but uses a standard set of S-boxes, and does not compute them from the key. (Rather, they are generated from the RAND tablesA Million Random Digits with 100,000 Normal Deviates
A Million Random Digits with 100,000 Normal Deviates is a 1955 book by the RAND Corporation. The book, consisting primarily of a random number table, was an important 20th century work in the field of statistics and random numbers...
, used as a source of "nothing up my sleeve number
Nothing up my sleeve number
In cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes...
s".) An advantage is that Khafre can encrypt a small amount of data very rapidly — it has good key agility. However, Khafre probably requires a greater number of rounds to achieve a similar level of security as Khufu, making it slower at bulk encryption. Khafre uses a key whose size is a multiple of 64 bits. Because the S-boxes are not key-dependent, Khafre XORs subkeys every eight rounds.
Differential cryptanalysis is effective against Khafre: 16 rounds can be broken using either 1500 chosen plaintexts or 238 known plaintexts. Similarly, 24 rounds can be attacked using 253 chosen plaintexts or 259 known plaintexts.