Greg Hewgill (ghewgill) wrote,
Greg Hewgill

s/key weaknesses

I've been investigating the S/Key One-Time Password System along with derived implementations such as OPIE in FreeBSD. I've experimented with OPIE on my own FreeBSD system and it seems to work as advertised. My idea was to use this technique for something, perhaps for an OpenID server. It would be good for use at a public terminal, where there is a risk of keyloggers stealing everything you type.

S/Key uses a hash function that takes arbitrary input and produces a 64-bit output. The hash function is initially applied to a salt plus the user's chosen passphrase. Then, the hash function is applied iteratively to each previous 64-bit hash result to generate a sequence of one-time passwords (which are the hashes). The server stores the last hash in sequence. The next one-time password that will work is the one that hashes to the previously used password, the one stored by the server. The password given then becomes the answer that the next password must hash to.

S/Key was designed to use a hash size of only 64 bits. This decision is justified in RFC 1760 with "This is believed to be long enough to be secure and short enough to be manually entered (see below, Form of Passwords) when necessary." Using the standard short-English-word encoding scheme, a 64-bit hash can be represented using six short English words chosen out of a 2048-word dictionary. Note that although different hash algorithms can be chosen (eg. MD4, MD5, SHA-1, RIPEMD-160), each of these functions is weakened by throwing away all but 64 bits of its output.

The problem is, 64 bits is not secure. Perhaps it was in 1995 when S/Key was designed, but the designers should have known better. My old 2 GHz P4 can calculate at least a million MD5 hashes per second, and that's not even trying very hard. With not too many computers and not too much time, one could create a table of hash inputs and outputs (with storage optimisations so the table can be stored and searched reasonably). After creating such a table, all uses of S/Key would be compromised. An attacker could intercept a one-time password you use (keylogger, looking over your shoulder, reading /etc/opiekeys, etc), and simply look it up in the appropriate table (each hash algorithm needs its own table) to find your next password. This would work regardless of what your original passphrase is.

Although the one-time password scheme introduced by S/Key seems useful, I believe using it seriously weakens the security of your system. I'm not aware of the existence of such a table of S/Key hashes, but I certainly wouldn't be surprised to learn that one exists. I also wouldn't be surprised if there are organisations out there (NSA, etc) with enough computing power to calculate the inverse hash in a short time (days? hours?) without even bothering to store a table. This is one of those "embarrassingly parallel" problems that just gets faster the more computing power you throw at it.

I believe that in principle, one-time passwords are still good for use at public terminals, or anywhere that the presence of a keylogger is possible or suspected. S/Key, however, is not the right implementation. It would be easy to implement an incompatible extension of S/Key that uses longer passwords. A better implementation could use 128 bit passwords, which is 12 short words from the S/Key dictionary, or 10 words of up to six letters. Unfortunately, doing this prevents the use of any of the existing S/Key password generators. Is the tradeoff worth it?

  • 2013 in review

    2013 is the year when everything changed. The biggest event was the birth of our daughter Lily. She was born prematurely in Shanghai while we…

  • 2012 in review

    2012 has been fairly quiet. Maybe it just seems that way because I haven't actually written anything new in this blog since last year's annual…

  • new photo galleries

    I've been busy processing photo galleries from the last year (or two) and putting them online for your perusal. Vancouver 2010 Northland…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded