This new revelation is actually rather minor compared to many others from recent years for reasons explained by Webroot in a blog entry: the number (2 million credentials) is actually small compared to many of the others, with the king of the hill being the Adobe breach of as many as 150 million credentials.
Troy Hunt's Have I been pwned? consolidates the databases from five major breaches for a single search:
152,445,165 Adobe accounts
859,777 Stratfor accounts
532,659 Gawker accounts
453,427 Yahoo! accounts
37,103 Sony accounts
Enter your email address and haveibeenpwned.com searches all of them and reports back. One of my addresses was in the Adobe database, but I knew that already:
I changed the password a while ago and hadn't used it on other sites.
As Hunt explains in a blog entry announcing the site, he built it in large part as an exercise to in using certain Windows Azure technologies, but he believes in the service and wants to make the site as useful as is practical. He says he has plans to add new databases as they come available and new features such as a service to alert you in case your email address shows up in a database and the ability to search on a whole domain (such as '@zdnet.com').
The other site, Should I Change My Password?, is mostly a front-end for pay services. The site already has the email alert service, which they call Email Watchdog, and which appears to be free. But if you simply search for an address and it's in one of their databases they won't give you any detail, just the fact that it was in a database:
It seems odd that they "...can't tell you which breach your email address was compromised in" as they say in their FAQ. haveibeenpwned.com has no trouble providing this information, as it is stored in their database for each breached record. shouldichangemypassword.com only stores a hash of the password email address, the date of the last compromise and the number of times it was compromised (i.e., presumably, the number of databases in which it was found). This seems less useful. If I learn from haveibeenpwned.com that my Adobe account was breached then I only have to change that password.
Regardless of your status on any of these databases, the only good strategy is to have strong and separate passwords for all services you use. Remembering all that is not humanly possible, so you'll need a password manager. I use LastPass, others I know use 1Password and RoboForm, and there are many others. I hope to write more about password managers soon.