Magenta

MAGENTA is a block cipher developed by Michael Jacobson and Klaus Huber for the German telecommunications company Deutsche Telekom AG . MAGENTA is short for Multifunctional Algorithm for General-purpose Encryption and Network Telecommunication Applications.

History

The development of MAGENTA began in 1990 with the basic principles described in an unpublished book ^[1] . The main idea was to use a simple technique, without magic tables and constants, which could be performed both hardware and software. The plans were to develop a chip that could transmit data at speeds up to 1 Gbit / s and be used for encryption in ATM . Unfortunately, the hardware implementation did not appear, as planned, due to the narrow application, but, despite this, studies have shown that such a chip can be developed ^[2] . MAGENTA entered the AES in 1998, but dropped out after the first round. The cipher became available to conference participants only on the day of the presentation, unlike the other ciphers participating. MAGENTA was used to encrypt data internally at Deutsche Telekom . It should be noted that before MAGENTA fast Fourier transform for cryptographic purposes was used in 2 ciphers. The specific name of the first could not be found ^[3] , it was invented by Jean-Pierre Wasser and registered on June 2, 1959. The second cipher is one of the implementations of the A3 algorithm - Comp-128.

Encryption

MAGENTA has a Feistel network structure. The round function is based on the fast Adamar transformation ^{] [4]} , except that instead of adding and subtracting at each stage, an S-block defined by the function f (x) is applied to one of the terms, and then they are added modulo 2 .

Let the set $B=\{0,1\}^{8}$ ${\ displaystyle B = \ {0,1 \} ^ {8}}$ $B=\{0,1\}^{8}$ .Block size $M=(x_{0},...,x_{15})\in B^{16}$ ${\ displaystyle M = (x_ {0}, ..., x_ {15}) \ in B ^ {16}}$ $M=(x_{0},...,x_{15})\in B^{16}$ the source text is 128 bits. The key size can take 3 values:

128 bit: $K=(K_{1},K_{2})$ ${\ displaystyle K = (K_ {1}, K_ {2})}$ $K=(K_{1},K_{2})$ ,
192 bit: $K=(K_{1},K_{2},K_{3})$ ${\ displaystyle K = (K_ {1}, K_ {2}, K_ {3})}$ $K=(K_{1},K_{2},K_{3})$ ,
256 bit: $K=(K_{1},K_{2},K_{3},K_{4})$ ${\ displaystyle K = (K_ {1}, K_ {2}, K_ {3}, K_ {4})}$ $K=(K_1,K_2,K_3,K_4)$ where $K_{1}=(y_{0},...,y_{7})\ K_{2}=(y_{8},...,y_{15})\ K_{3}=(y_{16},...,y_{23})\ K_{4}=(y_{24},...,y_{31})$ ${\ displaystyle K_ {1} = (y_ {0}, ..., y_ {7}) \ K_ {2} = (y_ {8}, ..., y_ {15}) \ K_ {3} = (y_ {16}, ..., y_ {23}) \ K_ {4} = (y_ {24}, ..., y_ {31})}$ $K_{1}=(y_{0},...,y_{7})\ K_{2}=(y_{8},...,y_{15})\ K_{3}=(y_{16},...,y_{23})\ K_{4}=(y_{24},...,y_{31})$ .

Let F be a round function. The block cipher M is calculated as follows: $Enc_{K}(M)={\begin{cases}F_{K_{1}}(F_{K_{1}}(F_{K_{2}}(F_{K_{2}}(F_{K_{1}}(F_{K_{1}}(M)))))),&K=(K_{1},K_{2})\in B^{16},\\F_{K_{1}}(F_{K_{2}}(F_{K_{3}}(F_{K_{3}}(F_{K_{2}}(F_{K_{1}}(M)))))),&K=(K_{1},K_{2},K_{3})\in B^{24},\\F_{K_{1}}(F_{K_{2}}(F_{K_{3}}(F_{K_{4}}(F_{K_{4}}(F_{K_{3}}(F_{K_{2}}(F_{K_{1}}(M)))))))),&K=(K_{1},K_{2},K_{3},K_{4})\in B^{32};\end{cases}}$ ${\ displaystyle Enc_ {K} (M) = {\ begin {cases} F_ {K_ {1}} (F_ {K_ {1}} (F_ {K_ {2}} (F_ {K_ {2}} (F_ {K_ {1}} (F_ {K_ {1}} (M)))))), & K = (K_ {1}, K_ {2}) \ in B ^ {16}, \\ F_ {K_ { 1}} (F_ {K_ {2}} (F_ {K_ {3}} (F_ {K_ {3}} (F_ {K_ {2}} (F_ {K_ {1}} (M))))) ), & K = (K_ {1}, K_ {2}, K_ {3}) \ in B ^ {24}, \\ F_ {K_ {1}} (F_ {K_ {2}} (F_ {K_ { 3}} (F_ {K_ {4}} (F_ {K_ {4}} (F_ {K_ {3}} (F_ {K_ {2}} (F_ {K_ {1}} (M))))) ))), & K = (K_ {1}, K_ {2}, K_ {3}, K_ {4}) \ in B ^ {32}; \ end {cases}}}$

