tea and xtea: making endianness configurable

[nmantani]

For tea and xtea commands, block operation is done with little endian.

Excerpt from refinery/units/crypto/cipher/tea.py:

def tea_block_operation(
    blk: Callable[[int, int, int, int, int, int], Tuple[int, int]]
) -> Callable[[TEA, ByteString], ByteString]:
    def wrapped(self: TEA, data: ByteString) -> ByteString:
        v0, v1 = blk(
            int.from_bytes(data[:4], 'little'),
            int.from_bytes(data[4:], 'little'),
            *self.derived_key
        )
        return v0.to_bytes(4, 'little') + v1.to_bytes(4, 'little')
    return wrapped

class TEABase(BlockCipher):

    block_size = 8
    valid_key_sizes = {16}
    derived_key: List[int]

    @property
    def key(self):
        return self.derived_key

    @key.setter
    def key(self, key):
        self.derived_key = [int.from_bytes(key[k:k + 4], 'little') for k in range(0, 16, 4)]

However, there are implementations of TEA and XTEA that block operation is done with big endian. For example, Crypt::XTEA Perl module has the little_endian option and the default is little_endian=0 (big endian). If block operation is done with big endian on encryption, tea and xtea commands cannot decrypt correctly. It would be great if endianness is configurable for tea and xtea commands.

A sample Perl script xtea.pl for encryption with XTEA:

use Crypt::XTEA;
use Crypt::ECB;

my $key = "0123456789abcdef";

# Little endian
my $xtea = Crypt::XTEA->new( $key, 32, little_endian => 1 );
my $ecb = Crypt::ECB->new( -cipher => $xtea );

my $text = 'This is a secret message.';
my $cipher_text = $ecb->encrypt( $text );
my $cipher_hex = unpack("H*", $cipher_text);

print("Ciphertext with little endian: $cipher_hex\n");

# Big endian (default)
$xtea = Crypt::XTEA->new( $key );
$ecb = Crypt::ECB->new( -cipher => $xtea );

$text = 'This is a secret message.';
$cipher_text = $ecb->encrypt( $text );
$cipher_hex = unpack("H*", $cipher_text);

print("Ciphertext with big endian: $cipher_hex\n");

Decryption results with xtea command:

$ perl xtea.pl
Ciphertext with little endian: a3bab9180f2ff58eb6d5bfe356fc2b436c9ae1338fee4cb70b626fd037e4a797
Ciphertext with big endian: eb7a1e2fe4de2699978ddfcec5bdd3649d654c0a7bc1c5c8b343cd8763afc88
$ echo -n a3bab9180f2ff58eb6d5bfe356fc2b436c9ae1338fee4cb70b626fd037e4a797 | hex | xtea -m ecb -L 0123456789abcdef | xxd
00000000: 5468 6973 2069 7320 6120 7365 6372 6574  This is a secret
00000010: 206d 6573 7361 6765 2e                    message.
$ echo -n eb7a1e2fe4de2699978ddfcec5bdd3649d654c0a7bc1c5c8b343cd8763afc883 | hex | xtea -m ecb -L 0123456789abcdef | xxd
00000000: 03dd 14c3 a150 5bf3 ffe0 a500 cc04 8402  .....P[.........
00000010: d7af 3dfa 64da 902b 3c87 1a19 72e2 22ab  ..=.d..+<...r.".
$

[huettenhain]

Got it. Makes perfect sense, I should be able to add this fairly quickly. Aiming for tomorrow.

[jhhcs]

Hey @nmantani, could you provide test strings for both big endian and little endian for TEA as well? You only had those for XTEA and I'd like to have tests for this before I push a change.

[jhhcs]

Oh and if that code you are working with also supports XXTEA, I would be grateful for test vectors for that one as well =).

[nmantani]

Sure! These are scripts to generate test strings for TEA. I will provide scripts for XXTEA later.

Perl script tea-big.pl for encryption with big endian (Crypt::TEA_XS module):

use Crypt::TEA_XS;
use Crypt::ECB;

my $key = "0123456789abcdef";

# Crypt::TEA_XS only supports big endian
my $tea = Crypt::TEA_XS->new( $key );
my $ecb = Crypt::ECB->new( -cipher => $tea );

my $text = 'This is a secret message.';
my $cipher_text = $ecb->encrypt( $text );
my $cipher_hex = unpack("H*", $cipher_text);

