Request for Comments: 4226 VeriSign
Category: Informational M. Bellare
UCSD
F. Hoornaert
Vasco
D. Naccache
Gemplus
O. Ranen
Aladdin
December 2005
HOTP: An HMAC-Based One-Time Password Algorithm
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
This document describes an algorithm to generate one-time password
values, based on Hashed Message Authentication Code (HMAC). A
security analysis of the algorithm is presented, and important
parameters related to the secure deployment of the algorithm are
discussed. The proposed algorithm can be used across a wide range of
network applications ranging from remote Virtual Private Network
(VPN) access, Wi-Fi network logon to transaction-oriented Web
applications.
This work is a joint effort by the OATH (Open AuTHentication)
membership to specify an algorithm that can be freely distributed to
the technical community. The authors believe that a common and
shared algorithm will facilitate adoption of two-factor
authentication on the Internet by enabling interoperability across
commercial and open-source implementations.
Table of Contents
1. Overview ........................................................3
2. Introduction ....................................................3
3. Requirements Terminology ........................................4
4. Algorithm Requirements ..........................................4
5. HOTP Algorithm ..................................................5
5.1. Notation and Symbols .......................................5
5.2. Description ................................................6
5.3. Generating an HOTP Value ...................................6
5.4. Example of HOTP Computation for Digit = 6 ..................7
6. Security Considerations .........................................8
7. Security Requirements ...........................................9
7.1. Authentication Protocol Requirements .......................9
7.2. Validation of HOTP Values .................................10
7.3. Throttling at the Server ..................................10
7.4. Resynchronization of the Counter ..........................11
7.5. Management of Shared Secrets ..............................11
8. Composite Shared Secrets .......................................14
9. Bi-Directional Authentication ..................................14
10. Conclusion ....................................................15
11. Acknowledgements ..............................................15
12. Contributors ..................................................15
13. References ....................................................15
13.1. Normative References .....................................15
13.2. Informative References ...................................16
Appendix A - HOTP Algorithm Security: Detailed Analysis ...........17
A.1. Definitions and Notations .................................17
A.2. The Idealized Algorithm: HOTP-IDEAL .......................17
A.3. Model of Security .........................................18
A.4. Security of the Ideal Authentication Algorithm ............19
A.4.1. From Bits to Digits ................................19
A.4.2. Brute Force Attacks ................................21
A.4.3. Brute force attacks are the best possible attacks ..22
A.5. Security Analysis of HOTP .................................23
Appendix B - SHA-1 Attacks ........................................25
B.1. SHA-1 Status ..............................................25
B.2. HMAC-SHA-1 Status .........................................26
B.3. HOTP Status ...............................................26
Appendix C - HOTP Algorithm: Reference Implementation .............27
Appendix D - HOTP Algorithm: Test Values ..........................32
Appendix E - Extensions ...........................................33
E.1. Number of Digits ..........................................33
E.2. Alphanumeric Values .......................................33
E.3. Sequence of HOTP values ...................................34
E.4. A Counter-Based Resynchronization Method ..................34
E.5. Data Field ................................................35
1. Overview
The document introduces first the context around an algorithm that
generates one-time password values based on HMAC [BCK1] and, thus, is
named the HMAC-Based One-Time Password (HOTP) algorithm. In Section
4, the algorithm requirements are listed and in Section 5, the HOTP
algorithm is described. Sections 6 and 7 focus on the algorithm
security. Section 8 proposes some extensions and improvements, and
Section 10 concludes this document. In Appendix A, the interested
reader will find a detailed, full-fledged analysis of the algorithm
security: an idealized version of the algorithm is evaluated, and
then the HOTP algorithm security is analyzed.
2. Introduction
Today, deployment of two-factor authentication remains extremely
limited in scope and scale. Despite increasingly higher levels of
threats and attacks, most Internet applications still rely on weak
authentication schemes for policing user access. The lack of
interoperability among hardware and software technology vendors has
been a limiting factor in the adoption of two-factor authentication
technology. In particular, the absence of open specifications has
led to solutions where hardware and software components are tightly
coupled through proprietary technology, resulting in high-cost
solutions, poor adoption, and limited innovation.
In the last two years, the rapid rise of network threats has exposed
the inadequacies of static passwords as the primary mean of
authentication on the Internet. At the same time, the current
approach that requires an end user to carry an expensive, single-
function device that is only used to authenticate to the network is
clearly not the right answer. For two-factor authentication to
propagate on the Internet, it will have to be embedded in more
flexible devices that can work across a wide range of applications.
The ability to embed this base technology while ensuring broad
interoperability requires that it be made freely available to the
broad technical community of hardware and software developers. Only
an open-system approach will ensure that basic two-factor
authentication primitives can be built into the next generation of
consumer devices such as USB mass storage devices, IP phones, and
personal digital assistants.
One-Time Password is certainly one of the simplest and most popular
forms of two-factor authentication for securing network access. For
example, in large enterprises, Virtual Private Network access often
requires the use of One-Time Password tokens for remote user
authentication. One-Time Passwords are often preferred to stronger
forms of authentication such as Public-Key Infrastructure (PKI) or
biometrics because an air-gap device does not require the
installation of any client desktop software on the user machine,
therefore allowing them to roam across multiple machines including
home computers, kiosks, and personal digital assistants.
This document proposes a simple One-Time Password algorithm that can
be implemented by any hardware manufacturer or software developer to
create interoperable authentication devices and software agents. The
algorithm is event-based so that it can be embedded in high-volume
devices such as Java smart cards, USB dongles, and GSM SIM cards.
The presented algorithm is made freely available to the developer
community under the terms and conditions of the IETF Intellectual
Property Rights [RFC3979].
The authors of this document are members of the Open AuTHentication
initiative [OATH]. The initiative was created in 2004 to facilitate
collaboration among strong authentication technology providers.
3. Requirements Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
4. Algorithm Requirements
This section presents the main requirements that drove this algorithm
design. A lot of emphasis was placed on end-consumer usability as
well as the ability for the algorithm to be implemented by low-cost
hardware that may provide minimal user interface capabilities. In
particular, the ability to embed the algorithm into high-volume SIM
and Java cards was a fundamental prerequisite.
R1 - The algorithm MUST be sequence- or counter-based: one of the
goals is to have the HOTP algorithm embedded in high-volume devices
such as Java smart cards, USB dongles, and GSM SIM cards.
R2 - The algorithm SHOULD be economical to implement in hardware by
minimizing requirements on battery, number of buttons, computational
horsepower, and size of LCD display.
R3 - The algorithm MUST work with tokens that do not support any
numeric input, but MAY also be used with more sophisticated devices
such as secure PIN-pads.
R4 - The value displayed on the token MUST be easily read and entered
by the user: This requires the HOTP value to be of reasonable length.
The HOTP value must be at least a 6-digit value. It is also
desirable that the HOTP value be ’numeric only’ so that it can be
easily entered on restricted devices such as phones.
R5 - There MUST be user-friendly mechanisms available to
resynchronize the counter. Section 7.4 and Appendix E.4 details the
resynchronization mechanism proposed in this document
R6 - The algorithm MUST use a strong shared secret. The length of
the shared secret MUST be at least 128 bits. This document
RECOMMENDs a shared secret length of 160 bits.
5. HOTP Algorithm
In this section, we introduce the notation and describe the HOTP
algorithm basic blocks -- the base function to compute an HMAC-SHA-1
value and the truncation method to extract an HOTP value.
5.1. Notation and Symbols
A string always means a binary string, meaning a sequence of zeros
and ones.
If s is a string, then |s| denotes its length.
If n is a number, then |n| denotes its absolute value.
If s is a string, then s[i] denotes its i-th bit. We start numbering
the bits at 0, so s = s[0]s[1]...s[n-1] where n = |s| is the length
of s.
Let StToNum (String to Number) denote the function that as input a
string s returns the number whose binary representation is s. (For
example, StToNum(110) = 6.)
Here is a list of symbols used in this document.
Symbol Represents
-------------------------------------------------------------------
C 8-byte counter value, the moving factor. This counter
MUST be synchronized between the HOTP generator (client)
and the HOTP validator (server).
K shared secret between client and server; each HOTP
generator has a different and unique secret K.
T throttling parameter: the server will refuse connections
from a user after T unsuccessful authentication attempts.
s resynchronization parameter: the server will attempt to
verify a received authenticator across s consecutive
counter values.
Digit number of digits in an HOTP value; system parameter.
5.2. Description
The HOTP algorithm is based on an increasing counter value and a
static symmetric key known only to the token and the validation
service. In order to create the HOTP value, we will use the HMAC-
SHA-1 algorithm, as defined in RFC 2104 [BCK2].
As the output of the HMAC-SHA-1 calculation is 160 bits, we must
truncate this value to something that can be easily entered by a
user.
HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
Where:
- Truncate represents the function that converts an HMAC-SHA-1
value into an HOTP value as defined in Section 5.3.
The Key (K), the Counter (C), and Data values are hashed high-order
byte first.
The HOTP values generated by the HOTP generator are treated as big
endian.
5.3. Generating an HOTP Value
We can describe the operations in 3 distinct steps:
Step 1: Generate an HMAC-SHA-1 value Let HS = HMAC-SHA-1(K,C) // HS
is a 20-byte string
Step 2: Generate a 4-byte string (Dynamic Truncation)
Let Sbits = DT(HS) // DT, defined below,
// returns a 31-bit string
Step 3: Compute an HOTP value
Let Snum = StToNum(Sbits) // Convert S to a number in
0...2^{31}-1
Return D = Snum mod 10^Digit // D is a number in the range
0...10^{Digit}-1
The Truncate function performs Step 2 and Step 3, i.e., the dynamic
truncation and then the reduction modulo 10^Digit. The purpose of
the dynamic offset truncation technique is to extract a 4-byte
dynamic binary code from a 160-bit (20-byte) HMAC-SHA-1 result.
DT(String) // String = String[0]...String[19]
Let OffsetBits be the low-order 4 bits of String[19]
Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
Let P = String[OffSet]...String[OffSet+3]
Return the Last 31 bits of P
The reason for masking the most significant bit of P is to avoid
confusion about signed vs. unsigned modulo computations. Different
processors perform these operations differently, and masking out the
signed bit removes all ambiguity.
Implementations MUST extract a 6-digit code at a minimum and possibly
7 and 8-digit code. Depending on security requirements, Digit = 7 or
more SHOULD be considered in order to extract a longer HOTP value.
The following paragraph is an example of using this technique for
Digit = 6, i.e., that a 6-digit HOTP value is calculated from the
HMAC value.
5.4. Example of HOTP Computation for Digit = 6
The following code example describes the extraction of a dynamic
binary code given that hmac_result is a byte array with the HMAC-
SHA-1 result:
int offset = hmac_result[19] & 0xf ;
int bin_code = (hmac_result[offset] & 0x7f) << 24
| (hmac_result[offset+1] & 0xff) << 16
| (hmac_result[offset+2] & 0xff) << 8
| (hmac_result[offset+3] & 0xff) ;
SHA-1 HMAC Bytes (Example)
-------------------------------------------------------------
| Byte Number |
-------------------------------------------------------------
|00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
-------------------------------------------------------------
| Byte Value |
-------------------------------------------------------------
|1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a|
-------------------------------***********----------------++|
* The last byte (byte 19) has the hex value 0x5a.
* The value of the lower 4 bits is 0xa (the offset value).
* The offset value is byte 10 (0xa).
* The value of the 4 bytes starting at byte 10 is 0x50ef7f19,
which is the dynamic binary code DBC1.
* The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19 .
* HOTP = DBC2 modulo 10^6 = 872921.
We treat the dynamic binary code as a 31-bit, unsigned, big-endian
integer; the first byte is masked with a 0x7f.
We then take this number modulo 1,000,000 (10^6) to generate the 6-
digit HOTP value 872921 decimal.
6. Security Considerations
The conclusion of the security analysis detailed in the Appendix is
that, for all practical purposes, the outputs of the Dynamic
Truncation (DT) on distinct counter inputs are uniformly and
independently distributed 31-bit strings.
The security analysis then details the impact of the conversion from
a string to an integer and the final reduction modulo 10^Digit, where
Digit is the number of digits in an HOTP value.
The analysis demonstrates that these final steps introduce a
negligible bias, which does not impact the security of the HOTP
algorithm, in the sense that the best possible attack against the
HOTP function is the brute force attack.
Assuming an adversary is able to observe numerous protocol exchanges
and collect sequences of successful authentication values. This
adversary, trying to build a function F to generate HOTP values based
on his observations, will not have a significant advantage over a
random guess.
The logical conclusion is simply that the best strategy will once
again be to perform a brute force attack to enumerate and try all the
possible values.
Considering the security analysis in the Appendix of this document,
without loss of generality, we can approximate closely the security
of the HOTP algorithm by the following formula:
Sec = sv/10^Digit
Where:
- Sec is the probability of success of the adversary;
- s is the look-ahead synchronization window size;
- v is the number of verification attempts;
- Digit is the number of digits in HOTP values.
Obviously, we can play with s, T (the Throttling parameter that would
limit the number of attempts by an attacker), and Digit until
achieving a certain level of security, still preserving the system
usability.
7. Security Requirements
Any One-Time Password algorithm is only as secure as the application
and the authentication protocols that implement it. Therefore, this
section discusses the critical security requirements that our choice
of algorithm imposes on the authentication protocol and validation
software.
The parameters T and s discussed in this section have a significant
impact on the security -- further details in Section 6 elaborate on
the relations between these parameters and their impact on the system
security.
It is also important to remark that the HOTP algorithm is not a
substitute for encryption and does not provide for the privacy of
data transmission. Other mechanisms should be used to defeat attacks
aimed at breaking confidentiality and privacy of transactions.
7.1. Authentication Protocol Requirements
We introduce in this section some requirements for a protocol P
implementing HOTP as the authentication method between a prover and a
verifier.
RP1 - P MUST support two-factor authentication, i.e., the
communication and verification of something you know (secret code
such as a Password, Pass phrase, PIN code, etc.) and something you
have (token). The secret code is known only to the user and usually
entered with the One-Time Password value for authentication purpose
(two-factor authentication).
RP2 - P SHOULD NOT be vulnerable to brute force attacks. This
implies that a throttling/lockout scheme is RECOMMENDED on the
validation server side.
RP3 - P SHOULD be implemented over a secure channel in order to
protect users’ privacy and avoid replay attacks.
7.2. Validation of HOTP Values
The HOTP client (hardware or software token) increments its counter
and then calculates the next HOTP value HOTP client. If the value
received by the authentication server matches the value calculated by
the client, then the HOTP value is validated. In this case, the
server increments the counter value by one.
If the value received by the server does not match the value
calculated by the client, the server initiate the resynch protocol
(look-ahead window) before it requests another pass.
If the resynch fails, the server asks then for another
authentication pass of the protocol to take place, until the
maximum number of authorized attempts is reached.
If and when the maximum number of authorized attempts is reached, the
server SHOULD lock out the account and initiate a procedure to inform
the user.
7.3. Throttling at the Server
Truncating the HMAC-SHA-1 value to a shorter value makes a brute
force attack possible. Therefore, the authentication server needs to
detect and stop brute force attacks.
We RECOMMEND setting a throttling parameter T, which defines the
maximum number of possible attempts for One-Time Password validation.
The validation server manages individual counters per HOTP device in
order to take note of any failed attempt. We RECOMMEND T not to be
too large, particularly if the resynchronization method used on the
server is window-based, and the window size is large. T SHOULD be
set as low as possible, while still ensuring that usability is not
significantly impacted.
Another option would be to implement a delay scheme to avoid a brute
force attack. After each failed attempt A, the authentication server
would wait for an increased T*A number of seconds, e.g., say T = 5,
then after 1 attempt, the server waits for 5 seconds, at the second
failed attempt, it waits for 5*2 = 10 seconds, etc.
The delay or lockout schemes MUST be across login sessions to prevent
attacks based on multiple parallel guessing techniques.
7.4. Resynchronization of the Counter
Although the server’s counter value is only incremented after a
successful HOTP authentication, the counter on the token is
incremented every time a new HOTP is requested by the user. Because
of this, the counter values on the server and on the token might be
out of synchronization.
We RECOMMEND setting a look-ahead parameter s on the server, which
defines the size of the look-ahead window. In a nutshell, the server
can recalculate the next s HOTP-server values, and check them against
the received HOTP client.
Synchronization of counters in this scenario simply requires the
server to calculate the next HOTP values and determine if there is a
match. Optionally, the system MAY require the user to send a
sequence of (say, 2, 3) HOTP values for resynchronization purpose,
since forging a sequence of consecutive HOTP values is even more
difficult than guessing a single HOTP value.
The upper bound set by the parameter s ensures the server does not go
on checking HOTP values forever (causing a denial-of-service attack)
and also restricts the space of possible solutions for an attacker
trying to manufacture HOTP values. s SHOULD be set as low as