459

Encrypting One Time Passwords [EOTP]

EOTP is a cryptographic One Time Password (OTP) protocol designed to provide a static encryption key across login sessions.
This protocol is a work in progress.

In its current form, I feel it is too complex to analyze and too difficult to implement. I will improve it when I have time. If you have an urgent need for an EOTP-like protocol, please contact me.

What's wrong with other OTP systems like S/KEY, PPP, and OTP-over-SMS?

Nothing is wrong with other OTP systems like S/KEY, Pefect Paper Passwords, OTP-over-SMS, and hardware OTP devices like the Yubikey. They are all much more secure than using a password alone, however, I believe they lack an important and useful feature:

Conventional OTP schemes do not provide a static secret key that can be used for data encryption.

Conventional OTP schemes can be used as a second factor of authentication, but they can't be used to encrypt data. When a user authenticates themselves to a server, the server receives a simple "authentication success" or "authentication failure" response from the OTP system. If the server needs to encrypt data on the user's behalf, it must fall back to generating an encryption key from the user's static password. So if the server gets hacked, a user's data is as secure as their password. The attacker is able to completely bypass the OTP authentication requirement and can run brute-force and dictionary attacks on the user's password.

EOTP changes the model. When EOTP is implemented, user data is encrypted with the combination of the user's password and a static key provided by EOTP.

Requirements for EOTP

As is necessary with any cryptographic protocol, security requirements must be explicit and understood prior to discussing the protocol itself. EOTP must...

  1. Strongly authenticate the client.
  2. Be at least as secure as classic password authentication.
  3. Be immune to passive man in the middle attacks.
  4. Not be vulnerable to replay attacks.
  5. Provide an encryption key to the server that is static across sessions.
  6. Be secure even when an attacker has collected a large amount of OTPs.
  7. Work for a reasonably long time after a single setup process through a secure channel.
  8. Not be vulnerable to Denial of Service attacks.
  9. Be as secure as the combination of the password and OTP. If the password has a security factor N and OTP key has a security factor M then the static key's security factor will be N * M.

How does EOTP work?

Hash Functions & Notation

EOTP makes heavy use of HMAC (Hash Based Message Authentication Code). Put simply, an HMAC is a keyed hash function. EOTP can be implemented using an HMAC constructed from any cryptographic hash function, but HMAC-SHA512 is recommended.

In the protocol description below, you will see the following notation:

The Setup Exchange

