6
$\begingroup$

Premise

Several cryptographic primitives employ randomized numerical constants. To avoid suspicious that the designer selected such constants in order to plant a backdoor, "nothing-up-my-sleeve numbers" are used. These are numbers constructed from the first digits of some important constants, like $\pi$, $e$, $\sqrt{2}$, ... so that they do not appear to be well-crafted to hide a backdoor.

The Problem

However, designers of different systems use different constants. Below some examples copied from the wikipedia's page:

  • Small roots of small integers (SHA-1, SHA-2)

  • $\sin 1, \sin 2, \dots$ (MD5)

  • $e$ (DFC)

  • $\pi$ (Blowfish and many other)

  • $1/\pi$ (ARIA)

  • 0x123456789ABCDEFFEDCBA9876543210 (KASUMI)

  • ASCII string "expand 32-byte k" (Salsa20)

But with enough degrees of freedom, it is clear that nothing-up-my-sleeve numbers lose their purpose. For example, who does guarantee that the sentence "expand 32-byte k" was not selected among thousands of similarly innocent ones ("expanding 32-byte k", "expansion of 32-byte k", "32-byte expanded k", ...) in order to hide a backdoor? Likewise for numerical constants.

The Question

In light of the previous considerations, was a "nothing-up-my-sleeve numbers standard" ever proposed? If not, why not?

A very simple standard could be: "A cryptographic primitive employing a randomized constant $C$ (if there are more randomized constants, $C$ is their binary concatenation) must fix $C$ to be the first digits of the binary representation of $\pi$."

$\endgroup$
2
2
$\begingroup$

A (probably weak) reason not to use a standard is that some nothing-up-my-sleeve numbers may serve some sort of purpose. As an example, you cannot change Salsa20's constants to anything, it must be sufficiently asymmetric. It's feasible to presume that another cipher may have a different set of requirements

As per this answer:

Salsa20 has strong rotational symmetry. The main point of these constant is that they're not invariant under rotations, introducing an asymmetry. The precise value isn't very important, as long as it's sufficiently asymmetric.

The answer goes into further detail, quoting DJB himself on the matter.

This answer also details several cryptographic constants, and the padding constant for HMAC is similarly designed to be asymmetric:

