Analysis of a key exchange protocol based on tropical matrix algebra

1 Introduction

In this paper, we analyze a key-exchange protocol based on tropical matrix algebra proposed in [3, Section 2]. Ideas similar to [3] were used before in the “classic” case, i.e., for algebras with familiar addition and multiplication. However, in the classic case, these schemes were shown to be vulnerable to various linear algebra attacks. The idea to use an algebra with another addition and multiplication came as an attempt to avoid those attacks, as there are no known algorithms for solving systems of linear equations in tropical sense (it is an active field of research currently).

2 Simple heuristic for original key generation method

In this section we argue that one can find a solution of system (1) by a very simple heuristic when the public information is generated as proposed in [3].

Consider a particular 3×3 matrix A with entries chosen uniformly randomly in the range [-100,100]

and its tropical powers

As we can see the entries in A⊗i very soon become negative and decrease linearly with i. In a linear combination of the matrices A⊗i with sufficiently small coefficients xi, say -10≤xi≤10, smaller monomials are irrelevant compared with the leading monomial, i.e., for any choice of the coefficients -10≤xi≤10 we have

This is precisely the case for key generation proposed in [3]. Half of the entries in A and B have negative value. The entries in the tropical-powers A⊗i and B⊗i become all negative very fast (when i≥2) and decrease faster than the range for coefficients which makes lower monomials in the polynomials p1,p2 irrelevant. Based on that observation one can expect that system (1) has a solution of the form

for some i,j∈[1,D] and c∈ℤ, where D is the upper bound for degrees of polynomials in the protocol.

This gives us the following simple heuristic attack. For each i,j∈[1,D] we compute the matrix

If Ti⁢j=(c)k⁢l for some constant c, then X=c⊗A⊗i, Y=B⊗j is a required solution to (1), and the algorithm successfully stops. If there are not such i and j, then the algorithm fails.

Table 1 shows success rates of the described algorithm for different key-generation strategies. If the keys are generated as originally proposed, then the success rate is 97%. Success rate decreases to 71% if we allow a larger range for coefficients in polynomials p1,p2. It becomes negligible if we allow only non-negative entries in A and B. Below we suggest an attack which works well in this case.

3 General attack

In this section we discuss a general attack on the protocol. The success rate of this attack does not depend on parameters of key generation and equals 100 %. We find matrices X and Y of the form

with unknown coefficients xi,yj∈ℤ. Clearly for such matrices the first and the second equality in (1) are satisfied. Notice that

Therefore, to break the protocol, we need to find x0,…,xD,y0,…,yD∈ℤ such that

where Vi⁢j=A⊗i⊗B⊗j. Using the definition of ⊕ and ⊗, we get a system of equations

This system is equivalent to the following system:

where Ti⁢j=Vi⁢j-U. Solving system (2) is the main goal of this section.

Denote by mi⁢j the least entry in the matrix Ti⁢j and by Pi⁢j the set of entries where the minimum is achieved:

Notice that any solution xi,yj, 0≤i,j≤D, of (2) satisfies the following conditions:

1. xi+yj≥-mi⁢j.

2. For every k,l there exist i,j such that (k,l)∈Pi⁢j and xi+yj=-mi⁢j.

Therefore, to solve (2), we need to find a cover C⊆{P00,P01,…,PD⁢D} of the set [1,n]×[1,n] and values xi,yj, 0≤i,j≤D, satisfying

Hence, in order to solve (2), we need to enumerate all minimal covers for [1,n]×[1,n] and then find those that define consistent systems of equalities and inequalities (3).

Recall that finding a minimal set cover problem is one of Karp’s 21 problems shown to be NP-complete in 1972. Nevertheless, for all randomly generated instances of the protocol it was relatively easy to enumerate all possible minimal covers.

We generate a set containing all the minimal covers using simple recursive procedure. As one can see in Table 2, often the number of covers is small, and rarely it is greater than 10,000. In every experiment we were able to enumerate them in a few seconds.

Also, we noticed that often an appropriate cover (a cover defining a consistent system (3)) is smaller than most other covers produced by our algorithm. Furthermore, for covers of the same size an appropriate cover often has smaller value of

than others. Therefore, to speed up computations, we sort the covers using these heuristic criteria. This strategy works very well, as shown in Table 2, on average we have to test only one or two covers to find a solution.

Finally, to determine if a system (3) is consistent for a particular cover C, we use the simplex method, see [2].

The described attacks were implemented in GAP [8]. The implementation can be found in [4]. Our tests were run on Intel Core i3 1.50 GHz computer with 4 GB of RAM, Ubuntu 14.04, GAP 4.7. We generated 100 random instances for every set of parameters presented in the tables.

4 Conclusion

The protocol described in [3, Section 2] is not secure when used with the proposed parameter values. It is not clear how to modify key generation to provide a sufficient level of security. We encourage an interested reader to use our code [4] and perform their computational experiments over the tropical algebra.