Cryptanalysis of the TTM Cryptosystem

In 1985 Fell and Diffie proposed constructing trapdoor functions with multivariate equations [11]. They used several sequentially solved stages that combine into a triangular system we call T. In the present paper, we study a more general family of TPM (for “Triangle Plus Minus”) schemes: a triangular construction mixed with some u random polynomials and with some r of the beginning equations removed. We go beyond all previous attacks proposed on such cryptosystems using a low degree component of the inverse function. The cryptanalysis of TPM is reduced to a simple linear algebra problem called MinRank(r): Find a linear combination of given matrices that has a small rank r. We introduce a new attack for MinRank called ‘Kernel Attack’ that works for qr small. We explain that TPM schemes can be used in encryption only if qr is small and therefore they are not secure.As an application, we showed that the TTM cryptosystem proposed by T.T. Moh at CrypTec’99 [15],[16] reduces to MinRank(2). Thus, though the cleartext size is 512 bits, we break it in O(252). The particular TTM of [15],[16] can be broken in O(228) due additional weaknesses, and we needed only few minutes to solve the challenge TTM 2.1. from the website of the TTM selling company, US Data Security.We also studied TPM in signature, possible only if qu small. It is equally insecure: the ‘Degeneracy Attack’ we introduce runs in qu· polynomial.