Security Idea: One-Time Passwords

Typing your password into a website is increasingly risky, especially when logging in via a wireless device or from an Internet terminal. The primary risk is interception of your login information and password by an eavesdropper or via a keystroke-capture spyware installed on the machine you are using without your knowledge. Fortunately there is a way to defend against this issue, and to protect your passwords from hackers in general. The concept is a “one-time password” and is based on the concept of a one-time pad that is used in cryptography.
onetime password.

A one-time password can only work once. After using it once it would expire. However, a sequence of one-time passwords may be defined in a manner such that it easy for users to figure out what the next one-time password in the sequence is, without giving away private information.

For example, each one-time password in the numeric sequence could be determined as the result of dividing a secret number by n+1, where n is the previous divisor you used for the previous one-time password. So to generate the next one-time password all you need to know is your secret number and the last value you used for n. Then on paper or with a calculator (or in your head) — but NOT on the computer or device you are using — do the division to generate the next one-time password.

For example, let’s say your secret number is 555555.

You generate onetime passwords by dividing 555555 by n = 2, 3, … infinity.

So your first onetime password is 555555/2 = 277778 (rounding up the .5). Your second onetime password is 185185, and so on.

Each time you use a onetime password it expires and can never be used again.

In order to keep track of this, you would need to write down the last value of n you used, or record it somehow, so that you can remember it for the next time you need to generate a onetime password.

Online services and Websites could either implement such systems on their own — or much better, they could integrate with a single onetime password management webservice (so that you could have a single onetime password system for all your passwords). This central service could be called onetimepassword.com and would have an API that would enable any website to check whether the onetime password you entered at their site was valid. So let’s say you login to your webmail somewhere, and enter your next onetime password as your password. Your ISP queries onetimepassword.com with your registered onetimepassword.com username (on file in your ISP account) and your onetimepassword for this session. Onetimepassword.com checks to see if the number is valid according to your secret number and current value for n, and returns either a “yes” or a “no” to your ISP.

This system works very well, but has one vulnerabilty: if an hacker were to intercept a long enough series of onetime passwords for a single user, they might be able to use brute force or other approaches to find a number series that fits the pattern, and thus infer what your secret number must be. There are several ways to protect against this:
– Use long secret numbers
– Change secret numbers frequently
– Generate values of n using a more sophisticated function. Instead of the next value of n being computed as the previous n plus 1, use a more complex equation for n values. For example, let n = a random number. The random number can be generated by simply visiting one onetimepad.com and asking for a random number. Next, either add, subtract, multiply or divide your secret number with this random number to generate your onetime password. Onetimepassword.com remembers all random numbers it has shown to all users in the last 60 minutes. It checks your new onetime password by adding, substracting, multiplying and dividing your secret number by all random numbers it has shown in the last hour. Your new onetimepassword is a member of the set or results of those operations, it is considered valid. This method would make it impossible for a spy to apply a number-series attack to derive your secret number because they would have no way of predicting n values for you, and even if they were able to eavesdrop on you and get a series of your n values, they would have no way of predicting your next n value, as long as you keep your secret number secret.
– For even more security, you could get your random number by making a phone call to an automated onetimepassword.com random number generator. Alternatively, you could use a portable random number generator that was time-synched with a random number generator at onetimepassword.com. This could fit on a credit card, for example. You could look at it to get your current random number, then simply divide your secret number by that number and type the resulting number in as your

Social tagging: >

