Why do these Python XTEA implementations require different deltas?

Question

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?

Answer 1

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.

Answer 2

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;
}