More on the danger revealed by duplicated keys

In my last post, I suggested that the existence duplicate keys generated by a particular device could lead an attacker to reverse engineer that device to learn the details of its entropy generation weakness. He could then replicate that weak process to generate large numbers of RSA keys and see if they match RSA public keys that haven been published or obtained some other way.  One can do even better, however. Instead of generating RSA keys to test, just generate primes, following the method the device uses to generate the first prime of an RSA pair. There is no need to spend time generating the second prime and forming the product. Each prime generated would then be tested to see if it divides any of the real RSA keys.  As Heninger points out, this test can be performed fairly quickly on all the keys at once by computing the product of all the real RSA keys.  

There is a further speed up possible. In generating primes to create an RSA key, one selects an odd number from some starting point (ideally random) and tests that number for primality, repeating the process until a prime is found. Getting certainty or a very high probability that a trial number is indeed prime takes considerable computation, involving a series of ever more stringent and expensive tests, see for example http://www.openssl.org/docs/apps/genrsa.html. For our purposes, however, a lower probability of primality suffices. The risk is that by limiting the testing, we might select a prime that the real software would have rejected and thus possibly miss a factorable key.That risk should be balanced by the possibility of testing many more keys. 

Another possible speed up might be to multiply a large number of test keys together and test their product against the product of the real keys in one big operation using a GCD algorithm. If a divisor is found, it can then be tested again the real keys to find the one (or more) that is broken. 

Testing candidate RSA primes is likely the most expensive computation in this process. However that operation is easily distributed to many processors working in parallel and might even be suitable for implementation on General Purpose Graphics processors (GPGPUs). Several groups have worked on using GPGPUs for modular arithmetic on large numbers of the type involved in primality tests. For a nice review, see:

http://brage.bibsys.no/hig/bitstream/URN:NBN:no-bibsys_brage_15987/1/Implementing%20modular%20arithmetic%20using%20OpenCL.pdf

However, the work I've seen attempts to use all the GPU processors for a single large number modular multiplication. It might be faster to test many candidate primes at once, perhaps from different entropy starting points, each on its own graphics processor, or SIMD unit.

Absent the hard work of implementing these suggestions, their potential to break real RSA keys is speculative. However, the possibility of such an attack is real enough to convince me that all keys generated by devices that have exhibited inadvertent key duplication are suspect and should be replaced as soon as possible. In my next post, I plan to offer some suggestions for generating enough strong entropy prior to key generation on systems that allow manual entropy input.

Duplicate keys could be a sign of exploitable weakness

In my previous post, I may have understated the danger of duplicate RSA keys. Here's what I said:

 "Say the entropy pool is nearly empty at the start. Then there is a good chance two different users, Adam and Alfred, using method A could generate the same two primes, and would have the same public key. That means Adam could read Alfred's mail, forge his signature and vice versa. Poor security to be sure, and anyone could find out this had happened by inspecting a public key database. But only Adam and Alfred can take advantage of the security hole, and if both Adam and Alfred are good guys, it's not that likely to be a problem.  It's like discovering two people in your town have the same front door key."

That's true as far as it goes, but discovering the existence of shared RSA keys is a clue that a weak source of entropy may had been used in generating them. If they were both created by the the same security appliance, say a particular brand of firewall, an attacker could purchase the same device and attempt to recreate the shared key by restarting the device multiple times. Collecting all available duplicate keys from the same appliance would allow them to be attacked together. But why stop there? By collecting every public key available that was generated from the same appliance, an attacker would likely discover many more keys that were created from the weak entropy pool, but had not been duplicated. With some more effort, the attacker could reverse engineer the key creation mechanism and its entropy pool weakness, allowing much faster attempts to find the vulnerable keys. They could generate hundreds of millions of keys and see which matched published or intercepted public keys. 

So the existence duplicate keys are a tell-tale that more weak keys are out there that are ripe for attack. Once the details of the poor entropy collection are known, even single-secret public keys, such as Diffie-Hellman or DSA, might be subject to such attacks. This weakness is not the instant fail of a single shared prime, but it may have broader impact. Discovering two people in your town have the same front door key could tell a thief that their locks are easy to pick.

