Sold out for 10 million. RSA back door. - Printable Version +- Deep Politics Forum (https://deeppoliticsforum.com/fora) +-- Forum: Deep Politics Forum (https://deeppoliticsforum.com/fora/forum-1.html) +--- Forum: Panopticon of Global Surveillance (https://deeppoliticsforum.com/fora/forum-42.html) +--- Thread: Sold out for 10 million. RSA back door. (/thread-11901.html) |
Sold out for 10 million. RSA back door. - Magda Hassan - 21-12-2013 I've always noticed how cheap it is to buy informers. !0 mil for the keys to the nation is a bargain. Also demonstrates the danger of proprietary encryption software. Quote:http://www.reuters.com/article/2013/12/20/us-usa-security-rsa-idUSBRE9BJ1C220131220 Sold out for 10 million. RSA back door. - Magda Hassan - 21-12-2013 Report: NSA paid RSA to make flawed crypto algorithm the defaultThe NSA apparently paid RSA $10M to use Dual EC random number generator.by Peter Bright - Dec 21 2013, 10:14am EST24 Security company RSA was paid $10 million to use the flawed Dual_EC_DRBG pseudorandom number generating algorithm as the default algorithm in its BSafe crypto library, according to sources speaking to Reuters. The NSA's work to make crypto worse and betterLeaked documents say that the NSA has compromised encryption specs. It wasn't always this way.The Dual_EC_DRBG algorithm is included in the NIST-approved crypto standard SP 800-90 and has been viewed with suspicion since shortly after its inclusion in the 2006 specification. In 2007, researchers from Microsoft showed that the algorithm could be backdoored: if certain relationships between numbers included within the algorithm were known to an attacker, then that attacker could predict all the numbers generated by the algorithm. These suspicions of backdooring seemed to be confirmed this September with the news that the National Security Agency had worked to undermine crypto standards. The impact of this backdooring seemed low. The 2007 research, combined with Dual_EC_DRBG's poor performance, meant that the algorithm was largely ignored. Most software didn't implement it, and the software that did generally didn't use it. One exception to this was RSA's BSafe library of cryptographic functions. With so much suspicion about Dual_EC_DRBG, RSA quickly recommended that BSafe users switch away from the use of Dual_EC_DRBG in favor of other pseduorandom number generation algorithms that its software supported. This raised the question of why RSA had taken the unusual decision to use the algorithm in the first place given the already widespread distrust surrounding it. RSA said that it didn't enable backdoors in its software and that the choice of Dual_EC_DRBG was essentially down to fashion: at the time that the algorithm was picked in 2004 (predating the NIST specification), RSA says that elliptic curves (the underlying mathematics on which Dual_EC_DRBG is built) had become "the rage" and were felt to "have advantages over other algorithms." Reuters' report suggests that RSA wasn't merely following the trends when it picked the algorithm and that contrary to its previous claims, the company has inserted presumed backdoors at the behest of the spy agency. The $10 million that the agency is said to have been paid was more than a third of the annual revenue earned for the crypto library. Other sources speaking to Reuters said that the government did not let on that it had backdoored the algorithm, presenting it instead as a technical advance. http://arstechnica.com/security/2013/12/report-nsa-paid-rsa-to-make-flawed-crypto-algorithm-the-default/#p3 Sold out for 10 million. RSA back door. - Magda Hassan - 21-12-2013 So, They Lied (The NSA, That Is -- Again) Reuters reporting here.... (Reuters) - As a key part of a campaign to embed encryption software that it could crack into widely used computer products, the U.S. National Security Agency arranged a secret $10 million contract with RSA, one of the most influential firms in the computer security industry, Reuters has learned. The claim is that the NSA paid RSA, a commercial firm that (among other things) makes dongles for "secure" logins to places like banks and similar, to insert a bad random number generator into their reference software and make it the default.As a quick refresh public-key cryptography relies on true random numbers. If you can guess the sequence -- that is, if the numbers aren't truly random -- you can compromise the encryption. This is much easier than actually trying to break the code itself; think of it as a safe with a big, thick door and a nasty, un-pickable lock -- but because you want to break in you get the owner to install a cheezy $20 screen door on the side of the vault. This would leave the keys generated by that software "guessable", and RSA was the publisher and owner of the code in question that then wound up -- and is probably still in -- hardware and software found basically everywhere. RSA a few months ago "urged" its customers to stop using the compromised random generator. But what of all the code that is out in the "wild" that has this software in it, and this random number generator, and is set to use it? The bombshell isn't that the flaw was suspected, it is that it is now being alleged that the NSA paid RSA to make the code breakable -- on purpose. Whether RSA knew it was breakable at the time is unknown, but the NSA sure appears to have been fully-aware of it, and if Reuters' reporting is correct they basically paid off the firm to insert it into their software that was then widely distributed to pretty-much everyone. So you want to trust companies based here in the US when it comes to cryptography eh? Sounds like a good idea to me. http://market-ticker.org/post=226971 Sold out for 10 million. RSA back door. - Magda Hassan - 21-12-2013 And then there was this from a few years back. Lockheed hacked using RSA keys... inside information? Collateral damage? An experiment? Testing the system? Or not... Quote:Lockheed Martin's Security Networks Were Hacked Sold out for 10 million. RSA back door. - Magda Hassan - 21-12-2013 For teh techies. http://www.tau.ac.il/~tromer/papers/acoustic-20131218.pdf Sold out for 10 million. RSA back door. - David Guyatt - 21-12-2013 Makes you wonder about encryption systems like Pretty Good Privacy doesn't it. In fact, it makes you wonder if any security / encryption system is genuinely able to do what it claims... Sold out for 10 million. RSA back door. - Magda Hassan - 21-12-2013 Well, I would never trust a proprietary software company to protect my privacy. At least with PGP and other open source software people, that is everyone, can see if any one is trying to pull a swifty on them and do some thing about it. It is like a glass house. No place to hide any thing nasty. Not so with proprietary software. In fact I think this exposure might be the end of all such ventures, people are so over all this crap, and will do the FOSS community a great service in the end. Sold out for 10 million. RSA back door. - Magda Hassan - 08-01-2014 How the NSA (may have) put a backdoor in RSA's cryptography: A technical primerPublished on January 06, 2014 12:00PM by Nick Sullivan.There has been a lot of news lately about nefarious-sounding backdoors being inserted into cryptographic standards and toolkits. One algorithm, a pseudo-random bit generator, Dual_EC_DRBG, was ratified by the National Institute of Standards and Technology (NIST) in 2007 and is attracting a lot of attention for having a potential backdoor. This is the algorithm into which the NSA allegedly inserted a backdoor and then paid RSA to use. So how is that possible? This is a technical primer that explains what a backdoor is, how easy it can be to create your own, and the dangerous consequences of using a random number generator that was designed to have a backdoor. This is necessarily a long technical discussion, but hopefully by the end it should be clear why Dual_EC_DRBG has such a bad reputation. BackdoorsThe concept of a backdoor has cast a shadow over the security industry for a long time. A backdoor is an intentional flaw in a cryptographic algorithm or implementation that allows an individual to bypass the security mechanisms the system was designed to enforce. A backdoor is a way for someone to get something out of the system that they otherwise would not be able to. If a security system is wall, a backdoor is a secret tunnel underneath it.Backdoors can be inserted by lazy programmers who want to bypass their own security systems for debugging reasons, or they can be created to intentionally weaken a system used by others. Government agencies have been known to insert backdoors into commonly used software to enable mass surveillance. Backdoors can be built into software, hardware, or even built into the design of an algorithm. In theory, a well-designed cryptographic system does not include a backdoor. In practice, it is hard to guarantee that a piece of software is backdoor-free. A backdoor was recently found in a widely-deployed version of D-Link router firmware. The backdoor allows anyone with knowledge of a secret user agent string to log in and modify settings on any router running the vulnerable software. The D-Link backdoor took a long time to find because the source code for the router software was not available to security researchers to examine. With open source software, a researcher can look directly at the part of the code that verifies authentication and check for backdoors. Open source is great tool for understanding how code works but it is not a cure-all for finding backdoors in software. It can be difficult and time-consuming to fully analyze all the code in a complicated codebase. The International Obfuscated C Code Contest shows how code can be made extremely hard to understand. The Underhanded C Contest takes this even further, showing that benign looking code can hide malicious behavior. The translation step between human programming languages and machine code can also be used to insert a backdoor. The classic article "Reflections on Trusting Trust" introduced this idea back in 1984. The cryptographic community has recently banded together to audit the open source disk encryption software TrueCrypt for backdoors. One of the key steps in this audit is verifying that the machine code distributed online for TrueCrypt matches the source code. This requires re-building the audited source code with a fully open source compiler and making sure the machine code matches. Reproducible binaries help demonstrate that a backdoor was not inserted in the program's machine code by a malicious person or compiler. Random weaknessIn some cases, even this might not be enough. For example, TrueCrypt, like most cryptographic systems, use the system's random number generator to create secret keys. If an attacker can control or predict the random numbers produced by a system, they can often break otherwise secure cryptographic algorithms. Any predictability in a system's random number generator can render it vulnerable to attacks.Examples of security systems being bypassed using flaws (intentionally created or otherwise) in random number generators are very common. Some recent examples:
A random stream that isn'tThe digits of pi are quite random looking but they don't make a very good random number generator because they are predictable. Anyone who knows that someone is using the digits of pi as their source of randomness can use that against them. Convincing someone to use a pi-based random number generator is a difficult challenge.Many pseudo-random number generators start with a number called a seed. The seed is the starting point for the internal state of the algorithm. The algorithm generates a stream of random numbers using some mathematical operation on the internal state. As long as the seed (and the subsequent internal state) are kept secret, the pseudo-random numbers output by the algorithm are unpredictable to any observer. Conversely, anyone who knows the state will be able to predict the output. Linux uses a pool of numbers as the internal state of /dev/random, its pseudo-random number generator. Every time a program requests random data from the system, Linux returns a cryptographic hash of its internal state using the algorithm SHA-1. This hash function is designed to be one-way, it is easy to compute but very difficult to find the input given an output. It is so difficult, no person has ever published an inversion of a SHA-1 hash without knowing the input beforehand. This keeps the internal state of the random number generator secret. The random data extracted by the hash function is then mixed back into internal state. Periodically, the hashes of the timestamps of "unpredictable" system events like clicks and key presses are also mixed in. Here's a diagram of the basic pseudo-random number generator construction: In this diagram F = SHA1 and G = SHA1 + mix with XOR This construction is pretty standard. The internal state is kept secret, data is output via a one-way function, and the internal state is updated by mixing the data back into the state. At any point, if an attacker can figure out the internal state, they can predict the output. The strategic choices for F and G here are what make this construction safe. You do not lose the randomness in the pool by XOR-ing with something else, entropy always goes up. If F and G were chosen to be two completely independent one-way functions, it would probably still be safe. Having SHA-1 as F and MD5 (a different hash function) as G would not be too unreasonable of a choice. The key here is in the word independent, but first a sidestep into elliptic curves. Elliptic Curves and one-way functionsIn a previous blog post we gave a gentle introduction to elliptic curve cryptography. We talked about how this class of curves can be used for encryption and digital signature algorithms. We also hinted that elliptic curves could be used for generating random numbers. That is what we we will describe here.The reason elliptic curves are used in cryptography is the strongly one-way function they enable. As described previously, there is a geometrically intuitive way to define an arithmetic on the points of an elliptic curve. Any two points on an elliptic curve can be "dotted" ("multiplied") together to get a new point on the curve. Dotting a point with itself any number of times is fast easy to do, but going back to the original point takes a lot of computation. This operation can be used to create a nice and simple one-way function from a point P1: Given a number n, output another number m:
The metaphor used in the previous post was that the one way function in elliptic curves is like playing a peculiar game of billiards. If someone were locked alone in a room they could play a certain number of shots and the ball would end up at a particular location. However, if you entered the room at some point and simply saw the position of the ball it would be very difficult to determine the number of shots the player had taken without playing through the whole game again yourself. With this billiards analogy, we can think of this random number generator as a new bizarro game of pool. Consider two balls on the infinite elliptic curve billiards table, the yellow ball called P1 and the blue ball called P2. These two balls have specific points on the curve where they start. This is a two person game where one person is called the generator and the other is the observer. The generator has a secret number "n". The generator takes the ball P1 and performs n shots, and lets the observer see its final location. Then it takes P2 and performs n shots, taking the final location of P2 as a new value for n. Then P1 and P2 are reset to their original location and that's the end of the turn. Each turn the observer sees a new pseudo-random location for P1, and that's the output of the game. There's a trap door in your one-way functionsIn the Linux random number generator example above, SHA-1 is used as the one-way function. Let's consider what happens when we use our elliptic curve one way function instead.Looking back at the construction for a pseudo-random number generator above, we need to choose two functions to serve as F and G. The elliptic curve one-way function above seems to fit the bill, so let's use the functions defined by two points on the curve, P1 and P2. Each one-way function is hard to reverse, and if P1 and P2 are chosen randomly, they should be independent. So how do we add a backdoor? The key is to choose P1 and P2 so that to any outside observer they look random and independent, but in reality they have a special relationship that only we know. Suppose we choose P2 to be P1 dotted with itself s times, where s is secret number. Then P1 and P2 are related but it is hard to prove how since finding s requires solving the elliptic curve discrete logarithm problem. Given an initial state n, let's look at what the output becomes and what the state gets updated to. The output is the x-coordinate of: Q = P1 ◦ P1 ◦ … ◦ P1 (n times) Then we get that the state S gets updated to: P2 ◦ P2 ◦ … ◦ P2 (n times) But P2 is just P1 dotted with itself s times, so the state is really (P1 ◦ P1 ◦ … ◦ P1 (s times)) ◦ … ◦ (P1 ◦ P1 ◦ … ◦ P1 (s times)) (n times) P1 ◦ P1 ◦ … ◦ P1 (s ◦ n times) or re-arranged (P1 ◦ P1 ◦ … ◦ P1 (n times)) ◦ … ◦ (P1 ◦ P1 ◦ … ◦ P1 (n times)) (s times) Seeing that P1 dotted with itself n times is the output Q, we can write this as: Q ◦ Q ◦ … ◦ Q (s times) And since we know s and the output (and therefore Q), we can calculate the next internal state of the algorithm. The state is revealed and all subsequent bytes can be predicted. In just one round! Since given P1 and P2, finding s requires solving the discrete logarithm problem, you get to be the only one who knows this mathematical backdoor. This can be described in the terms of the billiards game from the last section. Remember the output of one turn of the game is the location of P1 after n shots and generator's secret number comes from the location of P2 after n shots. Knowing the value s is like knowing how many shots it takes to go from P1 to P2. This lets the observer cheat at the game. If you know where P1 lands after n shots, you can shoot s times from that location to get the location of P2 after n shots. This gives you the generator's secret number and allows you to predict the next turn of the game. Back to the real worldThis toy random number generator may seem very simple and the backdoor might even seem obvious. The amazing fact is that our toy random number generator described above is Dual_EC_DRBG, almost exactly. It was published by the NSA with two "random" looking points P1 and P2. There is no indication of how these values were generated.The values for the points P1 and P2 could have been chosen randomly or they could have been chosen with a deliberate relationship. If they were chosen deliberately, there is a backdoor. If they truly were chosen randomly, then finding the internal state is as difficult as breaking elliptic curve cryptography. Unfortunately, there is no way to identify if the two points were chosen together or randomly without either solving the elliptic curve discrete logarithm function, or catching the algorithm's author with the secret backdoor value. This is the nature of a one-way trapdoor function. The authors did not provide any proof of randomness for the two points P1 and P2. This could have easily been done by choosing P1 and P2 as outputs of a hash function, but they did not. This is just one of many flaws in the design of this algorithm. The evidence is mounting for Dual_EC_DRBG being well-suited for use as a back door. A working proof of concept backdoor was published in late 2013 using OpenSSL, and a patent for using the construction as "key escrow" (another term for backdoor) was filed back in 2006. Up until recently, Dual_EC_DRBG was the default random number generator for several cryptographic products from RSA (the security division of EMC), even though cryptographers have long been skeptical of the algorithm's design. There are reports of impropriety connecting a $10 million investment by the United States government and RSA's decision to use this obscure and widely maligned algorithm in their widely-distributed products. Looking AheadIt is very difficult to implement a secure system. Backdoors can be introduced at the software, hardware or even algorithm level. Algorithms backed by standards are not necessarily safe or free of backdoors. Some lessons to take away from this exercise are:
http://blog.cloudflare.com/how-the-nsa-may-have-put-a-backdoor-in-rsas-cryptography-a-technical-primer |