M8 (cipher)

In cryptography, M8 is a block cipher designed by Hitachi in 1999. The algorithm negotiates introduced in 1997 M6, with the modified key length, which is enlarged to 64 bits or more. This cipher operates with Feistel network and designed to reach high performance on small implementation or 32 bits devices. For instance, by using round numbers = 10 it present encryption speed at 32 Mbit/s for dedicated hardware of 6K gates and 25 MHz clock or 208 Mbit/s for program, that uses C-language and Pentium-I 266 MHz. Due to the openness of description, it should not be used in open or multivendor software.

Structure of algorithm[]

Basic structure[]

The structural characteristics are that the cipher is based on substitution-permutation block like DES. There are 3 kinds of calculations: 32-bit circular rotation, addition in modulus 2³² and 32 bits-wise XOR. Actual function may be different each round. Key is used to be calculated using its value and that defines actual function each round.

After decision process, which is using round number, decision and expansion keys, the algorithm gets basic function (e π) or (d π). Then it is used either by key scheduler (which also takes 256 key expansion key and 64 bits data key), that products 256 bits execution key, and encryption/decryption block.

Algorithm decision key is consist of 24 bits. First 9 bits determine calculations: 0 means addition in 2³²modulus, 1 means bit-wise XOR. Other 3 blocks for 5 bits define left circular rotations. Algorithm expansion key concludes 3 blocks for 32bits, which determine α,β and γ.

The difference between basic function is only in the order of permutations: (e π) does it in the end, (d π) - at the beginning of calculation block.

Structure of basic functions[]

The structure has 9 blocks of calculations and 3 optionally blocks of left circle rotations.
It has a 64-bit block size and also 64-bit key length. It is Feistel cipher with S-blocks, that are dependent on large execution key.
At the start, there is permutation for (d π). Then algorithm takes the first block of plaintext and makes calculation 1 using K_L, then it optionally does rotation and goes to calculation 2. The it repeats, but there is α instead of K_L. Then it uses β for doing cal. 5. Then algorithm does calculations and rotation, described earlier, but using K_R. Further, it is used γ to do calc.8 and obtained result calculates with the other block of plaintext. In conclusion, algorithm permutates blocks.
For the (e π) it is the same, excluding the order of permutation and calculations of blocks.

Key schedule[]

The execution key obtains from 256-bit key expansion key, which divides into 2 identical set of four 64-bit blocks K0–K3, and 64 bit of data key. Every block of key expansion key is used to calculate with 32 bit of data key by (e Π [0-7]) and gives eight 32-bit blocks of expansion key on the output.

Encryption[]

Obtained expansion key divides into 4 pair block of 32-bit. This block divides into 32 bits of left and right range it is used to do calculations with 64-bit plaintext blocks using 4 subsequent steps. Then obtained ciphertext encrypts again using the same pairs of block of expansion key and the same steps round times.

Decryption[]

To decrypt cipher text it is enough to do the same operation, but using the another basic function.

Modes of operation[]

As determined in ISO 8372 or ISO/IEC 101116 there are 4 applicable modes:

1. Electronic Codebook (ECB) mode
   • The simplest encryption mode. Using this plaintext divides into blocks, which encrypts separately. The disadvantage of this method is the lack of diffusion. It means that generated cipher text blocks are not affected by previous cipher text blocks, so that the relationship between plaintext blocks and their resulting ciphertext blocks are poorly hidden. This makes this mode of operation vulnerable to replay attacks and known plaintext attacks. It is considered to be insecure and is not recommended for use in cryptographic protocols.
2. Cipher Block Chaining (CBC) mode
   • In this mode each block of plaintext is XORed with the previous before being encrypted. Every block will depend on all previous blocks and it should be used initialization vector in the first block to make each message unique.
3. Cipher Feedback (CFB) mode
   • This mode mode, a close relative of CBC, makes a block cipher into a self-synchronizing stream cipher. Operation is very similar; in particular, CFB decryption is almost identical to CBC encryption performed in reverse.
4. Output Feedback (OFB) mode
   • This mode makes a block cipher into a synchronous stream cipher. It generates keystream blocks, which are then XORed with the plaintext blocks to get the ciphertext. Just as with other stream ciphers, flipping a bit in the ciphertext produces a flipped bit in the plaintext at the same location. This property allows many error correcting codes to function normally even when applied before encryption.
     Because of the symmetry of the XOR operation, encryption and decryption are exactly the same.

Cryptoanalysis[]

