The Perl Journal August 2003
Khazad is a 64-bit block cipher that accepts a 128-bit key. The cipher is a uniform substitution-permutation network (SPN) whose inverse only differs from the forward operation in the key schedule. The overall cipher design follows the Wide Trail Strategy, favors component reuse, and permits a wide variety of implementation tradeoffs.
Block ciphers are important elements in many cryptographic systems. They are most often used to protect the secrecy of information, but are also used for generating pseudorandom numbers and to protect the authenticity of information. Block ciphers are the modern equivalent of the old Caesar cipher. They substitute message blocks of a fixed length with ciphertext blocks of the same length. The substitution is controlled by the key, a secret parameter that is known only to the sender and the receiver. Someone who doesn't know the key can't revert the substitution.
The security of block ciphers is not based on number- theoretic problems such as factoring. Consequently, they don't require large keys: Currently, 80-bit keys are considered enough for commercial applications, and 128-bit keys will protect even the most valuable information against the most determined attacker.
The Wide Trail Strategy was developed in the 1990s by Joan Daemen. It applies to all symmetric-cryptography algorithms, but its biggest success was the AES block cipher Rijndael, which became a standard of the US Federal Administration (FIPS-197). The strategy allows designing secure ciphers in a modular way, by specifying a number of different properties that have to be present in different components. For instance, one of the components has to achieve diffusion, another component has to achieve nonlinearity, and so on. The properties are defined in a very specific, mathematical way.
Khazad is a block cipher that processes its message input in blocks of 64 bits and that accepts a key of 128 bits. It is a finalist cryptographic primitive of the NESSIE project, and has been so named as a cryptic reference to J.R.R. Tolkien's The Lord of the Rings.
Khazad has many similarities to the AES block cipher Rijndael. Both ciphers were designed according to the Wide Trail Strategy, and consist of a number of iterations of a transformation called a "round." Each round is, itself, composed of certain fundamental mathematical operations: ByteSub, which replaces each data byte by a prescribed value; MixColumn, which combines different bytes within the data block and is responsible for information diffusion; and AddRoundKey, which mixes the data with secret information, the so-called round subkey, derived from the key by means of a key-schedule algorithm. The ciphers also apply an extra AddRoundKey before the first round, and omit MixColumn in the last round. The round structure of Khazad is shown in Figure 1.
Rijndael and Khazad have in common that all the components are based on mathematical functions over finite fields, instead of the more usual integer arithmetic modulo 232 or floating-point arithmetic. The use of finite field mathematics allows elegant constructions and proofs of properties that are relevant for the security of the ciphers.
A primary design principle of Khazad is that all algorithm components apart from the key schedule are involutions, that is, mathematical transformations that are their own inverses. This involutional structure is important to obtain efficient implementations. It also makes encryption and decryption equivalent operations except for the key schedule, which means that encryption and decryption are equally secure. (There are ciphers where these operations have different security levels.)
TPJ