Nothing-up-my-sleeve number

Last updated

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. [1] 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. [2] 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 exists in the possible choices that the utility of these numbers has been questioned.

Contents

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). [3] Thus a need was felt for a more transparent way to generate constants used in cryptography.

Card that was hidden in a sleeve Poker cheating 20170611.jpg
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

Counterexamples

Although not directly related, after the backdoor in Dual_EC_DRBG had been exposed, suspicious aspects of the NIST's P curve constants [16] led to concerns [17] that the NSA had chosen values that gave them an advantage in finding [18] private keys. [19] 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 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. [20]

Footnotes

  1. 1 2 Bruce Schneier (2007-11-15). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired News .
  2. 1 2 "Blowfish Paper". Archived from the original on 2011-09-06. Retrieved 2010-06-09.
  3. 1 2 Bruce Schneier. Applied Cryptography, second edition, John Wiley and Sons, 1996, p. 247.
  4. ↑ "How is the MD2 hash function S-table constructed from Pi?". Cryptography Stack Exchange. Stack Exchange. 2 August 2014. Retrieved 23 May 2021.
  5. ↑ RFC 1321 Sec. 3.4
  6. ↑ FIPS 180-2: Secure Hash Standard (SHS) Archived 2012-03-12 at the Wayback Machine (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
  7. ↑ "Revision of NEWDES, Robert Scott, 1996". Archived from the original on 2012-11-08. Retrieved 2010-06-09.
  8. ↑ Henri Gilbert; M. Girault; P. Hoogvorst; F. Noilhan; T. Pornin; G. Poupard; J. Stern; S. Vaudenay (May 19, 1998). "Decorrelated Fast Cipher: an AES candidate" (PDF/PostScript). Archived from the original on April 9, 2008. Retrieved June 9, 2010.
  9. ↑ A. Biryukov; C. De Cannière; J. Lano; B. Preneel; S. B. Örs (January 7, 2004). Security and Performance Analysis of ARIA (PostScript) (Report). Version 1.2—Final Report. Katholieke Universiteit Leuven. Archived from the original on July 16, 2011. Retrieved June 9, 2010.
  10. ↑ Rivest, R. L. (1994). "The RC5 Encryption Algorithm" (PDF). Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e. pp. 86–96.
  11. ↑ Bernstein, Daniel J., Salsa20 specification (PDF), p. 9
  12. ↑ "src/lib/libc/crypt/bcrypt.c - diff - 1.3". cvsweb.openbsd.org. Archived from the original on 2022-07-05. Retrieved 2022-07-05.
  13. ↑ "hash - Why is the BCrypt text "OrpheanBeholderScryDoubt"". Information Security Stack Exchange. Archived from the original on 2023-07-10. Retrieved 2022-07-05.
  14. ↑ Biryukov, Alex; Perrin, Léo; Udovenko, Aleksei (2016). "Reverse-Engineering the S-box of Streebog, Kuznyechik and STRIBOBr1 (Full Version)". Iacr-Eurocrypt-2016. doi:10.1007/978-3-662-49890-3_15. Archived from the original on 2023-08-02. Retrieved 2019-03-26.
  15. ↑ Perlroth, Nicole (September 10, 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times. Archived from the original on April 23, 2015. Retrieved September 11, 2013.
  16. ↑ "SafeCurves: Introduction". Archived from the original on 2017-09-05. Retrieved 2017-05-02.
  17. ↑ Maxwell, Gregory (September 8, 2013). "[tor-talk] NIST approved crypto in Tor?". Archived from the original on 2014-10-02. Retrieved 2015-05-20.
  18. ↑ "SafeCurves: Rigidity". safecurves.cr.yp.to. Archived from the original on 2015-05-22. Retrieved 2015-05-20.
  19. ↑ "The NSA Is Breaking Most Encryption on the Internet - Schneier on Security". www.schneier.com. Archived from the original on 2017-12-15. Retrieved 2015-05-20.
  20. ↑ How to manipulate curve standards: a white paper for the black hat Archived 2016-03-08 at the Wayback Machine 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

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm.

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modular exponentiation in Galois fields, such as the RSA cryptosystem and ElGamal cryptosystem.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also referred to as a cryptographic random number generator (CRNG).

<span class="mw-page-title-main">Daniel J. Bernstein</span> American mathematician, cryptologist and computer scientist (born 1971)

Daniel Julius Bernstein is an American mathematician, cryptologist, and computer scientist. He was a visiting professor at CASA at Ruhr University Bochum until 2024, as well as a research professor of Computer Science at the University of Illinois at Chicago. Before this, he was a visiting professor in the department of mathematics and computer science at the Eindhoven University of Technology.

Articles related to cryptography include:

<span class="mw-page-title-main">RSA Security</span> American computer security company

RSA Security LLC, formerly RSA Security, Inc. and trade name RSA, is an American computer and network security company with a focus on encryption and decryption standards. RSA was named after the initials of its co-founders, Ron Rivest, Adi Shamir and Leonard Adleman, after whom the RSA public key cryptography algorithm was also named. Among its products is the SecurID authentication token. The BSAFE cryptography libraries were also initially owned by RSA. RSA is known for incorporating backdoors developed by the NSA in its products. It also organizes the annual RSA Conference, an information security conference.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, Skipjack is a block cipher—an algorithm for encryption—developed by the U.S. National Security Agency (NSA). Initially classified, it was originally intended for use in the controversial Clipper chip. Subsequently, the algorithm was declassified.

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

NSA Suite B Cryptography was a set of cryptographic algorithms promulgated by the National Security Agency as part of its Cryptographic Modernization Program. It was to serve as an interoperable cryptographic base for both unclassified information and most classified information.

Below is a timeline of notable events related to cryptography.

The Microsoft Windows platform specific Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography. It is a set of dynamically linked libraries that provides an abstraction layer which isolates programmers from the code used to encrypt the data. The Crypto API was first introduced in Windows NT 4.0 and enhanced in subsequent versions.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

Dual_EC_DRBG is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criticism, including the public identification of the possibility that the National Security Agency put a backdoor into a recommended implementation, it was, for seven years, one of four CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014.

The following outline is provided as an overview of and topical guide to cryptography:

crypt is a POSIX C library function. It is typically used to compute the hash of user account passwords. The function outputs a text string which also encodes the salt, and identifies the hash algorithm used. This output string forms a password record, which is usually stored in a text file.

NIST SP 800-90A is a publication by the National Institute of Standards and Technology with the title Recommendation for Random Number Generation Using Deterministic Random Bit Generators. The publication contains the specification for three allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash DRBG, HMAC DRBG, and CTR DRBG. Earlier versions included a fourth generator, Dual_EC_DRBG. Dual_EC_DRBG was later reported to probably contain a kleptographic backdoor inserted by the United States National Security Agency (NSA).

Dell BSAFE, formerly known as RSA BSAFE, is a FIPS 140-2 validated cryptography library, available in both C and Java. BSAFE was initially created by RSA Security, which was purchased by EMC and then, in turn, by Dell. When Dell sold the RSA business to Symphony Technology Group in 2020, Dell elected to retain the BSAFE product line. BSAFE was one of the most common encryption toolkits before the RSA patent expired in September 2000. It also contained implementations of the RCx ciphers, with the most common one being RC4. From 2004 to 2013 the default random number generator in the library was a NIST-approved RNG standard, widely known to be insecure from at least 2006, containing a kleptographic backdoor from the American National Security Agency (NSA), as part of its secret Bullrun program. In 2013 Reuters revealed that RSA had received a payment of $10 million to set the compromised algorithm as the default option. The RNG standard was subsequently withdrawn in 2014, and the RNG removed from BSAFE beginning in 2015.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.