24 Dec 2008

Gmail has a nice feature: when delivering e-mail, everything including and after a + in a Gmail address is ignored. For example, mail arriving at all of these addresses would go to the same place if they were Gmail addresses,

account@example.com
account+nullprogram@example.com
account+slashdot@example.com

Thanks to this feature, when a user acquires a Gmail account, Google is actually providing about a googol (as in the number 10¹⁰⁰) different e-mail addresses to that user! Quite appropriate, really.

I have seen other mailers do similar things, like ignoring everything after dashes. A nice advantage to this is when registering at a new website I can customize my e-mail address for them by, say, throwing the website name in it. Because I have a google of e-mail addresses available, it is impossible to run out, so I can give every person I meet their own version of my address. The custom address can come in handy for sorting and filtering, and it will also tell me who is selling out my e-mail address. This, of course, assumes that someone isn't stripping out the extra text in my address to counter the Gmail feature.

However, in my personal experience, most websites will not permit +'s in addresses. This is completely ridiculous, because it means that virtually every website will incorrectly invalidate perfectly valid e-mail addresses. Even major websites, like coca-cola.com, screw this up. They see the + in the address and give up.

In fact, if I do a Google search for "email validation regex" right now, 9 of the first 10 results return websites with regular expressions that are complete garbage and will toss out many common, valid addresses. The only useful result was at the fifth spot (linked below).

For the love of Stallman's beard, stop writing your own e-mail address validators!

Why shouldn't you even bother writing your own? Because the proper Perl regular expression for RFC822 is over 6 kilobytes in length! Follow that link and look at that. This is the smallest regular expression you would need to get it right.

If you really insist on having a nice short one and don't want to use a validation library, which, again, is a stupid idea and you should be using a library, then use the dumbest, most liberal expression you can. (Just don't forget the security issues.) Like this,

.+@.+

Seriously, if you add anything else you most almost surely make it incorrectly reject valid addresses. Note that e-mail addresses can contain spaces, and even more than one @! These are valid addresses,

"John Doe"@example.com
"@TheBeach"@example.com

I have not yet found a website that will accept either of these, even though both are completely valid addresses. Even MS Outlook, which I use at work (allowing me to verify this), will refuse to send e-mail to these addresses (Gmail accepts it just fine). Hmmm... maybe having an address like these is a good anti-spam measure!

So if your e-mail address is "John Doe"@example.com no one using Outlook can send you e-mail, which sounds like a feature to me, really.

So, everyone, please stop writing e-mail validation regular expressions. The work has been done, and you will only get it wrong, guaranteed.

This is a similar rant I came across while writing mine: Stop Doing Email Validation the Wrong Way.

22 Dec 2008

If you are at all familiar with Dungeons and Dragons, you may have already heard of the stories of The Tale of Eric and the Dread Gazebo by Richard Aronson and The Head of Vecna. These are real classics. Read them now, if you haven't already, before you go on. If you are unfamiliar with tabletop role-playing games you should go learn a little about them first.

I would like to share one of my Dungeons and Dragons stories. It won't be anywhere as interesting as the two stories I mentioned, but I have gotten some laughs out of people I tell it to.

Back in my college days, a friend was running a 3.5 campaign and asked me to join in. The other players had rolled up their characters and done a couple practice sessions before I joined, so I was jumping into a group that had already had their start.

It was an evil campaign. Everyone in the group was either evil or neutral. We were serving some kind of evil sorcerer. I felt that being evil allowed much more variety of play and usually gave us more freedom in the game world than being good. If things started to get dry, someone would do something stupid like burn down the nearest town inn. The lawful evil characters weren't so happy about this, though.

I rolled up a chaotic evil half-orc barbarian named Gnohkk. I was lucky on my rolls and had some wonderful stats, so he was very big and strong. Gnohkk started with a two-handed axe that contained a magic fire gem in its head. After some training he was able to cause a fiery explosion at will centered at the location of the fire gem. If an untrained character wielded the axe, upon striking anything he would have to make a saving throw to prevent an explosion.

Because Gnohkk would also suffer from the explosion, this wasn't terribly useful at first, except against targets particularly vulnerable to fire, like trolls and magic trees. The training was mainly to make the axe usable.

At some point during the campaign the party got a hold of a ring of fire resistance, which was then used by Gnohkk. With this ring he was invulnerable to his own explosions, making the axe very powerful. The ring also provided a handful of simple fire spells that made combat more interesting.

Sadly, not long after the ring was found the fire gem axe chipped broke. Before discarding the broken axe, Gnohkk carefully removed the fire gem for safe keeping.

