LEX (cipher)

LEX (LEX-128, LEX-192, LEX-256) is a stream cipher developed by Alex Biryukov . Cipher participated in the eSTREAM contest and reached the 3 stages, but, nevertheless, was not selected for the final portfolio ^[1] .

Introduction

The name of the LEX cipher comes from the term English. Leak EXtraction . A certain block cipher is taken as the basis and the idea is to output parts of the internal state of the block cipher at certain rounds to the output gamut for in-line encryption (possibly after applying some filtering function). This method can be applied to any block cipher, but in each case, a careful study of what parts of the internal state to extract and at what frequency is necessary. This mainly depends on the round function of the block cipher and the round key generation algorithm it uses.

Description

Fig. 1 Initialization and generation of output gamma for the 128-bit version of the cipher

Fig. 2 Bytes extracted from the state matrix on odd (odd) and even (even) rounds (highlighted in gray)

The LEX cipher in the original version uses AES in Output Feedback (OFB) mode : in each round, 4 specific bytes are extracted from the state matrix. Versions of LEX-128, LEX-192 and LEX-256 differ in the length of the key used in encryption: 128, 192 and 256 bits, respectively. The differences with AES are that the cryptanalyst never sees the whole 128-bit ciphertext , but only portions of the intermediate state.

First, some initialization vector (IV) is encrypted by AES with key K to obtain S = AES _k (IV). Then S is repeatedly encrypted repeatedly in OFB mode and at this time, 32 bits are extracted from the state matrix on each round (see Fig. 1). After 500 encryption, another key K is selected and work continues.

A key part of the cipher is deciding which bytes to retrieve from the intermediate state and at what frequency. Cipher author suggests extracting bytes $B_{1}=(b_{0,0},b_{0,2},b_{2,0},b_{2,2})$ ${\ displaystyle B_ {1} = (b_ {0,0}, b_ {0,2}, b_ {2,0}, b_ {2,2})}$ in every odd round and bytes $B_{2}=(b_{0,1},b_{0,3},b_{2,1},b_{2,3})$ {\ displaystyle B_ {2} = (b_ {0,1}, b_ {0,3}, b_ {2,1}, b_ {2,3})} in each even (see Fig. 2). The byte order is not important for security, but is important for encryption speed. The above byte order allows you to extract them from the current state in just 4 steps using the formula:

{\begin{aligned}out32&=\left(\left(t_{0}\&0xFF00FF\right)<<8\right)\oplus \left(t_{2}\&0xFF00FF\right),\\\end{aligned}}

{\ displaystyle {\ begin {aligned} out32 & = \ left (\ left (t_ {0} \ & 0xFF00FF \ right) << 8 \ right) \ oplus \ left (t_ {2} \ & 0xFF00FF \ right), \\\ end {aligned}}}

where t ₀ and t ₂ respectively are the zero and second rows in the matrix of the intermediate state.

The choice of these byte positions is motivated by the following: both sets $B_{1}$ ${\ displaystyle B_ {1}}$ and $B_{2}$ ${\ displaystyle B_ {2}}$ are invariant with respect to the ShiftRows operation used in AES (the first row is not shifted, the third is shifted by two positions). Using different sets on even and odd rounds ensures that the input and output bytes on two adjacent rounds will not be connected only by the SubBytes and MixColumns operations . Thus, the attacker will be forced to analyze two consecutive rounds of encryption. Two rounds provide complete dissipation in the statistics of the cipher, which limits the attacker in using the principle of divide and conquer .

At the last stage, modulo 2 addition of the output gamma with clear text occurs.

LEX Cryptanalysis

Output Sequence Period

For stream ciphers, the most interesting is the question of the period of the obtained sequence in the gamma . Since LEX uses AES, the output sequence (gamma) will loop when the sequence of ciphertexts generated by AES is looped. If AES generated a sequence indistinguishable from random for a single key, then the length of the sequence would be $O(2^{128})$ ${\ displaystyle O (2 ^ {128})}$ .

If the output stream is a random permutation of a 128-bit block, it can be recognized as nonrandom after detecting the absence of 128-bit collisions in a stream of 2 ⁶⁴ output blocks. In the case of LEX, since only parts of the AES internal state are used in each round, the mapping of the internal state to the output is not one-to-one and, therefore, such collisions will occur.

Time-Memory Attacks

For resistance of the stream cipher to attacks based on a time-memory compromise, the following conditions must be met $|K|=|IV|=|State|/2$ ${\ displaystyle | K | = | IV | = | State | / 2}$ . This ensures that the complexity of the attack will be comparable to the complexity of exhaustive search. The initializing vector may be open, but then it must be completely random in order to avoid the tradeoff-resynchronization attack ^[2] . In the case of LEX $|K|=|IV|=|Block|=128$ ${\ displaystyle | K | = | IV | = | Block | = 128}$ bit, where Block is the state of the plaintext block during encryption. The internal state corresponds to a pair $(K,IV)$ ${\ displaystyle (K, IV)}$ at the beginning and $(Block,Key)$ ${\ displaystyle (Block, Key)}$ during encryption. In this way, $|K|+|IV|=|K|+|S|=256$ ${\ displaystyle | K | + | IV | = | K | + | S | = 256}$ bit, which is enough to reduce the possibility of an attack on naught.

Algebraic attacks

This type of attack has not yet been fully studied and can be very powerful. The possibility of its application to LEX should be carefully studied. It is expected that replacing the key after 500 encryption will avoid such attacks. By targeting a certain key, a cryptanalyst can get only 500 blocks of the output gamut; and after replacing the key, the system of equations compiled by him will become obsolete.

Performance

For a work cycle, AES gives 128 bits of ciphertext for all key options (128, 192, 256 bits), while LEX built on AES will give 32 * N _r (where N _r is the number of rounds for a given key length) bits of ciphertext. Thus, it is expected that LEX will outperform AES by approximately 2.5, 3 and 3.5 times, respectively, for keys in 128, 192 and 256 bits. In addition, the advantage of the cipher is that ready-made implementations of the used block cipher can be used, which reduces development time and money.

Notes

↑ CiteSeerX - Cryptanalysis of the Stream Cipher LEX
↑ J. Hong and P. Sarkar, "Rediscovery of time memory tradeoffs," 2005. http://eprint.iacr.org/2005/090

Links

[1] A New 128-bit Key Stream Cipher LEX
[2] A New Attack on the LEX Stream Cipher
[3] Algebraic Cryptanalysis of a Small-Scale Version of Stream Cipher LEX

[1] CiteSeerX - Cryptanalysis of the Stream Cipher LEX

[2] J. Hong and P. Sarkar, "Rediscovery of time memory tradeoffs," 2005. http://eprint.iacr.org/2005/090