8
$\begingroup$

Now that we know how the MD2 S-box was constructed, I find myself wondering how good a nothing up my sleeve number it really is. It is derived from $\pi$, but not in a very obvious way, even in retrospect.

How would you estimate the number of possible $\pi$-derived S-boxes that are no more complex or suspicious than the actual one is?

For example, "unique bytes of pi starting from the 96723th digit in base 256" is (arguably) simpler, but more suspicious. On the other hand, a longer description/algorithm would count as more complex.

Or more generally: how would you appraise how binding a nothing up my sleeve number is?

$\endgroup$
  • 3
    $\begingroup$ This might be hard to answer unless you can come up with a good measure for how suspicious an algorithm is. $\endgroup$ – mikeazo Aug 5 '14 at 16:07
  • 4
    $\begingroup$ You might find the (satirical but still substantive) paper "How to manipulate curve standards: a white paper for the black hat" interesting; it addresses this question in the context of ECC parameters. PDF: eprint.iacr.org/2014/571.pdf $\endgroup$ – Seth Aug 5 '14 at 17:21
  • 1
    $\begingroup$ Also check out this new project on manipulating SHA1 constants to create weak hash functions: malicioussha1.github.io $\endgroup$ – pg1989 Aug 6 '14 at 3:30
  • $\begingroup$ There's been a similar discussion of elliptic curve "rigidity" recently. If you're curious, look for one of the CFRG threads where DJB kicks someone's butt, IIRC. $\endgroup$ – Matt Nordhoff Aug 6 '14 at 4:08
  • 1
    $\begingroup$ @otus Thats a good question. Unfortunately, I do not think it is answerable. $\endgroup$ – DrLecter Aug 6 '14 at 19:00
7
$\begingroup$

Actually, given that the MD2 S-box needs to be a permutation, using a Fisher–Yates shuffle does seem a fairly obvious choice to me. (It's pretty much the standard algorithm for generating a uniformly chosen random permutation.) The rand() function used to convert the digits of $\pi$ into a random number from a given interval looks complicated, but is also a fairly standard method. (IIRC, it's essentially the same as what's described in Fisher and Yates' original book from 1938.)

That said, you asked about the number of degrees of freedom available, so let me try to count the various plausible choices one might've made in generating the permutation:

  • The first obvious choice is the base in which $\pi$ is expressed. The Rivest code uses base 10 digits, but since we're using a computer, at least the bases 2, 16 and 256 would've made sense (and using base-256 would've even allowed the rand() function to be simplified). That's four choices, or two bits of freedom.

  • Also, using only the fractional part of $\pi$ (i.e. skipping the first digit) would've probably been a plausible choice. That's one bit of freedom. One might've even been able to justify the use of $\tau = 2\pi$, or its fractional part, for another bit of freedom.

  • Obviously, there are plenty of other "obvious" irrational constants besides $\pi$ that could've been chosen. This excellent paper by D.J. Bernstein et al., mentioned by Seth in the comments above, lists 17 such constants: $\pi$, $e$, $\gamma$, $\sqrt2$, $\sqrt3$, $\sqrt5$, $\sqrt7$, $\log(2)$, $\varphi = (1+\sqrt5)/2$, $\zeta(3)$, $\zeta(5)$, $\sin(1)$, $\sin(2)$, $\cos(1)$, $\cos(2)$, $\tan(1)$ and $\tan(2)$. (Adding $\tau$ makes it 18.) Each of those has a reciprocal, and either the original constant or the reciprocal has a non-zero integer part that can be dropped, multiplying the number of possible constants by three, for a total of $18 \times 3 = 54$ possible choices, or $\log_2 54 \approx 5.8$ bits of freedom (including the two bits from the previous bullet point).

  • The Fisher–Yates shuffle has an "inside-out" version, which produces a different permutation for the same input. Also, either of the variants could be started from either the top or the bottom end of the array, yielding different results. That's two more bits of freedom.

  • The rejection sampling used in rand() could've been avoided by expressing $\pi$ in a mixed-radix system (with the base increasing or decreasing by one for each digit). Such a choice (which essentially amounts to a form of arithmetic decoding) could've been justified by the fact that it minimizes the amount of input "randomness" required to generate the needed pseudorandom digits. As there are at least two reasonably natural ways to do this (increasing or decreasing radix), we can increase the possible bases from four to six, giving us an extra 0.6 bits of freedom.

Putting all of these choices together, we have $4 \times 54 \times 6 = 1296$ reasonably plausible combinations to choose from, giving us at least $\log_2 1296 \approx 10.3$ bits of freedom.

Of course, if that's not enough, there are various other methods we could try, such as "accidentally" implementing Sattolo's algorithm or one of the many other subtly biased (but still pretty convincingly random) variants of the Durstenfeld–Knuth–Fisher–Yates shuffle.

We might even be able to appeal to tradition and use Fisher and Yates' original algorithm instead of the Durstenfeld variant, perhaps combined with simple rejection sampling for the first half (as originally suggested by Fisher and Yates), or perhaps the algorithm by C.R. Rao described in later editions of their book. Or we could even just go with pure rejection sampling (i.e. take the base-256 digits of $\pi$ and discard duplicates), or maybe some variant of the sort-by-pseudorandom-key method of generating permutations (which should allow plenty of freedom in how to generate the keys).

$\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.