M8 (cipher)
   HOME

TheInfoList



OR:

In
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 ...
, 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. Like M6, M8 is a
Feistel cipher In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research ...
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 A frog is any member of a diverse and largely carnivorous group of short-bodied, tailless amphibians composing the order Anura (ανοὐρά, literally ''without tail'' in Ancient Greek). The oldest fossil "proto-frog" ''Triadobatrachus'' is ...
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_, K_, ..., K_, K_. The cipher has a typical
Feistel cipher In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research ...
design. First, the 64-bit input block is split into two 32-bit halves. In each round, the left half undergoes a key-dependent transformation, and is then combined with the right half. Finally, the halves are swapped. In total, the round function consists of a sequence of nine customizable operations and three bitwise rotations: \begin R_&=L_i \\ x&=L_ \operatorname_1 K_\\ y&=((x <<< S_1) \operatorname_2 x) \operatorname_3 \alpha \\ z&=(((y <<< S_2) \operatorname_4 y) \operatorname_5 \beta) \operatorname_6 K_ \\ L_&=(((z <<< S_3) \operatorname_7 z) \operatorname_8 \gamma) \operatorname_9 R_i \end i denotes the round number, which takes inputs L_i and R_i. \alpha, \beta, \gamma are the three 32-bit words of the round's algorithm expansion key. K_, K_ are words from the execution key. <<< denotes a left bitwise rotation. \operatorname_j and S_k are defined by the 24-bit algorithm decision key as follows:
MSB                                      LSB
op1 op2 op3 op4 op5 op6 op7 op8 op9 S1 S2 S3
where op1 to op9 are each one bit (0 = addition mod 232, 1 = XOR) and S1 to S3 are five bits each. Key expansion consists of eight cipher rounds, using the first eight algorithm decision and expansion keys, the key expansion key as the execution key, and the data key as the input block. The eight intermediate outputs, L_1, L_2, ..., L_7, L_8 are used as the eight components of the execution key K_, K_, ..., K_, K_.


Cipher implementation

The following is an implementation of the cipher in
Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...
. # https://en.wikipedia.org/wiki/M8_(cipher) M = 0xffffffff def add(x, y): return (x + y) & M def xor(x, y): return x ^ y def rol(x, s): return ((x << s) , (x >> (32 - s))) & M def m8_round(L, R, ri, k, adk, aek): """ One round of the algorithm. L, R: input ri: round index k: 256-bit execution key adk: 24-bit algorithm decision key aek: 96-bit algorithm expansion key """ op = add, xor(adk >> (23 - i)) & 1] for i in range(9)] S1 = (adk >> 10) & 0x1f S2 = (adk >> 5) & 0x1f S3 = (adk >> 0) & 0x1f A = (aek >> 64) & M B = (aek >> 32) & M C = (aek >> 0) & M KR = (k >> (32 + 64 * (3 - ri % 4))) & M KL = (k >> (0 + 64 * (3 - ri % 4))) & M x = op L, KL) y = op op rol(x, S1), x), A) z = op op op rol(y, S2), y), B), KR) return op op op rol(z, S3), z), C), R), L def m8_keyexpand(dk, kek, adks, aeks): """ Key expansion. dk: 64-bit data key kek: 256-bit key expansion key adks: algorithm decision keys aeks: algorithm expansion keys """ L = (dk >> 32) & M R = (dk >> 0) & M k = 0 for i in range(8): L, R = m8_round(L, R, i, kek, adks aeks k , = (L << (32 * (7 - i))) return k def m8_encrypt(data, N, dk, kek, adks, aeks): """ Encrypt one block with M8. data: 64-bit input block N: number of rounds (must be >= 8) dk: 64-bit data key kek: 256-bit key expansion key adks: a list of N 24-bit algorithm decision keys aeks: a list of N 96-bit algorithm expansion keys """ ek = m8_keyexpand(dk, kek, adks, aeks) L = (data >> 32) & M R = (data >> 0) & M for i in range(N): L, R = m8_round(L, R, i, ek, adks aeks return (L << 32) , R # Published test vector from ISO/IEC 9979/0020 result = m8_encrypt( 0x0000_0000_0000_0001, 126, 0x0123_4567_89AB_CDEF, 0, x848B6D, 0x8489BB, 0x84B762, 0x84EDA2* 32, x0000_0001_0000_0000_0000_0000* 126, ) assert result

0xFE4B_1622_E446_36C0


Test vectors

The published version of ISO/IEC 9979-0020 includes the following test data:
* Round number: 126 * Key expansion key: 0256 (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 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 expose the cipher to a range of attacks, including differential cryptanalysis,
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 mos ...
and
mod n cryptanalysis In cryptography, mod ''n'' cryptanalysis is an attack applicable to block and stream ciphers. It is a form of partitioning cryptanalysis that exploits unevenness in how the cipher operates over equivalence classes (congruence classes) modulo '' ...
.


References

Feistel ciphers {{crypto-stub