M8 (cipher): Difference between revisions

M8
General
Designers	Hitachi
First published	1999
Derived from	M6
Cipher detail
Block sizes	64 bits
Structure	Feistel network
Rounds	Variable

Browse history interactively

← Previous edit Next edit →

Content deleted Content added

VisualWikitext

Inline

Revision as of 04:16, 6 December 2021

In cryptography, M8 is a block cipher designed by Hitachi in 1999. It is a modification of Hitachi's earlier M6 algorithm, designed for greater security and high performance in both hardware and 32-bit software implementations. M8 was registered by Hitachi in March 1999 as ISO/IEC 9979-0020.^[1]

Like M6, M8 is a Feistel cipher with a block size of 64 bits. The round function can include 32-bit rotations, XORs, and modular addition, making it an early example of an ARX cipher.

The cipher features a variable number of rounds (any positive integer N), each of which has a structure determined by a round-specific "algorithm decision key". Making the rounds key-dependent is intended to make cryptanalysis more difficult (see FROG for a similar design philosophy).

Cipher description

The round count can be set to any positive integer N, but a round count of at least 10 is recommended. The key consists of four components: a 64-bit data key, 256-bit key expansion key, a set of N 24-bit algorithm decision keys, and a set of N 96-bit algorithm expansion keys.

The round function is used for both key expansion and encryption/decryption. The key expansion process transforms the 64-bit data key and 256-bit key expansion key into a 256-bit execution key, consisting of 4 pairs of 32-bit numbers $K_{L_{0}},K_{R_{0}},...,K_{L_{3}},K_{R_{3}}$ .

The cipher has a typical Feistel cipher design. In each round, the input is split into two 32-bit halves. The left half undergoes a key-dependent computation, and is then combined with right half using a key-dependent operation; the halves are finally swapped. The round function consists of a sequence of nine customizable operations and three bitwise rotations. It consumes 3 32-bit words $\alpha ,\beta ,\gamma$ from the algorithm expansion key, as well as 2 32-bit words $K_{L_{i{\bmod {4}}}},K_{R_{i{\bmod {4}}}}$ from the execution key, as follows:

${\begin{aligned}R_{i+1}&=L_{i}\\x&=L_{i}\operatorname {op} _{1}K_{L_{i{\bmod {4}}}}\\y&=((x<<<S_{1})\operatorname {op} _{2}x)\operatorname {op} _{3}\alpha \\z&=(((y<<<S_{2})\operatorname {op} _{4}y)\operatorname {op} _{5}\beta )\operatorname {op} _{6}K_{R_{i{\bmod {4}}}}\\L_{i+1}&=(((z<<<S_{3})\operatorname {op} _{7}z)\operatorname {op} _{8}\gamma )\operatorname {op} _{9}L_{i}\end{aligned}}$

$i$ denotes the round number, which takes inputs $L_{i}$ and $R_{i}$ . $<<<$ denotes a left bitwise rotation. $\operatorname {op} _{k}$ is either addition mod $2^{32}$ or XOR, depending on the algorithm decision key. $S_{k}<math>arerotationalconstantsfromthealgorithmdecisionkey.The24-bitalgorithmdecisionkeyisencodedasfollows:<pre>MSBLSBop1op2op3op4op5op6op7op8op9S1S2S3</pre>whereop1toop9areeachonebit(0=addition,1=XOR)andS1toS3arefivebitseach.Keyexpansionconsistsofthefirsteightroundsofthemaincipher,usingthefirsteightalgorithmdecisionandexpansionkeys,andthekeyexpansionkeyastheexecutionkey.Theeightintermediateoutputs,<math>L_{1},L_{2},...,L_{7},L_{8}$ are used as the eight components of the execution key $K_{L_{0}},K_{R_{0}},...,K_{L_{3}},K_{R_{3}}$

Test vectors

The published version of ISO/IEC 9979-0020 includes the following test data:

Round number: 126

Key expansion key: 0²⁵⁶ (an all-zeros vector)

Data key: 0123 4567 89AB CDEF in hex

Algorithm decision key:
rounds 1, 5, 9, ...: 848B6D hex

rounds 2, 6, 10, ...: 8489BB hex

rounds 3, 7, 11, ...: 84B762 hex

rounds 4, 8, 12, ...: 84EDA2 hex

Algorithm expansion key: 0000 0001 0000 0000 0000 0000 hex for all rounds

Plaintext: 0000 0000 0000 0001 hex

Ciphertext after 7 rounds: C5D6 FBAD 76AB A53B hex

Ciphertext after 14 rounds: 6380 4805 68DB 1895 hex

Ciphertext after 21 rounds: 2BFB 806E 1292 5B18 hex

Ciphertext after 28 rounds: F610 6A41 88C5 8747 hex

Ciphertext after 56 rounds: D3E1 66E9 C50A 10A2 hex

