Madryga
Encyclopedia
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:
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.
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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, Madryga is a block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
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
RC5
In cryptography, RC5 is a block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, RC stands for "Rivest Cipher", or alternatively, "Ron's Code"...
and RC6
RC6
In cryptography, RC6 is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard competition. The algorithm was one of the five finalists, and was also submitted to the...
.
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
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
had already fulfilled nine of them. The three that DES did not fulfill were:
- Any possible key should produce a strong cipher. (Meaning no weak keyWeak keyIn cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, if one generates a random key to encrypt a message, weak keys are very...
s, which DES has.) - The length of the key and the text should be adjustable to meet varying security requirements.
- The algorithm should be efficiently implementable in software on large mainframesMainframe computerMainframes are powerful computers used primarily by corporate and governmental organizations for critical applications, bulk data processing such as census, industry and consumer statistics, enterprise resource planning, and financial transaction processing.The term originally referred to the...
, minicomputerMinicomputerA minicomputer is a class of multi-user computers that lies in the middle range of the computing spectrum, in between the largest multi-user systems and the smallest single-user systems...
s, and microcomputerMicrocomputerA microcomputer is a computer with a microprocessor as its central processing unit. They are physically small compared to mainframe and minicomputers...
s, and in discrete logicLogicIn philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
. (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 cryptanalysisDifferential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
and linear cryptanalysis
Linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers...
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
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
. 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
Eli Biham
Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. Starting from October 2008, Biham is the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate...
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
Alex Biryukov
Alex Biryukov is a cryptographer, currently an assistant professor at the University of Luxembourg. His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed impossible differential cryptanalysis together...
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
Ciphertext-only attack
In cryptography, a ciphertext-only attack or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts....
using 212 ciphertexts, under reasonable assumptions about the redundancy of the plaintext (for example, ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
-encoded English language
English language
English is a West Germanic language that arose in the Anglo-Saxon kingdoms of England and spread into what was to become south-east Scotland under the influence of the Anglian medieval kingdom of Northumbria...
). 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.