9 Responses to Security Idea: One-Time Passwords

  1. Tim Keller says:

    Nova, it’s a good idea but it’s been done already, several years ago, for Unix at least. There’s 2 versions, called S/KEY & OPIE. Here’s a good intro page on it: http://www.eda.org/pub/tools/skey_info.html
    Tim

  2. carolyn says:

    as well as SecureID, SofToken…

  3. Nova says:

    Thanks Tim, interesting link!!!
    Nova

  4. Nova says:

    Thanks carolyn!
    Nova

  5. Bill says:

    SecureID is a great example. Something you know plus something you have which changes every minute. The need for centralized administration is reduced to the local level.
    http://www.rsasecurity.com/products/securid/

  6. ::G says:

    Very dangerous proposition. The whole point of one-time pads is that there’s no possible correlation between previous messages and current messages. The method of using a single key to generate subkeys can always be broken through cryptanalysis, and has no relation to one-time pads (OTPs). Further, the suggestion of using a website to disseminate the subkeys is highly insecure, particularly susceptible to man-in-the-middle attacks that could be used to collect enough data to extrapolate the master key.
    Disclaimer: I’m not a crypto professional, but I have studied the subject enough to know basic security issues when I see them. Well, if reading Schneier and the occasional paper counts as studying, that is.
    It would be safer to just burn random bits onto pairs of DVD-Rs and give the other half — in person, not via mail!! — to the party you want to communicate with. OTPs are the only truly secure and unbreakable form of encryption. Of course there are other issues if someone breaks into your house and swipes your encryption DVDs….
    Sorry to be a downer. However, the wireless power thread is interesting, especially to a Tesla fan.
    ::G

  7. Nova Spivack says:

    Yes I suppose you are right there is a potential risk of a man-in-the-middle attack on the system. That’s why I proposed the random-number approach at the end of the post, but even that is still vulnerable to some degree. Still, you have to admit this system would be *a lot* better than the current way of doing passwords on the Web! It’s a tradeoff ultimately. A true onetime pad is too cumbersome because the user has to always have the pad with them. The method I was proposing is “halfway” because there is a way for the user to remember how to generate new passwords, but without extensive cryptanalysis an attacker would have a hard time making use of one or even just a few intercepted passwords (since they can only be used once and the pattern for generating them is effectively almost random, using the random key approach). Of course if someone was able to intercept a sequence of such “random” passwords even that could be easily cracked. So I wouldn’t advocate this for extremely sensitive data protection, etc. — for that I would propose quantum crytpo such as what MagiQ is making — it not only tells you if someone tried to intercept a key, but it also requires nearly infinite computing power to crack!

  8. A few challenges occur to me:
    1. How do you, the user, know the state of the system you are connecting to (or trying to) i.e. say I am on an only semi-reliable connection (WIFI for example) and try to connect to a website – it is not at all unlikely that at some point my connection will fail, leaving me uncertain as to the state of the password for that site – i.e. is it still the last “one-time” code that I tried to use (but did not succeed) or is it now the next one.
    2. Memory. Specifically the user’s – passwords are difficult to remember, but grow easier over time as you use the same password frequently, this system would require you to recall a CHANGING piece of key data over time – so memory aids would not work, thus many more people would have to write it down.
    3. If centralized what do I do if I am connecting to MULTIPLE sites during a given session (say via different browser windows)? Which password(s) do I use? What if I am not using the same browser but am using multiple browsers on my computer?
    What if I am using multiple computers at the same time? It implies, I think, that I have to recall a precise order of connection to each site – rendering automated tools to recall passwords difficult at best.
    I think it is a bit of overkill for the vast majority of websites that require passwords. Personally I recommend people use a two-tiered approach to passwords:
    For the first tier, “less important” sites (such as most websites that do not contain/impact financial or medical data, the NY Times website being a clear example) use a password that is unique to that site, but easily remembered by you – and regenerated if you forget it (i.e. use an internal system to generate the password that you can run again in the future and get the same result – something like “take the first letter of the site name and repeat it 5 times adding a number that is the number of characters in the domainname” – i.e. something that you can use to generate a 6-8 character password (where you are limited to that, with a variation where you are not so limited)
    Second – “secure” passwords – these are for your email, for your brokerage accounts, for your health data etc. Use a password that is either completely random – but such that you can memorize it, or use a password that is a menomic but unique to that site (the first letters of the first lyric of a song you like for example). Such passwords generally should contain numbers and generally some mixed-case as well.
    That’s basically what I do – sure it is not fully secure, but it is capable of working with the limitations of my own memory. (note – I use a very different algorithm for my passwords – just made that one up on the spot).
    Shannon

  9. ::G, someone did devise a system of randon bits burned onto a CD-ROM. It was called FolderSafe, and was used as a means of encrypting files on a specified directory on one’s hard drive. The idea was that without the key CD, the data in the secured directory on the hard drive would be invulnerable. Unfortunately, the company did not surive the dot-com collapse.