In cryptography, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes. The cryptographer may wish to pick these values in a way that demonstrates the constants were not selected for a nefarious purpose, for example, to create a backdoor to the algorithm. Thus a need was felt for a more transparent way to generate constants used in cryptography.

thumb|Card that was hidden in a sleeve

"Nothing up my sleeve" is a phrase associated with magicians, who sometimes preface a magic trick by holding open their sleeves to show they have no objects hidden inside.

Examples

  • Ron Rivest used pi to generate the S-box of the MD2 hash.
  • Ron Rivest used the trigonometric sine function to generate constants for the widely used MD5 hash.
  • The U.S. National Security Agency used the square roots of the first eight prime integers to produce the hash constants in their "Secure Hash Algorithm" functions, SHA-1 and SHA-2. SHA-1 also uses 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 as its initial hash value.
  • The Blowfish encryption algorithm uses the binary representation of − 3 to initialize its key schedule.
  • RFC 3526 describes prime numbers for internet key exchange that are also generated from .
  • The S-box of the NewDES cipher is derived from the United States Declaration of Independence.
  • The AES candidate DFC derives all of its arbitrary constants, including all entries of the S-box, from the binary expansion of .
  • The ARIA key schedule uses the binary expansion of 1/.
  • The key schedule of the RC5 cipher uses binary digits from both and the golden ratio.
  • Multiple ciphers including TEA and Red Pike use 2654435769 or 0x9e3779b9 which is , where is the golden ratio.
  • The BLAKE hash function, a finalist in the SHA-3 competition, uses a table of 16 constant words which are the leading 512 or 1024 bits of the fractional part of .
  • The key schedule of the KASUMI cipher uses 0x123456789ABCDEFFEDCBA9876543210 to derive the modified key.
  • The Salsa20 family of ciphers use the ASCII string "expand 32-byte k" or "expand 16-byte k" as constants in its block initialization process.
  • OpenBSD Bcrypt uses the string "OrpheanBeholderScryDoubt" as an initialization string

Counterexamples

  • The Streebog hash function S-box was claimed to be generated randomly, but was reverse-engineered and proven to be generated algorithmically with some "puzzling" weaknesses.
  • The Data Encryption Standard (DES) has constants that were given out by NSA. They turned out to be far from random, but instead made the algorithm resilient against differential cryptanalysis, a method not publicly known at the time. In September 2013 The New York Times wrote that "internal memos leaked by a former NSA contractor, Edward Snowden, suggest that the NSA generated one of the random number generators used in a 2006 NIST standard—called the Dual EC DRBG standard—which contains a back door for the NSA."
  • ANSSI FRP256v1 uses totally unexplained parameters.

Manipulatable, but not trivially

ANSI X9.62 claims to use a so-called "verifiably at random" selection of elliptic curves. This is in fact just the result of applying a cryptographic hash function to any piece of data, and is pseudo-random at best. Its claimed resistance to manipulation lies solely in the resistance of the chosen hash function to a preimage attack, i.e. the relative difficulty in producing a piece of data that hashes to a given value. Still, the set of possible choices space remains unrestricted; it is conceivable that an adversary could try many randomly-generated values until they find one with an exploitable property. Indeed, although the IEEE P1363 and NIST 186 standards had inherited these curves, they tone down the claims associated with the generation procedure. but the incomplete explanations do raise concern.

In practice, many protocols have since allowed replacing P-256 with Curve25519, a newer curve with better-explained parameters and in a form that is easy to implement in a fast and correct way. SafeCurves, by Bernstein, provide an analysis on several relatively popular curves (of the time) and identify which ones share the "good" features of Curve25519.

Footnotes

References

  • Bruce Schneier. Applied Cryptography, second edition. John Wiley and Sons, 1996.
  • Eli Biham, Adi Shamir, (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology – CRYPTO '90. Springer-Verlag. 2–21.