128 bits - the key K is divided into 2 parts - K ₁ and K ₂ . The number of rounds 6. The keys are applied in this order:

Round	one	2	3	four	five	6
Applicable key	K ₁	K ₁	K ₂	K ₂	K ₁	K ₁

192 bits - the key K is divided into 3 parts - K ₁ , K ₂ and K ₃ . The number of rounds 6. The keys are applied in this order:

Round	one	2	3	four	five	6
Applicable key	K ₁	K ₂	K ₃	K ₃	K ₂	K ₁

256 bits - the key K is divided into 4 parts - K ₁ , K ₂ , K ₃ and K ₄ . The number of rounds 8. The keys are applied in this order:

Round	one	2	3	four	five	6	7	eight
Applicable key	K ₁	K ₂	K ₃	K ₄	K ₄	K ₃	K ₂	K ₁

Decryption

It should be noted that the sequence of key parts used is a palindrome. Let be $V(x_{0},...,x_{15})\ =\ (x_{8},x_{9},...,x_{15},x_{0},x_{1},...,x_{7})$ ${\ displaystyle V (x_ {0}, ..., x_ {15}) \ = \ (x_ {8}, x_ {9}, ..., x_ {15}, x_ {0}, x_ {1 }, ..., x_ {7})}$ . Then

