Madryga

Last updated

In cryptography, Madryga is a block cipher published in 1984 by W. E. Madryga. It was designed to be easy and efficient for implementation in software. [1] 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,[ citation needed ] later used in other ciphers, such as RC5 and RC6.

Contents

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 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, [1] 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.

Cryptanalysis

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. [2] 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. [1]

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

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 affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

<span class="mw-page-title-main">International Data Encryption Algorithm</span> Symmetric-key block cipher

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher, the Proposed Encryption Standard (PES).

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

<span class="mw-page-title-main">Symmetric-key algorithm</span> Algorithm

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

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 widely used attacks on block ciphers; the other being differential cryptanalysis.

<span class="mw-page-title-main">RC5</span> Block cipher

In cryptography, RC5 is a symmetric-key block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, RC stands for "Rivest Cipher", or alternatively, "Ron's Code". The Advanced Encryption Standard (AES) candidate RC6 was based on RC5.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

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 plaintext prior to encryption, in all practical ciphertext-only attacks, the attacker still has some knowledge of the plaintext. For instance, the attacker might know the language in which the plaintext is written or the expected statistical distribution of characters in the plaintext. Standard protocol data and messages are commonly part of the plaintext in many deployed systems, and can usually be guessed or known efficiently as part of a ciphertext-only attack on these systems.

<span class="mw-page-title-main">DES-X</span> Block cipher

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

<span class="mw-page-title-main">MacGuffin (cipher)</span> Block cipher

In cryptography, MacGuffin is a block cipher created in 1994 by Bruce Schneier and Matt Blaze at a Fast Software Encryption workshop. It was intended as a catalyst for analysis of a new cipher structure, known as Generalized Unbalanced Feistel Networks (GUFNs). The cryptanalysis proceeded very quickly, so quickly that the cipher was broken at the same workshop by Vincent Rijmen and Bart Preneel.

In cryptography, NewDES is a symmetric key block cipher. It was created in 1984–1985 by Robert Scott as a potential DES replacement.

In cryptography, REDOC II and REDOC III are block ciphers designed by cryptographer Michael Wood for Cryptech Inc and are optimised for use in software. Both REDOC ciphers are patented.

In cryptography, FROG is a block cipher authored by Georgoudis, Leroux and Chaves. The algorithm can work with any block size between 8 and 128 bytes, and supports key sizes between 5 and 125 bytes. The algorithm consists of 8 rounds and has a very complicated key schedule.

In cryptography, SXAL is a block cipher designed in 1993 by Yokohama-based Laurel Intelligent Systems. It is normally used in a special mode of operation called MBAL. SXAL/MBAL has been used for encryption in a number of Japanese PC cards and smart cards.

<span class="mw-page-title-main">Speck (cipher)</span> Family of block ciphers

Speck is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013. Speck has been optimized for performance in software implementations, while its sister algorithm, Simon, has been optimized for hardware implementations. Speck is an add–rotate–xor (ARX) cipher.

References

  1. 1 2 3 Alex Biryukov; Eyal Kushilevitz (1998). From Differential Cryptanalysis to Ciphertext-Only Attacks. CRYPTO. pp. 72–88. CiteSeerX   10.1.1.128.3697 .
  2. ↑ Ken Shirriff (October 1995). "Differential Cryptanalysis of Madryga".{{cite journal}}: Cite journal requires |journal= (help) Unpublished manuscript.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.