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 RC x 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.
59-454: From 2004 to 2013, the default cryptographically secure pseudorandom number generator (CSPRNG) in BSAFE was Dual_EC_DRBG , which contained an alleged backdoor from NSA , in addition to being a biased and slow CSPRNG. The cryptographic community had been aware that Dual_EC_DRBG was a very poor CSPRNG since shortly after the specification was posted in 2005, and by 2007 it had become apparent that
118-715: A deterministic random bit generator ( DRBG ), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers . The PRNG-generated sequence is not truly random , because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators , pseudorandom number generators are important in practice for their speed in number generation and their reproducibility. PRNGs are central in applications such as simulations (e.g. for
177-500: A simple algorithm can remove a considerable amount of the bias in any bit stream, which should be applied to each bit stream before using any variation of the Santha–Vazirani design. CSPRNG designs are divided into two classes: "Practical" CSPRNG schemes not only include an CSPRNG algorithm, but also a way to initialize (" seed ") it while keeping the seed secret. A number of such schemes have been defined, including: Obviously,
236-643: A $ 10 million payment from the NSA to do so. On October 23, 2017, Shaanan Cohney , Matthew Green , and Nadia Heninger , cryptographers at the University of Pennsylvania and Johns Hopkins University , released details of the DUHK (Don't Use Hard-coded Keys) attack on WPA2 where hardware vendors use a hardcoded seed key for the ANSI X9.31 RNG algorithm, stating "an attacker can brute-force encrypted data to discover
295-515: A CSPRNG. Some classes of CSPRNGs include the following: It has been shown to be likely that the NSA has inserted an asymmetric backdoor into the NIST -certified pseudorandom number generator Dual_EC_DRBG . Most PRNG algorithms produce sequences that are uniformly distributed by any of several tests. It is an open question, and one central to the theory and practice of cryptography , whether there
354-645: A PRNG that shows the random numbers not to be truly random. Second, for most PRNGs, when their state has been revealed, all past random numbers can be retrodicted, allowing an attacker to read all past messages, as well as future ones. CSPRNGs are designed explicitly to resist this type of cryptanalysis . In the asymptotic setting , a family of deterministic polynomial time computable functions G k : { 0 , 1 } k → { 0 , 1 } p ( k ) {\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}} for some polynomial p ,
413-704: A forward secure PRNG with block length p ( k ) − k {\displaystyle p(k)-k} by splitting its output into the next state and the actual output. This is done by setting G ( s ) = G 0 ( s ) ‖ G 1 ( s ) {\displaystyle G(s)=G_{0}(s)\Vert G_{1}(s)} , in which | G 0 ( s ) | = | s | = k {\displaystyle |G_{0}(s)|=|s|=k} and | G 1 ( s ) | = p ( k ) − k {\displaystyle |G_{1}(s)|=p(k)-k} ; then G
472-670: A function f : N 1 → R {\displaystyle f:\mathbb {N} _{1}\rightarrow \mathbb {R} } (where N 1 = { 1 , 2 , 3 , … } {\displaystyle \mathbb {N} _{1}=\left\{1,2,3,\dots \right\}} is the set of positive integers) a pseudo-random number generator for P {\displaystyle P} given F {\displaystyle {\mathfrak {F}}} taking values in A {\displaystyle A} if and only if : ( # S {\displaystyle \#S} denotes
531-411: A high-quality source, generally the operating system's randomness API . However, unexpected correlations have been found in several such ostensibly independent processes. From an information-theoretic point of view, the amount of randomness, the entropy that can be generated, is equal to the entropy provided by the system. But sometimes, in practical situations, numbers are needed with more randomness than
590-658: A long period (see middle-square method ). Numbers selected from a non-uniform probability distribution can be generated using a uniform distribution PRNG and a function that relates the two distributions. First, one needs the cumulative distribution function F ( b ) {\displaystyle F(b)} of the target distribution f ( b ) {\displaystyle f(b)} : Note that 0 = F ( − ∞ ) ≤ F ( b ) ≤ F ( ∞ ) = 1 {\displaystyle 0=F(-\infty )\leq F(b)\leq F(\infty )=1} . Using
649-439: A polynomial time algorithm. A forward-secure PRNG with block length t ( k ) {\displaystyle t(k)} is a PRNG G k : { 0 , 1 } k → { 0 , 1 } k × { 0 , 1 } t ( k ) {\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}} , where
SECTION 10
#1732779897516708-579: A random number c from a uniform distribution as the probability density to "pass by", we get so that is a number randomly selected from distribution f ( b ) {\displaystyle f(b)} . This is based on the inverse transform sampling . For example, the inverse of cumulative Gaussian distribution erf − 1 ( x ) {\displaystyle \operatorname {erf} ^{-1}(x)} with an ideal uniform PRNG with range (0, 1) as input x {\displaystyle x} would produce
767-593: A random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to polynomial time in the size of the seed. Though a proof of this property is beyond the current state of the art of computational complexity theory , strong evidence may be provided by reducing to the CSPRNG from a problem that is assumed to be hard , such as integer factorization . In general, years of review may be required before an algorithm can be certified as
826-468: A simulation of the standard uniform distribution. An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method . The algorithm is as follows: take any number, square it, remove the middle digits of the resulting number as the "random number", then use that number as the seed for the next iteration. For example, squaring the number "1111" yields "1234321", which can be written as "01234321", an 8-digit number being
885-461: A true random number generator. When the maximum number of bits output from this PRNG is less than it, the expected security level is delivered and the output appears to be indistinguishable from a true random number generator. It is noted in the next revision that the claimed security strength for CTR_DRBG depends on limiting the total number of generate requests and the bits provided per generate request. The fourth and final PRNG in this standard
944-413: 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 ). Most cryptographic applications require random numbers, for example: The "quality" of the randomness required for these applications varies. For example, creating a nonce in some protocols needs only uniqueness. On
1003-577: Is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input ( p ( k ) > k {\displaystyle p(k)>k} for any k ), and if its output is computationally indistinguishable from true randomness, i.e. for any probabilistic polynomial time algorithm A , which outputs 1 or 0 as a distinguisher, for some negligible function μ {\displaystyle \mu } . (The notation x ← X {\displaystyle x\gets X} means that x
1062-424: Is a forward secure PRNG with G 0 {\displaystyle G_{0}} as the next state and G 1 {\displaystyle G_{1}} as the pseudorandom output block of the current period. Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higher-quality, quasi-random bit stream. Even earlier, John von Neumann proved that
1121-639: Is a pseudo-random number generator for P {\displaystyle P} , where F ∗ : ( 0 , 1 ) → R {\displaystyle F^{*}:\left(0,1\right)\rightarrow \mathbb {R} } is the percentile of P {\displaystyle P} , i.e. F ∗ ( x ) := inf { t ∈ R : x ≤ F ( t ) } {\displaystyle F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}} . Intuitively, an arbitrary distribution can be simulated from
1180-492: Is an important factor in the cryptographic suitability of a PRNG, but not the only one. The German Federal Office for Information Security ( German : Bundesamt für Sicherheit in der Informationstechnik , BSI) has established four criteria for quality of deterministic random number generators. They are summarized here: For cryptographic applications, only generators meeting the K3 or K4 standards are acceptable. Given: We call
1239-412: Is any way to distinguish the output of a high-quality PRNG from a truly random sequence. In this setting, the distinguisher knows that either the known PRNG algorithm was used (but not the state with which it was initialized) or a truly random algorithm was used, and has to distinguish between the two. The security of most cryptographic algorithms and protocols using PRNGs is based on the assumption that it
SECTION 20
#17327798975161298-413: Is chosen uniformly at random from the set X .) There is an equivalent characterization: For any function family G k : { 0 , 1 } k → { 0 , 1 } p ( k ) {\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}} , G is a PRNG if and only if the next output bit of G cannot be predicted by
1357-414: Is infeasible to distinguish use of a suitable PRNG from use of a truly random sequence. The simplest examples of this dependency are stream ciphers , which (most often) work by exclusive or -ing the plaintext of a message with the output of a PRNG, producing ciphertext . The design of cryptographically adequate PRNGs is extremely difficult because they must meet additional criteria. The size of its period
1416-537: Is named Dual EC DRBG . It has been shown to not be cryptographically secure and is believed to have a kleptographic NSA backdoor. A good reference is maintained by NIST . There are also standards for statistical testing of new CSPRNG designs: The Guardian and The New York Times reported in 2013 that the National Security Agency (NSA) inserted a backdoor into a pseudorandom number generator (PRNG) of NIST SP 800-90A , which allows
1475-589: Is required to have any confidence that a PRNG generates numbers that are sufficiently close to random to suit the intended use. John von Neumann cautioned about the misinterpretation of a PRNG as a truly random generator, joking that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." In practice, the output from many common PRNGs exhibit artifacts that cause them to fail statistical pattern-detection tests. These include: Defects exhibited by flawed PRNGs range from unnoticeable (and unknown) to very obvious. An example
1534-520: Is sometimes required, as illustrated by the following warning in the International Encyclopedia of Statistical Science (2010). The list of widely used generators that should be discarded is much longer [than the list of good generators]. Do not trust blindly the software vendors. Check the default RNG of your favorite software and be ready to replace it if needed. This last recommendation has been made over and over again over
1593-547: Is the Mersenne Twister (discussed below), which was published in 1998. Other higher-quality PRNGs, both in terms of computational and statistical performance, were developed before and after this date; these can be identified in the List of pseudorandom number generators . In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised linear congruential generators . The quality of LCGs
1652-440: The r i {\displaystyle r_{i}} are chosen uniformly at random from { 0 , 1 } t ( k ) {\displaystyle \{0,1\}^{t(k)}} . Any PRNG G : { 0 , 1 } k → { 0 , 1 } p ( k ) {\displaystyle G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}} can be turned into
1711-472: The Monte Carlo method ), electronic games (e.g. for procedural generation ), and cryptography . Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms , which do not inherit the linearity of simpler PRNGs, are needed. Good statistical properties are a central requirement for the output of a PRNG. In general, careful mathematical analysis
1770-638: The Transport Layer Security (TLS) protocol, submitted for standardization to IETF by an NSA employee, although it never became a standard. The extension would otherwise be harmless, but together with the Dual_EC_DRBG, it would make it easier to take advantage of the backdoor. The extension was previously not known to be enabled in any implementations, but in December 2017, it was found enabled on some Canon printer models, which use
1829-439: The security level of the underlying block cipher when the number of bits output from this PRNG is greater than two to the power of the underlying block cipher's block size in bits. When the maximum number of bits output from this PRNG is equal to the 2 , the resulting output delivers the mathematically expected security level that the key size would be expected to generate, but the output is shown to not be indistinguishable from
BSAFE - Misplaced Pages Continue
1888-468: The CSPRNG seemed to be designed to contain a hidden backdoor for NSA, usable only by NSA via a secret key. In 2007, Bruce Schneier described the backdoor as "too obvious to trick anyone to use it." The backdoor was confirmed in the Snowden leaks in 2013, and it was insinuated that NSA had paid RSA Security US$ 10 million to use Dual_EC_DRBG by default in 2004, though RSA Security denied that they knew about
1947-451: The NIST draft security standard approved for worldwide use in 2006. The leaked document states that "eventually, NSA became the sole editor". In spite of the known potential for a kleptographic backdoor and other known significant deficiencies with Dual_EC_DRBG, several companies such as RSA Security continued using Dual_EC_DRBG until the backdoor was confirmed in 2013. RSA Security received
2006-404: The NSA to readily decrypt material that was encrypted with the aid of Dual EC DRBG . Both papers reported that, as independent security experts long suspected, the NSA had been introducing weaknesses into CSPRNG standard 800-90; this being confirmed for the first time by one of the top-secret documents leaked to The Guardian by Edward Snowden . The NSA worked covertly to get its own version of
2065-742: The PRNG under consideration produces output by computing bits of pi in sequence, starting from some unknown point in the binary expansion, it may well satisfy the next-bit test and thus be statistically random, as pi is conjectured to be a normal number . However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi is currently in use (i.e. the state of the algorithm) will be able to calculate all preceding bits as well. Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts. First, while most PRNGs' outputs appear random to assorted statistical tests, they do not resist determined reverse engineering. Specialized statistical tests may be found specially tuned to such
2124-546: The RSA BSAFE library, because the extension number conflicted a part of TLS version 1.3. On November 25, 2015, RSA announced End of Life (EOL) dates for BSAFE. The End of Primary Support (EOPS) was to be reached on January 31, 2017, and the End of Extended Support (EOXS) was originally set to be January 31, 2019. That date was later further extended by RSA for some versions until January 31, 2022. During Extended Support, even though
2183-423: The available entropy can provide. Also, the processes to extract randomness from a running system are slow in actual practice. In such instances, a CSPRNG can sometimes be used. A CSPRNG can "stretch" the available entropy over more bits. The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups: For instance, if
2242-427: The backdoor had been stolen. It is also possible to derive the secret key by solving a single instance of the algorithm's elliptic curve problem (breaking an instance of elliptic curve cryptography is considered unlikely with current computers and algorithms, but a breakthrough may occur). In June 2013, Edward Snowden began leaking NSA documents. In November 2013, RSA switched the default to HMAC DRBG with SHA-256 as
2301-445: The backdoor in 2004. The Reuters article which revealed the secret $ 10 million contract to use Dual_EC_DRBG described the deal as "handled by business leaders rather than pure technologists". RSA Security has largely declined to explain their choice to continue using Dual_EC_DRBG even after the defects and potential backdoor were discovered in 2006 and 2007, and has denied knowingly inserting the backdoor. So why would RSA pick Dual_EC as
2360-469: The default option. The following month, Reuters published the report based on the Snowden leaks stating that RSA had received a payment of $ 10 million to set Dual_EC_DRBG as the default. With subsequent releases of Crypto-C Micro Edition 4.1.2 (April 2016), Micro Edition Suite 4.1.5 (April 2016) and Crypto-J 6.2 (March 2015), Dual_EC_DRBG was removed entirely. "Extended Random" was a proposed extension for
2419-454: The default? You got me. Not only is Dual_EC hilariously slow – which has real performance implications – it was shown to be a just plain bad random number generator all the way back in 2006. By 2007, when Shumow and Ferguson raised the possibility of a backdoor in the specification, no sensible cryptographer would go near the thing. And the killer is that RSA employs a number of highly distinguished cryptographers! It's unlikely that they'd all miss
BSAFE - Misplaced Pages Continue
2478-715: The following sense. If the initial state s 1 {\displaystyle s_{1}} is chosen uniformly at random from { 0 , 1 } k {\displaystyle \{0,1\}^{k}} , then for any i , the sequence ( y 1 , y 2 , … , y i , s i + 1 ) {\displaystyle (y_{1},y_{2},\dots ,y_{i},s_{i+1})} must be computationally indistinguishable from ( r 1 , r 2 , … , r i , s i + 1 ) {\displaystyle (r_{1},r_{2},\dots ,r_{i},s_{i+1})} , in which
2537-548: The input string s i {\displaystyle s_{i}} with length k is the current state at period i , and the output ( s i + 1 {\displaystyle s_{i+1}} , y i {\displaystyle y_{i}} ) consists of the next state s i + 1 {\displaystyle s_{i+1}} and the pseudorandom output block y i {\displaystyle y_{i}} of period i , that withstands state compromise extensions in
2596-521: The news about Dual_EC. As a cryptographically secure random number generator is often the basis of cryptography, much data encrypted with BSAFE was not secure against NSA. Specifically it has been shown that the backdoor makes SSL/ TLS completely breakable by the party having the private key to the backdoor (i.e. NSA). Since the US government and US companies have also used the vulnerable BSAFE, NSA can potentially have made US data less safe, if NSA's secret key to
2655-610: The number of elements in the finite set S {\displaystyle S} .) It can be shown that if f {\displaystyle f} is a pseudo-random number generator for the uniform distribution on ( 0 , 1 ) {\displaystyle \left(0,1\right)} and if F {\displaystyle F} is the CDF of some given probability distribution P {\displaystyle P} , then F ∗ ∘ f {\displaystyle F^{*}\circ f}
2714-512: The numbers were written to cards, they would take very much longer to write and read. On the ENIAC computer he was using, the "middle square" method generated numbers at a rate some hundred times faster than reading numbers in from punched cards . The middle-square method has since been supplanted by more elaborate generators. A recent innovation is to combine the middle square with a Weyl sequence . This method produces high-quality output through
2773-479: The other hand, the generation of a master key requires a higher quality, such as more entropy . And in the case of one-time pads , the information-theoretic guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy, and thus any kind of pseudorandom number generator is insufficient. Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from
2832-408: The output is not completely determined by their initial state. This addition aims to prevent attacks even if the initial state is compromised. Several CSPRNGs have been standardized. For example: The third PRNG in this standard, CTR_DRBG , is based on a block cipher running in counter mode . It has an uncontroversial design but has been proven to be weaker in terms of distinguishing attack, than
2891-419: The past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago. As an illustration, consider the widely used programming language Java . Up until 2020, Java still relied on a linear congruential generator (LCG) for its PRNG, which is of low quality (see further below). Java support was upgraded with Java 17 . One well-known PRNG to avoid major problems and still run fairly quickly
2950-473: The quality of the Mersenne Twister, which has a too-large state space and a very slow recovery from state spaces with a large number of zeros. A PRNG suitable for cryptographic applications is called a cryptographically-secure PRNG (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only negligible advantage in distinguishing the generator's output sequence from
3009-529: The rest of the encryption parameters and deduce the master encryption key used to encrypt web sessions or virtual private network (VPN) connections." During World War II , Japan used a cipher machine for diplomatic communications; the United States was able to crack it and read its messages , mostly because the "key values" used were insufficiently random. Pseudorandom number generator A pseudorandom number generator ( PRNG ), also known as
SECTION 50
#17327798975163068-427: The square of a 4-digit number. This gives "2343" as the "random" number. Repeating this procedure gives "4896" as the next result, and so on. Von Neumann used 10 digit numbers, but the process was the same. A problem with the "middle square" method is that all sequences eventually repeat themselves, some very quickly, such as "0000". Von Neumann was aware of this, but he found the approach sufficient for his purposes and
3127-609: The support policy stated that only the most severe problems would be patched, new versions were released containing bugfixes, security fixes and new algorithms. On December 12, 2020, Dell announced the reversal of RSA's past decision, allowing BSAFE product support beyond January 2022 as well as the possibility to soon acquire new licenses. Dell also announced it was rebranding the toolkits to Dell BSAFE . Cryptographically secure pseudorandom number generator A cryptographically secure pseudorandom number generator ( CSPRNG ) or cryptographic pseudorandom number generator ( CPRNG )
3186-410: The technique is easily generalized to any block cipher; AES has been suggested. If the key k is leaked, the entire X9.17 stream can be predicted; this weakness is cited as a reason for creating Yarrow. All these above-mentioned schemes, save for X9.17, also mix the state of a CSPRNG with an additional source of entropy. They are therefore not "pure" pseudorandom number generators, in the sense that
3245-408: The two-element field; such generators are related to linear-feedback shift registers . The 1997 invention of the Mersenne Twister , in particular, avoided many of the problems with earlier generators. The Mersenne Twister has a period of 2 − 1 iterations (≈ 4.3 × 10 ), is proven to be equidistributed in (up to) 623 dimensions (for 32-bit values), and at the time of its introduction
3304-435: Was known to be inadequate, but better methods were unavailable. Press et al. (2007) described the result thus: "If all scientific papers whose results are in doubt because of [LCGs and related] were to disappear from library shelves, there would be a gap on each shelf about as big as your fist." A major advance in the construction of pseudorandom generators was the introduction of techniques based on linear recurrences on
3363-451: Was running faster than other statistically reasonable generators. In 2003, George Marsaglia introduced the family of xorshift generators, again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests. In 2006, the WELL family of generators was developed. The WELL generators in some ways improves on
3422-469: Was the RANDU random number algorithm used for decades on mainframe computers . It was seriously flawed, but its inadequacy went undetected for a very long time. In many fields, research work prior to the 21st century that relied on random selection or on Monte Carlo simulations, or in other ways relied on PRNGs, were much less reliable than ideal as a result of using poor-quality PRNGs. Even today, caution
3481-405: Was worried that mathematical "fixes" would simply hide errors rather than remove them. Von Neumann judged hardware random number generators unsuitable, for, if they did not record the output generated, they could not later be tested for errors. If they did record their output, they would exhaust the limited computer memories then available, and so the computer's ability to read and write numbers. If
#515484