1
$\begingroup$

I once needed to an XTEA snippet to from C++ to Python and it did not work properly. I then found a function on ActiveState.com and noticed that it looks almost exactly like mine, with one exception - for some reason, its "delta" variable was changed. Here's the test code:

import struct

def XTEA_encrypt(buf, k):
    ret = bytearray()
    for offset in range(int(len(buf)/8)):
        v0 = struct.unpack("<I", bytes(buf[offset*8:offset*8+4]))[0]
        v1 = struct.unpack("<I", bytes(buf[offset*8+4:offset*8+8]))[0]
        delta = 0x9E3779B9
        sum_ = 0

        for _ in range(32):

            v0 = (v0 + ((v1<<4 ^ v1>>5) + v1) ^ (sum_ + k[sum_ & 3])) & 0xFFFFFFFF

            sum_ = (sum_ + delta) & 0xFFFFFFFF

            v1 = (v1 + ((v0<<4 ^ v0>>5) + v0) ^ (sum_ + k[sum_>>11 & 3])) & 0xFFFFFFFF

        ret += struct.pack("<I", v0) + struct.pack("<I", v1)
    return ret

print(repr(XTEA_encrypt('\xfc\xd9\xd8A\x0b\xc4~\x82',
    [4060739823, 3225438839, 2808461571, 1241583342])))

With the new delta = 0x9E3779B9, the code prints \xec\xe8\xeaZ!\xec7\xde, as expected. On the other hand, the original C++ implementation (https://github.com/otland/forgottenserver/blob/788198e1afd96a0b83ddeb025a9f3910e72626d5/src/protocol.cpp#L87) had delta = 0x61C88647, which results in \x87Z\xed})\t:\xbe being printed. Why do the implementations differ?

$\endgroup$
5
$\begingroup$

If you take a close look at line 105 of the C++ implementation, you see that it subtracts delta from the sum instead of adding it:

103            for (int32_t i = 32; --i >= 0;) {
104                    v0 += ((v1 << 4 ^ v1 >> 5) + v1) ^ (sum + k[sum & 3]);
105                    sum -= delta;
106                    v1 += ((v0 << 4 ^ v0 >> 5) + v0) ^ (sum + k[sum >> 11 & 3]);
107            }

Since $\textrm{0x61C88647+0x9E3779B9}=2^{32}$, this is equivalent to adding the "normal" delta.

A rather odd design choice, if you ask me, but it works.

$\endgroup$
4
$\begingroup$

0x61C88647 is the 2's complement representation of -0x9E3779B9. You can implement XTEA as:

void XTEA_Encrypt(uint32_t v[2], uint32_t const key[4]) 
{
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < 32; i++) 
    {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

or

void XTEA_Encrypt(uint32_t v[2], uint32_t const key[4]) 
{
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x61C88647;
    for (i=0; i < 32; i++) 
    {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum -= delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.