In what way is XXTEA really vulnerable? I'm looking at using the XXTEA algorithm to encrypt a small amount of data (say, less than 32KB) in the context of a software licensing algorithm. That is, we wish to make it difficult (not impossible) for our customers to forge (encrypted) license files of their own.

Our intent is that our software will read the encrypted license file when it starts up. It will decrypt it with a key that is embedded in the executable. The license file will be read from disk and decrypted. The results of the decryption are then copied into a set of C language structures that contain licensing information.

We are looking to create something that prevents casual attempts to defeat the licensing mechanism. We are not trying to create a system that stands up to someone willing to invest a significant amount of time and effort in defeating the system.

The encrypting algorithm I'd like to use is XXTEA, using the "clarified" code from the bottom of the XXTEA Wikipedia page without modification: http://en.wikipedia.org/wiki/XXTEA

Our Intellectual Property lawyer is questioning this decision. He claims that the algorithm is weak and that we should find a better one. I disagree, since there are other, simpler ways to defeat the licensing mechanism than launching a cryptographic attack on the license file data. 

However, I'm not a cryptographer and so I don't know how to interpret statements like these:


  XXTEA is vulnerable to a chosen-plaintext attack requiring 2**59 queries and negligible work. See cryptanalysis below.


and


  However, due to the incomplete nature of the round function, two large
  ciphertexts of 53 or more 32-bit words identical in all but 12 words
  can be found by a simple brute-force collision search requiring
  2*(96−N) memory, 2*N time and 2*N+2*(96−N) chosen plaintexts, in
  other words with a total time*memory complexity of 296, which is
  actually 2**(wordsize*fullcycles/2) for any such cipher. It is
  currently unknown if such partial collisions pose any threat to the
  security of the cipher. Eight full cycles would raise the bar for such
  collision search above complexity of parallel brute-force attacks.


I would be grateful for any advice on the vulnerabilities and/or reasonableness of what we are proposing to do.
XXTEA (also known as Corrected Block TEA) is a block cipher with $128$-bit key and block width parameterizable to $n\cdot32$ bits for $n\ge2$. It is an Unbalanced Feistel Cipher making $q=6+\lfloor52/n\rfloor$ passes over the block, with $q\cdot n$ rounds each modifying $32$ bits of the block. The round function is a simple Add-Rotate-Xor function of two 32-bit words (one for $n=2$), which are the next and previous ones modified in the round.

In Cryptanalysis of XXTEA, it is presented a chosen-plaintext attack, making use of differential cryptanalysis, recovering the key with about $2^{59}$ chosen-plaintext/ciphertext pairs and work comparable to enciphering that amount of data, applicable when $q=6$, that is $n&gt;52$. The article is not peer-reviewed, but the argument seems plausible to me, and I take this attack as a given.

The practical significance of the attack in the context of the question is very low. That's because there is no way the attacker can obtain even a tiny fraction of the required ciphertext from the original publisher, much less with chosen plaintext; thus the only way that even a huge improvement of the attack could be performed is by using some derivative form of the original software with its original key as an encryption mean. The assumed attacker then has the key right in the software it is trying to use, and can recover it by reverse engineering (like stepping execution). Given the tremendous number of encryptions necessary, the attacker must deeply optimize its software, thus will have no trouble to spot the key. Therefore, the only practical risk I can see of using XXTEA (rather then an unbroken symmetric cipher and operating mode) in the context of the question is a tiny one of image for the publisher: one could demonstrate that the software is using a broken algorithm.

There's an easy solution to that: repair the algorithm by increasing the number of passes, e.g. by changing to q = 6 + 52/n to q = 16 + 52/n in the source code. This single-character insertion is more than adequate to block any attack remotely similar to the existing one, with a much less than threefold reduction in performance, entirely acceptable in the context. Update: If we want to keep the original $32$ rounds for the minimum $n=2$, which motivate the constant $52$, we should make an extra change and use q = 16 + 32/n.



The question does not detail how XXTEA would be used in the licensing scheme: it is not stated in which direction the data transfer is, and if the goal is to protect confidentiality or integrity. I note that towards that later goal, enciphering the whole data as a single block with some fixed field (checked after decryption, and wide enough, say at least $10$ bytes) is sound, because changes in the ciphertext propagate everywhere in the plaintext. That would not be achieved using the more conventional approach of a fixed-block-size cipher in some operating mode like CBC or CTR.

I must point out that public-key cryptography can make sense in this context: it allows enciphering data to the publisher and verifying integrity of data from the publisher without any secret key on the customer side. This in turn enables things theoretically impossible with symmetric algorithms. In particular, even assuming that an attacker has a rightfully licensed software, and gains complete understanding of how the copy-protection works, it remains impossible to illegitimately activate an unmodified copy of the software on another computer, assumed to be distinguishable from the licensed one by some identifier(s), such as MAC address, disk serial number, volume ID, OS-supplied UUID. The best attacks would require modifying the software, or the APIs it uses to get the identifiers (which nowadays is often as easy as licensing the software in a virtual machine, then cloning that).



Update: I'm facing a reasonable diverging opinion, stating that "You should never ever use a cipher or a hash function, that has been broken in academic terms". I agree with that advise in general when defining a new system, and I do suggest to at least summarily repair the academically broken XXTEA rather than use it as is. But there are a few exceptions beside using deployed gear with a minor dent when the risk is acceptable (which is common and perfectly justifiable). One such exception is when using a cryptographic primitive outside the normal hypothesis of cryptography, in particular this cornerstone: the key of a block cipher is assumed secret. Here we are in software copy protection, and in that game the key is next to the hands of the adversary; that makes cryptanalytic resistance of secondary importance. What is much more important is that the code using cryptography is hard to locate and  circumvent, and that means one should avoid use of standard cryptographic libraries, or OS-provided cryptographic APIs. This is one of few cases where rolling one's own implementation of cryptographic code is justified; then, given the secondary importance of cryptanalytic resistance, the simplicity of XXTEA (combined with a static field anywhere in the plaintext for authentication purposes) is appealing compared to the complexity of AES-GCM, which in addition is arguably more likely to become practically vulnerable in the field due to a weakness in the TRNG or whatever is used for the initial value of the counter.