Lai–Massey scheme

The Lai–Massey scheme is a cryptographic structure used in the design of block ciphers. 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, using a round function and a half-round function. The round function is a function which takes two inputs, a sub-key and a Data block, and which returns one output of equal length to the Data block. The half-round function takes two inputs and transforms them into two outputs. For any given round, the input is split into two halves, left and right.

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