Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (October 2013) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Lai–Massey scheme" – news · newspapers · books · scholar · JSTOR (July 2021) (Learn how and when to remove this message) (Learn how and when to remove this message)

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 ${\displaystyle \mathrm {F} }$ be the round function, and ${\displaystyle \mathrm {H} }$ a half-round function, and let ${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$ be the sub-keys for the rounds ${\displaystyle 0,1,\ldots ,n}$ respectively.

Then the basic operation is as follows:

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

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

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

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

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

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

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

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

Then ${\displaystyle (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 ${\displaystyle \mathrm {F} }$ does not have to be invertible.

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

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

where both ${\displaystyle \sigma }$ and ${\displaystyle 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 ${\displaystyle 2^{n}}$), "almost orthomorphisms" are used instead.

${\displaystyle \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 ${\displaystyle n.5}$" for a cipher that otherwise has ${\displaystyle 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

References

1. Aaram Yun, Je Hong Park, Jooyoung Lee: Lai-Massey Scheme and Quasi-Feistel Networks. IACR Cryptology.
2. Serge Vaudenay: On the Lai-Massey Scheme Archived 2022-07-12 at the Wayback Machine. ASIACRYPT'99.
3. X. Lai. On the design and security of block ciphers. ETH Series in Information Processing, vol. 1, Hartung-Gorre, Konstanz, 1992

• Block ciphers