TTM

The (unofficial) web page for the TTM public key cryptosystem invented by T.T. Moh.

News, recent events:

Up to 100 000 dollars offered for breaking TTS. See here.

The story of TTM:

On May 2nd, 2000 Nicolas Courtois and Louis Goubin broke a class of cryptosystems that included TTM as it was initially proposed by T.T.Moh and U.S. Data Security inc. In the paper published at Asiacrypt 2000, Kyoto, Japan the attack is described. The TTM 2.1. contest for 1000$ by U.S. Data Security inc. has been broken all too easily. The answer is:

"Tao TTP way BCKP of living hui mountain wen river moon love pt".

Our improved program found the result in 3 minutes, but U.S. Data Security inc. has never paid us the 1000$. It is true that we did not recover the secret key (they don't even understand the basic fact that a cryptosystem can be broken without recovering the secret key). In fact we could recover it with a little additional work, but we don't actually believe that U.S. Data Security inc. will ever keep their promise anyway. For instance they removed their contest TTM 2.3. for 5000$, fearing it would be broken, and will probably replace it later with something else, after they can read our paper and figure out how to get it right.

Recent developments:

Since T.T. Moh claimed that TTM is secure when new improved polynomials were used inside. Even if it were, which is doubtful because no convincing example is given, TTM is much less interesting that other multivariate schemes such as Hfe/Quartz /Flash /Sflash etc.
In an example given by T.T. Moh, found in a rather annoying e-mail sent to many people from the crypto community, it would have the security of 2^115 for a 352-bits cryptosystem. Well, most other multivariate schemes will achieve the security of about 2^115, already for a 128-bit cryptosystem.

Moreover, if you look closely at the example found on the page 5 of this document, and if you read our paper from Asiacrypt 2000, you will understand that in fact this system is exactly as weak as described in the paper. It will be broken in essentially 2^52, because we found MinRank solutions with r=2, and not r=8 as claimed in the document. It is even weaker, because there are several such MinRank solutions and you can combine them to recover single variables....

Since the system given in the paper is actually broken with r=2, and not r=8 as claimed, there are all reasons to believe that the second 1000 $ challenge (TTM 2.2. called also Learner's Challenge II+) has also probably r=2 and is broken in about 2^52 too...
Amazingly enough, just after that we told that at Asiacrypt 2000 conference, U.S.Data Security desactivated all their challenges on the internet. They don't give any ciphertext anymore....

Tzuong-Tsieng Moh home page at Purdue University, USA

U.S. Data Security documents about Ttm.

The full paper from Asiacrypt about the cryptanalysis of TTM

Slides from the Asiacrypt 2000 talk on the cryptanalysis of TTM.

Interesting links: multivariate cryptanalysis:
Algebraic attacks on AES, Rijndael, Serpent, Camellia, etc.., the XSL attack on block ciphers

Algebraic attacks (or XL attacks) applied to stream ciphers
Interesting links: multivariate cryptography:
The McEliece_based short signature scheme CFS
The HFE cryptosystem home page
The Minrank Zero-knowledge identification scheme
Quartz /Flash /Sflash signature schemes
Nicolas Courtois research page 
TTM cryptosystem, GPT cryptosystem