12
$\begingroup$

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 9E3779B916 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?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sounds reasonable. Would 2^32/pi or 2^32/sqrt(2) have worked just as well, then? $\endgroup$ – user4772 Apr 21 '11 at 13:49
  • $\begingroup$ @Tim: I guess so, but it is instrumental to double check the new magic numbers in the context of TEA internal operations. $\endgroup$ – M.S. Dousti Apr 21 '11 at 15:13
  • 5
    $\begingroup$ Furthermore, a reason to choose a mathematical constant like 2^32/phi, rather than a randomly-generated value with acceptable properties, is to give a smidgen of confidence that this isn't a value chosen for additional unrevealed properties — a backdoor value. $\endgroup$ – Gilles 'SO- stop being evil' Apr 21 '11 at 20:02
  • 2
    $\begingroup$ @Gilles, indeed, they are even called "nothing up my sleeve number" for that reason, see en.wikipedia.org/wiki/Nothing_up_my_sleeve_number $\endgroup$ – Henno Brandsma May 17 '11 at 9:50
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Sadeq: 'mod 1' refers to the fractional part of the multiples - in this case these would be [.62, .24, .85, .47, .09, .71, .33, .94, .56, .18]. Equidistribution in the limit means that any subinterval [a, b] of [0, 1] contains the expected proportion (b-a) of these values; while it turns out that the fractional parts of the multiples of any irrational number are evenly distributed on [0, 1], those of the golden ratio approach that even distribution faster than any other number; they don't 'clump' on the unit interval. $\endgroup$ – Steven Stadnicki Apr 21 '11 at 20:03
  • 8
    $\begingroup$ $\pi$'s close approximation by 355/113, for instance, means that $113\pi$ will be much closer to an integer than it 'should be' and this shows up as a clustering of the fractional parts of its values; $\{(n+113)\pi\}$ will be exceptionally close to $\{n\pi\}$. The golden ratio has no such good approximations, though; all of its approximations are 'maximally far' from it. ( en.wikipedia.org/wiki/… covers this) $\endgroup$ – Steven Stadnicki Apr 21 '11 at 20:10
  • 8
    $\begingroup$ that's a very neat property of the golden ratio $\endgroup$ – Suresh Venkat Apr 21 '11 at 21:00
  • 2
    $\begingroup$ Thanks for great description. It was really great! Do you have any comments on k[i], as defined in MD5? (See my answer above.) $\endgroup$ – M.S. Dousti Apr 21 '11 at 21:33
  • 2
    $\begingroup$ Unfortunately, I don't; - the only thing that comes to mind is that they may be chosen for approximate linear independence, since the functions $\sin(nx)$ are linearly independent over $x$ - but I don't know any reason to believe that this particular set of values should lead to relatively large values for $a_i$ in any linear relation $\Sigma a_i k[i] = 0$. $\endgroup$ – Steven Stadnicki Apr 21 '11 at 22:00

Your Answer

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