$V((Enc_{K}(x_{0},...,x_{15}))\ =\ Enc_{K}^{-1}(V(x_{0},...,x_{15})).$ ${\ displaystyle V ((Enc_ {K} (x_ {0}, ..., x_ {15})) \ = \ Enc_ {K} ^ {- 1} (V (x_ {0}, ..., x_ {15})).}$ ^[5] ^[6]

Thus decryption $Dec_{K}(M)\ =\ V(Enc_{K}(V(M))).$ ${\ displaystyle Dec_ {K} (M) \ = \ V (Enc_ {K} (V (M))).}$

Round F function

The input block X of size 128 bits of a round nc with a round key K _{n is} divided into 2 parts X ₁ and X _{2 of} size 64 bits each.

X = X ₁ X ₂

After passing the round we get X ^' = X ₂ F (X ₂ K _n )

From the dependence of the division into parts of the original key on the number of rounds: the length of the key part used in each round is always 64 bits.

Therefore, function F takes a 128-bit argument and should return a 64-bit or 8-byte result.

We introduce auxiliary functions through which we then express F:

Function	Size of accepted arguments	Return Value Size	Description
f (x)	1 byte	1 byte	Returns the element number x in the S-block
A (x, y)	1 byte	1 byte	f (x ⊕ f (y))
PE (x, y)	1 byte	2 bytes	(A (x, y) A (y, x)) - concatenates the results of A (x, y) and A (y, x)
P (X)	16 bytes	16 bytes	X = X ₀ X ₁ ... X ₁₄ X ₁₅ (PE (X ₀ , X ₈ ) PE (X ₁ , X ₉ ) ... PE (X ₆ , X ₁₄ ) PE (X ₇ , X ₁₅ )) - concatenates the results of PE (X _i , X _{i + 8} ) i = 0 ... 7, X _i has a size of 1 byte.
T (X)	16 bytes	16 bytes	P (P (P (P (P (X)))) - applies the function P. to X 4 times
S (x)	16 bytes	16 bytes	(X ₀ X ₂ X ₄ ... X ₁₄ X ₁ X ₃ X ₅ ... X ₁₅ ) - performs a rearrangement of bytes X: bytes with an even serial number are written first, then with an odd one.
C (k, X)	k∈Ν X - 16 bytes	16 bytes	Recursive function: C (1, X) = T (X)) C (k, X) = T (X ⊕ S (C (k-1, X)))

The scheme of the function P (X):

F is assumed to be equal to the first 8 bytes from S (C (n, (X ₂ K _n ))), that is, bytes C (n, (X ₂ K _n )) with an even serial number. Initially, n was set equal to 7, but tests showed that in this case the cipher can be cracked. Therefore, then they put n = 3. As the tests showed, this is the best choice that does not allow cryptographic weaknesses that affect the entire cipher. In this way,

F is assumed to be equal to the first 8 bytes from S (C (3, (X ₂ K _n )))

S-block

S-block is formed as follows:

The first element is 1, the next ones are formed by a bit shift to the left of the previous one, until 1 goes beyond the left border of the byte. Accordingly, the beginning of the block is 1 2 4 8 16 32 64 128

256 ₁₀ = 1 0000 0000 ₂ , 1 out of bounds of byte. In this case, it is necessary to add modulo 2 to the resulting shifted number 0000 0000 ₂ with the number 101 ₁₀ = 0110 0101 ₂ :

0000 0000 ₂ ⊕ 0110 0101 ₂ = 0110 0101 ₂ = 101 ₁₀ , that is, after 128 it will stand 101.

101 ₁₀ = 0110 0101 ₂ << 1 = 1100 1010 ₂ = 202 ₁₀ , 1 did not go abroad, therefore, the next element 202.
202 ₁₀ << 1 = 1100 1010 ₂ << 1 = 1001 0100 ₂ , 1 went abroad:

1001 0100 ₂ ⊕ 0110 0101 ₂ = 1111 0001 ₂ = 241 ₁₀ .

The last 256 element is set equal to 0. The result is such an S-block:

  1 2 4 8 16 32 64 128
  101 202 241 135 107 214 201 247
  139 115 230 169 55 110 220 221
  223 219 211 195 227 163 35 70
  140 125 250 145 71 142 121 242
  129 103 206 249 151 75 150 73
  146 65 130 97 194 225 167 43
   86 172 61 122 244 141 127 254
  153 87 174 57 114 228 173 63
  126 252 157 95 190 25 50 100
  200 245 143 123 246 137 119 238
  185 23 46 92 184 21 42 84
  168 53 106 212 205 255 155 83
  166 41 82 164 45 90 180 13
   26 52 104 208 197 239 187 19
   38 76 152 85 170 49 98 196
  237 191 27 54 108 216 213 207
  251 147 67 134 105 210 193 231
  171 51 102 204 253 159 91 182
    9 18 36 72 144 69 138 113 113
  226 161 39 78 156 93 186 17
   34 68 136 117 234 177 7 14
   28 56 112 224 165 47 94 188
   29 58 116 232 181 15 30 60
  120 240 133 111 222 217 215 203
  243 131 99 198 233 183 11 22
   44 88 176 5 10 20 40 80
  160 37 74 148 77 154 81 162
   33 66 132 109 218 209 199 235
  179 3 6 12 24 48 96 192
  229 175 59 118 236 189 31 62
  124 248 149 79 158 89 178 0

Going deeper into the theory, we can summarize: Let there be a Galois field GF (2 ⁸ ) and a polynomial defining this field - p (x) = x ⁸ + x ⁶ + x ⁵ + x ² +1 and let α be a primitive element of the field, p ( α) = 0. Then the element f (x) in the S-block with index x can be represented as $f(x)=\left\{{\begin{matrix}\alpha ^{x},&x\neq 255,\\0,&x=255;\\\end{matrix}}\right.$ ${\ displaystyle f (x) = \ left \ {{\ begin {matrix} \ alpha ^ {x}, & x \ neq 255, \\ 0, & x = 255; \\\ end {matrix}} \ right.}$

Properties of functions used

f (x)

During one execution of MAGENTA, the f (x) function is calculated 2304 times for 128 and 192 bit keys and 3072 times for 256 bit key. Since the function is a nonlinear part of the algorithm, it is of particular importance for the analysis of the entire algorithm. The following properties of f (x) are known:

f (x) is a one-to-one function, that is, a permutation over the set B = {0,1} ⁸ - of all eight-bit binary vectors.
This permutation can be represented as the result of 6 unrelated cycles of length 198 38 9 5 5 and 1. According to combinatorial analysis, these values are “normal” and do not differ significantly from similar cycles for random permutations. The singular remaining in place is 161.
∀x ∈ B and such that f (x) ∈ {1,2, ... 127} holds:

f (x + 1) = 2 ∙ f (x), where ∙ is the product of decimal numbers. ∀ (x, y) ∈B ² and such that f (x) ∙ f (y) ∈ {1,2, ... 255} it holds that f ((x + y) mod 255) = f (x) ∙ f (y)

If we consider f (x) as a vector function, that is, f (x) = (f ₇ (x), f ₆ (x), ... f ₀ (x)), then each of the 8 Boolean functions is non-linear and of degree 7. Also all kinds of nontrivial XOR combinations of these functions are nonlinear. An explicit representation of these functions can be found here. ^[7] Another interesting property is that each such function has 128 terms.

PE (x, y)

Cryptanalysis

Differential Cryptanalysis

It turns out that at least part of MAGENTA can be opened by the methods of this cryptanalysis. The difference between two elements (plaintext or ciphers) is taken modulo 2 addition between these elements. This determination of the difference is due to the frequent use of the xor operation in this cipher. XOR table row indexes are all kinds of differences between plaintexts, and column indexes are ciphertexts. At the intersection of a specific difference in plaintext, that is, a string index, and a specific difference in ciphers, that is, a column index, is the number of plaintext pairs satisfying this difference, whose ciphers differ by column index. The XOR table for function f is 256 * 256 in size. The sum of each row and column is 256. The first element of the first row (with index 0), corresponding to the zero difference of plaintext and cipher, is 256. All the rest of the first row are equal to 0. Similarly, all elements of 1 column, except the first, equal to 256, are equal 0. Of particular interest for differential analysis are large values - the largest value in this table is 8. It takes place with such differences

Difference between plain text	Difference between ciphers
51	35, 66, 154, 155, 250
102	111, 114, 232, 233, 244
153	96, 97, 115, 229, 247
204	18, 19, 38, 207, 251

The remaining cells of the table contain numbers 0, 2, 4, 6. The maximum probability of a transition for nonzero differences is ${\tfrac {8}{256}}=2^{-5}$ ${\ displaystyle {\ tfrac {8} {256}} = 2 ^ {- 5}}$ .
For the PE function - maximum values were also determined - it is 36 for the difference in the plaintext (234, 234) and the zero difference in the ciphers. The maximum probability of transition is ${\tfrac {36}{256^{2}}}$ ${\ displaystyle {\ tfrac {36} {256 ^ {2}}}}$ ≈ ${\tfrac {1}{1820}}$ ${\ displaystyle {\ tfrac {1} {1820}}}$ .
The maximum transition probability for the function T is $2^{-20}$ ${\ displaystyle 2 ^ {- 20}}$ , for C (3, X) - $2^{-60}$ ${\ displaystyle 2 ^ {- 60}}$ . Since the number of cipher pairs required is greater than the reciprocal of the transition probability, this type of differential analysis based on xor tables is not applicable to MAGENTA. However, the question of other types remains open.

Linear Cryptanalysis

A linear approximation table for the S-block was calculated. ^[8] . For functions $f_{0},...,f_{7}$ ${\ displaystyle f_ {0}, ..., f_ {7}}$ and for each xor-sum $f_{0}\oplus f_{1},f_{0}\oplus f_{2},...,f_{0}\oplus f_{1}\oplus ...\oplus f_{7}$ ${\ displaystyle f_ {0} \ oplus f_ {1}, f_ {0} \ oplus f_ {2}, ..., f_ {0} \ oplus f_ {1} \ oplus ... \ oplus f_ {7} }$ as for all linear functions, it was determined how many digits of values in the table are consistent with the corresponding digits of the considered linear functions. As a result, 255 values were obtained between 0 and 256. The normalization was to subtract 128. All values in the table lay on the interval [-24; 26]. These values are as expected for randomly selected $f_{0},...,f_{7}$ ${\ displaystyle f_ {0}, ..., f_ {7}}$ . A value of 26 is obtained with the following linear combinations:

$f_{1}\oplus f_{2}\oplus f_{3},f_{1}\oplus f_{3}\oplus f_{4}\oplus f_{6},$ ${\ displaystyle f_ {1} \ oplus f_ {2} \ oplus f_ {3}, f_ {1} \ oplus f_ {3} \ oplus f_ {4} \ oplus f_ {6},}$

$f_{1}\oplus f_{3}\oplus f_{6},f_{2}\oplus f_{3}\oplus f_{4}\oplus f_{6},$ ${\ displaystyle f_ {1} \ oplus f_ {3} \ oplus f_ {6}, f_ {2} \ oplus f_ {3} \ oplus f_ {4} \ oplus f_ {6},}$

$f_{1}\oplus f_{4}\oplus f_{7},f_{2}\oplus f_{3}\oplus f_{5}\oplus f_{6},$ ${\ displaystyle f_ {1} \ oplus f_ {4} \ oplus f_ {7}, f_ {2} \ oplus f_ {3} \ oplus f_ {5} \ oplus f_ {6},}$

$f_{2}\oplus f_{6}\oplus f_{7},f_{3}\oplus f_{4}\oplus f_{5}\oplus f_{6}.$ ${\ displaystyle f_ {2} \ oplus f_ {6} \ oplus f_ {7}, f_ {3} \ oplus f_ {4} \ oplus f_ {5} \ oplus f_ {6}.}$

Applying the sign-on lemma to the round function F ( $p_{i}=0.6$ ${\ displaystyle p_ {i} = 0.6}$ , l = 12)

${\frac {1}{2}}+2^{l-1}\prod _{i=1}^{l}p_{i}\approx {\frac {1}{2}}+2\cdot 10^{-9}$ ${\ displaystyle {\ frac {1} {2}} + 2 ^ {l-1} \ prod _ {i = 1} ^ {l} p_ {i} \ approx {\ frac {1} {2}} + 2 \ cdot 10 ^ {- 9}}$ The value obtained is the upper limit of the best affine transformation for F. Approximately $p^{-2}$ ${\ displaystyle p ^ {- 2}}$ plain text pairs - the cipher is needed to use the affine linear approximation with probability ${\frac {1}{2}}+p$ ${\ displaystyle {\ frac {1} {2}} + p}$ ^[8] . Given the previous results, an attack on F requires $2.5\cdot 10^{17}$ ${\ displaystyle 2.5 \ cdot 10 ^ {17}}$ . Therefore, due to the nonlinearity of f (x), MAGENTA will not be able to crack by attacks based on linear cryptanalysis.

Notes

↑ K. Huber. Neue Kryptographische Verfahren durch Kombination von Operationen in endlichen K? Örpern mit der schnellen Walshtransformation. Unpublished manuscript, 1990.
↑ K. Huber and S. Wolter. Telekom's MAGENTA algorithm for en- / decryption in the gigabit / sec range. In ICASSP 1996 Conference Proceedings, volume 6, pages 3233 - 3235, 1996.
↑ JP Vaseur. Verschl? Uesselungsanordnung mit Mischverdrahtung. Deutsches Patentamt Auslegeschrift 1148397, Anmeldetag: 2.Juni 1959, Auslegeschrift: 9.Mai 1963, Anmelder: Compagnie Generale de Telegraphie sans Fil, Paris.
↑ SY Kung. VLSI Array Processors. Prentice Hall, 1988.
↑ M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Computing, 17 (2): 373-386, April 1988.
↑ J. Pieprzyk and B. Sadeghiyan. Design of Hashing Algorithms, volume 756 of Lecture Notes in Computer Science. Springer, 1993.
↑ SIT GmbH. Abschlussbericht - Untersuchung eines universellen Kryptoalgorithmus. Technical report, SIT GmbH, 1994.
↑ ¹ ² E. Biham. On Matsui's linear cryptanalysis. In Proc. EUROCRYPT '94, volume 658 of Lecture Notes in Computer Science, pages 81-91, 1995.

Links

MJ Jacobson, Jr. and K. Hubery The MAGENTA Block Cipher Algorithm
JJG Savard. The Computer Era. Towards the 128-bit era: AES Candidates. Magenta // A Cryptographic Compendium
El Biham, Al. Biryukov, N. Ferguson, LR Knudsen, B. Schneier, Ad. Shamir Cryptanalysis of Magenta

[1] K. Huber. Neue Kryptographische Verfahren durch Kombination von Operationen in endlichen K? Örpern mit der schnellen Walshtransformation. Unpublished manuscript, 1990.

[2] K. Huber and S. Wolter. Telekom's MAGENTA algorithm for en- / decryption in the gigabit / sec range. In ICASSP 1996 Conference Proceedings, volume 6, pages 3233 - 3235, 1996.

[3] JP Vaseur. Verschl? Uesselungsanordnung mit Mischverdrahtung. Deutsches Patentamt Auslegeschrift 1148397, Anmeldetag: 2.Juni 1959, Auslegeschrift: 9.Mai 1963, Anmelder: Compagnie Generale de Telegraphie sans Fil, Paris.

[4] SY Kung. VLSI Array Processors. Prentice Hall, 1988.

[5] M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Computing, 17 (2): 373-386, April 1988.

[6] J. Pieprzyk and B. Sadeghiyan. Design of Hashing Algorithms, volume 756 of Lecture Notes in Computer Science. Springer, 1993.

[7] SIT GmbH. Abschlussbericht - Untersuchung eines universellen Kryptoalgorithmus. Technical report, SIT GmbH, 1994.

[линейный_криптоанализ-8] ¹ ² E. Biham. On Matsui's linear cryptanalysis. In Proc. EUROCRYPT '94, volume 658 of Lecture Notes in Computer Science, pages 81-91, 1995.