cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, Madryga is a

block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...

published 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 cryptography, RC6 (Rivest cipher 6) 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 (AES) competition. ...

. 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 Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include: People * Des Buckingham, English football manager * Des Corcoran, (1928–2004), Australian politician * Des Dillon (disambiguation), sever ...

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 key In 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 rando ...

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

mainframes A mainframe computer, informally called a mainframe or big iron, is a computer used primarily by large organizations for critical applications like bulk data processing for tasks such as censuses, industry and consumer statistics, enterprise ...

minicomputer A minicomputer, or colloquially mini, is a class of smaller general purpose computers that developed in the mid-1960s and sold at a much lower price than mainframe and mid-size computers from IBM and its direct competitors. In a 1970 survey, ...

s, and

microcomputer A microcomputer is a small, relatively inexpensive computer having a central processing unit (CPU) made out of a microprocessor. The computer also includes memory and input/output (I/O) circuitry together mounted on a printed circuit board (PC ...

s, and in discrete

logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...

. (DES has a large amount of bitwise permutations, which are 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

XOR Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...

s 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.

Cryptanalysis

At a glance, Madryga seems less secure than, for example, DES. All of Madryga's operations are linear. DES's

S-box In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Sha ...

es are its only non-linear component, and flaws in them are what both

differential 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 information input can aff ...

and

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. Linear cryptanalysis is one of the two most ...

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 In cryptography, the avalanche effect is the desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions, wherein if an input is changed slightly (for example, flipping a single bit), the output changes ...

. 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 ( he, אלי ביהם) is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion - Israel Institute of Technology Computer Science department. Starting from October 2008 and till 2013, Biham was the dean of t ...

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 Parity may refer to: * Parity (computing) ** Parity bit in computing, sets the parity of data for the purpose of error detection ** Parity flag in computing, indicates if the number of set bits is odd or even in the binary representation of the r ...

refers to the XOR sum of all the bits. In 1995, Ken Shirriff found a differential attack on Madryga that requires 5,000

chosen plaintext A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.Ross Anderson, ''Security Engineering: A Guide to Building Dependable Distributed Systems'' ...

s. Unpublished manuscript. 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 In cryptography, a ciphertext-only attack (COA) or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts. While the attacker has no channel providing access to the pl ...

using 2¹² ciphertexts, under reasonable assumptions about the redundancy of the plaintext (for example,

ASCII ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...

-encoded

English language English is a West Germanic language of the Indo-European language family, with its earliest forms spoken by the inhabitants of early medieval England. It is named after the Angles, one of the ancient Germanic peoples that migrated to the is ...

). 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.

The algorithm

Cryptanalysis

References

Further reading