The article is a bit miss leading. The so called security flaw does not reveal the e-mail address directly, but a MD5 hash of it. Sure it can be cracked, but it doesn't mean that it will get cracked.
And E-Mail-addresses aren't passwords; trying a few hundred variations for each firstname for each lastname is perfectly feasible and should crack a nice percentage of these hashes.
My email is firstname@companyname.co.nz (I have a few of these at different companies). I'm fairly confident this isn't going to be cracked any time soon by random MD5 hashing.
(of course, my real name can be extrapolated from my HN username)
Given 10^6 possible first names (that's really generous but, hey, I like my dictionaries to be cosmopolitan in character) and 10^6 domains (again, generous) exhaustive search takes 10^12 hashes. My laptop can do 10^7 in a second. This means you have about 10^5 seconds until your email is broken given that the MD5 hash is divulged. That's plus or minus three hours.
Your call on whether "An adversary can only defeat my security given three hours and a hardware investment of $1,600 2010 dollars" is an acceptable security bound for your users. If it isn't, don't use MD5 for crypto purposes.
The rainbow table would just need to include alphanumeric letters + '@' for up to 30 letters. I think your emails are in nearly every rainbow table in existence.
Just the 1-10 character lowercase alphanumeric rainbow table from freerainbowtables.com is 297 GB. Of course, you can generate rainbow tables with various parameters and tradeoffs so it's not trivial to compare them.
Still, I don't think I've ever had a rainbow table that contained plaintexts longer than 12 characters. Are 30+ length tables common these days?
They are after a specific list of politicians which the email addresses are probably known already. So there is no security. Hashing and hashing with salt only protects population, not individual with knowledge.
