# 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.

-
It would probably be better to use authenticated encryption or a MAC, $\hspace{2.06 in}$ depending on whether or not you need confidentiality. $\;$ –  Ricky Demer Jan 17 at 21:14
I would tend to look at it from the other direction: do you have a specific reason to use something other than AES? If not, that's an obvious and safe choice (with many freely-available implementations). –  Jerry Coffin Jan 18 at 6:21
since the key is embedded in the executable, any weakness in a TEA variant is going to be much much harder to exploit than simply extracting the key, increasing the strength of the algorithm will not make the licensing any more secure. –  Richie Frame Jan 18 at 9:25
"there are other, simpler ways to defeat the licensing mechanism than launching a cryptographic attack on the license file data." I completely agree with that statement. But it's not clear to me that you actually want encryption in the first place. A MAC or a digital signature might fit your needs better. –  CodesInChaos Jan 20 at 9:58

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.

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>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.

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.

-
+1 for your Public-key section (seems I deleted my previous comment :/ ) –  figlesquidge Jan 20 at 18:00

The XXTEA cipher is badly broken. Even though the paper is not published at a conference, the author verified it on reduced versions of XXTEA.

You should never ever use a cipher or a hash function, that has been broken in academic terms, in particular if you are not a cryptographer. Attacks always get better, and a cipher does not attract much attention after the first successful attack if it is not a worldwide standard. So many better attacks have been just overlooked.

There are much better alternatives to XXTEA if you want to achieve confidentiality and integrity of the data. You should look for authenticated encryption schemes: AES-GCM, OCB, EAX.

-
I'd agree with you if this question were about actual security. But since this question is about DRM (a licensing scheme) it almost certainly relies on security-through-obscurity. Compared to the attacker simply extracting the key or patching the software, the risk arising from a weak blockcipher like XXTEA is probably negligible. –  CodesInChaos Jan 20 at 19:05
It is just a very bad practice to use broken schemes when there are unbroken alternatives. Environments often change, and a library with a weak cipher implemented might be used where it is critical. Another thing is that security-through-obscurity is usually about the implementation, but not about the cipher's output. If it were biased this would be seen at every scheme. –  Dmitry Khovratovich Jan 21 at 11:12
AES-GCM, OCB, EAX are not full replacement for XXTEA: they lack the desirable property of XXTEA that, even with a stalled TRNG (a failure that is easy to induce for the adversary in a DRM context when enciphering on the user/adversary side), any change in any bit of plaintext leads to a change in any bit of ciphertext (with odds 1/2). Also, AES-GCM, OCB, EAX.. are vastly more complex to implement, thus vastly more likely to be implemented using existing code or system functions, which makes it considerably easier to recover the key in a DRM context. –  fgrieu Jan 21 at 16:19

It seems to me that what you need is a public-key scheme like signatures.

The process would work something like this:

• A user license $L$ is created by your license generator
• Your system signs it to give $s(L)$ and the licence is $\{L,s(L)\}$.

When program tries to open the user's license $\{t,v\}$:

• The system verifies that $v$ is indeed a valid signature for $t$.
• If it is, then the program checks that $t$ makes sense as a valid set of attributes (ie $t$ has the format you'd expect it to). If $t$ does not have this format then $v$ is a fake.
• If both these tests are passed, program loads.
• If not, license is fake (presumably you'd send a copy of the fake to your servers?)
-