print("Ciphertext with big endian: $cipher_hex\n");

To use Crypt:TEA_XS module, TEA_XS.pm has to be modified as follows to avoid error. From:

use constant keysize => $KEY_SIZE;
use constant blocksize => $BLOCK_SIZE;

To:

sub keysize   () { 16 }
sub blocksize () {  8 }

TEA ciphertext with big endian:

$ perl tea-big.pl
Ciphertext with big endian: 18381cf66f04b5430236afbb34e8fc97878ef127b31b29356525faf2978a2726
$

Python script tea-little.py with little endian (tea-python module):

import tea
import Cryptodome.Util.Padding

key = b'0123456789abcdef'
plaintext = b'This is a secret message.'

# tea-python requires padding and only supports little endian
plaintext = Cryptodome.Util.Padding.pad(plaintext, 8)
ciphertext = tea.encrypt(plaintext, key)

print('Ciphertext with little endian: ' + ciphertext.hex())

TEA ciphertext with little endian:

PS > python.exe .\tea-little.py
Ciphertext with little endian: 518c4bf6048edaaeb5c760dd797f6f010c87feec5c7e3a08c942a4540ed494b3
PS >

[jhhcs]

This issue here was fixed in 83f030edbf82b2946955b7147044f16375e442bf, the units tea and xtea now have a --swap switch (shorthand -s) similar to the serpent unit, where I had similar issues around byte ordering. In b70fc2eaf550be9dfd96adaa789f1018d208d6f1 I added an equivalent option to xxtea, but it doesn't have any tests for the big endian version yet. I will add those as soon as you can provide some. I will close this issue out, and please let me know if you would like me to release a new version.

[nmantani]

Thank you! Regarding xxtea, encryption fails and the -p option does not work when the input data is not aligned to a multiple of 4 bytes.

$ echo "This is a secret message." | xxtea -R -R -p pkcs7 0123456789abcdef | xxd
(00:45:16) failure in xxtea: exception of type ValueError; The input data is not aligned to a multiple of 4 bytes.
$

And decryption fails with the -s option.

