Khufu and Khafre

Khufu and Khafre

In cryptography, Khufu and Khafre are two block ciphers 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 Pharaohs 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 [http://groups.google.com/groups?selm=7981%40hoptoad.uucp] ; [http://groups.google.com/groups?selm=497%40lexicon.com] . It would appear this was against Merkle's wishes [http://groups.google.com/groups?selm=1638%40arisia.Xerox.COM] . The scheme was subsequently published at the 1990 CRYPTO conference (Merkle, 1990).

Khufu and Khafre are patented by Xerox; US patent|5003597, issued on 26th March, 1991.

Khufu

Infobox block cipher
name = Khufu


caption =
designers = Ralph Merkle
publish date = 1989
derived from =
derived to =
related to = Khafre
certification =
key size = 512 bits
block size = 64 bits
structure = Feistel network
rounds = 16
cryptanalysis = Gilbert and Chauvaud's differential attack
Khufu is a 64-bit block cipher which, unusually, uses keys 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".

Khafre

Infobox block cipher
name = Khafre


caption =
designers = Ralph Merkle
publish date = 1989
derived from =
derived to =
related to = Khufu
certification =
key size = 512 bits
block size = 64 bits
structure = Feistel network
rounds = 16 or more
cryptanalysis = Biham and Shamir's differential attack is fasterthan brute force even for 24 rounds
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 tables, used as a source of "nothing up my sleeve numbers".) 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.

References

* cite conference
author = R.C. Merkle
title = Fast Software Encryption Functions
booktitle = Advances in Cryptology—CRYPTO '90
pages = pp.476–501
publisher = Springer-Verlag
date = August 1990
location = Santa Barbara, California
url = http://citeseer.ist.psu.edu/ralph90fast.html
format = PDF/PostScript
accessdate = 2007-08-23

* cite conference
author = Eli Biham, Adi Shamir
title = Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer
booktitle = Advances in Cryptology—CRYPTO '91
pages = pp.156–171
publisher = Springer-Verlag
date = August 1991
location = Santa Barbara, California
url = http://citeseer.ist.psu.edu/163342.html
format = PDF/PostScript
accessdate = 2007-08-23

* cite conference
author = Henri Gilbert, Pascal Chauvaud
title = A Chosen Plaintext Attack of the 16-round Khufu Cryptosystem
booktitle = Advances in Cryptology—CRYPTO '94
pages = pp.359–368
publisher = Springer-Verlag
date = August 1994
location = Santa Barbara, California

* cite conference
author = Bruce Schneier, John Kelsey
title = Unbalanced Feistel Networks and Block Cipher Design
booktitle = 3rd International Workshop on Fast Software Encryption (FSE '96)
pages = pp.121–144
publisher = Springer-Verlag
date = February 1996
location = Cambridge
url = http://www.schneier.com/paper-unbalanced-feistel.html
format = PDF/PostScript
accessdate = 2007-08-23

* cite conference
author = Eli Biham, Alex Biryukov, Adi Shamir
title = Miss in the Middle Attacks on IDEA, Khufu and Khafre
booktitle = 6th International Workshop on Fast Software Encryption (FSE '99)
pages = pp.124–138
publisher = Springer-Verlag
date = March 1999
location = Rome
url = http://www.wisdom.weizmann.ac.il/~albi/fse99idea.ps.gz
format = gzipped PostScript
accessdate = 2007-02-14

* cite conference
author = David Wagner
title = The Boomerang Attack
booktitle = 6th International Workshop on Fast Software Encryption (FSE '99)
pages = pp.156–170
publisher = Springer-Verlag
date = March 1999
location = Rome
url = http://citeseer.ist.psu.edu/wagner99boomerang.html
format = PDF/PostScript
accessdate = 2007-02-05


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Khufu Et Khafre — La pyramide de Khéops (Khufu) Résumé …   Wikipédia en Français

  • Khufu et khafre — La pyramide de Khéops (Khufu) Résumé …   Wikipédia en Français

  • Khufu et Khafre — La pyramide de Khéops (Khufu) Résumé Concepteur(s) Ralph Merkle Première publication 1990 Déri …   Wikipédia en Français

  • Khafre — Khufu et Khafre Khufu et Khafre La pyramide de Khéops (Khufu) Résumé …   Wikipédia en Français

  • Khufu — et Khafre Khufu et Khafre La pyramide de Khéops (Khufu) Résumé …   Wikipédia en Français

  • Khufu/Khafre — Khufu et Khafre Khufu et Khafre La pyramide de Khéops (Khufu) Résumé …   Wikipédia en Français

  • Khufu — This article is about a Pharaoh. For a cipher, see Khufu and Khafre. Khufu Cheops, Suphis Statue of Khufu in the Cairo Museum …   Wikipedia

  • Khufu — /kooh fooh/, n. Cheops. * * * ▪ king of Egypt Greek  Cheops  flourished 25th century BCE       second king of the 4th dynasty (Egypt, ancient) (c. 2575–c. 2465 BCE) of Egypt and builder of the Great Pyramid at Al Jīzah (Jīzah, Al ) (see Pyramids… …   Universalium

  • Khafre — /kaf ray, kahf /, n. (Chephren) fl. late 26th century B.C., Egyptian king of the fourth dynasty (son of Cheops): builder of second pyramid at El Giza. Also, Kafre. * * * ▪ king of Egypt also spelled  Khafra , Greek  Chephren  flourished 26th… …   Universalium

  • Khufu ship — The reconstructed solar barge of Khufu …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”