Tiny Encryption Algorithm (TEA) weakness

Question

The Wikipedia states that different multiples of a magic constant are used to prevent simple attacks based on the symmetry of the rounds. The magic constant, 2654435769 or 0x9E3779B9 is chosen to be ⌊$2^{32}$/ϕ⌋, where ϕ is the golden ratio.

And according to the code which wiki provides.

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

Since the constant is known, how could this constant prevent attacks? I was stuck in the description.

Answer 1

The constant delta is here so that sum changes, so that distinct round functions are used, which is an essential condition for the security of a Feistel structure.

If delta was zero, sum would stay to zero, and the inside of the round loop would simplify to

    v0 += ((v1<<4) + k0) ^ v1 ^ ((v1>>5) + k1);
    v1 += ((v0<<4) + k2) ^ v0 ^ ((v0>>5) + k3);

which uses the same round function for all odd and all even rounds - and simpler ones than in the original. That's ideal grounds for some cryptanalytic attacks, most notably the slide attack (as pointed in that other answer).

The magic value's goal is that the values of sum at each of the 32 loops act like arbitrary (pseudo-random) values, unique to each loop (each doing two rounds). That goal is not quite reached (in particular, bit $i$ of sum repeats after $2^{i+1}$ loops, as illustrated below), but using a more complex PRNG to generate sum would slow the cipher.

---

Illustration per request:

 i  sum (hex)            sum (binary)
 0  9e3779b9    10011110001101110111100110111001
 1  3c6ef372    00111100011011101111001101110010
 2  daa66d2b    11011010101001100110110100101011
 3  78dde6e4    01111000110111011110011011100100
 4  1715609d    00010111000101010110000010011101
 5  b54cda56    10110101010011001101101001010110
 6  5384540f    01010011100001000101010000001111
 7  f1bbcdc8    11110001101110111100110111001000
 8  8ff34781    10001111111100110100011110000001
 9  2e2ac13a    00101110001010101100000100111010
10  cc623af3    11001100011000100011101011110011
11  6a99b4ac    01101010100110011011010010101100
12  08d12e65    00001000110100010010111001100101
13  a708a81e    10100111000010001010100000011110
14  454021d7    01000101010000000010000111010111
15  e3779b90    11100011011101111001101110010000
16  81af1549    10000001101011110001010101001001
17  1fe68f02    00011111111001101000111100000010
18  be1e08bb    10111110000111100000100010111011
19  5c558274    01011100010101011000001001110100
20  fa8cfc2d    11111010100011001111110000101101
21  98c475e6    10011000110001000111010111100110
22  36fbef9f    00110110111110111110111110011111
23  d5336958    11010101001100110110100101011000
24  736ae311    01110011011010101110001100010001
25  11a25cca    00010001101000100101110011001010
26  afd9d683    10101111110110011101011010000011
27  4e11503c    01001110000100010101000000111100
28  ec48c9f5    11101100010010001100100111110101
29  8a8043ae    10001010100000000100001110101110
30  28b7bd67    00101000101101111011110101100111
31  c6ef3720    11000110111011110011011100100000

The rightmost bit of sum (bit 0) is alternatively 0 or 1, and that cycle repeats after 2 loops. More generally, bit $i$ of sum repeats after $2^{i+1}$ loops, something (among other weaknesses) that would not happen with a better PRNG to generate sum.

Answer 2

The slide attack takes advantage of self-similarity of rounds. The constant plays a role in adding non-symmetry among rounds.(page 8 of the reference)

This is a good link to understand the slide attack tutorial

FYI: the slide attack is independent of round numbers unlike differential and linear crypt-analysis.