More on the RSA shared prime story

A new blog post by Nadia Heninger https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs provides an expiation for most of the strange results reported by Lenstra et al. that my previous blog post discusses. It seems almost all of the duplicated and factorable RSA keys were generated by security appliances like firewalls and routers. These typically have poor access to entropy, particularly when they first start up, and often that is when they generate their public key pairs. 

In particular, she offers a simple explanation of the shared prime problem, based on two snippets of pseudo-code for generating an RSA key:

// method A:

seed_random_number_generator (entropy-pool)

P=generate_random_prime ()

Q=generate_random_prime ()

public_key=P*Q  

// method B:

seed_random_number_generator (entropy-pool)

P=generate_random_prime ()

add_entropy_to_pool (whatever)

Q=generate_random_prime ()

public_key=P*Q  

At first glance method B seems more secure. We want our primes to be random and adding more entropy to a random number generator can only make things better, right? Had you asked me yesterday I might have agreed. Wrong!

Say the entropy pool is nearly empty at the start. Then there is a good chance two different users, Adam and Alfred, using method A could generate the same two primes, and would have the same public key. That means Adam could read Alfred's mail, forge his signature and vice versa. Poor security to be sure, and anyone could find out this had happened by inspecting a public key database. But only Adam and Alfred can take advantage of the security hole, and if both Adam and Alfred are good guys, it's not that likely to be a problem.  It's like discovering two people in your town have the same front door key. 

Now suppose Ben and Bill use method B. There's a good chance they will share the same first prime, P, but their second prime, Q, is likely to be different. Again anyone could find out this had happened by inspecting a public key database, but in this case, once they do that, they can easily break both public keys using Euclid's two thousand year old GCD algorithm. So anyone, not just Ben and Bill, can take advantage of this security hole. It's like publishing a hi-def photo of your front door key on Flickr, allowing anyone to make a copy.  

Security software isn't easy.

So the problem does not seem to be the Random Number Generator Attack I speculated on yesterday, but that attack mode is still a real threat. Heninger has notified the manufacturers of the security devices she found to have this problem.  Whether they will be more responsive to this threat than they have been so far to the WPS problem that I blogged about in January remains to be seen.

Was Whit really right?

A recent paper titled "Ron was wrong, Whit is right" by Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter (http://eprint.iacr.org/2012/064.pdf) presents some disturbing results from their analysis of several million RSA public keys, which they obtained from published databases of key certificates. The authors did what amounts to a sanity check, testing the keys for simple vulnerabilities. Basically an RSA public key is a number that is the product of two large prime numbers. The corresponding secret key is, essentially, either of the two prime numbers. Once one is known, finding the other can be obtained by a simple (for a computer) division operation. The security RSA  depends on the widely-believed difficulty of factoring numbers, that is finding either prime given that you know the product. 

Each prime is supposed to be chosen in a random manner, making duplications unlikely. What Lenstra and his team found was that a surprising number of RSA keys were duplicated in more than one certificate (i.e. both primes were the same). Even more surprising, they found a small but significant fraction (about 0.2%) of RSA keys in their database shared one prime factor with a different RSA key in the database. That's a serious problem because there is a simple and efficient algorithm, known to Euclid, that lets you find a factor that two numbers share.  Looking for dups is easy, just sort the public keys by size. Finding shared factors is a little trickier for such a large collection, but the authors found an efficient way to test all pairs of keys in the database to see if they have a common prime factor.

Some duplicate keys appear to have the same owner, which is harmless enough. But the large number of duplicates, and particularly the keys with one shared prime, are much harder to understand. 

I would like to float one possible explanation that involves a simple, but subtle way to attack computer security: using malware injection to subvert a computer system's random number generation process. All that is necessary is to insert code that intercepts calls to the system's random number generator and replaces the proper returned value with a number generated by an algorithm crafted by the attacker.  This algorithm would be designed to have a relatively small state space, producing say only a few million or even billion possible results. These would appear random enough to simple inspection, but the attacker could test the limited number of possible keys generated using the cooked algorithm to find the correct key, thus defeating all security. Note that this attack does not require the infected computer transmit stolen keys, or logged passwords. Indeed the malware need not communicate with the outside world in any way, making detection very difficult. 

I propose that the Lenstra research may have found a signature of this attack in operation.  That is, the weakness in the substituted random number generator on infected machines may have caused the duplications. Perhaps a statistical model of the types of duplication a random number generator attack might produce could test this hypothesis. 

Lenstra et. al.'s title suggest that, due to their their findings, RSA is less secure than other public key systems, such as Diffie-Hellman. The latter only needs a single secret prime number, hence there can be no shared factors. But If I am correct, those too would have been compromised by random number generator attacks, though in ways that are less evident, since the attacker still has a limited number of possible primes to test.

WPS Spells Whoops, or the Collapse of Wi-Fi Security

The good folks at the Wi-Fi Alliance have taken a fine security product and smashed it to smithereens by adding a poorly thought out feature. The damage affects most new Wi-Fi routers and will take years to fully repair, since must users will never hear about it.

We're all familiar with Wi-Fi, the technology that literally unleashed the Internet by eliminating the Ethernet cable that tied our computers to the wall. Wi-Fi is nurtured by an industry trade association know as the Wi-Fi Alliance that was formed in 1999 to insure that products using a wireless networking standard known as IEEE 802.11 could all work together. Complex standards like 802.11 have lots of options and typically leave some issues unaddressed. Manufacturers of wireless products based on 802.11 can choose among options and fill in the missing pieces in ways that prevent their products from talking to products made by other manufacturers. The Wi-fi Alliance tied up those loose ends in a way that insures interoperability. The "Wi-Fi" trademark is owned by the alliance and manufacturers who do things the way the alliance recommends get to use the Wi-Fi Certified mark on their products. 

One issue that the original 802.11 spec did not properly address is security. The older wired Ethernet standard for joining computers to networks provided a modest level of security, in that you needed to plug the cable in to a network outlet. That usually meant you had to at least get inside the building where the network was located and do your mischief there. Wi-Fi, on the other hand, is wireless. Each Wi-Fi device is  miniature radio station, often broadcasting beyond the walls of the place where it is used. The signals can often be picked up from an adjacent parking lot or even hundred of meters away, by using a high gain directional antenna. 

The Wi-Fi Alliance alliance recognized that more security was needed and included something called Wired Equivalent Privacy or WEP in their early recommendations. WEP, as the name implies,  was intend to roughly match the modest security provided by the earlier wired systems. It didn't even accomplish that. Flaws in the WEP encryption algorithm allow it to be broken in a few minutes.

The Wi-Fi Alliance responded by developing a much stronger security system called Wi-Fi Protected Access or WPA. Developing a good encryption system is always tricky, but Wi-Fi Alliance faced an additional challenge in that many wireless device already sold had just enough computing power to implement WEP.  WPA had to be retrofitted to those devices and that took a lot of ingenuity.

Meanwhile the IEEE committee responsible for 802.11 also took up the security challenge and produced an encryption protocol for wireless called 802.11i that avoided the compromises needed for WPA but took more compute power. The alliance adopted 802.11i as WPA2 and all newer Wi-Fi certified devices do WPA2. 

Encryption systems scramble messages based on a key and  all encryption schemes face need a way for senders and recipients to exchange those keys securely. WPA and WPA2 have a fancy way of doing this in corporate environments that requires special security servers, but for individual users and smaller organizations, Wi-Fi security depends on a secret password they call a "Pre-shared Key" (PSK) that all devices on a network must possess .

Though WPA and WPA2 take steps to slow down the rate at which passwords can be tested, the steady increase in computing power available for a given cost, especially the availability graphics processors that have hundreds of general purpose computing elements, has made it possible to rapidly try large numbers of passwords to find the correct one. These days short passwords, even with the 8 character minimum length that the Wi-Fi Alliance recommends, can be broken with inexpensive computing equipment.

Users can overcome this problem by using a longer password or pass phrase. I recommend a minimum of 6 randomly chosen short words and provide a simple tool, Diceware (www.diceware.com), that lets you create a random passphrase using ordinary dice. With a long enough pass phrase, WPA and especially WPA2 are quite strong. 

Or so it seemed.

The Wi-Fi Alliance was concerned that the process of selecting and entering a good password or pass phrase was too complicated for the average user. Alliance members also wanted to sell a variety of special devices that did not have a full keyboard with which to enter a pass phase. So they came up with another recommendation, WiFi Protected Setup or WPS.

WPS offers several ways to add a device to a Wi-Fi network. One method, Push Button Connect, uses two push buttons, a button on the unit seeking access and the other button on the Wi-Fi router. Press both buttons within two minutes of each other and the two devices exchange all the information they need to add the new device to the network.

Another method uses an 8-digit number the Wi-Fi Alliance refers to as a PIN. (PIN usually stands for Personal Identification Number, but we get the idea.)  Each router that meets the WPS certification requirements has a PIN. You can enter that PIN into a device seeking network access and it calls your Wi-Fi router on the radio. The router asks the device for the PIN and if it has the correct number, the router gives the device the networks pass phrase and it's welcomed into the network. 

Here's where things get nasty.

It turns out that the WPS protocol breaks the 8-digit PIN into two have and tests them separately. A wrong PIN generates different errors depending on whether the first four digits failed to match or the last four were wrong. This lets an attacker test the two halves separately, a huge security gaff, cutting the maximum number of combinations to be tested from many millions to just 20,000.

To get their grade in Security 101 from D- to F, the designers of WPS included a check digit in the 8 digit PIN, so an attacker who has gotten the first 4 digits, 5000 attempts needed on average, only needs 500 more guesses on average to get the whole PIN. Note that there is absolutely no need for a check sum in a situation like this. If a user copies the wrong number from the label  on the device, the security protocol itself will provide the needed warning. From  security standpoint, the longer the PIN, the better; the only limit on PIN size is the patience of the human user. So why waste a digit on a check sum?

Software has been published on the Internet that takes advantage of this WPS hole to break most recent Wi-Fi router's security in a few hours.

Even without this hole, the way WPS was typically implemented presented security problems. Having the PIN number right on the router means anyone who get physical access to it can write down, photograph ore even memorize your PIN. Once they have the magic number, they can connect to your network whenever they wish. Most routers do not allow you to change the PIN  (TP_Link is an exception). So if you think your PIN may have been stolen, there's nothing you can do about it except buy a new router.

There a variety of solutions to these problems, depending on whether you are a user or a router manufacturer.

Fixes for users

If you're a user, first, determine if your wireless router has the WPS feature. Look for a label on the router with a bunch of long numbers, typically a serial number,pone or more MAC addresses and so on. See if there is a 8-digit decimal number, like 1234-5678 on the label, that is a WPS PIN. It may be marked PIN, WPS, QSS or with an icon showing two arrows pointed at each other's tails. In general, that likely means you have WPS and the security problem. One exception is Verizon's FIOS routers. According to their manual, the WPS feature is not working yet, but was to be enabled by a future firmware release so there is a PIN on their label. Procrastination pays.

One you've determined you have WPS, your best option is to disable it.  Many Belkin, DLink, Netgear and TP-Link models allow this. Many Cisco models currently do not. If you can't disable WPS on your router, check your junk closet for an older model that lacks WPS, which you could put back in service while your router manufacturer gets its act together. (Call their customer support line and ask when a fix can be expected. They need to hear from you.) Absent that, if security is important consider buying a new router from one of the manufacturers that currently let you disable WPS.

While your at it, write down you WPS PIN and put it in a safe place, then cover it over with paint, nail polish or tape to protect it from casual glances.

The simplest way to fix router firmware

Here is a very simple fix for router manufacturers who want to get a patch out quickly:

Disable the WPS feature after, say, five successive failed PIN entries and have the count reset to zero whenever the router is powered off and on.  This fix would be very simple to implement in firmware, requiring no change to the user interface, no persistent parameter storage and little end user education.  Users are already used to the idea of turning power off and on when they encounter a problem, so they would likely figure out what to do if their WPS stopped working. 

The needed changes to router firmware are extremely simple and easy to code-review and test:  There would be one new variable. It would be set to zero during power up initialization. It would be tested to make sure it hasn't exceeded the threshold before any remote PIN registration attempt is allowed, if not it would be incremented by one whenever a remote PIN registration attempt fails and and set to zero whenever a remote PIN registration attempt succeeds. 

The ideal fix 

The idle fix would combine the above with the ability to change the PIN and  the ability to turn WPS off if desired. A warning message if excessive bad WPS attempts were detected would be handy.

Check back here. I'll post more info when I get it.

A common Diceware question

Here is an e-mail I received today and my reply:

>Hello,

>Have you seen https://www.grc.com/passwords.htm?

>It is way more random and therefore safer for WPA.

>I mean, words are cool, but they are just that --

>a string with  random printable ASCII characters is

>certainly harder to crack, it seems.

>Cheers

>Indian mathematician in training

It's true that random characters provide more security (entropy) for a string of the same length, but for many people words are easier to remember. For example a 7 word Diceware(tm) phrase has about the same entropy as a 20 letter random string.  As my FAQ explains, you can also generate random characters using dice if you prefer.

As for the GRC site, they say they are not generating true random numbers, but using a pseudo-random algorithm. The algorithm they say they are using isn't terrible, but you are relying on them to be doing what they say and to be sure that their server has not been hacked. There is really no way to audit that. Dice, on the other hand, are completely secure and truly random.

Best wishes,

Arnold

The PS-3 Private Key Break

At the December 2010 Chaos Communication Congress in Berlin, a group calling itself ''fail0verflow'' announced it had succeeded in bypassing a number of Sony PlayStation 3 restrictive measures. These included the recovery of the private key Sony uses to sign code. Sony was using a technology called public key cryptography to insure that only programs it approved could run on the PS3. Public key cryptography uses one key, which is kept private, to create a mathematical puzzle that is very hard to solve, but which can be unlocked using a different key that can safely be made public. These puzzles can then be used to create electronic signatures that can be verified by any computer that has the public key. Absent unforeseen mathematical breakthroughs, if the public key algorithm is implemented correctly and the private key is kept secret, no one can forge such a signature.

The PS3 private key recovery was made possible by an improper implementation of the public key cryptography system Sony employed, Elliptic Curve Digital Signature Algorithm or ECDSA. ECDSA requires a secret random number to be generated for each signature. Those secret numbers must be different for each signature. If two signatures are found that used the same secret number, even if that number itself is not known, the private key can be recovered by simple algebra. Sony reportedly used the same secret number for all its signatures. As a result, anyone with the now-public private key can sign code it a way that is indistinguishable from a signature issued by Sony.

This flaw was not in any of the PS3 software or the IBM Cell processor that's at the heart of the PS3. It was a mistake in the program used to sign software approved to run on the PS3. That program presumably runs only on some highly guarded server at a facility controlled by Sony. The signing program could have been fixed by adding one line of code, a call to a strong random number generator, like /dev/random, to generate a new random number for each signature.  You may have to go back to the US and UK's Venona exploit in the Cold War to find an example of a large organization (the USSR in that case) screwing up what should have been an unbreakable system.

The lesson from this fiasco is that in cryptography details are crucial. Cryptographic software must be intensively reviewed by experts, not programers who recently read a book or took a course on the subject. The best solution may be open source implementations that have been available for public scrutiny for many years, and even then, an expert review of the final software is still essential. And all user of ECDSA and similar algorithms should review their signing software to insure it does not contain the same bug. This barn may contain more than one horse, so its's worth checking the door.

Here is a YouTube link to the complete presentation: http://www.youtube.com/watch?v=hcbaeKA2moE