possible, while still ensuring that usability is not impacted.
7.5. Management of Shared Secrets
The operations dealing with the shared secrets used to generate and
verify OTP values must be performed securely, in order to mitigate
risks of any leakage of sensitive information. We describe in this
section different modes of operations and techniques to perform these
different operations with respect to the state of the art in data
security.
We can consider two different avenues for generating and storing
(securely) shared secrets in the Validation system:
* Deterministic Generation: secrets are derived from a master
seed, both at provisioning and verification stages and generated
on-the-fly whenever it is required.
* Random Generation: secrets are generated randomly at
provisioning stage and must be stored immediately and kept
secure during their life cycle.
Deterministic Generation
------------------------
A possible strategy is to derive the shared secrets from a master
secret. The master secret will be stored at the server only. A
tamper-resistant device MUST be used to store the master key and
derive the shared secrets from the master key and some public
information. The main benefit would be to avoid the exposure of the
shared secrets at any time and also avoid specific requirements on
storage, since the shared secrets could be generated on-demand when
needed at provisioning and validation time.
We distinguish two different cases:
- A single master key MK is used to derive the shared secrets;
each HOTP device has a different secret, K_i = SHA-1 (MK,i)
where i stands for a public piece of information that identifies
uniquely the HOTP device such as a serial number, a token ID,
etc. Obviously, this is in the context of an application or
service -- different application or service providers will have
different secrets and settings.
- Several master keys MK_i are used and each HOTP device stores a
set of different derived secrets, {K_i,j = SHA-1(MK_i,j)} where
j stands for a public piece of information identifying the
device. The idea would be to store ONLY the active master key
at the validation server, in the Hardware Security Module (HSM),
and keep in a safe place, using secret sharing methods such as
[Shamir] for instance. In this case, if a master secret MK_i is
compromised, then it is possible to switch to another secret
without replacing all the devices.
The drawback in the deterministic case is that the exposure of the
master secret would obviously enable an attacker to rebuild any
shared secret based on correct public information. The revocation of
all secrets would be required, or switching to a new set of secrets
in the case of multiple master keys.
On the other hand, the device used to store the master key(s) and
generate the shared secrets MUST be tamper resistant. Furthermore,
the HSM will not be exposed outside the security perimeter of the
validation system, therefore reducing the risk of leakage.
Random Generation
-----------------
The shared secrets are randomly generated. We RECOMMEND following
the recommendations in [RFC4086] and selecting a good and secure
random source for generating these secrets. A (true) random
generator requires a naturally occurring source of randomness.
Practically, there are two possible avenues to consider for the
generation of the shared secrets:
* Hardware-based generators: they exploit the randomness that
occurs in physical phenomena. A nice implementation can be based on
oscillators and built in such ways that active attacks are more
difficult to perform.
* Software-based generators: designing a good software random
generator is not an easy task. A simple, but efficient,
implementation should be based on various sources and apply to the
sampled sequence a one-way function such as SHA-1.
We RECOMMEND selecting proven products, being hardware or software
generators, for the computation of shared secrets.
We also RECOMMEND storing the shared secrets securely, and more
specifically encrypting the shared secrets when stored using tamper-
resistant hardware encryption and exposing them only when required:
for example, the shared secret is decrypted when needed to verify an
HOTP value, and re-encrypted immediately to limit exposure in the RAM
for a short period of time. The data store holding the shared
secrets MUST be in a secure area, to avoid as much as possible direct
attack on the validation system and secrets database.
Particularly, access to the shared secrets should be limited to
programs and processes required by the validation system only. We
will not elaborate on the different security mechanisms to put in
place, but obviously, the protection of shared secrets is of the
uttermost importance.
8. Composite Shared Secrets
It may be desirable to include additional authentication factors in
the shared secret K. These additional factors can consist of any
data known at the token but not easily obtained by others. Examples
of such data include:
* PIN or Password obtained as user input at the token
* Phone number
* Any unique identifier programmatically available at the token
In this scenario, the composite shared secret K is constructed during
the provisioning process from a random seed value combined with one
or more additional authentication factors. The server could either
build on-demand or store composite secrets -- in any case, depending
on implementation choice, the token only stores the seed value. When
the token performs the HOTP calculation, it computes K from the seed
value and the locally derived or input values of the other
authentication factors.
The use of composite shared secrets can strengthen HOTP-based
authentication systems through the inclusion of additional
authentication factors at the token. To the extent that the token is
a trusted device, this approach has the further benefit of not
requiring exposure of the authentication factors (such as the user
input PIN) to other devices.
9. Bi-Directional Authentication
Interestingly enough, the HOTP client could also be used to
authenticate the validation server, claiming that it is a genuine
entity knowing the shared secret.
Since the HOTP client and the server are synchronized and share the
same secret (or a method to recompute it), a simple 3-pass protocol
could be put in place:
1- The end user enter the TokenID and a first OTP value OTP1;
2- The server checks OTP1 and if correct, sends back OTP2;
3- The end user checks OTP2 using his HOTP device and if correct,
uses the web site.
Obviously, as indicated previously, all the OTP communications have
to take place over a secure channel, e.g., SSL/TLS, IPsec
connections.
10. Conclusion
This document describes HOTP, a HMAC-based One-Time Password
algorithm. It also recommends the preferred implementation and
related modes of operations for deploying the algorithm.
The document also exhibits elements of security and demonstrates that
the HOTP algorithm is practical and sound, the best possible attack
being a brute force attack that can be prevented by careful
implementation of countermeasures in the validation server.
Eventually, several enhancements have been proposed, in order to
improve security if needed for specific applications.
11. Acknowledgements
The authors would like to thank Siddharth Bajaj, Alex Deacon, Loren
Hart, and Nico Popp for their help during the conception and
redaction of this document.
12. Contributors
The authors of this document would like to emphasize the role of
three persons who have made a key contribution to this document:
- Laszlo Elteto is system architect with SafeNet, Inc.
- Ernesto Frutos is director of Engineering with Authenex, Inc.
- Fred McClain is Founder and CTO with Boojum Mobile, Inc.
Without their advice and valuable inputs, this document would not be
the same.
13. References
13.1. Normative References
[BCK1] M. Bellare, R. Canetti and H. Krawczyk, "Keyed Hash
Functions and Message Authentication", Proceedings of
Crypto’96, LNCS Vol. 1109, pp. 1-15.
[BCK2] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
Hashing for Message Authentication", RFC 2104, February
1997.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC3979] Bradner, S., "Intellectual Property Rights in IETF
Technology", BCP 79, RFC 3979, March 2005.
[RFC4086] Eastlake, D., 3rd, Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106, RFC 4086,
June 2005.
13.2. Informative References
[OATH] Initiative for Open AuTHentication
http://www.openauthentication.org
[PrOo] B. Preneel and P. van Oorschot, "MD-x MAC and building
fast MACs from hash functions", Advances in Cryptology
CRYPTO ’95, Lecture Notes in Computer Science Vol. 963, D.
Coppersmith ed., Springer-Verlag, 1995.
[Crack] Crack in SHA-1 code ’stuns’ security gurus
http://www.eetimes.com/showArticle.jhtml?
articleID=60402150
[Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005.
http://www.schneier.com/blog/archives/2005/02/
sha1_broken.html
[Res] Researchers: Digital encryption standard flawed
http://news.com.com/
Researchers+Digital+encryption+standard+flawed/
2100-1002-5579881.html?part=dht&tag=ntop&tag=nl.e703
[Shamir] How to Share a Secret, by Adi Shamir. In Communications
of the ACM, Vol. 22, No. 11, pp. 612-613, November, 1979.
Appendix A - HOTP Algorithm Security: Detailed Analysis
The security analysis of the HOTP algorithm is summarized in this
section. We first detail the best attack strategies, and then
elaborate on the security under various assumptions and the impact of
the truncation and make some recommendations regarding the number of
digits.
We focus this analysis on the case where Digit = 6, i.e., an HOTP
function that produces 6-digit values, which is the bare minimum
recommended in this document.
A.1. Definitions and Notations
We denote by {0,1}^l the set of all strings of length l.
Let Z_{n} = {0,.., n - 1}.
Let IntDiv(a,b) denote the integer division algorithm that takes
input integers a, b where a >= b >= 1 and returns integers (q,r)
the quotient and remainder, respectively, of the division of a by b.
(Thus, a = bq + r and 0 <= r < b.)
Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that takes
a k-bit key K and c-bit counter C and returns an n-bit output H(K,C).
(In the case of HOTP, H is HMAC-SHA-1; we use this formal definition
for generalizing our proof of security.)
A.2. The Idealized Algorithm: HOTP-IDEAL
We now define an idealized counterpart of the HOTP algorithm. In
this algorithm, the role of H is played by a random function that
forms the key.
To be more precise, let Maps(c,n) denote the set of all functions
mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key
space Maps(c,n), so that a "key" for such an algorithm is a function
h from {0,1}^c to {0,1}^n. We imagine this key (function) to be
drawn at random. It is not feasible to implement this idealized
algorithm, since the key, being a function from {0,1}^c to {0,1}^n,
is way too large to even store. So why consider it?
Our security analysis will show that as long as H satisfies a certain
well-accepted assumption, the security of the actual and idealized
algorithms is for all practical purposes the same. The task that
really faces us, then, is to assess the security of the idealized
algorithm.
In analyzing the idealized algorithm, we are concentrating on
assessing the quality of the design of the algorithm itself,
independently of HMAC-SHA-1. This is in fact the important issue.
A.3. Model of Security
The model exhibits the type of threats or attacks that are being
considered and enables one to assess the security of HOTP and HOTP-
IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the purpose of
this security analysis.
The scenario we are considering is that a user and server share a key
K for ALG. Both maintain a counter C, initially zero, and the user
authenticates itself by sending ALG(K,C) to the server. The latter
accepts if this value is correct.
In order to protect against accidental increment of the user counter,
the server, upon receiving a value z, will accept as long as z equals
ALG(K,i) for some i in the range C,...,C + s-1, where s is the
resynchronization parameter and C is the server counter. If it
accepts with some value of i, it then increments its counter to i+1.
If it does not accept, it does not change its counter value.
The model we specify captures what an adversary can do and what it
needs to achieve in order to "win". First, the adversary is assumed
to be able to eavesdrop, meaning, to see the authenticator
transmitted by the user. Second, the adversary wins if it can get
the server to accept an authenticator relative to a counter value for
which the user has never transmitted an authenticator.
The formal adversary, which we denote by B, starts out knowing which
algorithm ALG is being used, knowing the system design, and knowing
all system parameters. The one and only thing it is not given a
priori is the key K shared between the user and the server.
The model gives B full control of the scheduling of events. It has
access to an authenticator oracle representing the user. By calling
this oracle, the adversary can ask the user to authenticate itself
and get back the authenticator in return. It can call this oracle as
often as it wants and when it wants, using the authenticators it
accumulates to perhaps "learn" how to make authenticators itself. At
any time, it may also call a verification oracle, supplying the
latter with a candidate authenticator of its choice. It wins if the
server accepts this accumulator.
Consider the following game involving an adversary B that is
attempting to compromise the security of an authentication algorithm
ALG: K x {0,1}^c --> R.
Initializations - A key K is selected at random from K, a counter C
is initialized to 0, and the Boolean value win is set to false.
Game execution - Adversary B is provided with the two following
oracles:
Oracle AuthO()
--------------
A = ALG(K,C)
C = C + 1
Return O to B
Oracle VerO(A)
--------------
i = C
While (i <= C + s - 1 and Win == FALSE) do
If A == ALG(K,i) then Win = TRUE; C = i + 1
Else i = i + 1
Return Win to B
AuthO() is the authenticator oracle and VerO(A) is the verification
oracle.
Upon execution, B queries the two oracles at will. Let Adv(B) be the
probability that win gets set to true in the above game. This is the
probability that the adversary successfully impersonates the user.
Our goal is to assess how large this value can be as a function of
the number v of verification queries made by B, the number a of
authenticator oracle queries made by B, and the running time t of B.
This will tell us how to set the throttle, which effectively upper
bounds v.
A.4. Security of the Ideal Authentication Algorithm
This section summarizes the security analysis of HOTP-IDEAL, starting
with the impact of the conversion modulo 10^Digit and then focusing
on the different possible attacks.
A.4.1. From Bits to Digits
The dynamic offset truncation of a random n-bit string yields a
random 31-bit string. What happens to the distribution when it is
taken modulo m = 10^Digit, as done in HOTP?
The following lemma estimates the biases in the outputs in this case.
Lemma 1
-------
Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in
Z_{m} let:
P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}]
Then for any z in Z_{m}
P_{N,m}(z) = (q + 1) / N if 0 <= z < r
q / N if r <= z < m
Proof of Lemma 1
----------------
Let the random variable X be uniformly distributed over Z_{N}. Then:
P_{N,m}(z) = Pr [X mod m = z]
= Pr [X < mq] * Pr [X mod m = z| X < mq]
+ Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N]
= mq/N * 1/m +
(N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq
0 if N - mq <= z <= m
= q/N +
r/N * 1 / r if 0 <= z < N - mq
0 if r <= z <= m
Simplifying yields the claimed equation.
Let N = 2^31, d = 6, and m = 10^d. If x is chosen at random from
Z_{N} (meaning, is a random 31-bit string), then reducing it to a 6-
digit number by taking x mod m does not yield a random 6-digit
number.
Rather, x mod m is distributed as shown in the following table:
Values Probability that each appears as output
----------------------------------------------------------------
0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6
483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6
If X is uniformly distributed over Z_{2^31} (meaning, is a random
31-bit string), then the above shows the probabilities for different
outputs of X mod 10^6. The first set of values appears with
probability slightly greater than 10^-6, the rest with probability
slightly less, meaning that the distribution is slightly non-uniform.
However, as the table above indicates, the bias is small, and as we
will see later, negligible: the probabilities are very close to
10^-6.
A.4.2. Brute Force Attacks
If the authenticator consisted of d random digits, then a brute force
attack using v verification attempts would succeed with probability
sv/10^Digit.
However, an adversary can exploit the bias in the outputs of
HOTP-IDEAL, predicted by Lemma 1, to mount a slightly better attack.
Namely, it makes authentication attempts with authenticators that are
the most likely values, meaning the ones in the range 0,...,r - 1,
where (q,r) = IntDiv(2^31,10^Digit).
The following specifies an adversary in our model of security that
mounts the attack. It estimates the success probability as a
function of the number of verification queries.
For simplicity, we assume that the number of verification queries is
at most r. With N = 2^31 and m = 10^6, we have r = 483,648, and the
throttle value is certainly less than this, so this assumption is not
much of a restriction.
Proposition 1
-------------
Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume
s <= m. The brute-force-attack adversary B-bf attacks HOTP using v
<= r verification oracle queries. This adversary makes no
authenticator oracle queries, and succeeds with probability
Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s
which is roughly equal to
sv * (q+1)/2^31
With m = 10^6 we get q = 2,147. In that case, the brute force attack
using v verification attempts succeeds with probability
Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6
As this equation shows, the resynchronization parameter s has a
significant impact in that the adversary’s success probability is
proportional to s. This means that s cannot be made too large
without compromising security.
A.4.3. Brute force attacks are the best possible attacks.
A central question is whether there are attacks any better than the
brute force one. In particular, the brute force attack did not
attempt to collect authenticators sent by the user and try to
cryptanalyze them in an attempt to learn how to better construct
authenticators. Would doing this help? Is there some way to "learn"
how to build authenticators that result in a higher success rate than
given by the brute-force attack?
The following says the answer to these questions is no. No matter
what strategy the adversary uses, and even if it sees, and tries to
exploit, the authenticators from authentication attempts of the user,
its success probability will not be above that of the brute force
attack -- this is true as long as the number of authentications it
observes is not incredibly large. This is valuable information
regarding the security of the scheme.
Proposition 2 ------------- Suppose m = 10^Digit < 2^31, and let
(q,r) = IntDiv(2^31,m). Let B be any adversary attacking HOTP-IDEAL
using v verification oracle queries and a <= 2^c - s authenticator
oracle queries. Then
Adv(B) < = sv * (q+1)/ 2^31
Note: This result is conditional on the adversary not seeing more
than 2^c - s authentications performed by the user, which is hardly
restrictive as long as c is large enough.
With m = 10^6, we get q = 2,147. In that case, Proposition 2 says
that any adversary B attacking HOTP-IDEAL and making v verification
attempts succeeds with probability at most
Equation 1
----------
sv * 2148/2^31 roughly = sv * 1.00024045/10^6
Meaning, B’s success rate is not more than that achieved by the brute
force attack.
A.5. Security Analysis of HOTP
We have analyzed, in the previous sections, the security of the
idealized counterparts HOTP-IDEAL of the actual authentication
algorithm HOTP. We now show that, under appropriate and well-
believed assumption on H, the security of the actual algorithms is
essentially the same as that of its idealized counterpart.
The assumption in question is that H is a secure pseudorandom
function, or PRF, meaning that its input-output values are
indistinguishable from those of a random function in practice.
Consider an adversary A that is given an oracle for a function f:
{0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A)
as the prf-advantage of A, which represents how well the adversary
does at distinguishing the case where its oracle is H(K,.) from the
case where its oracle is a random function of {0,1}^c to {0,1}^n.
One possible attack is based on exhaustive search for the key K. If
A runs for t steps and T denotes the time to perform one computation
of H, its prf-advantage from this attack turns out to be (t/T)2^-k.