MULTI2
Encyclopedia
MULTI2 is a block cipher
, developed by Hitachi
in 1988. Designed for general-purpose cryptography, its current use is encryption of high-definition television
broadcasts in Japan
.
of 64 bits, and a key size
of 64 bits. A 256-bit implementation-dependent substitution box
constant is used during key schedule
. Scramble and descramble is done by repeating four basic functions (involutions).
You can perform the following single byte modifications (modification here means XOR against the original key byte):
In this case there are 15 different keys which will schedule to the same 8 32-bit round keys for the ciphers bulk encryption path. The keys are all different in the first keyword used in the Pi3 round function (keys k[1] and k[5]). The collision occurs because a single byte difference turns into a pattern like 0X0X0000 (rotated by 0, 8, 16, or 24 bits) which then expands to a variation of 0X000X00 and finally in the second last line (with the rotate by 16 and the XOR) the differences cancel out. Turning into a zero-delta.
The problem stems from the fact that the function
Where ROL means rotate left by y bits, is not bijective for any value of y. There are similar problems with the Pi2 and Pi4 functions but they are seemingly harder to exploit because the rotation value is smaller.
There are other observations too, for example
Found in Pi3, is an identity function for 50% of the values of x (where the most significant byte is zero).
This also means it is possible to have weak keys where instead of forcing single byte differences in the key, they are in the plaintext into Pi3 produces a zero-delta output and possibly leading to a 1R differential.
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
, developed by Hitachi
Hitachi, Ltd.
is a Japanese multinational conglomerate headquartered in Marunouchi 1-chome, Chiyoda, Tokyo, Japan. The company is the parent of the Hitachi Group as part of the larger DKB Group companies...
in 1988. Designed for general-purpose cryptography, its current use is encryption of high-definition television
High-definition television
High-definition television is video that has resolution substantially higher than that of traditional television systems . HDTV has one or two million pixels per frame, roughly five times that of SD...
broadcasts in Japan
Japan
Japan is an island nation in East Asia. Located in the Pacific Ocean, it lies to the east of the Sea of Japan, China, North Korea, South Korea and Russia, stretching from the Sea of Okhotsk in the north to the East China Sea and Taiwan in the south...
.
Cipher details
MULTI2 is a symmetric key algorithm with variable number of rounds. It has a block sizeBlock size (cryptography)
In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size...
of 64 bits, and a key size
Key size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...
of 64 bits. A 256-bit implementation-dependent substitution box
Substitution box
In cryptography, an S-Box is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext — Shannon's property of confusion...
constant is used during key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
. Scramble and descramble is done by repeating four basic functions (involutions).
History
- 1988 MULTI2 patent applied by Hitachi, Ltd on April 28
- 1989 Algorithm announced to DPS-SIG Information Processing Society of Japan
- 1991 Patent number 4942492 granted for MULTI2 algorithm in United States
- 1994 Algorithm registered with ISO/IEC 9979 and assigned registration number 9
- 1995 MULTI2 adopted as standard cipher for CS-Digital broadcasting in Japan
- 1998 Japanese Patent number 2760799 granted for MULTI2 algorithm
Cryptanalysis
There are a large class of equivalent keys in the Multi2 block cipher. The largest class (so far found) stems from the fact that the Pi3 round function in the key schedule is not bijective. For example, with the following 40-byte input key to the key schedule:
45 ec 86 d8
b6 5e 24 d5
38 fe 1d 90
ce fc a4 22
3e 39 1b e3
da 03 0f cb
9c 9e d7 c6
1c e4 73 61
d0 fa 39 86
58 5d 5b 90
You can perform the following single byte modifications (modification here means XOR against the original key byte):
Can mod byte 5 with CF
Can mod byte 7 with 77
Can mod byte 20 with 9A
Can mod byte 20 with A9
Can mod byte 20 with D7
Can mod byte 21 with 35
Can mod byte 21 with 6A
Can mod byte 21 with 9F
Can mod byte 21 with CC
Can mod byte 22 with 4D
Can mod byte 22 with 7A
Can mod byte 22 with A7
Can mod byte 23 with 53
Can mod byte 23 with AE
In this case there are 15 different keys which will schedule to the same 8 32-bit round keys for the ciphers bulk encryption path. The keys are all different in the first keyword used in the Pi3 round function (keys k[1] and k[5]). The collision occurs because a single byte difference turns into a pattern like 0X0X0000 (rotated by 0, 8, 16, or 24 bits) which then expands to a variation of 0X000X00 and finally in the second last line (with the rotate by 16 and the XOR) the differences cancel out. Turning into a zero-delta.
The problem stems from the fact that the function
x = ROL(x, y) ^ x
Where ROL means rotate left by y bits, is not bijective for any value of y. There are similar problems with the Pi2 and Pi4 functions but they are seemingly harder to exploit because the rotation value is smaller.
There are other observations too, for example
x = ROL(x, 1) - x
Found in Pi3, is an identity function for 50% of the values of x (where the most significant byte is zero).
This also means it is possible to have weak keys where instead of forcing single byte differences in the key, they are in the plaintext into Pi3 produces a zero-delta output and possibly leading to a 1R differential.