Encrypting One Time Passwords [EOTP]

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

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:

• H(X) - Hash X.
• HMAC(X, K) - HMAC X with key K.
• A || B - Concatenate A and B.
• E(K, X) - Encrypt plaintext X with key K.
• D(K, Y) - Decrypt ciphertext Y with key K.

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 R_a, R_b, R_x and sends them to Bob.
3. Bob uses a RNG to generate three random numbers R_c, R_d, R_y and sends them to Alice.
4. Bob and Alice both compute (and save) sequence key K_s = H(R_a || R_c).
5. Bob and Alice both compute static key K_t = H(R_b || R_d).
6. Bob and Alice both compute (and save) salt S = H(R_x || R_y).
7. Bob uses a RNG to generate a master key K_m.
8. Bob computes C_m = E( HMAC(K_t, <Alice's Password>), K_m) then destroys K_m
9. Bob saves token T = HMAC(K_t || S, <Alice's Password> || S) and destroys K_t.
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 I_a and I_b denote Alice's and Bob's counter respectively.

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

Alice's random numbers R_a, R_b, and R_x 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 K_s = HMAC(K_s, I_a || S) and increments I_a until I_a == I_b.
4. Alice computes OTP = K_s XOR K_t and sends her password and OTP to Bob.
5. Bob obtains K_t = OTP XOR K_s.
6. Bob computes T' = HMAC(K_t || 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 K_m by decrypting C_m with key HMAC(K_t, <Alice's Password>).
9. Bob saves K_s = HMAC(K_s, I_b || S) and increments I_b.
10. Bob destroys of K_t and the previous K_s.
11. Bob uses K_m to encrypt and decrypt Alice's data and destroys it when finished.

Visually,

Alice	Bob
"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 K_m 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:

• C_m
• The current K_s - HMAC(K_s, I_b || S) of the previous K_s
• S
• I_b
• T

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

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

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

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

Collecting OTPs

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

K_s = HMAC(previous K_s , I_b || S)

Assuming this process represents a cryptographically strong stream cipher, the value K_s 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 K_t. The size of K_s is critical to security here. For that reason, K_s 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

• Must be at least as secure as normal passwords.
• Must provide strong authentication to the client.
• Client and server must only have to communicate securely once to setup the system.
• Must provide proof that a password has not been used before.
• Must allow an attacker to collect and analyze old passwords and still be secure.
• Must provide the server with an encryption key that is the same across sessions.
• Must not be vulnerable to a DoS scenario created by an attacker trying to guess passwords.
• Must allow the attacker to gain physical access to the server at any time and not be able to re-create the encryption key without the client's next one time password.
• Passwords may be computed in advance and printed or computed as needed with a mobile device.

EOTP Description

Functions

• H(data) - Secure hash function such as SHA256
• E(key, data) - A block cipher, encrypts 'data' with the key, 'key'. Such as (AES, Serpent, Twofish, etc..).
• D(key, data) - The reverse operation of E. Decryption.

People

• Bob - The server
• Alice - The client

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:

• Pass the key that only Alice has, to Bob. This is done by encrypting the key with the IV. The result of this encryption is the one time password.
• Change (increment) both Alice's and Bob's IV to create a different shared secret. That way, the next time they authenticate, the result of the encryption in the above point (the one time password) is different the next time they authenticate.

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:

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.

• Man In The Middle Attacks

  Like normal passwords and other OTP systems, EOTP is vulnerable to MITM attacks. If the connection between Alice and Bob is not secure, the attacker could automate a MITM attack that would let him impersonate Alice for the duration of the session. This is also possible if the malware on the system is smart enough to do this attack. EOTP, and OTP systems are designed to defend against passive attacks. These are things like network sniffing and keylogging. The only way to defend against an active MITM attack is to trust the computer you are using and connect with a secure connection. In the case of MITM, EOTP has an advantage over regular passwords by not allowing the MITM to discover the encryption key being used to encrypt the user's data.

• As Secure as Normal Passwords

  This system builds on top of the concept of "normal passswords". The only difference is that this "password" is encrypted differently each time Alice wants to log in. So even if the encryption keys (the IV) are compromised, the security of EOTP is provably at least as secure as normal passwords.

• Strong Authentication

  Using EOTP, Bob can be very sure that Alice is not an imposter. He can verify that the key alice has sent him using EOTP is correct by verifying the hash that was created during the key setup.

• Secure Connection Required Only Once

  The key setup only has to happen once for EOTP to work for a long time, assuming the keys and passwords are at least 128 or 256 bits.

• Password Replay Prevention

  An attacker can not replay an old password because when bob tries to derrive the key, he will attempt to decrypt it with his IV. His IV has already been incremented since the replayed password has been used. When he tries to decrypt it, it won't decrypt into the right key. When Bob hashes it, the hash will not match the hash Bob has saved to verify Alice's identity.

• Attacker Can Analyze Old Passwords

  With EOTP, the password the attacker sees is the key encrypted with the IV. Alice and Bob are the only ones who know the current IV. It is a shared secret that changes for every login, so the attacker will never be able to decrypt the one time password into the key. To decrypt a password, the attacker needs the matching IV that it was encrypted with.

  However, if the old IVs are not disposed of properly, the attacker can decrypt old passwords. This makes step 6 (Bob destroys old IV) VERY important. If Bob doesn't destroy his old IV, the attacker can compromise Bob and use the old IV to decrypt an old password. This can be protected against by having Bob never let the IV touch non-volatile memory. He can keep his IV in RAM, but if the power goes out, Alice and Bob will have to redo the initial key setup. If they have to do that, Alice can prove her identity one last time by directly sending the key, which Bob can check with his hash. It's probably not a good idea to have Alice send her key to Bob (she could be being tricked). If there is a chance of Bob losing his IV, they should create a seperate shared key and use that to re-authenticate each other in the event of Bob losing his IV.

  The key is used to increment the IVs. So if the 'I' function is weak or easily reversible (e.g. XOR), he may be able to figure out the next IV. These possibilities are eliminated when the 'I' function is secure.

• The Key Provided to Bob Remains Constant

  The key Bob gets is the same every time, the only difference is that it is encrypted with a different key every time.

• No DoS Attacks

  If the attacker tries to guess the next one time password, no DoS situation is created. Bob never increments his IV unless Alice gives him the correct key to begin with. So an attacker can't force Alice to redo the initial key setup.

• Server Compromise

  In the case of Bob being compromised, the attacker finds two things: The hash of the encryption key, and Bob's current IV. He cannot obtain the encryption key from the hash, if the hash algorithm is strong. The IV is the decryption key for the next one time password. The current IV is useless to the attacker unless he has the next one time password. He has the key to a ciphertext that doesn't exist yet. As long as Alice doesn't authenticate to Bob while Bob is under the control of an attacker, Alice's key will not be exposed.

• Passwords Computed In Advance or As Needed

  After the key setup has been completed, Alice can pre-generate as many one time passwords as she wants. She can also generate them one at a time. All she has to do is repeat steps 1 and 2 and saves the result instead of sending it to Bob.

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.

Page Hits:	43642
Unique Hits:	25197

Defuse Security | Secure Pastebin | Password Generator | » CrackStation