Cryptanalysis of “MAKE”

1 Introduction

Ever since the invention in 1976 of the Diffie–Hellman key exchange [1] based on the multiplicative group of a finite field, researchers have investigated other groups and algebraic structures that can be used for similarly constructed key exchanges. A natural candidate was the general linear groups over the finite field F q of q elements. However, in 1997 Menezes and Wu [2] proved that the discrete log problem in the group GL( n , q ) of invertible n × n matrices is not more difficult than the discrete log problem in F q n ; therefore, a Diffie–Hellman key exchange in GL( n , q ) has no advantage over the original Diffie–Hellman construction.

Despite this result of Menezes and Wu, researchers have continued to look for ways to use matrix groups and semigroups for Diffie–Hellman style key exchange. Many of the specific constructions using such ideas have been broken, basically by exploiting an underlying linear structure. For example, Stickel’s nonabelian key exchange [3] was cryptanalyzed by Shpilrain [4] 3 years later; and the instantiation of a key exchange based on semidirect products in ref. [5] was cryptanalyzed shortly later in refs [6,7].

A recent construction of this type is the MAKE key exchange of Rahman and Shpilrain [8]. We analyze the latest posted version (February 2021) and show that MAKE also succumbs to a linear algebra attack – an adversary can recover the shared secret key by solving a system of n 2 linear equations. After describing the MAKE key exchange, we explain how the adversary can obtain such a linear system. We then give an alternative attack that leads to a system of n 4 linear equations that can be solved to give the entries in an ( n 2 × n 2 ) -matrix from which the shared key can immediately be found.

2 MAKE

The MAKE key exchange is based on the semidirect product of the additive group M n of n × n matrices and the product of two multiplicative semigroups consisting of powers of fixed H 1 , H 2 ∈ M n . More concretely, the analog of the k th power of a matrix M ∈ M n (where M plays the role of a generator of F q × in the classical Diffie–Hellman protocol) is the sum

In the protocol, Alice and Bob agree on three n × n matrices M , H 1 , and H 2 over the prime field of p elements (with p large), where H 1 and H 2 have determinant zero and do not commute with M . These three matrices are public. Alice chooses a secret positive integer x and Bob likewise chooses y . Alice can efficiently compute

and Bob computes the analogous sum B with x replaced by y . The shared key is then

which Alice and Bob can each compute using their secret key. Here H 1 , H 2 , and M are fixed parameters.

3 Telescoping

Note that although H 1 x B H 2 x is not publicly known, an adversary can multiply equation (1) by H 1 on the left and by H 2 on the right and then subtract equation (1) to obtain

and so the cryptanalyst can immediately compute H 1 x M H 2 x from the publicly known H 1 , H 2 , A , and M . Knowing H 1 x M H 2 x opens the way to a linear algebra attack.

4 Attack using Cayley–Hamilton

If we can find the entries in the matrix H 1 x B H 2 x , we are done by equation (2), because the shared secret key is obtained simply by adding A .

For a matrix H ∈ M n let H i j denote its i j -entry, 0 ≤ i , j ≤ n − 1 . Let vec ( H ) denote the column vector of height n 2 whose ( j n + i ) th entry is H i j ; thus, vec ( H ) is obtained by simply stringing the second column of H under the first column, the third column under the second column, and so on.

We now regard H 1 , H 2 ∈ M n and a positive integer x as fixed, and define a function L ( Y ) = L H 1 , H 2 ( Y ) from M n to M n 2 by setting

In other words, the ( h n + g ) th column of L ( Y ) is vec ( H 1 g Y H 2 h ) .

The Cayley–Hamilton theorem states that if P H ( λ ) = det ( λ I n − H ) is the characteristic polynomial of an n × n matrix H , then P H ( H ) = 0 . This allows one to express H x for x ≥ n in terms of H i , 0 ≤ i < n . By the Cayley–Hamilton theorem we can write

Define S ∈ M n by S i j = p i q j and set s = vec ( S ) .

The adversary first computes H 1 x M H 2 x by equation (3) and then solves the system of n 2 linear equations

for t . By Lemma 1 with Y = M , this system has at least one solution s ; and by Lemma 1 with Y = B , the same vector s also solves the system

We claim that the adversary’s vector t also satisfies

To see this, we set u = t − s . We apply Lemma 2 with Y = M for ℓ = 0 , 1 , … , y − 1 , and add. We find that

Hence, L ( B ) t = L ( B ) s + L ( B ) u = vec ( H 1 x B H 2 x ) by equation (4). From B and t the adversary can now recover H 1 x B H 2 x and hence the shared key z = A + H 1 x B H 2 x .

5 Attack by simulating Bob

Recall that the tensor product of an ( m 1 × n 1 ) -matrix X and an ( m 2 × n 2 ) -matrix Y is the ( m 1 m 2 × n 1 n 2 ) -matrix X ⊗ Y given by

We have the following identity for three matrices X , Y , Z whenever the product X Y Z is defined:

We also note that ( X ⊗ Y ) ℓ = X ℓ ⊗ Y ℓ . In particular,

From this and equation (2) it follows that if we can determine the unknown ( n 2 × n 2 ) -matrix H = ( H 2 T ⊗ H 1 ) x , we just have to compute H vec ( B ) + vec ( A ) to get the shared private key.

We find the n 4 unknown entries of H by obtaining n 4 independent linear equations that they satisfy. We do this in two ways: (1) by using a general commutativity property and (2) by simulating Bob with various choices of his secret y .

(1) The first method for finding equations uses only the parameters H 1 , H 2 and not the values A , B of a particular exchange of keys. Let I n denote the n × n identity matrix. The commutation relations

give us equations (6), where we again let H = ( H 2 T ⊗ H 1 ) x denote our unknown ( n 2 × n 2 ) -matrix and apply equation (5):

In numerical experiments with randomly chosen rank- ( n − 1 ) matrices H 1 and H 2 , these give n 2 ( n 2 − 1 ) independent equations for the n 4 entries of H , that is, just n 2 fewer than we need.

(2) Perhaps the simplest identity satisfied by H is H M = H 1 x M H 2 x , where the right side is publicly known by equation (3). This gives n 2 linear equations for the entries of H . We can regard this as the case y = 0 of the key exchange, that is, B = 0 , z = A . For any integer y ≥ 0 , we can write the equation

where the adversary, simulating Bob, chooses arbitrary^[1] y and then knows both sides except for the entries of H . If the value y = 0 does not give n 2 independent equations that are also independent of the n 2 ( n 2 − 1 ) equations from the commutation relations, then the adversary continues with y = 1 , 2 , 3 , … until they get the required number of independent equations. Numerical experiments indicate that a very few small values of y are sufficient.

6 Conclusion

The MAKE key exchange is insecure; the shared key can be recovered by linear algebra in polynomial time. This shows once again that even a matrix-based protocol that seems much more complicated than a standard Diffie–Hellman key exchange may have an essential linearity that makes it vulnerable. Caution seems to be especially necessary when considering matrix-based cryptosystems.