Final ciphertext after 126 rounds: FE4B 1622 E446 36C0 hex

Cryptanalysis

The key-dependent behaviour of the cipher results in a large class of weak keys which expose the cipher to a range of attacks, including differential cryptanalysis, linear cryptanalysis and mod n cryptanalysis^[2].

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.
^ Toshio Tokita; Tsutomu Matsumoto. "On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm M8 (ISO9979-20)". Ipsj Journal. 42 (8).

This cryptography-related article is a stub. You can help Wikipedia by expanding it.

[1] "ISO/IEC9979-0020 Register Entry" (PDF). Professor Chris Mitchell, Information Security Group, Royal Holloway, University of London. ISO/IEC 9979 Register of Cryptographic Algorithms.

[2] Toshio Tokita; Tsutomu Matsumoto. "On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm M8 (ISO9979-20)". Ipsj Journal. 42 (8).

[1]

[2]

@@ Line 27: / Line 27: @@
 The round count can be set to any positive integer N, but a round count of at least 10 is recommended. The key consists of four components: a 64-bit data key, 256-bit key expansion key, a set of N 24-bit algorithm decision keys, and a set of N 96-bit algorithm expansion keys.
-The round function is used for both key expansion and encryption/decryption. The key expansion is an eight-round version of the main cipher, using the first eight algorithm decision and expansion keys. It transforms the 64-bit data key and 256-bit key expansion key into a 256-bit execution key (obtained as the concatenation of the eight intermediate outputs from each round).
+The round function is used for both key expansion and encryption/decryption. The key expansion process transforms the 64-bit data key and 256-bit key expansion key into a 256-bit execution key, consisting of 4 pairs of 32-bit numbers <math>K_{L_0}, K_{R_0}, ..., K_{L_3}, K_{R_3}</math>.
-The cipher has a typical [[Feistel cipher]] design. In each round, the input is split into two 32-bit halves. The left half undergoes a key-dependent computation, and is then combined with right half using a key-dependent operation; the halves are finally swapped. The round function consists of a sequence of nine customizable operations and three bitwise rotations. It consumes 3 32-bit words <math>\alpha, \beta, \gamma</math> from the algorithm expansion key, as well as 2 32-bit words <math>K_L, K_R</math> from the execution key, as follows:
+The cipher has a typical [[Feistel cipher]] design. In each round, the input is split into two 32-bit halves. The left half undergoes a key-dependent computation, and is then combined with right half using a key-dependent operation; the halves are finally swapped. The round function consists of a sequence of nine customizable operations and three bitwise rotations. It consumes 3 32-bit words <math>\alpha, \beta, \gamma</math> from the algorithm expansion key, as well as 2 32-bit words <math>K_{L_{i\bmod 4}}, K_{R_{i\bmod 4}}</math> from the execution key, as follows:
 <math>
 \begin{align}
 R_{i+1}&=L_i \\
-x&=L_{i} \operatorname{op}_1 K_L\\
+x&=L_{i} \operatorname{op}_1 K_{L_{i\bmod 4}}\\
 y&=((x <<< S_1) \operatorname{op}_2 x) \operatorname{op}_3 \alpha \\
-z&=(((y <<< S_2) \operatorname{op}_4 y) \operatorname{op}_5 \beta) \operatorname{op}_6 K_R \\
+z&=(((y <<< S_2) \operatorname{op}_4 y) \operatorname{op}_5 \beta) \operatorname{op}_6 K_{R_{i\bmod 4}} \\
 L_{i+1}&=(((z <<< S_3) \operatorname{op}_7 z) \operatorname{op}_8 \gamma) \operatorname{op}_9 L_i
 \end{align}
 </math>
-<math> <<< </math> denotes a left bitwise rotation. <math>\operatorname{op}_k</math> is either addition mod <math>2^{32}</math> or XOR, depending on the algorithm decision key.
+<math>i</math> denotes the round number, which takes inputs <math>L_i</math> and <math>R_i</math>. <math> <<< </math> denotes a left bitwise rotation. <math>\operatorname{op}_k</math> is either addition mod <math>2^{32}</math> or XOR, depending on the algorithm decision key. <math>S_k<math> are rotational constants from the algorithm decision key. The 24-bit algorithm decision key is encoded as follows:
+<pre>
+MSB                                      LSB
+op1 op2 op3 op4 op5 op6 op7 op8 op9 S1 S2 S3
+</pre>
+where op1 to op9 are each one bit (0 = addition, 1 = XOR) and S1 to S3 are five bits each.
+Key expansion consists of the first eight rounds of the main cipher, using the first eight algorithm decision and expansion keys, and the key expansion key as the execution key. The eight intermediate outputs, <math>L_1, L_2, ..., L_7, L_8</math> are used as the eight components of the execution key <math>K_{L_0}, K_{R_0}, ..., K_{L_3}, K_{R_3}</math>
 ==Test vectors==