The block cipher MISTY, developed by Mitsuru Matsui for the Mitsubishi Corporation, was the first cipher to demonstrate a novel method of obtaining a level of provable security against both differential and linear cryptanalysis. A paper explaining these basic principles in the context of the closely related block cipher KASUMI is available on the web.
The description of MISTY given here refers to MISTY1 as described in RFC2994. MISTY is patented, but is available from Mitsubishi for noncommercial use and, with licensing, for commercial use on generous terms.
The following diagram illustrates the first two Feistel rounds within MISTY:
The key material used in MISTY consists of sixteen 16-bit subkeys. They are divided into two groups of eight, designated K0 through K7 and K8 through K15. From one f-function to the next, corresponding subkeys are replaced by the next subkey in sequence within their group of eight subkeys.
Note that prior to the first two Feistel rounds, the two halves of the block are independently subjected to what is a linear operation, but under the nonlinear control of two subkeys. This operation is repeated after each pair of Feistel rounds, and again, corresponding subkeys are replaced by the next subkey in sequence within their group of eight subkeys. Thus, in this operation, one moves through the subkeys at half the speed as one does within the f-functions.
MISTY uses eight Feistel rounds, and after the last pair of Feistel rounds, this novel nonlinearly keyed linear operation is again applied to the halves of the block.
The first eight subkeys in MISTY are obtained by dividing the 128-bit key into eight 16-bit parts. The second group of eight subkeys is obtained by putting the first group of eight subkeys through the basic operation used within the MISTY f-function (which is termed FI): K0 encrypted with K1 yields K8, K1 encrypted with K2 yields K9, and so on, up to K8 encrypted with K0 yielding K15.
This is illustrated by the diagram below:
Note that keys consisting of eight identical 16-bit subblocks may be considered weak; but, of course, any keys belonging to a known small family would be weak against a brute-force search in any case.
Skip to Next Chapter
Table of Contents