After an intense battle against some type of monsters with big horns, Gnohkk found himself a nice metal helmet. He also managed to scrounge up 10 horns from the monster corpses, which gave him a great idea. When the party got to the next town, Gnohkk visited the blacksmith, and requested to have him affix the 10 horns around the outside of the helmet. In the front of the helmet he wanted to have a socket created and the fire gem embedded inside it. The blacksmith said it would take a couple of days.

I was hoping this giant helmet would make Gnohkk more intimidating. So far in the campaign, every time he had attempted to intimidate an NPC he failed his rolls and came off looking stupid instead.

So, this was pretty cool: a giant horned helmet with a gem in the front. With the helmet on, Gnohkk could explode into a ball of flames at will and without warning. What a wonderful toy for a chaotic evil!

When Gnohkk returned to the blacksmith a couple days later he found the shop was destroyed. Some of the walls remained, the roof was gone, and weapons and tools were thrown all over the area. The blacksmith's charred body had been dead for some time. However, the helmet was completed and basically intact. Gnohkk shrugged, grabbed the helmet and left, all without having to pay a single copper to the now dead blacksmith.

We figured out later what happened (the GM probably just told us). Gnohkk failed to tell the blacksmith about the properties of the gem. When the blacksmith tapped the gem into the socket, the fire gem activated and exploded, killing him and destroying his shop.

16 Dec 2008

Some time ago I was watching through the entire series of Deep Space 9. It was a Star Trek television show about a space station that rests next a wormhole that connects to the other side of the galaxy (The Delta quadrant).

The Delta quadrant is ruled by a group called the Dominion, and they are looking to conquer the Federation side of the galaxy (the Alpha quadrant). At one point during the series, the Federation needs to temporarily disable the wormhole to prevent Dominion ships from crossing through. They do this by mining the wormhole with identical, cloaked, self-replicating mines.

If a mine is destroyed, the neighboring mines will replicate a replacement. The minefield repairs itself. This makes removing the minefield within a reasonable amount of time difficult to impossible. If even a single mine is left behind, it can replicate the entire minefield again.

The most interesting question here is this:

When the Federation returns and wants to remove the minefield, how would they do it? What would stop the Dominion from doing the same thing?

The first thing that comes to mind is having a kill signal, but what would this signal be? It could simply be a plain "kill" command, but the Dominion could also broadcast such a signal to disable the minefield. Consider that the Dominion could capture a single mine and study everything about its workings. The minefield itself could therefore hold no secrets whatsoever. This leaves out any possibility of a secret kill command stored in the mines.

Here's what I would do, assuming that humans or aliens have not yet discovered some giant breakthrough in factoring in the Star Trek universe. I would randomly generate two very large prime numbers. Today, two 1024-bit primes should be more than enough, but in 350 years even larger numbers would probably be necessary. Then, I multiply these two number together and store this number in the mine software. To disable the minefield, I simply broadcast these two numbers into the minefield. The mines would be programmed to take the product of any pairs of numbers it receives. If the product matches the internal number, the mine shuts down.

Voila! A method for shutting down the minefield. The enemy can know everything about every single mine's construction, including the software and data stored on every mine, but will be unable to disable the minefield without factoring a very large composite number, which would presumably be difficult or impossible (within a reasonable amount of time).

Another possibility would be using a hash. Come up with a strong passphrase, then use a hashing algorithm like SHA-1 or MD5, or whatever is available and appropriate in 350 years, to hash the passphrase. Store the hash in the mines. When you want to disable the minefield, broadcast the passphrase. These mines will hash the broadcast and compare it to the stored hash. It's really the same solution as before: a one-way function. This is also similar to how passwords are stored inside a computer today.

If we wanted more commands, like "don't blow up any ships for awhile" or "increase minefield density", we could generate more composites corresponding to each command. However, once a command is issued, the secret -- the two prime numbers -- is out, and it cannot be used again. In this case, I would go into the realm of public key cryptography.

I would issue a command, along with a timestamp, and maybe even a nonce that could double as a global identifier for the command, and sign the whole deal using my private key. On each mine I would store the public key. When a command is received, the mines would check the signature before executing the command. I could then issue repeat commands, as the timestamps would change each time. An adversary learns nothing when a command is issued, because the time stamps would make any replay attacks useless.

Minefields just like this exist today all over the Internet, as botnets. Thousands of computers all around the world become infected with malware and come under the control of a single individual or group. Individual machines in the botnet could be taken out, but removing the entire botnet is difficult as it grows and repairs itself. Any security researcher could disassemble the botnet malware and learn anything about it, so the malware can store no secrets. How does a malicious person control the botnet, then, without someone else taking control? Public key cryptography, just as described above.