#jsDisabledContent { display:none; } My Account | Register | Help
 Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Madryga

Article Id: WHEBN0000719303
Reproduction Date:

 Title: Madryga Author: World Heritage Encyclopedia Language: English Subject: Collection: Broken Block Ciphers Publisher: World Heritage Encyclopedia Publication Date:

### Madryga

In cryptography, Madryga is a block cipher created in 1984 by W. E. Madryga. It was designed to be easy and efficient for implementation in software. Serious weaknesses have since been found in the algorithm, but it was one of the first encryption algorithms to make use of data-dependent rotations, later used in other ciphers, such as RC5 and RC6.

In his proposal, Madryga set forth twelve design objectives that are generally considered to be good goals in the design of a block cipher. DES had already fulfilled nine of them. The three that DES did not fulfill were:

1. Any possible key should produce a strong cipher. (Meaning no weak keys, which DES has.)
2. The length of the key and the text should be adjustable to meet varying security requirements.
3. The algorithm should be efficiently implementable in software on large mainframes, minicomputers, and microcomputers, and in discrete logic. (DES has a large amount of bitwise permutations, which are very inefficient in software implementations.)

## The algorithm

Madryga met the objective of being efficient in software: the only operations it uses are XOR and rotations, both operating only on whole bytes. Madryga has a variable-length key, with no upper limit on its length.

Madryga is specified with eight rounds, but this can be increased to provide more security if need be. In each round, the algorithm passes over the entire plaintext n times, where n is the length of the plaintext in bytes. The algorithm looks at three bytes at a time, so Madryga is a 24-bit block cipher. It XORs a key byte with the rightmost byte, and rotates the other two as one block. The rotation varies with the output of the XOR. Then, the algorithm moves to the right by one byte. So if it were working on bytes 2, 3 and 4, after it finished rotating and XORing them, it would repeat the process on bytes 3, 4 and 5.

The key schedule is very simple. To start with, the entire key is XORed with a random constant of the same length as the key, then rotated to the left by 3 bits. It is rotated again after each iteration of rotation and XOR. The rightmost byte of it is used in each iteration to XOR with the rightmost byte of the data block.

The decryption algorithm is simply the reverse of the encryption algorithm. Due to the nature of the XOR operation, it is reversible.

## Analysis of Madryga

At a glance, Madryga seems less secure than, for example, DES. All of Madryga's operations are linear. DES's S-boxes are its only non-linear component, and flaws in them are what both differential cryptanalysis and linear cryptanalysis seek to exploit. While Madryga's rotations are data-dependent to a small degree, they are still linear.

Perhaps Madryga's fatal flaw is that it does not exhibit the avalanche effect. Its small data block is to blame for this. One byte can only influence the two bytes to its left and the one byte to its right.

Eli Biham has reviewed the algorithm without making a formal analysis. He noticed that "the parity of all the bits of the plaintext and the ciphertext is a constant, depending only on the key. So, if you have one plaintext and its corresponding ciphertext, you can predict the parity of the ciphertext for any plaintext." Here, parity refers to the XOR sum of all the bits.

In 1995, Ken Shirriff found a differential attack on Madryga that requires 5,000 chosen plaintexts. Biryukov and Kushilevitz (1998) published an improved differential attack requiring only 16 chosen-plaintext pairs, and then demonstrated that it could be converted to a ciphertext-only attack using 212 ciphertexts, under reasonable assumptions about the redundancy of the plaintext (for example, ASCII-encoded English language). A ciphertext-only attack is devastating for a modern block cipher; as such, it is probably more prudent to use another algorithm for encrypting sensitive data.

## References

• W. E. Madryga, "A High Performance Encryption Algorithm", Computer Security: A Global Challenge, Elsevier Science Publishers, 1984, pp. 557–570.
• Ken Shirriff, Differential Cryptanalysis of Madryga, unpublished manuscript, October 1995.
• Alex Biryukov, Eyal Kushilevitz: From Differential Cryptoanalysis to Ciphertext-Only Attacks. CRYPTO 1998: pp. 72–88
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.

By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.