In
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (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
cipher
In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode i ...
s. 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.
[ These fears can be allayed by using numbers created in a way that leaves little room for adjustment. An example would be the use of initial digits from the number as the constants.][ Using digits of millions of places after the decimal point would not be considered trustworthy because the algorithm designer might have selected that starting point because it created a secret weakness the designer could later exploit—though even with natural-seeming selections, enough ]entropy
Entropy is a scientific concept, most commonly associated with states of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynamics, where it was first recognized, to the micros ...
exists in the possible choices that the utility of these numbers has been questioned.
Digits in the positional representations of real numbers such as , ''e'', and irrational roots are believed to appear with equal frequency (see normal number). Such numbers can be viewed as the opposite extreme of Chaitin–Kolmogorov random numbers in that they appear random but have very low information entropy. Their use is motivated by early controversy over the U.S. Government's 1975 Data Encryption Standard, which came under criticism because no explanation was supplied for the constants used in its S-box (though they were later found to have been carefully selected to protect against the then-classified technique of differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can a ...
).Bruce Schneier
Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is an Adjunct Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman ...
. ''Applied Cryptography'', second edition, John Wiley and Sons, 1996, p. 247. Thus a need was felt for a more transparent way to generate constants used in cryptography.
"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
Ronald Linn Rivest (;
born May 6, 1947) is an American cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity.
He is an Institute Profess ...
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
The National Security Agency (NSA) is an intelligence agency of the United States Department of Defense, under the authority of the director of national intelligence (DNI). The NSA is responsible for global monitoring, collection, and proces ...
used the square root
In mathematics, a square root of a number is a number such that y^2 = x; in other words, a number whose ''square'' (the result of multiplying the number by itself, or y \cdot y) is . For example, 4 and −4 are square roots of 16 because 4 ...
s 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
In cryptography, the so-called product ciphers are a certain kind of cipher, where the (de-)ciphering of data is typically done as an iteration of '' rounds''. The setup for each round is generally the same, except for round-specific fixed va ...
.
* 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 Declaration of Independence, formally The unanimous Declaration of the thirteen States of America in the original printing, is the founding document of the United States. On July 4, 1776, it was adopted unanimously by the Second Continen ...
.
* The AES candidate DFC derives all of its arbitrary constants, including all entries of the S-box, from the binary expansion of .
* The ARIA
In music, an aria (, ; : , ; ''arias'' in common usage; diminutive form: arietta, ; : ariette; in English simply air (music), air) is a self-contained piece for one voice, with or without instrument (music), instrumental or orchestral accompan ...
key schedule uses the binary expansion of 1/.
* The key schedule of the RC5 cipher uses binary digits from both and the golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their summation, sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if
\fr ...
.
* 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
bcrypt is a password-hashing function designed by Niels Provos and David Mazières. It is based on the Blowfish (cipher), Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt (cryptography), salt to protect against rain ...
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
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can a ...
, a method not publicly known at the time.
* Dual_EC_DRBG
Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criti ...
, a NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical s ...
-recommended cryptographic pseudo-random bit generator, came under criticism in 2007 because constants recommended for use in the algorithm could have been selected in a way that would permit their author to predict future outputs given a sample of past generated values. 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."
* P curves are standardized by NIST for elliptic curve cryptography. The coefficients in these curves are generated by hashing unexplained random seeds, such as:
** P-224: bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5
.
** P-256: c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
.
** P-384: a335926a a319a27a 1d00896a 6773a482 7acdac73
.
Although not directly related, after the backdoor in Dual_EC_DRBG had been exposed, suspicious aspects of the NIST's P curve constants led to concerns that the NSA had chosen values that gave them an advantage in finding private keys. Since then, many protocols and programs started to use Curve25519 as an alternative to NIST P-256 curve.
Limitations
Bernstein and coauthors demonstrate that use of nothing-up-my-sleeve numbers as the starting point in a complex procedure for generating cryptographic objects, such as elliptic curves, may not be sufficient to prevent insertion of back doors. For example, many candidates of seemingly harmless and "uninteresting" simple mathematical constants exist, such as π, e, Euler gamma, √2, √3, √5, √7, log(2), (1 + √5)/2, ζ(3), ζ(5), sin(1), sin(2), cos(1), cos(2), tan(1), or tan(2). For these constants, there also exists several different binary representations to choose. If a constant is used as a random seed, a large number of hash function candidates also exist for selection, such as SHA-1, SHA-256, SHA-384, SHA-512, SHA-512/256, SHA3-256, or SHA3-384.
If there are enough adjustable parameters in the object selection procedure, combinatorial explosion
In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to the way its combinatorics depends on input, constraints and bounds. Combinatorial explosion is sometimes used to justify the intractability of cert ...
ensures that the universe of possible design choices and of apparently simple constants can be large enough so that an automatic search of the possibilities allows construction of an object with desired backdoor properties.How to manipulate curve standards: a white paper for the black hat
Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hu ̈lsing, Eran Lambooij, Tanja Lange, Ruben Niederhagen, and Christine van Vredendaal, September 27, 2015, accessed June 4, 2016
Footnotes
{{reflist
References
* Bruce Schneier
Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is an Adjunct Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman ...
. ''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.
Random number generation
Cryptography
Transparency (behavior)