Wednesday, 13 April 2011

XTEA Encryption Interoperability

Recently someone I work with had a requirement to encrypt data in the browser on the client (ActionScript) and have the data decrypted on the server (Java).  His initial approach was to use the XTEA[1][2] encryption algorithm (XTEA = eXtended TEA, where TEA = Tiny Encryption Algorithm) due to its speed and ease of implementation.  XTEA implementations were found for both Java[3][4] and ActionScript[5][6].

After some quick testing, it became clear that while both implementations would encrypt text and then allow the encrypted text to be successfully decrypted, the two implementations would not interoperate.  They generated different cipher text given the same key and plain text.  I had some time available and was interested in the topic so I took a look at the code and did a little research.

As always, the devil is in the details.  The core of the two algorithms looked basically the same, but there were some issues.  The Java package was a bare bones implementation.  You initialized a key and an operation (encrypt/decrypt) and then passed in 8 bytes of data and received back 8 bytes of processed data.  The ActionScript  class was similar, but the demo UI that I used for testing[7] wrapped the basic algorithm with additional functionality which provided a mode[8], padding, and an initialization vector.  Not being a Flex/ActionScript programmer, I was using the UI to test the ActionScript code, although my friend did set me up to allow debugging of the ActionScript code in Eclipse.  This proved invaluable as it allowed me to single step and see the state of the variables in the same manner as the Java code.

So the first challenge was to see if I could determine how to remove the mode/padding/initialization vector from the equation.  After some research I determined that if I insured that my plain text was a multiple of 8 bytes then I could specify NONE for the padding method.  Similarly, the ECB or Electronic Code Book mode encrypts each block of 8 characters using only the key without any feedback from other plain text or cipher text.  Specifying ECB essentially eliminated the mode as an issue, and since the initialization vector is not used in ECB it went away as well.

Next up was character encoding.  Since I was starting with Strings as my plain text in Java, I needed to insure that the bytes returned by getBytes() matched those being processed in the browser.  I specified the US-ASCII character set in my getBytes() call and verified that on the browser I was getting the same bytes being passed into the XTEA encrypt method on the client.  However, the encrypted results were still different on the two platforms.

I took a closer look at the code and saw some differences:

  1. The ActionScript code was performing 64 rounds while the Java code was only performing 32.  I changed the Java code to 64.

  2. The ActionScript code was initializing the 'sum' to the 'delta' value times the number of rounds for decryption.  The java code was initializing it to a constant, which as it turns out was equal to 32 * the 'delta' value.  I changed the initialization to be ROUNDS * DELTA so when ROUNDS changes the 'sum' initialization would change appropriately.

  3. The packing and unpacking of data bytes and key bytes differed between the two implementations.  In the Java version, byte 0 of the input was being placed in the low order position (bits 24 to 31 of the first 32 bit word), the second to the left of the first (bits 16 to 23), so a single-byte character stream coming in like this: A B C D E F G H would end up in the two 32 bit words like this:  D C B A   H G F E.  The ActionScript ordered them in the manner that I would expect (A B C D  E F G H).  I modified the Java code to do the same as the ActionScript for the data packing, unpacking, and the key packing.  Note that I am not sure which way is correct, I just changed the Java side because it made more sense to me, and it was easier for me.

  4. Lastly, I determined after a significant amount of effort and some dumb luck that the ActionScript implementation had a bug.  The right shifts in the code (>> ) should be unsigned right shifts (>>> ) otherwise the high order bit gets replicated instead of being replaced with a zero.  After I figured this out, I went to post an issue against the project and there was already an issue posted :o  egg on my face.

After these four changes, the cipher text from each implementation matched for the same input, and the decryption for both implementations successfully decrypted the cipher text.

The final modified ActionScript code is here[9] and the final modified Java code is here[10].  There is a license file associated with the ActionScript code, and it is here[11].

As time permits I will be looking into the following:
  • Adding mode and padding support around the Java code
  • Publishing a set of expected cipher text values given a set of input values.  There doesn't seem to be any practical way to insure that an algorithm is generating the correct results.  This appears to have resulted in various incompatible (and possibly incorrect) implementations out on the web.
  • Looking into extending the javax.crypto Service Provider Interface so XTEA can be easily integrated into any Java app using standard interfaces.
  • Look into writing a Javascript version of XTEA

[1] XTEA algorithm description
[2] TEA/XTEA Background and History
[3] Original Java XTEA implementation source code 
[4] Copy of original Java XTEA implementation source code on my server, just in case 
[5] Original ActionScript XTEA Implementation   
[6] Copy of original ActionScript XTEA implementation source code on my server, just in case  
[7] ActionScript Crypto Package Demo UI
[8] Block Cipher modes of operation and padding 
[9] Modified Java XTEA implementation source
[10] Modified ActionScript XTEA implementation source
[11] Crypto package license file



Technorati Tags:

Posted by john at 3:16 PM in Cryptography
« May »