• In M8 key determines both calculation objects and round numbers. If a hostile person knows the structure of every round, it will be possible to evaluate M8 by using conventional methods. With the estimate of Hitachi, there is possibility that if it has less than 10 rounds, it will be easier to encrypt M8 than DES. Therefore it is recommended to use >10 rounds. The cryptographic strength increases as the number of rounds are growing, but it is necessary to remember, that the speed of encryption will decrease inversely as round numbers. If the structure of rounds are not known, there is only the way to do exhaustive search, which will be non-effective due to a huge number of round function variations. Summary, it is needed to trade-off between speed and safety of the algorithm.
• Like an M6, it is sensitive to mod n cryptanalysis, which was suggested in 1999 by John Kelsey, Bruce Schneier, and David Wagner. It is a form of partitioning cryptanalysis that exploits unevenness in how the cipher operates over equivalence classes (congruence classes) modulo n. These attacks used the properties of binary addition and bit rotation modulo a Fermat prime. One known plaintext allows recovering the key with about 2³⁵ trial encryptions; "a few dozen" known plaintexts reduces this to about 2³¹.
• Because it has weak key schedule, M8 is subject to decryption to a slide attack, which requires less known plaintext than mod n cryptanalysis, but less calculations. Lets assume that cipher has n bits and uses key scheduler, which consist K₁-K_M as keys of any length. This encryption method breaks up into identical permutation functions F of cipher. This functions may consist of more than 1 round of cipher, it is defined by key-schedule. For example, if cipher uses alternating key-schedule, which switches between K₁ and K₂, there are 2 rounds into F. Every K_i will appear at least once.
  Depending on the characteristics of the cipher, the next step will collect 2^n/2 pairs of plaintext and ciphertext. By the birthday paradox, it should not be required to collect more than this number. Then these pairs, which are denoted as ${\displaystyle (P,C)}$ are used to find "slid" pairs, which are denoted as ${\displaystyle (P_{0},C_{0})(P_{1},C_{1})}$. Every "slid" pair has the property ${\displaystyle P_{0}=F(P_{1})}$ and ${\displaystyle C_{0}=F(C_{1})}$. "Slid" pair get its name because it "slid" over one encryption. It can be imagined like result of applying one time function F.
  Once this pair is identified, the key can be easily extracted from this pairing, and the cipher is broken because of vulnerability to known-plaintext attacks.
  The process of finding a slid pair can be different but follows the same basic scheme. One uses the fact that it is relatively easy to extract the key from just one iteration of F. Choose any pair of plaintext-ciphertext pairs, ${\displaystyle (P_{0},C_{0})(P_{1},C_{1})}$ and check to see what the keys corresponding to ${\displaystyle P_{0}=F(P_{1})}$ and ${\displaystyle C_{0}=F(C_{1})}$ are. If these keys match, this is a slid pair; otherwise move on to the next pair.
  With ${\displaystyle 2^{n/2}}$ plaintext-ciphertext one slid pair is expected. The number of false-positives depends on structure of the algorithm. False-positives can be reduced by applying keys to different message-cipherkey pair, because it is very low possibility for a good cipher, that the wrong key can correctly encrypt >2 messages.
  Sometimes the structure of the cipher greatly reduces the number of plaintext-ciphertext pairs needed, and thus also a large amount of the work.
  The clearest of these examples is the Feistel cipher using a cyclic key schedule. The reason for this is given a ${\displaystyle P=(L_{0},R_{0})}$ the search is for a ${\displaystyle P_{0}=(R_{0},L_{0}\bigoplus F(R_{0},K))}$. This reduces the possible paired messages from ${\displaystyle 2^{n}}$ down to ${\displaystyle 2^{n/2}}$ (since half the message is fixed) and so at most ${\displaystyle 2^{n/4}}$ plaintext-ciphertext pairs are needed in order to find a slid pair.

See also[]

• M6 (cipher)
• Data Encryption Standard
• Slide attack
• Mod n cryptanalysis

References[]

• "ISO/IEC9979-0020 Register Entry" (PDF). Professor Chris Mitchell, Information Security Group, Royal Holloway, University of London. ISO/IEC 9979 Register of Cryptographic Algorithms.
• "Mod n Cryptanalysis, with Applications Against RC5P and M6" (PDF). J. Kelsey, B. Schneier, and D. Wagner. Fast Software Encryption, Sixth International Workshop Proceedings (March 1999), Springer-Verlag, 1999, pp. 139-155.
• E.K. Grossman & B. Tuckerman (1977). "Analysis of a Feistel-like cipher weakened by having no rotating key". IBM Thomas J. Watson Research Report RC 6375. Cite journal requires |journal= (help)
• Henry Beker & Fred Piper (1982). Cipher Systems: The Protection of Communications. John Wiley & Sons. pp. 263–267. ISBN 0-471-89192-4. (contains a summary of the paper by Grossman and Tuckerman)
• Alex Biryukov and David Wagner (March 1999). Slide Attacks (PDF/PostScript). 6th International Workshop on Fast Software Encryption (FSE '99). Rome: Springer-Verlag. pp. 245–259. Retrieved 2007-09-03.
• Alex Biryukov & David Wagner (May 2000). Advanced Slide Attacks (PDF/PostScript). Advances in Cryptology, Proceedings of EUROCRYPT 2000. Bruges: Springer-Verlag. pp. 589–606. Retrieved 2007-09-03.
• S. Furuya (December 2001). Slide Attacks with a Known-Plaintext Cryptanalysis (PDF). 4th International Conference on Information Security and Cryptology (ICISC 2001). Seoul: Springer-Verlag. pp. 214–225. Archived from the original (PDF) on 2007-09-26. Retrieved 2007-09-03.
• Eli Biham (1994). "New Types of Cryptanalytic Attacks Using Related Keys" (PDF/PostScript). Journal of Cryptology. 7 (4): 229–246. doi:10.1007/bf00203965. ISSN 0933-2790. Retrieved 2007-09-03.
• M. Ciet, G. Piret, J. Quisquater (2002). "Related-Key and Slide Attacks: Analysis, Connections, and Improvements" (PDF/PostScript). Retrieved 2007-09-04. Cite journal requires |journal= (help)CS1 maint: multiple names: authors list (link)