What is special about $2^{32}/\phi$ in cryptography?

Question

In the Tiny Encryption Algorithm:

Different multiples of a magic constant are used to prevent simple attacks based on the symmetry of the rounds. The magic constant, 2654435769 or 9E3779B9₁₆ is chosen to be $2^{32}/ \phi$, where ϕ is the golden ratio.

Which properties does $2^{32}/ \phi$ have that makes it useful in this context?

Answer 1

AFAIK, such "magic" values have the following two properties:

1. They are somehow unique, and look random.
2. They can take part in algebraic operations repeatedly; i.e. even after applying some specific operation (say multiplication or exponentiation) many times, the "magic" value is still able to generate new values.

You may find a similar case in the MD5. Consider the following line:

k[i] := floor(abs(sin(i + 1)) × (2 pow 32))

Here, sin(i + 1) is meant to generate magic values; which are unique, random-looking, and can work for a lot of i's. (Actually, i ranges in 0..63).

Edit: Reading the original paper on TEA, one understands that the answer given by "Steven Stadnicki" is correct. Note that the magic constant is name delta:

A different multiple of delta is used in each round so that no bit of the multiple will not change frequently. We suspect the algorithm is not very sensitive to the value of delta and we merely need to avoid a bad value. It will be noted that delta turns out to be odd with truncation or nearest rounding, so no extra precautions are needed to ensure that all the digits of sum change.

Since only 32 multiples of delta is used (one per each round), it is not odd that the algorithm is not very sensitive to any specific delta. (See Steven Stadnicki's answer for more info.)

Edit 2: Incidentally, MD4 uses square roots of 2 (0x5a827999) and 3 (0x6ed9eba1) as "magic" constants in its operations. Section 5.4.4 of the book Network Security: Private Communication in a Public World explains this well:

To show that the designers didn't purposely choose a diabolical value of the constant, the constant is based on the square root of 2.

This explanation is the same as the point made below in a comment by Gilles.

Answer 2

One reason that $\varphi$ makes a particularly useful 'magic number' in this context is that the multiples $n\varphi$ are guaranteed to be 'maximally far' from integers (this has to do with the lack of large terms in the continued fraction for $\varphi$), and thus the sequence $\{n\varphi\}$ (or more accurately, its initial segments) is more uniformly distributed mod 1 than the sequence $\{n\alpha\}$ for any other irrational $\alpha$.

To give an example: suppose we choose a magic constant $C_\pi = \lfloor {2^{32}/\pi}\rfloor = 1367130551$. Then $(355C_\pi)\mod {2^{32}} = 41157$, an unexpectedly small result for such a small multiple of our magic constant. By contrast, if we use the magic constant $C_\varphi = \lfloor {2^{32}/\varphi}\rfloor = 2654435769$, then the smallest $n$ for which $|(nC_\varphi)\mod {2^{32}}| \leq 2^{16}$ (abusing notation a bit) is $n=28657$. In practice, this can conceivably lead to things like unexpectedly large correlations between the values $X_n$ and $X_{n+k}$ of a linear congruential random number generator for some smallish $k$; for the most part, though, it's folkloreish black magic, based more on the intuition that 'small multiples of this number being small mod $2^{32}$ will be bad' than on any specific theoretical results.