The padding constants for HMAC, 0x36 for ipad and 0x5C for opad, are repeated (for the hash function's block size) and XORed with the key to generate the prefixes for the two hashing steps. 0x36 = 0b00110110 and 0x5C = 0b01011100 - these two values are about "as different as possible", to avoid any attacks which rely on a similar hash state after the key block for inner and outer hash. This is mainly a heuristic, as far as I understand.

$\endgroup$
6
  • $\begingroup$ I don't think it is such a good reason. If constants of a special forms are needed, a "nothing-up-my-sleeve numbers standard" could say: use the digits of $\pi$ after the $k$th binary position, where $k$ is the smallest positive integer such that the the special form for the constant is found. For the case of Salsa20, the sentence you quoted says: "The main point of these constant is that they're not invariant under rotations" I strongly doubt that the first $\pi$ digits are invariant under rotations... $\endgroup$
    – user38141
    Jan 20 at 10:32
  • $\begingroup$ @user38141 It is a better reason than the one you give for creating a standard I think. Anyhow, you have just confirmed that you strongly doubt the first digits of pi are not suitable if the requirement (for another scheme) is that they ARE invariant under rotations. I doubt the first digits of pi are "about as different as possible" per the HMAC padding as well. $\endgroup$
    – Modal Nest
    Jan 20 at 10:50
  • $\begingroup$ "you have just confirmed that you strongly doubt the first digits of pi are not suitable if the requirement (for another scheme) is that they ARE invariant under rotations." Come on... if, for example, one wants a 32-bits constant that is invariant respect to 8 bits rotations, then one just picks an 8-bits string (from the digits of $\pi$) and repeat it four times. $\endgroup$
    – user38141
    Jan 20 at 15:23
  • 1
    $\begingroup$ @user38141 I probably deserved the downvote just for the way I worded that, tbf. What about HMAC padding? If you have a crypto standard that details what to do in the case of every possible requirement (assuming that's possible), why should we trust that it hasn't been proposed in order facilitate potential backdoors? $\endgroup$
    – Modal Nest
    Jan 20 at 16:25
  • $\begingroup$ @user38141 I've edited my answer from "good reason" to "(potentially weak) reason" $\endgroup$
    – Modal Nest
    Jan 20 at 22:50
2
$\begingroup$

The constants in cryptography that can be chosen arbitrarily are typically not likely to be good candidates for backdooring. The constants in cryptography that can be backdoored usually have requirements that make it impractical to generate them randomly in the first place.

But with enough degrees of freedom, it is clear that nothing-up-my-sleeve numbers lose their purpose.

Enough degrees of freedom absolutely do reduce the benefit from using nothing-up-my-sleeve numbers. A paper titled How to manipulate curve standards: a white paper for the black hat explains the math behind this risk for constants as used in ECC curves. Actual proof of concept code for a simple 32-bit pseudo-NUMS generator is also available. Although it may be better if everyone used the same constants, the risk is not so bad as to say that they completely lose their purpose.

who does guarantee that the sentence "expand 32-byte k" was not selected among thousands of similarly innocent ones ("expanding 32-byte k", "expansion of 32-byte k", "32-byte expanded k", ...) in order to hide a backdoor?

That particular instance is a constant which really isn't suspicious due to what it is used for. It simply needs to have asymmetry and be non-null. It is fed into the random function in ChaCha along with the nonce, counter, and key. If there was a special constant that could reduce the security of the ChaCha core, then an attacker could exploit it on their own by choosing a malicious nonce or counter anyway.

In light of the previous considerations, was a "nothing-up-my-sleeve numbers standard" ever proposed?

I am not aware of any proposed standard that can be used everywhere, for all purposes. This is because it's often required that constants have certain properties and can't simply be random. There are solutions to this though, such as that employed by the well-known Oakley groups, generated deterministically using $\pi$ as a constant in RFC 3526. The specific technique, designed by Richard Schroeppel, can be scaled to generate any large, pseudorandom prime for use as a constant without causing suspicions. It is specifically intended for Diffie–Hellman. The algorithm is as so:

$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi \rfloor + c)$

Here, $n$ is the desired size of the prime in bits and $c$ is the smallest non-negative integer that satisfies $p,(p-1)/2 \in \mathbb{P}$ (i.e. that ensures $p$ is a safe prime, required for the properties of primes in DH) and $p \equiv 7 \pmod 8$. This equation proves that you can generate structured NUMS constants from unstructured NUMS constants (in this case, generating a prime from an irrational number). If we want $n = 2048$, we get $c = 124476$ (DH group 14). Note that this only works to generate primes.

If not, why not?

One common place where nothing-up-my-sleeve numbers would have a hard time being used is in the S-box for block ciphers. The S-box is better off being specially designed for good differential properties, and an S-box that is good for one cipher might not be good for another. Although you could use a totally random S-box generated using nothing-up-my-sleeve numbers, the security properties would not be ideal. An S-box generated without any rationale is likely to arouse the suspicion of cryptographers. This happened with the Russian Streebog hash function (GOST R 34.11-2012) and the Kuznyechik block cipher (GOST R 34.12-2015), whose S-boxes are generally believed to have been designed non-randomly, introducing a weakness that is very likely to be a backdoor.

The idea of backdoored nothing-up-my-sleeve numbers, while not new, is not something that many cryptographers have thought about. This is largely because most backdoored constants need to have special properties that are extremely uncommon. Take the NIST ECC curves, for example. These curves have parameters that some consider suspicious. They were generated by passing an ostensibly random input through SHA-1 and using the resultant digest as the constant. The idea is that weak curve parameters are rare enough that it would be effectively impossible to find them by luck, and generating a specific backdoored parameter would require a preimage attack against SHA-1, which is thought to be infeasible (read: not gonna happen). It would be incredibly unlikely that there are so many classes of curves with weak properties that one could find them among a pool of random (due to SHA-1) curves but that cryptographers would not know about.

$\endgroup$
-3
$\begingroup$

There's also a very good reason that no one will want to.

A 'designer' gets to choose the initialisation constants for their new primitive/what have you. But there are only few people in the world with sufficient qualifications to do so if their baby is to be adopted into general use. To wit, the designer's have the power.

Logically you're correct, just settle on $\pi$ digits. Yet you've also listed $\frac{1}{\pi}$. Why? Why all that load of $ \sin(\mathbb{Z}) $? And more exotically, there's NewDes which draws upon the US Declaration of Independence. I wouldn't be surprised to see something in the future with constants based on the names of the characters in the extended Sesame Street universe.

Why? Philosophically, because it's a signature. It's hubris, showmanship and bravado. An artist (even a mathematically focused one) does not want to repeat others' work. I wouldn't. That's why there are so many different mechanisms for creating them, progressively getting more imaginative/weirder.

"But with enough degrees of freedom,..."

You're right. "expand 32-byte k" does sound a little suspicious even if it's not. That segways directly to:-

"I no longer trust the constants."

-Bruce Schneier.

But you do have to trust Elmo, Grover and Kermit.

$\endgroup$
3
  • 1
    $\begingroup$ It has nothing at all to do with someone being protective of their own NUMS ideas. Just because you think cryptographers see themselves as artists who must make their "mark" does not mean they do. The fact is, cryptographers do like repeating others' work. It's how the field progresses. As for Schneier's comment, that was about specific baked constants, not NUMS constants in general. $\endgroup$
    – forest
    Jan 21 at 5:26
  • 1
    $\begingroup$ Paul, do not apply to others your own flaws. It's not because you feel driven by hubris that everybody is. $\endgroup$
    – A. Hersean
    Jan 21 at 8:56
  • $\begingroup$ @A.Hersean Teach that to Banksy. $\endgroup$
    – Paul Uszak
    Jan 23 at 21:54

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.