The following one-time setup procedure must be done through a secure channel. This can be something as simple as a user (Alice) using a trusted computer to communicate with a web server (Bob) over a TLS connection.

  1. Alice authenticates herself to Bob using the existing password-based authentication.
  2. Alice uses a RNG to generate three random numbers Ra, Rb, Rx and sends them to Bob.
  3. Bob uses a RNG to generate three random numbers Rc, Rd, Ry and sends them to Alice.
  4. Bob and Alice both compute (and save) sequence key Ks = H(Ra || Rc).
  5. Bob and Alice both compute static key Kt = H(Rb || Rd).
  6. Bob and Alice both compute (and save) salt S = H(Rx || Ry).
  7. Bob uses a RNG to generate a master key Km.
  8. Bob computes Cm = E( HMAC(Kt, <Alice's Password>), Km) then destroys Km
  9. Bob saves token T = HMAC(Kt || S, <Alice's Password> || S) and destroys Kt.
  10. Bob destroys all information related to Alice's password other than T.
  11. Bob and Alice save 128-bit counters initialized to 0. Let Ia and Ib denote Alice's and Bob's counter respectively.

At this point, Bob and Alice share a secret "sequence" key Ks and salt S. They both have 128-bit counters set to 0. Alice has the "static" key Kt. Bob has Cm which is the "master" key Km encrypted with Kt, but does not have Kt. Bob also has T, the HMAC of Alice's password and Kt.

Alice's random numbers Ra, Rb, and Rx may be omitted if she is unable to generate random numbers (e.g. if she is a website user).

The Authentication Procedure

Alice would like to authenticate herself to Bob over an insecure channel that is vulnerable to passive sniffing attacks (e.g. using a computer with a keylogger installed).

  1. Alice identifies herself to Bob.
  2. Bob responds with the current value of his 128-bit counter.
  3. Alice repeatedly computes Ks = HMAC(Ks, Ia || S) and increments Ia until Ia == Ib.
  4. Alice computes OTP = Ks XOR Kt and sends her password and OTP to Bob.
  5. Bob obtains Kt = OTP XOR Ks.
  6. Bob computes T' = HMAC(Kt || S, <Alice's Password> || S).
  7. Bob compares T' and T. If they are identical, Alice is authenticated, if not, Bob stops here.
  8. Bob computes Km by decrypting Cm with key HMAC(Kt, <Alice's Password>).
  9. Bob saves Ks = HMAC(Ks, Ib || S) and increments Ib.
  10. Bob destroys of Kt and the previous Ks.
  11. Bob uses Km to encrypt and decrypt Alice's data and destroys it when finished.

Visually,

AliceBob
"Hi, I'm Alice" -->
<Alice's Password> -->

Until Ia == Ib:
    Ks = HMAC(Ks, Ia || S)
    Ia = Ia + 1
OTP = Ks XOR Kt-->

<--Ib





Kt = OTP XOR Ks
T' = HMAC(Kt || S, <Alice's Password> || S)
Auth fail if T != T'
Km = D(HMAC(Kt, <Alice's Password>), Cm) Destroy Kt
Ks = HMAC(Ks, Ib || S) Destroy previous Ks
Ib = Ib + 1

At this point, Alice has Authenticated herself to Bob and Bob has a key Km which can be used to encrypt Alice's data.

How secure is EOTP?

Decrypting Alice's Data

If Bob is compromised, the attacker will obtain:

It is also likely that the attacker will have the latest OTP that Alice sent.

Alice's data is encrypted with Km. The attacker has Cm, which is Km encrypted with HMAC(Kt, <Alice's Password>). Suppose, for the sake of argument, that the attacker knew Alice's password. Now, to obtain the key to decrypt Cm, the attacker must obtain Kt = OTP XOR Ks, the previous Ks. Bob has destroyed the previous Ks, but his current Ks is a function of the old Ks: HMAC(Ks, Ib - 1 || S). To obtain Kt from OTP, the attacker must reverse the HMAC to obtain the previous Ks. Assuming a strong HMAC function, it is not computationally feasible.

The attacker has T = HMAC(Kt || S, <Alice's Password> || S). This is not helpful since, assuming a strong HMAC function and nonempty S, it is impossible to deduce HMAC(Kt, <Alice's Password>).

The only other way to decrypt Cm is to guess the value of HMAC(Kt, <Alice's Password>). Assuming a strong HMAC function, doing so requires 2n+m operations, assuming it would take 2n operations to guess Alice's password and 2m operations to guess Kt.

Collecting OTPs

Following the protocol, the OTP is Kt XOR Ks. Ks really represents a pseudorandom stream of bits:

Ks = HMAC(previous Ks , Ib || S)

Assuming this process represents a cryptographically strong stream cipher, the value Ks will not repeat for a very long time, so even an attacker who is able to obtain many OTPs would not be able to obtain Kt. The size of Ks is critical to security here. For that reason, Ks should be at least 512 bits wide.

Impersonating Alice

- use a block cipher to encrypt the password rather than simple xor, to be safe

Destroying Data

EOTP vs. Keyloggers and Man-In-The-Middle

- general security arguments here

EOTP vs. Server Compromise

EOTP vs. Passwords

EOTP is intended to be used alongside password authentication.

EOTP vs. Other OTP Schemes

- Passwords Computed In Advance or As Needed

Portable C Implementation

This is the

PHP Implementation

Ruby Implementation

Old

With Facebook now supporting one time passwords, the world is finally catching on the the concept of single use passwords. The idea is simple, use a different password every time you login. Once you login with a "one time" password, it can't be used again. This is useful when you want to log in to a public computer that may have spyware installed on it. When you login, any spyware on that machine will only record your single use password, which, since it has been used, can't be used to login again.

Current one time password schemes are a very good way to authenticate users. The combination of a normal password and a one time password makes that authentication even stronger. But some services want to store encrypted data on the user's behalf. To create an encryption key for this data, the server needs to get a static token each time the user logs in. From this static token, a hash algorithm can be applied to create an encryption key. In most implementations, the encryption key is created from the normal password only, or is stored in plain text on the server.

Unfortunately, in current one time password systems like S/KEY and Perfect Paper Passwords, there is no way for the server to obtain a token that is static across login sessions, so these systems can't be used to create encryption keys. If the server is storing encrypted data on the user's behalf, and the user's normal password has been logged by spyware on a public machine, their data will be decryptable without requiring their next one time password. Right now, one time passwords can only stop attackers from being able to access the ciphertext remotely, in the event of server compromise, OTP systems provide no protection of the data. They can't provide any provable security in the form of encryption.

It would be nice for the stronger authentication that one time passwords provide to extend to encryption as well. If such a system existed, the key used to encrypt the user's data would be created from both the one time password and the normal password. This would arguably increase the security of the encrypted data considerably. For this reason, we have created the Encrypting One Time Password (EOTP) system, who's goal is to provide the server with strong authentication as well as a static token that can be used to create the same encryption key every session.

Goals

EOTP Description

Functions

People

Initial Key Setup

Alice and Bob need to have a secure connection at least once to setup EOTP.

  1. Using random data from both Alice and Bob, they generate a random key, 'key'.
  2. Using random data from both Alice and Bob, they generate a random initialization vector and each save a copy, 'IVa' and 'IVb'.
  3. Bob saves H(key) and IVb.
  4. Alice saves key and IVa.
  5. Alice sets a counter (CTRa) to 0
  6. Bob sets a counter (CTRb) to 0

Both key and the IVs (IVa, IVb) have to be kept a secret. 'key' is the static key Bob will receive from Alice every session. It gets used for authentication and derivation of the application's encryption key. The IVs are going to used as a second key to encrypt 'key' as it is sent from Alice to Bob. These IVs are going to change every time Alice and Bob authenticate, which is how the same key will be sent from Alice to Bob, but will appear different (in transit) each time.

Authenticating a Session

Once EOTP has been setup, Alice can now authenticate to Bob.

The key setup is simple. Alice ends up with the key and an IV. Bob ends up with a hash of the key and the same IV. Now, both Alice and Bob share a common secret, the IV.

The goal of the authentication steps are to:

Alice is sending the same key to Bob every time, the uniqueness of the password comes from encrypting it with a different key every time it is sent.

Cryptographically, this is how it's done:

EOTP Description

Implementation:

  1. Alice computes P = E(IVa,key) [encrypts key with IVa].
  2. Alice saves IVa = H(IVa), replacing her old IVa.
  3. Alice increments CTRa
  4. Alice sends P and CTRa to Bob. P is the One time password.
  5. Bob checks CTRa against his own counter, CTRb. Bob creates a temporary CTRb and IVb and repeates steps 9 and 10 until CTRa = CTRb. He should NOT yet replace the old IVb and CTRb with the new values.
  6. Bob computes key = D(IVb,P) [decrypts P with IVb]
  7. Bob validates that H(key) is equal to the hash he saved in the initial key setup. If they are not equal, Alice is an imposter. He must then STOP what he is doing and reject the attempt. If the hash is valid, Bob can now replace his CTRb and IVb with the new values (from step 5).
  8. Bob destroys all traces of IVb from non-volatile memory, so the only copy is in RAM.
  9. Bob saves IVb = H(IVb)
  10. Bob increments CTRb
  11. Bob creates an encryption key for applications to use: H(key+salt) where salt is some random data that is unique to Alice.
  12. Bob removes all traces of key from memory

Note: This requires that both Bob and Alice are synchronized in the number of times their IV has been incremented. In the case of a power outage, error, etc.. they may become out of sync. To solve this, they each have a counter. If they become out of sync, Alice sends repeates step 2 and 3 until her counter is ahead of Bob's. Bob will then follow step 5 to finish the syncronization. If the passwords were computed in advance, this would be as easy as skipping to the next password in the sequence.

Analysis

To verify the security of EOTP, we will check if our goals have be satisfied. If all of our goals can be satisifed, we can be sure that EOTP is at least as secure as normal passwords and other OTP systems. We can also be sure that EOTP is infact useful to protect the user's data in the case of the server being compromised.

Conclusion

There are many ways EOTP can be used. It can be used in combination with a regular password, to provide multifactor authentication. It can also be used to send the user's normal password to the server if the user only rarely uses untrusted computers. This is much more secure, in my oppinion, than having a text message sent to you with a temporary password.

Also, EOTP could be implemented in a way where a user has one password for every service, and when they want to login, they use an app on their smart phone to strengthen (hash) then encrypt their password with EOTP before they ever type it in. This would solve the problem of users choosing weak passwords. No matter how bad their password is, the attacker wouldn't be able to log in without knowing the secret stored in the user's device. If the server database was ever leaked, they couldn't even brute-force the user's password with the IV because all they have is an encryption key to a ciphertext that hasn't been created yet.

Encrypting One Time Passwords (EOTP) is at least as secure as regular passwords and other one time password systems. It provides the additional benifit of providing a static key to the server, with no drawbacks. It is also very easy to implement. A OTP system that provides encryption and authentication is more secure than a OTP system that only provides authentication. Therefore, I suggest that the community reviews EOTP to verify it's security, and that EOTP becomes a standard one time password system.

The Encrypting One Time Passwords (EOTP) system is not and never will be patented, copyrighted, or protected in any way. It is, and always will be free for anyone to use for whatever purpose.

If you would like to submit a peer review paper, please contact me.