Message Of The Day

Wed, 20 Dec 2006

13:37 [zork(~)] cat opie.txt

How One-Time Passwords Work

The great part about this image is that it's *wrong*!

Security experts always moan about how few people properly understand security and cryptography, and the smart ones point out that UI problems in security and crypto tools lead pretty directly to security problems. I'm convinced that the lion's share of these UI problems come from an insistance on clinging to mathematically correct metaphors that don't survive translation into everyday English.

The big example of this that I give out often is the terms used in public-key cryptography. Yes, it's true that both the public and private keys are "keys" in a mathematical sense. But one of the reasons I constantly see novices accidentally leaking private keys or otherwise confusing the two is that these names tell you nothing about their everyday purpose. In actuality, the private key is the only one that is in any sense a "key", and the public key is actually a lock.

If I want to give you an account on my system and I ask for you to use ssh keys, it's like I have a set of bicycle kennels that I am letting out for people to store their bikes in. If I decide that you should be allowed to have one, I simply ask for you to give me a lock that I can slip through the hasp on the front door and you obviously keep the key so that I never need to see it. Likewise if I give you a shell account on my system, you give me your ssh lock ("public key", to use the standard confusing terminology) which allows you to use your key (ssh private key) to enter.

That aside, one of the cleverest security access techniques to come out in recent years is OPIE, or One-time Passwords In Everything. It's basically designed so that you generate a new key each time you enter the system, like one of those constantly-changing password systems they use in spy movies. This has many of the advantages of the ssh public key system, but with the added convenience that you don't need to carry a two-kilobyte key file around with you. This convenience prevents a lot of clumsy workarounds for the key problem, which on average can be a benefit to security (if you allow long but easily remembered passphrases, for example, you avoid the problem of people keeping the short punctuation-laden passwords in their e-mail or doing something else equally dangerous).

So let's start with what the user sees when she logs into my system with the One-Time Password system. When you ssh to without an ssh key, you get a prompt such as the following:

otp-md5 73 fr8981 ext, Response:

This requires the user to use a password-generator program to generate the password. She runs the program, enters her secret passphrase and the 73 fr8981 part of the above challenge, and gets back a result like this:


She then copies and pastes these six words into the ssh window, and is let in. The next time she logs in, Zork says:

otp-md5 72 fr8981 ext, Response:

and the generator gives her:


Now, it may sound inconvenient to require this password software on every system you want to connect from. If you're in an Internet cafe, for example, you don't want to have to download and install special programs. For this reason, I have set up the page at to have both a Java ssh client (on the right) and a JavaScript One-Time Password generator program (on the left). So almost any Web browser can be used to run this password generator on any machine.

This looks like it involves a lot of spooky scary hard-to-understand crypto math, but in actuality it's a super elegant and easy to understand system. So what follows is an attempt to explain the inner workings in plain English.

If you have access to a modern Unixy system (basically every major OS except for Windows, these days. Poor bastards at Microsoft are still behind the curve there), you'll see that there's a program called md5sum that's used to make "checksums" of any amount of data you like.

A checksum is basically just a statistical summary of characteristics of the data. They usually show up as a long string of hexadecimal numbers, which make a number so large that the number of possible combinations is enough to give one of these strings to every atom in the universe.

[nick@frotz(~)] md5sum /etc/motd
74d4639801fad57b90932584d1bd8646  /etc/motd
[nick@frotz(~)] echo -n 'hello' | md5sum
5d41402abc4b2a76b9719d911017c592  -
[nick@frotz(~)] echo -n 'hello, world' | md5sum
e4d7f1b4ed2e42d15898f4b27b019da4  -
[nick@frotz(~)] echo -n 'hello' | md5sum
5d41402abc4b2a76b9719d911017c592  -

This is partly useful because it means that if you have a huge file and I have what I think is the same huge file, we can each run md5sum on it and compare the 32-character checksum string instead of comparing all umpteen gigaboobles of data. In fact, most unix nerds use a program called "rsync" instead of ftp or scp, which checksums pieces of each file to send only chunks that are different. It's very fast, and if there's an error you can just restart and it'll quickly find where it left off. The popular BitTorrent file-sharing program makes heavy use of checksums, and you may have seen it spit out the occasional Piece failed checksum: Re-downloading. log message.

The really great thing about this sort of checksum, though, is that it's impossible to go backward. You can't look at that long number up there and use it to generate the original /etc/motd file. To do this would be like trying to recreate the Oxford English Dictionary from a list of statistics saying how many spaces were in it and the average length of all the words and so on. Or it's like trying to do a sketch of someone's face using only a set of fingerprints. It's a one-way function: lobster go in, lobster stay in.

So what does this have to do with the crazy OTP password scheme? Well you may remember that the full string you see when you log in says something like otp-md5 999 fr8713. That otp-md5 is there because it uses md5 checksums to verify your passphrase.

When you enter your passphrase into the password generator, it combines the fr8713 part with it first (just to stir things up a bit, in case two people accidentally have the same secret passphrase, and you don't want it to be obvious by making the one-time passwords for the two users match up). Then it runs md5sum on this combination, and gets one of those 32-character hexadecimal checksum numbers.

Then it combines the fr8713 with the 32-character checksum it just got and runs md5sum on that. It keeps doing this 999 times (or 998 or 432 or 73 or whatever it said in the otp-md5 line) and then converts the hard-to-type 32-character checksum string into those six words so that you don't have to squint so hard to make sure you typed it in properly. The translation between the six words and the long hex string is two-way, since the computer can easily and quickly flip back and forth between them almost as easily as it can switch a word between UPPERCASE and lowercase.

So remember how the md5sum process was one-way? Knowing the result of run number 999 doesn't let you go backward to number 998 any more than those statistics let you recreate the OED or my fingerprints give you a full-color mug shot. And the system you're connecting to only stores the result of run number 999 in your account settings.

So after you set your account up by entering run number 999, the first time you log in it will say otp-md5 998 fr8713, and you'll run the JavaScript which will do the md5sum game 998 times. You'll type the englishified result into zork, and zork will de-englishify it and run md5sum on it one last time to make sure that what it gets is what it has stored for run number 999.

So Zork never actually knows your secret password, but it knows how to tell whether or not you know it. Because it knows that if it just runs this md5 checksum feedback loop thing enough times, the result will look like what it has stored.

The OTP generator Web page I have up is all JavaScript that runs in your browser, and the passphrase never leaves your machine. Have a look at the page sometime, and view source. You can scroll down and see the list of words that it uses for translating the 74d4639801fad57b90932584d1bd8646 stuff into something more typable, and then there's a function called core_md5 that does the same thing as the md5sum program. The rest is just loops so that it runs the checksum the number of times you tell it, and mixes in the fr8713 and does a couple of other basic management tasks.

[zork(~)] cal
[zork(~)] tree
[zork(~)] cat README