$ echo "This is a secret message..." | xxtea -R 0123456789abcdef | xxtea 0123456789abcdef | xxd
00000000: 5468 6973 2069 7320 6120 7365 6372 6574  This is a secret
00000010: 206d 6573 7361 6765 2e2e 2e0a             message....
$ echo "This is a secret message..." | xxtea -R -s 0123456789abcdef | xxtea -s 0123456789abcdef | xxd
00000000: 7bbd ce09 9034 1d47 a45a 5bdb ecb4 249d  {....4.G.Z[...$.
00000010: 7ecb d7db 0e87 bc69 8367 7612            ~......i.gv.
$

The fix for the decryption failure is as follows:

diff --git a/refinery/units/crypto/cipher/xxtea.py b/refinery/units/crypto/cipher/xxtea.py
index 66ac68a2..5f4cfc7d 100644
--- a/refinery/units/crypto/cipher/xxtea.py
+++ b/refinery/units/crypto/cipher/xxtea.py
@@ -51,7 +51,7 @@ class xxtea(BlockCipherUnitBase):
                 k = (p & 3) ^ e
                 x = ((z >> 5) ^ (y << 2)) + ((y >> 3) ^ (z << 4)) ^ (s ^ y) + (key[k] ^ z)
                 z = v[p] = v[p] + x & 0xFFFFFFFF
-        return chunks.pack(v, 4)
+        return chunks.pack(v, 4, self.args.swap)

     def decrypt(self, v: ByteString) -> ByteString:
         key = self._key
@@ -68,4 +68,4 @@ class xxtea(BlockCipherUnitBase):
                 x = ((z >> 5) ^ (y << 2)) + ((y >> 3) ^ (z << 4)) ^ (s ^ y) + (key[k] ^ z)
                 y = v[p] = v[p] - x & 0xFFFFFFFF
             s = s - 0x9E3779B9 & 0xFFFFFFFF
-        return chunks.pack(v, 4)
+        return chunks.pack(v, 4, self.args.swap)

With the fix:

$ echo "This is a secret message..." | xxtea -R 0123456789abcdef | xxtea 0123456789abcdef | xxd
00000000: 5468 6973 2069 7320 6120 7365 6372 6574  This is a secret
00000010: 206d 6573 7361 6765 2e2e 2e0a             message....
$ echo "This is a secret message..." | xxtea -R -s 0123456789abcdef | xxtea -s 0123456789abcdef | xxd
00000000: 5468 6973 2069 7320 6120 7365 6372 6574  This is a secret
00000010: 206d 6573 7361 6765 2e2e 2e0a             message....
$

I also tested compatibility with an other XXTEA implementation. I used the following Perl script xxtea-big.pl with Crypt::XXTEA_XS Perl module:

use Crypt::XXTEA_XS;
use Crypt::ECB;

my $key = "0123456789abcdef";

# Crypt::XXTEA_XS only supports big endian
my $xxtea = Crypt::XXTEA_XS->new( $key );
my $ecb = Crypt::ECB->new( -cipher => $xxtea );

my $text = 'This is a secret message.';
my $cipher_text = $ecb->encrypt( $text );
my $cipher_hex = unpack("H*", $cipher_text);

print("Ciphertext with big endian: $cipher_hex\n");

To use Crypt:XXTEA_XS module, XXTEA_XS.pm has to be modified as follows to avoid error. From:

use constant keysize => $KEY_SIZE;
use constant blocksize => $BLOCK_SIZE;

To:

sub keysize   () { 16 }
sub blocksize () {  8 }

XXTEA ciphertext with big endian:

$ perl xxtea-big.pl
Ciphertext with big endian: 4cbf21be1cf30657918e439b5ce890c5c2c43f248d4f2341872f8c2dfc2191cd
$

But this ciphertext cannot be decrypted:

$ echo 4cbf21be1cf30657918e439b5ce890c5c2c43f248d4f2341872f8c2dfc2191cd | hex | xxtea -s 0123456789abcdef | xxd
00000000: f431 e233 c6a1 9eee 283d c00f 3124 f5fb  .1.3....(=..1$..
00000010: 3188 446a 46f0 cba9 d149 f89c 2a34 86c0  1.DjF....I..*4..
$

I cannot find out the cause of the incompatibility so far.

[huettenhain]

No worries, I will figure it out. Thanks a lot for the test cases.

[huettenhain]

This Perl implementation is extremely odd, I don't think it should serve as a valid reference implementation. Looking at the Perl code, it is clear that the XXTEA routines are invoked for 8-byte blocks rather than to the entire input. We can, in fact, simulate this odd behaviour with refinery:

[00:26] emit h:4cbf21be1cf30657918e439b5ce890c5c2c43f248d4f2341872f8c2dfc2191cd | chop 8 [| xxtea -Ls 0123456789abcdef -vv ]]| peek -W35
-------------------------------------------------------------------------------------------------------------------------------------------------
00.035 kB; 44.11% entropy; ASCII text
-------------------------------------------------------------------------------------------------------------------------------------------------
00: 54 68 69 73 20 69 73 20 0A 61 20 73 65 63 72 65 74 0A 20 6D 65 73 73 61 67 65 0A 2E 07 07 07 07 07 07 07  This.is..a.secret..message.........
-------------------------------------------------------------------------------------------------------------------------------------------------

[huettenhain]

Reading up on XXTEA, I must correct my statement: This is probably how XXTEA is actually meant to be implemented, just that the block size is variable. The reference implementation is designed as the block encryption/decryption routine. The reality in malware, however, will be that people take the C code and just call it on the entire message, i.e. they treat each input as a single block. I need to think a bit about how to implement this so that it will continue to work with code I see in malware, and also gives you the option to use it as a "normal" block cipher.

[huettenhain]

With cf8f0a1, the xxtea unit can now handle both cases. In order to work with the example output you got from the Perl library, you have to specify that it is using 2-word blocks:

$ emit h:4cbf21be1cf30657918e439b5ce890c5c2c43f248d4f2341872f8c2dfc2191cd  | xxtea -b2 -s 0123456789abcdef
This is a secret message.

However, the default setting for -b is 1, which tells the unit to treat the input as one single block.

[huettenhain]

Tests are green, I am closing this out. I think the TEAs are in a better place now.

[nmantani]

Awesome! Thank you so much for fixing it with blazing speed!

[jhhcs]

Don't mention it! I am very grateful for the bug reports. Keep it coming! =)