Madryga

Madryga is a algorithm of Chiffrement per block designed in 1984 by W.E. Madryga. Intended for a software implementation effective and simple to implement, the algorithm suffers however from important weaknesses. It however posed the algorithmic bases and mathematics concerning rotations dependant on the data. Those will be included in other codings like RC5 and RC6.

In its proposal, Madryga proposes 12 objectives which must be considered at the time of the realization of a good coding per block. OF the filled 9 of them. The 3 remaining criteria were:

any key must produce a robust coding (IE. no the weak key )
the length of the key and text must be adjustable according to desired safety
the algorithm must be able to be implemented easily on the computers and the discrete logic (OF uses operations on the bits as the permutations which are very ineffective in a software implementation).

Operation

Madryga filled its objectives of effectiveness in a software implementation: the only operations used are XOR and rotations. Both work on Octet S. Madryga has a key of variable, unbounded size higher.

The specification of Madryga envisages eight turns but this number can be incremented for more safety so necessary. It uses a block of 24 bits and proceeds to a XOR between a byte of the key and the byte of weak weight of the block. The two other bytes of the block undergo a rotation. This one depends on the exit of the XOR. Then, the algorithm carries out a rotation towards the line of a byte. Of this way if Madryga works on bytes 2,3 and 4, it would deal with bytes 3,4 and 5 after having carried out rotations and the XOR.

The Key schedule is very simple. A XOR between the key and a random constant of the same size are carried out. A rotation towards the left of 3 bits is applied. After each turn, this rotation on the key/constant result is applied again. The intermediate key of each turn is obtained thanks to the weak byte of weight of this combination. Coding is carried out thus via a XOR between the weak byte of weight of the block and the weak byte of weight of the circular register containing the key.

The deciphering consists simply of an opposite use of the operations. This is made possible thanks to the properties of inversibility of the XOR.

Cryptanalyse

At first sight, Madryga seems weaker than DES. All the operations of Madryga are linear. Uses at least S-Box are, component non-linear in coding which were put at evil by the linear Cryptanalyse and differential. In spite of the presence of rotations which depend partly on the data, Madryga is always linear.

The biggest problem of Madryga is the absence of an avalanche effect (a modification in entry will not influence all the bits at the exit). This defect is caused by an insufficient size of block.

Eli Biham carried out an abstract analysis of the algorithm. He noticed that the “parity of all the bits of the clear text and the quantified text is a constant which depends only on the key. In this way, being given a plaintext, you can establish the parity of the quantified text”. The parity corresponds here to a XOR between all the bits of a sequence.,

In 1995, Ken Shirrif presents a differential attack which requires 5 000 selected clear texts. Biryukov and Kushilevitz publish in 1998 an improved differential attack which requires only 16 selected clear texts. Their demonstration goes further and shows that the attack can be converted between an attack by text quantified with 2¹² quantified texts, under favorable assumptions (redundancies, for example of the French text). This type of attack destroys Madryga definitively.

External bonds

Attack of Biryukov and Kushilevitz

References

Alex Biryukov, Eyal Kushilevitz: From Differential Cryptoanalysis to Ciphertext-Only Attacks. CRYPTO 1998:72 - 88
W.E. Madryga, “has High Performance Encryption Algorithm”, Computer Security: With Total Challenge , Elsevier Publishers Science, 1984, pp. 557-570.
Ken Shirriff, Differential Cryptanalysis off Madryga, unpublished manuscript, October 1995.

Random links: