Just add salt

LinkedIn.com recently experienced a security breach that exposed 6.5 million LinkedIn hashed passwords. While the thieves did not publish the user names that correspond to each password hash, there is no reason to doubt they have that information. One commentator claims he was able to crack 2 million of the 6.5 million passwords using an old PC with no graphics processor, and widely available software.  

The stolen hashed passwords were not protected by salt,  technique that stores a random number  (the "salt") with each password hash. The salt is incorporated into the hash along with the user's password. This forces an attacker to crack each password separately, rather than cracking them all at once or using widely-available precomputed tables containing the hashes of common passwords.

Last week Vicente Silveira of LinkedIn posted a blog entitled "An Update On Taking Steps To Protect Our Members." While LinkedIn is to be commended for responding quickly in public, there are some details in that blog that I'd like to comment on.

Silveira says LinkedIn has notified users whose passwords they think may be at risk and says they don't believe others are at risk, but does not say what the basis for that assurance is. More concrete info from LinkedIn would be helpful.

He goes on to advise users who have not been contacted that "it is good practice to change your passwords on any website you log into every few months."  This has to be the silliest "I screwed up,  but it it's your fault" blame shifting ever. Hint: no one does this and no one ever will. It's like telling people whose credit card numbers have been stolen that they should have been getting new credit cards every few months anyway. 

Finally, the blog reports "We have built a world-class security team here at LinkedIn including experts such as Ganesh Krishnan, formerly vice president and chief information security officer at Yahoo!, who joined us in 2010. … Under this team’s leadership, one of our major initiatives was the transition from a password database system that hashed passwords, i.e. provided one layer of encoding, to a system that both hashed and salted the passwords, i.e. provided an extra layer of protection that is a widely recognized best practice within the industry. That transition was completed prior to news of the password theft breaking on Wednesday."

Salt is not "best practice," it's de minimis security these days, but at least the "world-class team" got the importance of salt and made it a "major initiative."

So what took them so long to implement this vital security measure? 

Converting an unsalted hashed password system to a salted system should be an afternoon's work for a good security programmer. Ok, I understand, this is a production system for a major Internet presence. So they'll need design reviews, code reviews, unit testing, some forensic work to make sure no programmer pokes into the password file instead of using the proper authentication calls, full-up tests, etc., etc. So bump that afternoon to a month's work with a small team. But surely not two years?

What to do

For other enterprises that are storing unsalted hashes,  here is a simple way to convert the entire password database:

Let's say the current system has a password file indexed by user name that for each user stores H(userpassword), where H is whatever hash algorithm is currently in use.  This entry is stored at account creation and whenever a user changes their password. 

We create a new file, indexed the same way, with entries: 

           version,  salt, Hnew (salt, H(userpassword)).

* salt is a random number generated for each user. It should be at least a 32,bit value, with 64 bit preferable. While high quality random numbers are generally needed in security applications, salt is one exception. All that is needed is that the value be distributed reasonably uniformly over the size of the salt field, so the likelihood of multiple passwords having the same salt is small. 

* Hnew is a high quality, cryptographic hash, such as a member of the NIST secure hash algorithm family. SHA1 is probably good enough, but since this is a new design, I would suggest SHA512.  If SHA3 is released before you act on this, it should be a good choice. 

*version is just a number (e.g. 2) so you can switch to a different algorithm in the future-- this is just good database practice. 

As long as the original hash, H, produces a wide enough output, 128 bits should be fine, 64 bits so so, the new hash plus salt will eliminate the threat of parallel attacks or rainbow tables. For extra credit, use a key strengthening hash such as PBKDF2 or scrypt. 

Passwords and the Fifth Amendment

Note: I am not a lawyer and cannot give legal advice. See a lawyer if you need legal advice.

Many people would like to believe that the Fifth Amendment to the U.S. constitution lets them keep their password or pass phrase a secret. "No person … shall be compelled in any criminal case to be a witness against himself" But the law is not that simple. On several occasions, the U. S. government has gotten courts to order defendants to decrypt their hard drive, rather than ask for the password itself.

The question of whether and when the U.S. government can force a criminal suspect to decrypt data has finally reached a higher court. On February 23, 2012, The U.S. Court of Appeals for the Eleventh Circuit issued a ruling in U.S. v. John Doe that limits the governments ability to force someone to decrypt their hard drives. As I read it, the ruling says the government can only demand a hard drive be decrypted if it already has some specific knowledge about the files contained on that drive, so that the act of producing them would not constitute testimony that the files exist.  

In January 2012, a federal district judge in Colorado ordered a criminal defendant to decrypt her laptop's hard drive. "I find and conclude that the Fifth Amendment is not implicated by requiring production of the unencrypted contents of the Toshiba Satellite M305 laptop computer."  https://www.eff.org/cases/us-v-fricosu http://news.cnet.com/8301-31921_3-57364330-281/judge-americans-can-be-forced-to-decrypt-their-laptops/

The appeals court distinguished its case from Colorado case (which is in a different circuit) because there the government had wiretaps which mentioned data on the defendant's laptop. The appeals court decision is worth reading if you're interested in this subject. It's at https://www.eff.org/sites/default/files/filenode/OpinionDoe22312.pdf

A simple fix for the WPS security hole

In mid February, I wrote about the huge hole in Wi-Fi security caused by the WiFi Protected Setup feature that's included in most new wireless routers.

Here is what I wrote: "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."

Some routers let you turn WPS off, a good idea, but many popular brands do not. What's been done by the manufacturers whose routers are vulnerable and lack a way to turn off WPS? Not much. What's needed in most cases is a router firmware update. 

In the hope of prodding them along, I'm proposing a very simple fix for the WPS PIN vulnerability that should be easy to implement on any router.  It only requires adding six lines of source code and uses just one additional word of memory. No persistent storage or change to the user interface is required.  All it does is keep a count of how many consecutive failures to enter a valid PIN are detected. If that number exceeds some maximum, say 7, no more PIN entries will be accepted.  The count is reset whenever the router is turned off and then on.

Here are the needed software changes, in pseudocode:

Parameter macro declarations (this sets the maximum number of consecutive failed WPS code entries, 7 is a suggested value), add:

     WPS_FAIL_LIMIT = 7

Variable declarations, add:

     integer WPS_fail_count

Power up initialization code, add:

     WPS_fail_count = 0

Modify the firmware's test for successful WPS PIN entry, which presumably looks like something this:

     if (enteredPIN == storedPIN)  then register new device

         else handle bad PIN entry

to include WPS_fail_count  test: 

    if (enteredPIN == storedPIN AND WPS_fail_count <= WPS_FAIL_LIMIT)  then begin

                 WPS_fail_count = 0

                  register new device

                  end

          else begin

    If (WPS_fail_count <= WPS_FAIL_LIMIT) then WPS_fail_count = WPS_fail_count + 1

                 handle bad PIN entry

                 end

The altered code simply keeps track of how many bad PINs were added consecutively and does not allow a PIN to be registered if the found exceeds a limit. The failure limit is reset whenever power is turned off and on. Since users are familiar with cycling power as a way to clear router problems, no special user interface or documentation is required.  

This is simple and, in my opinion, foolproof. I hereby release my ideas contained in this post regarding fixes to WiFi browsers to the public domain as specified by the Creative Commons CC0 1.0 Universal declaration (http://creativecommons.org/publicdomain/zero/1.0/)

Practical sources of randomness for key generation

As promised, here are some suggestions about sources of randomness suitable for use on systems that allow entropy input to their random number generator via external typing. 

Dice

This is the Diceware™ blog, after all, so it's appropriate to start with this ancient but highly dependable source of entropy. Each roll of a die has six possible outcomes, yielding 2.58 bits of entropy [log2 (6)]. To get 128 bit of entropy, you'll need to type in the outcomes of 50 rolls. Putting 10 dice in a box with enough room to shake them up would let you enter the required number of rolls in 5 operations.

Type the outcomes of the dice rolls into whatever program you are using to generate keys, assuming it allows such input. If not, and you are using Unix-like operating system, such as Linux or Mac OS X, you can enter the entropy into its /dev/random generator.  Bring up a terminal window and type at the prompt: 

    cat >/dev/random 

followed by return. Then enter the dice rolls or one of the random string generated by other methods described below. Type Control-D when your done.

Mistakes when you're typing in these random strings just add more randomness, so if you type something wrong, don't go back, just type in the correct value and continue. 

Playing cards

Paying card are another good source of randomness, assuming they have been properly shuffled.  Seven through riffle shuffles are needed for full randomness; do a couple more for good measure. Wikipedia has a nice article on various shuffling techniques.  http://en.wikipedia.org/wiki/Shuffling A fully shuffled deck has 225 bits of entropy [log2(52!)].  The first card dealt has 5.7 bits of entropy, [log2(52)] and the amount per card decreases slowly as more cards are dealt. To get 128 bits of entropy, you should deal out 25 cards. Type in the cards including the suit, for example, you'd type

    3djs10hac …

for the 3 of Diamonds, Jack of Spades, 10 of Hearts, Ace of Clubs, and so on. There's no need to put spaces delimiters between the card values. Here is a full example that took me about 80 seconds to type in:

     4d3s4c10s2hqc5c10c3dqs6hah2dkd3hjs10dqd7s3c9s8c7c6s8h

If you need more entropy, say 256 bits, shuffle the deck again and type in another 25 cards. The deck should be shuffled again after you are done so no one can reproduce what you typed in.

Video camera 

Another way to generate randomness is to take a picture with a computer's webcam and "digest it" with a cryptographic hash function. The old saying, "a picture is worth a 1000 words" is an understatement in the computer world. Camera images typically take half a million bytes of memory or more. 

There are two sources of randomness in a digital photograph: randomness inherent in the image content and electrical noise generated by the image capture hardware. The later is likely more than enough for our purposes, but since it is not feasible to test every camera and lighting situation that my occurs, we might as well use both sources.

Here are instructions for doing this on a Mac:

1. Find and and and open Photo Booth, then take a picture. Save the snapshot file on the desktop using an uncompressed format such as TIFF.

2. Open a terminal window and type the following at the prompt (don't hit return yet):

       $ openssl dgst -sha512 

3. Drag the picture from Photo Booth picture file onto the terminal window. The Terminal program will add the file path to  the command string.

4. now type:  > /dev/random

5. Finally delete the Photo Booth picture using Finder -> Secure Empty Trash

It probably doesn't matter what you point the camera at--there should be enough noise in any camera image--but here are some suggestions:

o Trees outside your window

o Your head, especially if you had a bad hair day

o A cluttered (physical) desktop

o The screen of an old analog TV tuned to a nonexistent station. 

The last is a good choice if you want to set up a webcam as a permanent resource, say for initializing virtual machines. You'll need to write a script that mounts the camera device, takes a photo, hashes it into the randomness generator and then releases the camera for the next virtual machine.

Sound input

Even if your computer does not have a camera, you can grab random data using its audio input or microphone.  If your computer does not have a sound capture utility, you can download a free one for Windows,  Mac or Linux at http://audacity.sourceforge.net (Mac's with ILife already have GarageBand, though it's a bit complicated for this task.)

For a sound source, use a radio tuned between stations. An AM radio is preferable because FM sets tend to lock on to the nearest strong signal. If your in a noisy computer room, that might do in itself. Record 15 seconds or so of noise and save the file to the desktop, preferably using an uncompressed format (choose Export from the Audacity file menu). Then follow the steps for camera input, above. Don't forget to clean up by securely erasing the sound file when your done.

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.