Editing Nothing-up-my-sleeve number

{{Short description|Cryptography number with no hidden properties}}
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 [[cryptographic hash|hashes]] and [[cipher]]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 (computing)|backdoor]] to the algorithm.<ref name=wired-schneier/> 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 [[pi|{{pi}}]] as the constants.<ref name=blowfish/> Using digits of {{pi}} 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 (information theory)|entropy]] exists in the possible choices that the utility of these numbers [[#Limitations|has been questioned]].

Digits in the [[Positional notation|positional representations]] of real numbers such as {{pi}}, [[E (mathematical constant)|''e'']], and irrational roots are believed to appear with equal frequency (see [[normal number]]). Such numbers can be viewed as the opposite extreme of [[Kolmogorov complexity#Kolmogorov randomness|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]]).<ref name="schneier">[[Bruce Schneier]]. ''Applied Cryptography'', second edition, John Wiley and Sons, 1996, p. 247.</ref> Thus a need was felt for a more transparent way to generate constants used in cryptography.

[[File:Poker cheating 20170611.jpg|thumb|Card that was hidden in a sleeve]]
"Nothing up my sleeve" is a phrase associated with [[magic (illusion)|magician]]s, 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 function)|MD2]] hash.<ref>{{cite web|date=2 August 2014|title=How is the MD2 hash function S-table constructed from Pi?|url=https://crypto.stackexchange.com/a/18444|access-date=23 May 2021|website=Cryptography Stack Exchange|publisher=Stack Exchange}}</ref>
* Ron Rivest used the trigonometric [[sine]] function to generate constants for the widely used [[MD5]] hash.<ref>RFC 1321 Sec. 3.4</ref>
* The U.S. [[National Security Agency]] used the [[square root]]s of the first eight [[prime numbers|prime integers]] to produce the hash constants in their "Secure Hash Algorithm" functions, [[SHA-1]] and [[SHA-2]].<ref>[http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf FIPS 180-2: Secure Hash Standard (SHS)] {{Webarchive|url=https://web.archive.org/web/20120312101511/http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf |date=2012-03-12 }} ([[Portable Document Format|PDF]], 236 kB) – Current version of the Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512), 1 August 2002, amended 25 February 2004</ref> SHA-1 also uses 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 as its initial hash value.
* The [[Blowfish (cipher)|Blowfish]] encryption algorithm uses the binary representation of {{pi}} − 3 to initialize its [[key schedule]].<ref name=blowfish>{{Cite web |url=http://www.schneier.com/paper-blowfish-fse.html |title=Blowfish Paper<!-- Bot generated title --> |access-date=2010-06-09 |archive-date=2011-09-06 |archive-url=https://web.archive.org/web/20110906144128/http://www.schneier.com/paper-blowfish-fse.html |url-status=live }}</ref>
* RFC 3526 describes prime numbers for [[internet key exchange]] that are also generated from {{pi}}.
* The [[S-box]] of the [[NewDES]] cipher is derived from the [[Declaration of Independence (United States)|United States Declaration of Independence]].<ref>{{Cite web |url=http://groups.google.com/group/sci.crypt/msg/7fb986b231fa9dc5 |title=Revision of NEWDES, Robert Scott, 1996 |access-date=2010-06-09 |archive-date=2012-11-08 |archive-url=https://web.archive.org/web/20121108210518/http://groups.google.com/group/sci.crypt/msg/7fb986b231fa9dc5 |url-status=live }}</ref>
* The [[Advanced Encryption Standard process|AES candidate]] [[DFC (cipher)|DFC]] derives all of its arbitrary constants, including all entries of the S-box, from the binary expansion of {{math|''e''}}.<ref>{{cite web |author1=Henri Gilbert |author2=M. Girault |author3=P. Hoogvorst |author4=F. Noilhan |author5=T. Pornin |author6=G. Poupard |author7=J. Stern |author8=S. Vaudenay |title=Decorrelated Fast Cipher: an AES candidate |date=May 19, 1998 |url=http://citeseer.ist.psu.edu/gilbert98decorrelated.html |format=PDF/[[PostScript]] |access-date=June 9, 2010 |archive-date=April 9, 2008 |archive-url=https://web.archive.org/web/20080409235139/http://citeseer.ist.psu.edu/gilbert98decorrelated.html |url-status=live }}</ref>
* The [[ARIA (cipher)|ARIA]] key schedule uses the binary expansion of 1/{{pi}}.<ref>{{cite report |author1=A. Biryukov |author-link1=Alex Biryukov |author2=C. De Cannière |author3=J. Lano |author4=B. Preneel |author-link4=Bart Preneel |author5=S. B. Örs |title=Security and Performance Analysis of ARIA |version=Version 1.2&mdash;Final Report |publisher=[[Katholieke Universiteit Leuven]] |date=January 7, 2004 |url=http://www.cosic.esat.kuleuven.be/publications/article-500.ps |format=[[PostScript]] |access-date=June 9, 2010 |archive-date=July 16, 2011 |archive-url=https://web.archive.org/web/20110716200503/http://www.cosic.esat.kuleuven.be/publications/article-500.ps |url-status=live }}</ref>
* The key schedule of the [[RC5]] cipher uses binary digits from both {{math|''e''}} and the [[golden ratio]].<ref>{{cite conference|last=Rivest|first=R. L.|year=1994|title=The RC5 Encryption Algorithm|book-title=Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e|pages=86&ndash;96|url=http://theory.lcs.mit.edu/~rivest/Rivest-rc5rev.pdf}}</ref>
* Multiple ciphers including [[Tiny Encryption Algorithm|TEA]] and [[Red Pike (cipher)|Red Pike]] use 2654435769 or 0x9e3779b9 which is {{nowrap|floor(2<sup>32</sup>/{{φ}})}}, where {{φ}} is the golden ratio.
* The [[BLAKE (hash function)|BLAKE hash function]], a finalist in the [[NIST hash function competition|SHA-3 competition]], uses a table of 16 constant words which are the leading 512 or 1024 bits of the [[fractional part]] of {{pi}}.
* 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.<ref>{{Citation |last=Bernstein|first=Daniel J.|title=Salsa20 specification|pages=9|url=https://cr.yp.to/snuffle/spec.pdf }}</ref>
* OpenBSD [[Bcrypt]] uses the string "OrpheanBeholderScryDoubt" as an initialization string<ref>{{Cite web |title=src/lib/libc/crypt/bcrypt.c - diff - 1.3 |url=https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/bcrypt.c.diff?r1=1.2&r2=1.3&f=h |access-date=2022-07-05 |website=cvsweb.openbsd.org |archive-date=2022-07-05 |archive-url=https://web.archive.org/web/20220705191336/https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/bcrypt.c.diff?r1=1.2&r2=1.3&f=h |url-status=live }}</ref><ref>{{Cite web |title=hash - Why is the BCrypt text "OrpheanBeholderScryDoubt" |url=https://security.stackexchange.com/questions/227459/why-is-the-bcrypt-text-orpheanbeholderscrydoubt |access-date=2022-07-05 |website=Information Security Stack Exchange |language=en |archive-date=2023-07-10 |archive-url=https://web.archive.org/web/20230710213551/https://security.stackexchange.com/questions/227459/why-is-the-bcrypt-text-orpheanbeholderscrydoubt |url-status=live }}</ref>

==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.<ref>{{Cite journal|last1=Biryukov|first1=Alex|last2=Perrin|first2=Léo|last3=Udovenko|first3=Aleksei|date=2016|title=Reverse-Engineering the S-box of Streebog, Kuznyechik and STRIBOBr1 (Full Version)|url=https://eprint.iacr.org/2016/071|journal=Iacr-Eurocrypt-2016|doi=10.1007/978-3-662-49890-3_15|access-date=2019-03-26|archive-date=2023-08-02|archive-url=https://web.archive.org/web/20230802045902/https://eprint.iacr.org/2016/071|url-status=live}}</ref>
*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.<ref name="schneier" />
* [[Dual_EC_DRBG]], a [[NIST]]-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.<ref name=wired-schneier>{{cite magazine |date=2007-11-15 |author=[[Bruce Schneier]] |title=Did NSA Put a Secret Backdoor in New Encryption Standard? |url=https://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 |magazine=[[Wired News]] }}</ref> 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."<ref>{{cite news|first=Nicole|last=Perlroth|title=Government Announces Steps to Restore Confidence on Encryption Standards|url=http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/?src=twrhp&_r=1&|access-date=September 11, 2013|newspaper=The New York Times|date=September 10, 2013|archive-date=April 23, 2015|archive-url=https://web.archive.org/web/20150423131626/http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/?src=twrhp&_r=1&|url-status=live}}</ref>
* P curves are standardized by NIST for [[elliptic curve cryptography]]. The coefficients in these curves are generated by [[Cryptographic hash function|hashing]] unexplained [[random seed]]s, such as:
** P-224: <code>bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5</code>.
** P-256: <code>c49d3608 86e70493 6a6678e1 139d26b7 819f7e90</code>.
** P-384: <code>a335926a a319a27a 1d00896a 6773a482 7acdac73</code>.
Although not directly related, after the backdoor in Dual_EC_DRBG had been exposed, suspicious aspects of the NIST's P curve constants<ref>{{cite web |url=https://safecurves.cr.yp.to/ |title=SafeCurves: Introduction |access-date=2017-05-02 |archive-date=2017-09-05 |archive-url=https://web.archive.org/web/20170905203243/http://safecurves.cr.yp.to/ |url-status=live }}</ref> led to concerns<ref>{{Cite web|url = https://lists.torproject.org/pipermail/tor-talk/2013-September/029956.html|title = [tor-talk] NIST approved crypto in Tor?|date = September 8, 2013|access-date = 2015-05-20|first = Gregory|last = Maxwell|archive-date = 2014-10-02|archive-url = https://web.archive.org/web/20141002093604/https://lists.torproject.org/pipermail/tor-talk/2013-September/029956.html|url-status = live}}</ref> that the NSA had chosen values that gave them an advantage in finding<ref>{{Cite web|title = SafeCurves: Rigidity|url = https://safecurves.cr.yp.to/rigid.html|website = safecurves.cr.yp.to|access-date = 2015-05-20|archive-date = 2015-05-22|archive-url = https://web.archive.org/web/20150522224408/http://safecurves.cr.yp.to/rigid.html|url-status = live}}</ref> private keys.<ref>{{Cite web|title = The NSA Is Breaking Most Encryption on the Internet - Schneier on Security|url = https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929|website = www.schneier.com| date=5 September 2013 |access-date = 2015-05-20|archive-date = 2017-12-15|archive-url = https://web.archive.org/web/20171215132353/https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929|url-status = live}}</ref> Since then, many protocols and programs started to use [[Curve25519]] as an alternative to NIST P-256 curve.

==Limitations==
[[Daniel J. Bernstein|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 [[Pi|π]], [[e (mathematical constant)|e]], [[Euler gamma]], [[√2]], [[√3]], [[√5]], √7, log(2), [[Golden Ratio|(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]] 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.<ref>[https://bada55.cr.yp.to/bada55-20150927.pdf How to manipulate curve standards: a white paper for the black hat] {{Webarchive|url=https://web.archive.org/web/20160308020636/http://bada55.cr.yp.to/bada55-20150927.pdf |date=2016-03-08 }} 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</ref>

==Footnotes==
{{reflist}}

==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.

[[Category:Random number generation]]
[[Category:Cryptography]]
[[Category:Transparency (behavior)]]