Paper 2001/072

On the Goubin-Courtois Attack on TTM

T. Moh and Jiun-Ming Chen

Abstract

In the paper [1] published in ``Asiacrypt 2000", L. Goubin and N.T. Courtois propose an attack on the TTM cryptosystem. In paper [1], they mispresent TTM cryptosystem. Then they jump an attack from an example of TTM to the general TTM cryptosystem. Finally they conclude:"There is very little hope that a secure triangular system (Tame transformation system in our terminology) will ever be proposed". This is serious challenge to many people working in the field. In this paper, we will show that their attack is full of gaps in section 5. Even their attack on one implementation of TTM is questionable. We write a lengthy introduction to restate TTM cryptosystem and point out many possible implementations. It will be clear that their attack on one implementation can not be generalized to attacks on other implementations. As one usually said: "truth is in the fine details", we quote and analysis their TPM system at the end of the introduction and $\S$ 2. We further state one implementations of TTM cryptosystem in $\S$ 3. We analysis their MiniRank(r) attack in $\S$ 4 and show that is infeasible. We conclude that the attack of [1] on the TTM cryptosystem is infeasible and full of gaps. There is no known attacks which can crack the TTM cryptosystem.