The KHAZAD Block Cipher

The Bridge of Khazad-dûm. Painting by Paul Monteagle.

Welcome!

KHAZAD is a legacy-level block cipher designed by Vincent Rijmen and Paulo S. L. M. Barreto. As such, it operates on data blocks of length 64 bits, and uses keys of length 128 bits. It has been submitted as a candidate algorithm for the NESSIE cryptographic primitive evaluation effort, and its tweaked form was selected as finalist.



---

The cipher

KHAZAD is an iterated 64-bit block cipher with 128-bit keys. It comprises 8 rounds; each round consists of eight 8-bit to 8-bit S-box parallel lookups, a linear transformation (multiplication by a constant MDS diffusion matrix) and round key addition.

The S-box and the diffusion matrix were chosen in a way which guarantees that encryption and decryption are the same operation except in the round subkeys.

KHAZAD belongs to the same family of block ciphers as the AES algorithm, RIJNDAEL. It is very similar to the SHARK cipher, the main differences being sketched in the following table:

---

The documentation

The original definition of KHAZAD (dubbed KHAZAD-0) is now obsolete. The current, final form of the cipher was "tweaked" to make it more efficiently implementable in hardware. In this form, KHAZAD has been accepted as NESSIE finalist, and the updated specification can be found here, or locally here.

The tweak does not change the basic structure of KHAZAD; rather, it replaces the S-box, which in the original submission is generated entirely at random (i.e. lacks any internal structure), by a recursive structure: the new 8x8 substitution box is composed of smaller pseudo-randomly generated 4x4 "mini-boxes" (the P-box and the Q-box).

The recursive structure of the "tweaked" S-box:


The P mini-box:

u	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
P(u)	3	F	E	0	5	4	B	C	D	A	9	6	7	8	2	1




The Q mini-box:

u	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
Q(u)	9	E	5	6	A	2	3	C	F	0	4	D	7	B	1	8






---

The security statement

This section is an excerpt from the documentation submitted to NESSIE.

KHAZAD is expected, for all key lengths defined, to behave as good as can be expected from a block cipher with the given block and key lengths (in the sense of being K-secure and hermetic).

This implies among other things, the following.



The most efficient key-recovery attack for KHAZAD is exhaustive key search. Obtaining information from given plaintext-ciphertext pairs about other plaintext-ciphertext pairs cannot be done more efficiently than by determining the key by exhaustive key search. The expected effort of exhaustive key search depends on the bit length of the cipher key and is 2127 applications of KHAZAD.

The rationale for this is that a considerable safety margin is taken with respect to all known attacks. We do however realise that it is impossible to make non-speculative statements on things unknown.

In spite of any analysis, doubts might remain regarding the presence of trapdoors deliberately introduced in the algorithm. That is why the NESSIE effort asked for the designers' declaration on the contrary. Therefore we, the designers of KHAZAD, do hereby declare that there are no hidden weaknesses inserted by us in the KHAZAD primitive.



---

The availability

KHAZAD is not (and will never be) patented. It may be used free of charge for any purpose.



---

The reference implementation and test vectors

Test vectors

64-bit C implementation

32-bit C implementation

Java implementation


These implementations are in the public domain. But before you go and use it, please read the following disclaimer:


THIS SOFTWARE IS PROVIDED BY THE AUTHORS ''AS IS'' AND ANY EXPRESS
OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.



---

The name

Thus he brought me back at last to the secret ways of Khazad-dûm...
KHAZAD is named after Khazad-dûm, the "Mansion of the Khazâd," which in the tongue of the Dwarves is the name of the great realm and city of Dwarrowdelf, of the haunted mithril mines in Moria, the Black Chasm. But all this should be quite obvious -- unless you haven't read J.R.R. Tolkien's The Lord of the Rings, of course .


Gandalf and the Balrog on the Bridge of Khazad-dûm. Painting by John Howe.


---

The links

The Pairing-Based Crypto Lounge The Hashing Function Lounge

The ANUBIS Block Cipher The WHIRLPOOL Hashing Function

Paulo's page Vincent's (old) page

---

Visits since 2001.09.23:

Last update: 2002.09.18
Copyright © 2001, 2002 by Paulo S. L. M. Barreto.  All rights reserved.