Talk:XXTEA

Cryptography: Computer science Low‑importance

	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.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
Low	This article has been rated as Low-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Low-importance).

XXTEA broken ?

An XXTEA differential attack demonstration

Collisions

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)[reply]

What do you mean by unpublished?

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)[reply]

Legal implications of using the provided code verbatim

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)[reply]

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)[reply]

Using this code without modification is a bad idea. It contains obvious bugs. Haael (talk) 09:19, 4 July 2010 (UTC)[reply]

Partial Ciphertext Collisions

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 2⁴⁸. 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 2⁹⁶ 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)[reply]

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)[reply]

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)[reply]

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)[reply]

Then consider it noted in a published work. Ruptor (talk) 16:11, 17 April 2008 (UTC)[reply]

Which work, so that others can look it up? --Damian Yerrick (talk | stalk) 16:51, 17 April 2008 (UTC)[reply]

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)[reply]

Cryptanalysis by Yarrkov

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 2⁵⁹ 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)[reply]

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 2^34.7 queries and the test confirmed this complexity. The attack aginst the full 6-round XXTEA is conjectured to take 2⁵⁹ 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 2³⁵ chosen plaintext query pairs, about 2^34.7 being the expected number"

"While the method doesn’t give an exact probability, it is reasonable and provides consistent output. Thus, about 2⁵⁹ 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)[reply]

I have invited the editor, User:Robwentworth to this thread. -- intgr [talk] 14:30, 10 September 2012 (UTC)[reply]

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)[reply]

Round diagram image wrong?

The image in the summary does not look accurate, X_r-1 and X_r+1 need to be switched. According to the specification y, which holds the data for the next block, is shifted by 2 and 3; and z, holding the data from the previous block, as being shifted by 5 and 4. The specification also has z XOR the sub-key and y XOR the delta multiple, the image shows the opposite to all these. — Preceding unsigned comment added by Informalmunch (talk • contribs) 23:06, 22 January 2015 (UTC)[reply]

@Ruptor: Are you still active on Wikipedia? Since you're the author of the original image File:Algorithm diagram for XXTEA cipher.png, it seems that Informalmunch is correct. -- intgr [talk] 09:40, 23 January 2015 (UTC)[reply]

I can go ahead and edit the image, citing the original artist if they arn't around to do it themselvesInformalmunch (talk) 16:33, 18 February 2015 (UTC)[reply]