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 Mbps for dedicated hardware of 6K gates and 25 MHz clock or 208 Mbps 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 232 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 or. Then it is used either by key scheduler, 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 232modulus, 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: does it in the end, - 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. Then algorithm takes the first block of plaintext and makes calculation 1 using KL, then it optionally does rotation and goes to calculation 2. The it repeats, but there is α instead of KL. Then it uses β for doing cal. 5. Then algorithm does calculations and rotation, described earlier, but using KR. 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 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 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:- Electronic Codebook 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 data hides not enough well and it is not recommended to use for cryptographic protocols at all.
- Cipher Block Chaining 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.
- Cipher Feedback 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.
- Output Feedback 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 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 235 trial encryptions; "a few dozen" known plaintexts reduces this to about 231.
- 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 K1-KM 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 K1 and K2, there are 2 rounds into F. Every Ki will appear at least once.
Depending of characteristics of cipher, next step will collect 2n/2 pairs of plaintext and ciphertext. By the birthday paradox, it should not be required to collect more than this number. Theh these pairs, which are denoted as , are used to find "slid" pairs, which are denoted as . Every "slid" pair has the property P0=F and C0=F. "Slid" pair get its name because it "slid" over one encryption. It can be imagined like result of applying one time function F.
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 ofplaintext-ciphertext pairs, and check to see what the keys corresponding to and are. If these keys match, this is a slid pair; otherwise move on to the next pair.
With 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 the search is for a. This reduces the possible paired messages from down to and so at most plaintext-ciphertext pairs are needed in order to find a slid pair.