Introduction

With the ongoing AES competition, it was decided to look at 4-strand Luby-Rackoff schemes because of difficulties with 64-bit arithmetic/logic functions in 32-bit architectures.   This happens to coincide with several AES entries using 4-strand Feistel schemes.   In the light of some of the following analysis, we can see why certain design choices were made.

Originally, this study aimed at determining the minimal number of hashes required for 4-strand Luby-Rackoff structures.   The focus was on the degree of avalanche between inputs and outputs for both encryption and decryption.   In Luby-Rackoff schemes we may assume that each hash function has an avalanche depth of at least 1 and probably 2 or 3.

Also, the integrity of the structure is examined to see if any of the internal blocks can be analysed, thus making the overall analysis easier.

Standard 2-Strand Luby-Rackoff configuration (Figs. 1 and 2)

In Fig. 1, note that H_B occurs on all paths though the system and is exposed to differential analysis by bit-flipping R and looking at L'.   H_C can be examined using the known input and calculating the output differentials.   The minimal path thought the hash stages is highlighted in bold type.

Similarly, in the reverse direction (decryption) H_A can be analysed.

After adding a fourth stage to the 2-strand scheme (Fig. 2), some hash functions become difficult to examine - either in a static mode or differentially.   With H_B and H_C at least 2 hash functions are involved in each input/output pair of readings.   However, the outer two hash functions are still susceptible as in the 3-stage scheme.

Note: There is encryption/decryption symmetry with these 2-strand configurations - something difficult to achieve when there are 3 or more strands.

4-Strand Luby-Rackoff configurations (Fig.3 - single hash output)

Seven stages are required before there is an avalanche path through the network from any input strand to any output strand (in the forward or encryption direction).   As with the 2-strand, 3-stage scheme, the centre stage (H_D) and the latter 3 stages can be easily interrogated.

However, when this is inspected in the reverse direction, we discover that there are a number of avalanche paths that are missing.  In order to get full reverse avalanche, a minimum of 13 (see Fig. 4) stages are required.   This strange result occurs when:
    (a) the number of strands is > 2 and
    (b) when the output of the hash modifies only one strand.

If this scheme is visualised in 3-D with the 4 strands in a square, then the avalanche flow becomes a square spiral.   In the reverse direction, the spiral appears to be going the wrong way as the stages are performed in reverse order.   This causes the avalanche to bypass pairs of stages.   E.G.   P' to R passes through H_E and H_B, ignoring stages H_D and H_C.

Note that H_M is crucial for the reverse avalanche path P' to P (H_M, H_J, H_C, H_D).   Also note the inefficiency - 2 out of 3 hashes are not used.   Compare this with the MARS and CAST-256 AES entries.

In Cast-256, the first 24 stages are used for the forward avalanche (6 forward quad-rounds in CAST-256 terminology) and the the following 24 are used for the reverse avalanche ( 6 reverse quad-rounds).   This means that in the forward mode, the avalanche passes through between 18 and 24 stages, whereas in the reverse mode it passes through between 4 and 8 stages.

MARS uses a type-3 Feistel scheme where one strand is used to modify the other three.   It says '... this construct provides much better diffusion properties with only a slightly added cost.'   To complicate matters, not only are there are forward and backward stages but also there are two types of each: a mixing and a keyed transformation.   The mixing stages accentuate rapid mixing and key avalanche to frustrate chosen-plaintext and differential attacks.   The transformation or cryptographic core stages are designed frustrate chosen-ciphertext attacks.

4-Strand Luby-Rackoff configurations (Fig. 5 - multiple hash outputs)

It is possible to combine the hash outputs with the all strands except the one being hashed.   With 5 stages, there is an avalanche path from all inputs to all outputs and vice versa for the reverse case.   However, H_D is exposed to analysis and changes to S are reflected in the same differential change to Q' and R'.

Some of the objections to the previous scheme can be overcome by increasing the number of stages from 5 to 6.   However, by comparing the differentials from R' and S', the differential output of H_D can be determined.

4-Strand Luby-Rackoff configurations (Fig. 7 - multiple hash inputs and outputs)

The two input strands must be hashed together in a non-trivial way, otherwise cancellation attacks are possible.   Also, if you examine the equations for the 4 strands, the contributions of the hash functions can cancel out - making way for a known plaintext attack.   Twofish and RC6 don't suffer from this problem because the two outputs are substantially different, making cancellation impossible.

Back to home page _{AES,block cipher,CAST-256,cipher,crypto,cryptography, czczcz,cipher design,encryption,Feistel,Luby-Rackoff,MARS, RC6,Twofish}