Lai–Massey scheme

The Lai–Massey scheme is a cryptographic structure used in the design of block ciphers, an alternative to the Feistel network for converting a non-invertible keyed round function to an invertible keyed cipher. It is used in IDEA and IDEA NXT. The scheme was originally introduced by Xuejia Lai with the assistance of James L. Massey, hence the scheme's name, Lai-Massey.

Design

The Lai-Massey Scheme is similar to a Feistel network in design, but in addition to using a using a non-invertible round function whose input and output is half the data block size, each round uses a full-width invertible half-round function. Either, or preferably both of the functions may take a key input as well.

Initially, the inputs are passed through the half-round function. In each round, the difference between the inputs is passed to the round function along with a sub-key, and the result from the round function is then added to each input. The inputs are then passed through the half-round function. This is then repeated a fixed number of times, and the final output is the encrypted data. Due to its design, it has an advantage over a Substitution-permutation network since the round-function does not need to be inverted - just the half-round - enabling it to be more easily inverted, and enabling the round-function to be arbitrarily complex. The encryption and decryption processes are fairly similar, decryption instead requiring a reversal of the key schedule, an inverted half-round function, and that the round function's output be subtracted instead of added.

Construction details

Let $\mathrm {F}$ be the round function, and $\mathrm {H}$ a half-round function, and let $K_{0},K_{1},\ldots ,K_{n}$ be the sub-keys for the rounds $0,1,\ldots ,n$ respectively.

Then the basic operation is as follows:

Split the plaintext block into two equal pieces, ($L_{0}$, $R_{0}$).

For each round $i=0,1,\dots ,n$, compute

$(L_{i+1}',R_{i+1}')=\mathrm {H} (L_{i}'+T_{i},R_{i}'+T_{i}),$

where $T_{i}=\mathrm {F} (L_{i}'-R_{i}',K_{i})$, and $(L_{0}',R_{0}')=\mathrm {H} (L_{0},R_{0})$.

Then the ciphertext is $(L_{n+1},R_{n+1})=(L_{n+1}',R_{n+1}')$.

Decryption of a ciphertext $(L_{n+1},R_{n+1})$ is accomplished by computing for $i=n,n-1,\ldots ,0$

$(L_{i}',R_{i}')=\mathrm {H} ^{-1}(L_{i+1}'-T_{i},R_{i+1}'-T_{i}),$

where $T_{i}=\mathrm {F} (L_{i+1}'-R_{i+1}',K_{i})$, and $(L_{n+1}',R_{n+1}')=\mathrm {H} ^{-1}(L_{n+1},R_{n+1})$.

Then $(L_{0},R_{0})=(L_{0}',R_{0}')$ is the plaintext again.

The Lai–Massey scheme offers security properties similar to those of the Feistel structure. It also shares its advantage over a substitution–permutation network that the round function $\mathrm {F}$ does not have to be invertible.

The half-round function is required to prevent a trivial distinguishing attack ($L_{0}-R_{0}=L_{n+1}-R_{n+1}$). It commonly applies an orthomorphism $\sigma$ on the left hand side, that is,

$\mathrm {H} (L,R)=(\sigma (L),R),$

where both $\sigma$ and $x\mapsto \sigma (x)-x$ are permutations (in the mathematical sense, that is, a bijection – not a permutation box). Since there are no orthomorphisms for bit blocks (groups of size $2^{n}$), "almost orthomorphisms" are used instead.

$\mathrm {H}$ may depend on the key. If it doesn't, the last application can be omitted, since its inverse is known anyway. The last application is commonly called "round $n.5$" for a cipher that otherwise has $n$ rounds.

Literature

• X. Lai. On the design and security of block ciphers. ETH Series in Information Processing, vol. 1, Hartung-Gorre, Konstanz, 1992
• X. Lai, J. L. Massey. A proposal for a new block encryption standard. Advances in Cryptology EUROCRYPT'90, Aarhus, Denmark, LNCS 473, p. 389–404, Springer, 1991
• Serge Vaudenay: A Classical Introduction to Cryptography, p. 33