| General | |
|---|---|
| Designers | Hitachi |
| First published | 1988 |
| Cipher detail | |
| Key sizes | 64 bits |
| Block sizes | 64 bits |
| Structure | Feistel network |
| Rounds | Variable |
MULTI2 is ablock cipher, developed byHitachi in 1988. Designed for general-purpose cryptography, its current use is encryption ofhigh-definition televisionbroadcasts inJapan.
MULTI2 is asymmetric key algorithm with variable number of rounds. It has ablock size of 64 bits, and akey size of 64 bits. A 256-bit implementation-dependentsubstitution box constant is used duringkey schedule. Scramble and descramble is done by repeating four basic functions (involutions).
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 notbijective. 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 CFCan mod byte 7 with 77Can mod byte 20 with 9ACan mod byte 20 with A9Can mod byte 20 with D7Can mod byte 21 with 35Can mod byte 21 with 6ACan mod byte 21 with 9FCan mod byte 21 with CCCan mod byte 22 with 4DCan mod byte 22 with 7ACan mod byte 22 with A7Can mod byte 23 with 53Can 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.
