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?
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?
I'm totally cryptoignorant, but doesn't the use of salt mean you have to create a dictionary for every possible salt?
![[info]](http://stat.livejournal.com/img/userinfo.gif){kind=small}
ghewgill
2007-10-25T18:52:16Z
That's a good observation. However, in fact the salt is only used once, when the user's passphrase is hashed the first time. This allows the user to reuse the same passphrase between different systems and not generate the same sequence of one-time passwords.
If the salt were used on each iteration of the hash function, which would be an easy modification of the protocol, then you are right, the big dictionary approach would not work. The protocol would then be only vulnerable to an active attacker with a large amount of computing resources.
If the salt were used on each iteration of the hash function, which would be an easy modification of the protocol, then you are right, the big dictionary approach would not work. The protocol would then be only vulnerable to an active attacker with a large amount of computing resources.
decibel45
2007-10-27T06:26:27Z
Perhaps we should run a contest to break one of these...
ghewgill
2007-10-27T07:53:23Z
That's what I was thinking. The fun thing would be to break all of them, not just one, which would render S/Key and derived implementations such as OPIE completely useless.
2007-10-25T11:50:48Z