Talk:XXTEA

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science   
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the quality scale.
 ???  This article has not yet received a rating on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science.
 

XXTEA broken ?[edit]

An XXTEA differential attack demonstration

Collisions[edit]

Reference post: http://groups.google.com/group/sci.crypt/browse_thread/thread/5ed40f85e693ef04 Further investigation needs to be done with respect to the viability of this algorithms security.

-Anon. —Preceding unsigned comment added by 78.46.82.176 (talk) 18:45, 17 December 2008 (UTC)

What do you mean by unpublished?[edit]

From the article: "the algorithm was presented in an unpublished technical report in October 1998 (Wheeler and Needham, 1998)."

By "unpublished" do the editors mean an "unpublished work" in the copyright law sense of "author has not distributed copies of the work to the public", or only in the sense of "this article was first published outside of scholarly journals"? --Damian Yerrick (talk | stalk) 03:04, 4 October 2007 (UTC)

Legal implications of using the provided code verbatim[edit]

If I use the code provided in the article, without modification, in my own programs, what license would it be covered under? GFDL seems to be a strange license to release source code under. Is the code in the public domain, or covered by some other license like the GPL? Algebra 00:10, 11 October 2007 (UTC)

As far as I can tell, a derivative of PD code is also PD if the changes by themselves do not make an original work. --Damian Yerrick (talk | stalk) 22:27, 11 October 2007 (UTC)
Using this code without modification is a bad idea. It contains obvious bugs. Haael (talk) 09:19, 4 July 2010 (UTC)

Partial Ciphertext Collisions[edit]

If anyone can provide a reference to a cryptologic research paper explaining this simple phenomenon, please do. If not, please write one. Currently I only have a working C source code of a program that quickly finds partial state collisions for 3 full cycles of XXTEA or for 6 full cycles of an XXTEA-like cipher with 16-bit words with a total time*memory complexity naturally equal to 248. It's a simple demonstration of this natural quality of all such incomplete UFN constructions that are meant to support arbitrarily large blocks. A change in any given number of words cannot cover the entire unbounded block after any fixed number of cycles, therefore partial state collisions will always occur. For XXTEA, it is as complex as finding a collision between two 6-word (192-bit) random numbers, iterating the cipher through which the change will be canceled out on every cycle leaving the rest of the block unaffected. This 296 search is easily accellerated by a time-memory trade-off. My guess is that once found, such partial collisions can assist in key recovery with a simple algebraic or guess-and-determine attack. So personally, I would advise to use 8 full cycles for 128-bit security. Ruptor 23:35, 30 October 2007 (UTC)

Ruptor, Wikipedia is not the place for original research. Please provide a reference to formal cryptanalysis or remove the vulnerability paragraph. cdv (talk) 00:54, 11 April 2008 (UTC)
CDV, I know what Wikipedia is and what it isn't. It is certainly a place where people come to find knowledge. If I can't stick your nose into a reference to some old book where trivial TMTO algorithms for finding collisions are explained, it doesn't mean that this obvious property should not be pointed out. A working program for finding those collisions is no research. There is nothing to research. It's an obvious property that must be pointed out. But it is certainly NOT a vulnerability and there is no research proving that it is exploitable or not. This property is there whether there is an official "peer reviewed" academic publication describing it or not and removing that paragraph would be equivalent to disinformation. I have pointed it out in one of my papers published at the SASC-2008, but it is such a trivial thing that it is hardly worth writing a paper about. Ruptor (talk) 02:38, 12 April 2008 (UTC)
The "original research" policy is that, unless a fact has been noted in a published work, then it's not appropriate to include it in Wikipedia. — Matt Crypto 08:32, 12 April 2008 (UTC)
Then consider it noted in a published work. Ruptor (talk) 16:11, 17 April 2008 (UTC)
Which work, so that others can look it up? --Damian Yerrick (talk | stalk) 16:51, 17 April 2008 (UTC)
EnRUPT: First all-in-one symmetric cryptographic primitive. The SASC 2008 workshop record PDF.zip, page 268. Ruptor (talk) 22:50, 18 April 2008 (UTC)

Cryptanalysis by Yarrkov[edit]

I think the cryptanalysis be Yarrkov is currently misrepresented, and I'd like to use the talk page in order to avoid an edit war. In particular the author does indeed seem to claim that the attack using 259 chosen messages works against 6 rounds. Since this is too time consuming to verify in experiments, the author did the experiments with reduced round variants that require significantly less chosen messages. 178.195.225.28 (talk) 13:27, 9 September 2012 (UTC)

Agreed, this is the norm in the cryptanalysis community -- the attack is tested on reduced-round versions and then conjectured how it applies to the full-round version. In cases where the full-round attack is less complex than a brute-force search, it is considered "broken".
In this case, breaking 4-round XXTEA was conjectured to take 234.7 queries and the test confirmed this complexity. The attack aginst the full 6-round XXTEA is conjectured to take 259 queries, but was not tested. Quoting relevant bits from the paper:
"The attack was succesfully used against XXTEA reduced to 4 of 6 full cycles. A right pair was found after about 235 chosen plaintext query pairs, about 234.7 being the expected number"
"While the method doesn’t give an exact probability, it is reasonable and provides consistent output. Thus, about 259 chosen plaintext queries is expected to be enough"
For another example, see the Biclique attack paper on AES (page 25, "On practical verification").
-- intgr [talk] 14:24, 10 September 2012 (UTC)
I have invited the editor, User:Robwentworth to this thread. -- intgr [talk] 14:30, 10 September 2012 (UTC)
Okay, I undid my revisions. I must have misinterpreted the Yarrkov details back when I read it. I think that XXTEA is still useful, especially if you increase the number of rounds enough. When the original TEA was written, 6 was the MINIMUM recommended (with a comment that it should be increased in the future when computers get more powerful). -- Robwentworth [talk] 17:20, 10 September 2012 (UTC)