< draft-mraihi-oath-hmac-otp-00.txt   draft-mraihi-oath-hmac-otp-01.txt >
Internet Draft D. MÆRaihi Internet Draft D. M'Raihi
Category: Informational Verisign Category: Informational Verisign
Document: draft-mraihi-oath-hmac-otp-00.txt M. Bellare Document: draft-mraihi-oath-hmac-otp-01.txt M. Bellare
Expires: April 2005 UCSD Expires: April 2005 UCSD
F. Hoornaert F. Hoornaert
Vasco Vasco
D. Naccache D. Naccache
Gemplus Gemplus
O. Ranen O. Ranen
Aladdin Aladdin
October 2004 October 2004
HOTP: An HMAC-based One Time Password Algorithm HOTP: An HMAC-based One Time Password Algorithm
Status of this Memo Status of this Memo
By submitting this Internet-Draft, I certify that any applicable By submitting this Internet-Draft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed, patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I become aware will be or will be disclosed, and any of which I become aware will be
disclosed, in accordance with RFC 3668. disclosed, in accordance with RFC 3668.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as
Drafts. Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than a "work in as reference material or to cite them other than a "work in
progress." progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
skipping to change at page 2, line 28 skipping to change at page 2, line 28
5.2 Description..............................................6 5.2 Description..............................................6
5.3 Generating an HOTP value.................................6 5.3 Generating an HOTP value.................................6
5.4 Example of HOTP computation for Digit = 6................7 5.4 Example of HOTP computation for Digit = 6................7
6. Security and Deployment Considerations.....................8 6. Security and Deployment Considerations.....................8
6.1 Authentication Protocol Requirements.....................8 6.1 Authentication Protocol Requirements.....................8
6.2 Validation of HOTP values................................8 6.2 Validation of HOTP values................................8
6.3 Throttling at the server.................................9 6.3 Throttling at the server.................................9
6.4 Resynchronization of the counter.........................9 6.4 Resynchronization of the counter.........................9
7. HOTP Algorithm Security: Overview.........................10 7. HOTP Algorithm Security: Overview.........................10
8. Protocol Extensions and Improvements......................10 8. Protocol Extensions and Improvements......................10
8.1 Number of Digits........................................10 8.1 Number of Digits........................................11
8.2 Alpha-numeric Values....................................11 8.2 Alpha-numeric Values....................................11
8.3 Sequence of HOTP values.................................11 8.3 Sequence of HOTP values.................................11
8.4 A Counter-based Re-Synchronization Method...............12 8.4 A Counter-based Re-Synchronization Method...............12
9. Conclusion................................................12 9. Conclusion................................................12
10. Acknowledgements..........................................13 10. Acknowledgements..........................................13
11. Contributors..............................................13 11. Contributors..............................................13
12. References................................................13 12. References................................................13
12.1 Normative...............................................13 12.1 Normative...............................................13
12.2 Informative.............................................13 12.2 Informative.............................................13
13. AuthorsÆ Addresses........................................13 13. Authors' Addresses........................................13
Appendix - HOTP Algorithm Security: Detailed Analysis..........14 Appendix - HOTP Algorithm Security: Detailed Analysis..........14
A.1 Definitions and Notations.................................14 A.1 Definitions and Notations.................................15
A.2 The idealized algorithm: HOTP-IDEAL.......................15 A.2 The idealized algorithm: HOTP-IDEAL.......................15
A.3 Model of Security.........................................15 A.3 Model of Security.........................................15
A.4 Security of the ideal authentication algorithm............17 A.4 Security of the ideal authentication algorithm............17
A.4.1 From bits to digits.....................................17 A.4.1 From bits to digits.....................................17
A.4.2 Brute force attacks.....................................18 A.4.2 Brute force attacks.....................................18
A.4.3 Brute force attacks are the best possible attacks.......19 A.4.3 Brute force attacks are the best possible attacks.......19
A.5 Security Analysis of HOTP.................................20 A.5 Security Analysis of HOTP.................................20
1. Overview 1. Overview
skipping to change at page 3, line 28 skipping to change at page 3, line 28
interoperability among hardware and software technology vendors has interoperability among hardware and software technology vendors has
been a limiting factor in the adoption of two-factor authentication been a limiting factor in the adoption of two-factor authentication
technology. In particular, the absence of open specifications has technology. In particular, the absence of open specifications has
led to solutions where hardware and software components are tightly led to solutions where hardware and software components are tightly
coupled through proprietary technology, resulting in high cost coupled through proprietary technology, resulting in high cost
solutions, poor adoption and limited innovation. solutions, poor adoption and limited innovation.
In the last two years, the rapid rise of network threats has In the last two years, the rapid rise of network threats has
exposed the inadequacies of static passwords as the primary mean of exposed the inadequacies of static passwords as the primary mean of
authentication on the Internet. At the same time, the current authentication on the Internet. At the same time, the current
approach that requires an end-user to carry an expensive, single- approach that requires an end-user to carry an expensive,
function device that is only used to authenticate to the network is single-function device that is only used to authenticate to the
clearly not the right answer. For two factor authentication to network is clearly not the right answer. For two factor
propagate on the Internet, it will have to be embedded in more authentication to propagate on the Internet, it will have to be
flexible devices that can work across a wide range of applications. embedded in more flexible devices that can work across a wide range
of applications.
The ability to embed this base technology while ensuring broad The ability to embed this base technology while ensuring broad
interoperability require that it be made freely available to the interoperability require that it be made freely available to the
broad technical community of hardware and software developers. Only broad technical community of hardware and software developers. Only
an open system approach will ensure that basic two-factor an open system approach will ensure that basic two-factor
authentication primitives can be built into the next-generation of authentication primitives can be built into the next-generation of
consumer devices such USB mass storage devices, IP phones, and consumer devices such USB mass storage devices, IP phones, and
personal digital assistants). personal digital assistants).
One Time Password is certainly one of the simplest and most popular One Time Password is certainly one of the simplest and most popular
forms of two-factor authentication for securing network access. For forms of two-factor authentication for securing network access. For
example, in large enterprises, Virtual Private Network access often example, in large enterprises, Virtual Private Network access often
requires the use of One Time Password tokens for remote user requires the use of One Time Password tokens for remote user
authentication. One Time Passwords are often preferred to stronger authentication. One Time Passwords are often preferred to stronger
forms of authentication such as PKI or biometrics because an air- forms of authentication such as PKI or biometrics because an
gap device does not require the installation of any client desktop air-gap device does not require the installation of any client
software on the user machine, therefore allowing them to roam desktop software on the user machine, therefore allowing them to
across multiple machines including home computers, kiosks and roam across multiple machines including home computers, kiosks and
personal digital assistants. personal digital assistants.
This draft proposes a simple One Time Password algorithm that can
be implemented by any hardware manufacturer or software developer
HOTP: An HMAC-based One Time Password Algorithm October 2004 HOTP: An HMAC-based One Time Password Algorithm October 2004
This draft 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. to create interoperable authentication devices and software agents.
The algorithm is event-based so that it can be embedded in high 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 volume devices such as Java smart cards, USB dongles and GSM SIM
cards. The presented algorithm is made freely available to the cards. The presented algorithm is made freely available to the
developer community under the terms and conditions of the IETF developer community under the terms and conditions of the IETF
Intellectual Property Rights [RFC3668]. Intellectual Property Rights [RFC3668].
The authors of this document are members of the Open AuTHentication The authors of this document are members of the Open AuTHentication
initiative [OATH]. The initiative was created in 2004 to facilitate initiative [OATH]. The initiative was created in 2004 to facilitate
collaboration among strong authentication technology providers. collaboration among strong authentication technology providers.
skipping to change at page 5, line 7 skipping to change at page 5, line 7
reasonable length. The HOTP value must be at least a 6-digit value. 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 is also desirable that the HOTP value be 'numeric only' so that
it can be easily entered on restricted devices such as phones. it can be easily entered on restricted devices such as phones.
R4 - There MUST be user-friendly mechanisms available to R4 - There MUST be user-friendly mechanisms available to
resynchronize the counter. The sections 6.4 and 8.4 detail the resynchronize the counter. The sections 6.4 and 8.4 detail the
resynchronization mechanism proposed in this draft. resynchronization mechanism proposed in this draft.
HOTP: An HMAC-based One Time Password Algorithm October 2004 HOTP: An HMAC-based One Time Password Algorithm October 2004
R5- The algorithm MUST use a strong shared secret. The length of R5 - The algorithm MUST use a strong shared secret. The length of
the shared secret MUST be at least 128 bits. This draft RECOMMENDs the shared secret MUST be at least 128 bits. This draft RECOMMENDs
a shared secret length of 160 bits. a shared secret length of 160 bits.
5. HOTP Algorithm 5. HOTP Algorithm
In this section, we introduce the notation and describe the HOTP In this section, we introduce the notation and describe the HOTP
algorithm basic blocks û the base function to compute an HMAC-SHA-1 algorithm basic blocks - the base function to compute an HMAC-SHA-1
value and the truncation method to extract an HOTP value. value and the truncation method to extract an HOTP value.
5.1 Notation and Symbols 5.1 Notation and Symbols
A string always means a binary string, meaning a sequence of zeros A string always means a binary string, meaning a sequence of zeros
and ones. and ones.
If s is a string then |s| denotes its length. If s is a string then |s| denotes its length.
If n is a number then |n| denotes its absolute value. If n is a number then |n| denotes its absolute value.
skipping to change at page 5, line 38 skipping to change at page 5, line 38
of s. of s.
Let StToNum (String to Number) denote the function which as input a Let StToNum (String to Number) denote the function which as input a
string s returns the number whose binary representation is s. string s returns the number whose binary representation is s.
(For example StToNum(110) = 6). (For example StToNum(110) = 6).
Here is a list of symbols used in this document. Here is a list of symbols used in this document.
Symbol Represents Symbol Represents
------------------------------------------------------------------- -------------------------------------------------------------------
C 8-byte (Little Endian) counter value, which is the moving C 8-byte (Little Endian) counter value, which is
factor. This counter MUST be synchronized between the HOTP The moving factor. This counter MUST be synchronized
generator (client) and the HOTP validator (server); between the HOTP generator (client) and the
HOTP validator (server);
K shared secret between the client and the server; each HOTP K shared secret between client and server; each HOTP
generator has a different and unique secret K; generator has a different and unique secret K;
T throttling parameter: the server will refuse connections T throttling parameter: the server will refuse connections
from a user after T unsuccessful authentication attempts; from a user after T unsuccessful authentication attempts;
s resynchronization parameter: the server will attempt to s resynchronization parameter: the server will attempt to
verify a received authenticator across s consecutive verify a received authenticator across s consecutive
counter values; counter values;
Digit number of digits in an HOTP value; system parameter. Digit number of digits in an HOTP value; system parameter.
HOTP: An HMAC-based One Time Password Algorithm October 2004 HOTP: An HMAC-based One Time Password Algorithm October 2004
5.2 Description 5.2 Description
The HOTP algorithm is based on an increasing counter value and a The HOTP algorithm is based on an increasing counter value and a
static symmetric key known only to the token and the validation static symmetric key known only to the token and the validation
service. In order to create the HOTP value, we will use the HMAC- service. In order to create the HOTP value, we will use the
SHA-1 algorithm, as defined in RFC 2104 [BCK2]. HMAC-SHA-1 algorithm, as defined in RFC 2104 [BCK2].
As the output of the HMAC-SHA1 calculation is 160 bits, we must As the output of the HMAC-SHA1 calculation is 160 bits, we must
truncate this value to something that can be easily entered by a truncate this value to something that can be easily entered by a
user. user.
HOTP(K,C) = Truncate(HMAC-SHA-1(K,C)) HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
Where: Where:
- Truncate represents the function that converts an HMAC-SHA-1 - Truncate represents the function that converts an HMAC-SHA-1
value into an HOTP value as defined in Section 5.3. value into an HOTP value as defined in Section 5.3.
skipping to change at page 7, line 23 skipping to change at page 7, line 23
Digit = 7 or more SHOULD be considered in order to extract a longer Digit = 7 or more SHOULD be considered in order to extract a longer
HOTP value. HOTP value.
The following paragraph is an example of using this technique for 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 Digit = 6, i.e. that a 6-digit HOTP value is calculated from the
HMAC value. HMAC value.
5.4 Example of HOTP computation for Digit = 6 5.4 Example of HOTP computation for Digit = 6
The following code example describes the extraction of a dynamic The following code example describes the extraction of a dynamic
binary code given that hmac_result is a byte array with the HMAC- binary code given that hmac_result is a byte array with the
SHA1 result: HMAC-SHA1 result:
int offset = hmac_result[19] & 0xf ; int offset = hmac_result[19] & 0xf ;
int bin_code = (hmac_result[offset] & 0x7f) << 24 int bin_code = (hmac_result[offset] & 0x7f) << 24
| (hmac_result[offset+1] & 0xff) << 16 | (hmac_result[offset+1] & 0xff) << 16
| (hmac_result[offset+2] & 0xff) << 8 | (hmac_result[offset+2] & 0xff) << 8
| (hmac_result[offset+3] & 0xff) ; | (hmac_result[offset+3] & 0xff) ;
SHA-1 HMAC Bytes (Example) SHA-1 HMAC Bytes (Example)
------------------------------------------------------------- -------------------------------------------------------------
skipping to change at page 8, line 7 skipping to change at page 8, line 7
* The value of the 4 bytes starting at byte 10 is 0x50ef7f19, * The value of the 4 bytes starting at byte 10 is 0x50ef7f19,
which is the dynamic binary code DBC1 which is the dynamic binary code DBC1
* The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19 * The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19
* HOTP = DBC2 modulo 10^6 = 872921. * HOTP = DBC2 modulo 10^6 = 872921.
We treat the dynamic binary code as a 31-bit, unsigned, big-endian We treat the dynamic binary code as a 31-bit, unsigned, big-endian
integer; the first byte is masked with a 0x7f. integer; the first byte is masked with a 0x7f.
HOTP: An HMAC-based One Time Password Algorithm October 2004 HOTP: An HMAC-based One Time Password Algorithm October 2004
We then take this number modulo 1,000,000 (10^6) to generate the 6- We then take this number modulo 1,000,000 (10^6) to generate the
digit HOTP value 872921 decimal. 6-digit HOTP value 872921 decimal.
6. Security and Deployment Considerations 6. Security and Deployment Considerations
Any One-Time Password algorithm is only as secure as the Any One-Time Password algorithm is only as secure as the
application and the authentication protocols that implement it. application and the authentication protocols that implement it.
Therefore, this section discusses the critical security Therefore, this section discusses the critical security
requirements that our choice of algorithm imposes on the requirements that our choice of algorithm imposes on the
authentication protocol and validation software. The parameters T authentication protocol and validation software. The parameters T
and s discussed in this section have a significant impact on the and s discussed in this section have a significant impact on the
security û further details in Section 7 elaborate on the relations security - further details in Section 7 elaborate on the relations
between these parameters and their impact on the system security. between these parameters and their impact on the system security.
6.1 Authentication Protocol Requirements 6.1 Authentication Protocol Requirements
We introduce in this section some requirements for a protocol P We introduce in this section some requirements for a protocol P
implementing HOTP as the authentication method between a prover and implementing HOTP as the authentication method between a prover and
a verifier. a verifier.
RP1 - P MUST be two-factor, i.e. something you know (secret code RP1 - P MUST be two-factor, i.e. something you know (secret code
such as a Password, Pass phrase, PIN code, etc.) and something you 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 have (token). The secret code is known only to the user and usually
entered with the one-time password value for authentication purpose entered with the one-time password value for authentication purpose
(two-factor authentication). (two-factor authentication).
RP3 - P MUST NOT be vulnerable to brute force attacks. This implies RP3 - P MUST NOT be vulnerable to brute force attacks. This implies
that a throttling/lockout scheme is REQUIRED on the validation that a throttling/lockout scheme is REQUIRED on the validation
server side. server side.
RP4 û P SHOULD be implemented with respect to the state of the art RP4 - P SHOULD be implemented with respect to the state of the art
in terms of security, in order to avoid the usual attacks and risks in terms of security, in order to avoid the usual attacks and risks
associated with the transmission of sensitive data over a public associated with the transmission of sensitive data over a public
network (privacy, replay attacks, etc.) network (privacy, replay attacks, etc.)
6.2 Validation of HOTP values 6.2 Validation of HOTP values
The HOTP client (hardware or software token) increments its counter The HOTP client (hardware or software token) increments its counter
and then calculates the next HOTP value HOTP-client. If the value and then calculates the next HOTP value HOTP-client. If the value
received by the authentication server matches the value calculated received by the authentication server matches the value calculated
by the client, then the HOTP value is validated. In this case, the by the client, then the HOTP value is validated. In this case, the
skipping to change at page 9, line 32 skipping to change at page 9, line 32
maximum number of possible attempts for One-Time-Password maximum number of possible attempts for One-Time-Password
validation. The validation server manages individual counters per validation. The validation server manages individual counters per
HOTP device in order to take note of any failed attempt. We HOTP device in order to take note of any failed attempt. We
RECOMMEND T not to be too large, particularly if the RECOMMEND T not to be too large, particularly if the
resynchronization method used on the server is window-based, and resynchronization method used on the server is window-based, and
the window size is large. T SHOULD be set as low as possible, while the window size is large. T SHOULD be set as low as possible, while
still ensuring usability is not significantly impacted. still ensuring usability is not significantly impacted.
6.4 Resynchronization of the counter 6.4 Resynchronization of the counter
Although the serverÆs counter value is only incremented after a Although the server's counter value is only incremented after a
successful HOTP authentication, the counter on the token is successful HOTP authentication, the counter on the token is
incremented every time a new HOTP is requested by the user. Because 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 of this, the counter values on the server and on the token might be
out of synchronization. out of synchronization.
We RECOMMEND setting a look-ahead parameter s on the server, which We RECOMMEND setting a look-ahead parameter s on the server, which
defines the size of the look-ahead window. In a nutshell, the defines the size of the look-ahead window. In a nutshell, the
server can recalculate the next s HOTP-server values, and check server can recalculate the next s HOTP-server values, and check
them against the received HOTP-client. them against the received HOTP-client.
skipping to change at page 10, line 10 skipping to change at page 10, line 10
go on checking HOTP values forever (causing a DoS attack) and also go on checking HOTP values forever (causing a DoS attack) and also
restricts the space of possible solutions for an attacker trying to restricts the space of possible solutions for an attacker trying to
manufacture HOTP values. s SHOULD be set as low as possible, while manufacture HOTP values. s SHOULD be set as low as possible, while
still ensuring usability is not impacted. still ensuring usability is not impacted.
HOTP: An HMAC-based One Time Password Algorithm October 2004 HOTP: An HMAC-based One Time Password Algorithm October 2004
7. HOTP Algorithm Security: Overview 7. HOTP Algorithm Security: Overview
The conclusion of the security analysis detailed in the Appendix The conclusion of the security analysis detailed in the Appendix
section is that, for all practical purposes, the outputs of HOTP on section is that, for all practical purposes, the outputs of the
distinct counter inputs are uniformly and independently distributed dynamic truncation (DT) on distinct counter inputs are uniformly
strings. and independently distributed 31-bit strings.
As a result, the best possible attack against the HOTP function is The security analysis then details the impact of the conversion
the brute force attack. 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 Assuming an adversary is able to observe numerous protocol
exchanges and collect sequences of successful authentication exchanges and collect sequences of successful authentication
values. This adversary, trying to build a function F to generate values. This adversary, trying to build a function F to generate
HOTP values based on his observations, will not have a significant HOTP values based on his observations, will not have a significant
advantage over a random guess. advantage over a random guess.
The logical conclusion is simply that is best strategy will once The logical conclusion is simply that is best strategy will once
again be to perform a brute force attack to enumerate and try all again be to perform a brute force attack to enumerate and try all
the possible values. the possible values.
skipping to change at page 10, line 48 skipping to change at page 11, line 4
Obviously, we can play with s, T (the Throttling parameter that Obviously, we can play with s, T (the Throttling parameter that
would limit the number of attempts by an attacker) and Digit until would limit the number of attempts by an attacker) and Digit until
achieving a certain level of security, still preserving the system achieving a certain level of security, still preserving the system
usability. usability.
8. Protocol Extensions and Improvements 8. Protocol Extensions and Improvements
We introduce in this section several enhancements and suggestions We introduce in this section several enhancements and suggestions
to further improve the security of the algorithm HOTP to further improve the security of the algorithm HOTP
HOTP: An HMAC-based One Time Password Algorithm October 2004
8.1 Number of Digits 8.1 Number of Digits
A simple enhancement in terms of security would be to extract more A simple enhancement in terms of security would be to extract more
digits from the HMAC-SHA1 value. digits from the HMAC-SHA1 value.
HOTP: An HMAC-based One Time Password Algorithm October 2004 For instance, calculating the HOTP value modulo 10^8 to build an
8-digit HOTP value would reduce the probability of success of the
For instance, calculating the HOTP value modulo 10^8 to build an 8-
digit HOTP value would reduce the probability of success of the
adversary from sv/10^6 to sv/10^8. adversary from sv/10^6 to sv/10^8.
This could give the opportunity to improve usability, e.g. by This could give the opportunity to improve usability, e.g. by
increasing T and/or s, while still achieving a better security increasing T and/or s, while still achieving a better security
overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which
is the theoretical optimum for 6-digit code when s = 1. is the theoretical optimum for 6-digit code when s = 1.
8.2 Alpha-numeric Values 8.2 Alpha-numeric Values
Another option is to use A-Z and 0-9 values; or rather a subset of Another option is to use A-Z and 0-9 values; or rather a subset of
skipping to change at page 11, line 50 skipping to change at page 12, line 5
As we suggested for the resynchronization to enter a short sequence As we suggested for the resynchronization to enter a short sequence
(say 2 or 3) of HOTP values, we could generalize the concept to the (say 2 or 3) of HOTP values, we could generalize the concept to the
protocol, and add a parameter L that would define the length of the protocol, and add a parameter L that would define the length of the
HOTP sequence to enter. HOTP sequence to enter.
Per default, the value L SHOULD be set to 1, but if security needs Per default, the value L SHOULD be set to 1, but if security needs
to be increased, users might be asked (possibly for a short period to be increased, users might be asked (possibly for a short period
of time, or a specific operation) to enter L HOTP values. of time, or a specific operation) to enter L HOTP values.
HOTP: An HMAC-based One Time Password Algorithm October 2004
This is another way, without increasing the HOTP length or using This is another way, without increasing the HOTP length or using
alphanumeric values to tighten security. alphanumeric values to tighten security.
Note: The system MAY also be programmed to request synchronization Note: The system MAY also be programmed to request synchronization
on a regular basis (e.g. every night, or twice a week, etc.) and to on a regular basis (e.g. every night, or twice a week, etc.) and to
achieve this purpose, ask for a sequence of L HOTP values. achieve this purpose, ask for a sequence of L HOTP values.
HOTP: An HMAC-based One Time Password Algorithm October 2004
8.4 A Counter-based Re-Synchronization Method 8.4 A Counter-based Re-Synchronization Method
In this case, we assume that the client can access and send not In this case, we assume that the client can access and send not
only the HOTP value but also other information, more specifically only the HOTP value but also other information, more specifically
the counter value. the counter value.
A more efficient and secure method for resynchronization is A more efficient and secure method for resynchronization is
possible in this case. The client application will not send the possible in this case. The client application will not send the
HOTP-client value only, but the HOTP-client and the related C- HOTP-client value only, but the HOTP-client and the related
client counter value, the HOTP value acting as a message C-client counter value, the HOTP value acting as a message
authentication code of the counter. authentication code of the counter.
Resynchronization Counter-based Protocol (RCP) Resynchronization Counter-based Protocol (RCP)
---------------------------------------------- ----------------------------------------------
The server accepts if the following are all true, where C-server is The server accepts if the following are all true, where C-server is
its own current counter value: its own current counter value:
1) C-client >= C-server 1) C-client >= C-server
2) C-client û C-server <= s 2) C-client - C-server <= s
3) Check that HOTP-client is valid HOTP(K,C-Client) 3) Check that HOTP-client is valid HOTP(K,C-Client)
4) If true, the server sets C to C-client + 1 and client 4) If true, the server sets C to C-client + 1 and client
is authenticated is authenticated
In this case, there is no need for managing a look-ahead window In this case, there is no need for managing a look-ahead window
anymore. The probability of success of the adversary is only v/10^6 anymore. The probability of success of the adversary is only v/10^6
or roughly v in one million. A side benefit is obviously to be able or roughly v in one million. A side benefit is obviously to be able
to increase s ôinfinitelyö and therefore improve the system to increase s "infinitely" and therefore improve the system
usability without impacting the security. usability without impacting the security.
This resynchronization protocol SHOULD be use whenever the related This resynchronization protocol SHOULD be use whenever the related
impact on the client and server applications is deemed acceptable. impact on the client and server applications is deemed acceptable.
9. Conclusion 9. Conclusion
This draft describes HOTP, a HMAC-based One-Time Password This draft describes HOTP, a HMAC-based One-Time Password
algorithm. It also recommends the preferred implementation and algorithm. It also recommends the preferred implementation and
related modes of operations for deploying the algorithm. related modes of operations for deploying the algorithm.
The draft also exhibits elements of security and demonstrates that The draft also exhibits elements of security and demonstrates that
the HOTP algorithm is practical and sound, the best possible attack the HOTP algorithm is practical and sound, the best possible attack
HOTP: An HMAC-based One Time Password Algorithm October 2004
being a brute force attack that can be prevented by careful being a brute force attack that can be prevented by careful
implementation of countermeasures in the validation server. implementation of countermeasures in the validation server.
Eventually, several enhancements have been proposed, in order to Eventually, several enhancements have been proposed, in order to
improve security if needed for specific applications. improve security if needed for specific applications.
HOTP: An HMAC-based One Time Password Algorithm October 2004
10. Acknowledgements 10. Acknowledgements
The authors would like to thank Siddharth Bajaj, Alex Deacon and The authors would like to thank Siddharth Bajaj, Alex Deacon and
Nico Popp for their help during the conception and redaction of Nico Popp for their help during the conception and redaction of
this document. this document.
11. Contributors 11. Contributors
The authors of this draft would like to emphasize the role of two The authors of this draft would like to emphasize the role of two
persons who have made a key contribution to this document: persons who have made a key contribution to this document:
skipping to change at page 13, line 41 skipping to change at page 13, line 46
Crypto'96, LNCS Vol. 1109, pp. 1-15. Crypto'96, LNCS Vol. 1109, pp. 1-15.
[BCK2] M. Bellare, R. Canetti, and H. Krawczyk, HMAC: [BCK2] M. Bellare, R. Canetti, and H. Krawczyk, HMAC:
Keyed-Hashing for Message Authentication, IETF Network Keyed-Hashing for Message Authentication, IETF Network
Working Group, RFC 2104, February 1997. Working Group, RFC 2104, February 1997.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC3668] Bradner, S., "Intellectual Propery Rights in IETF [RFC3668] Bradner, S., "Intellectual Propery Rights in IETF
Technologyö, BCP 79, RFC 3668, February 2004. Technology", BCP 79, RFC 3668, February 2004.
12.2 Informative 12.2 Informative
[OATH] www.openauthentication.org, Initiative for Open [OATH] www.openauthentication.org, Initiative for Open
AuTHentication AuTHentication
13. AuthorsÆ Addresses 13. Authors' Addresses
HOTP: An HMAC-based One Time Password Algorithm October 2004
Primary point of contact (for sending comments and question): Primary point of contact (for sending comments and question):
David M'Raihi David M'Raihi
VeriSign, Inc. VeriSign, Inc.
685 E. Middlefield Road Phone: 1-650-426-3832 685 E. Middlefield Road Phone: 1-650-426-3832
Mountain View, CA 94043 USA Email: dmraihi@verisign.com Mountain View, CA 94043 USA Email: dmraihi@verisign.com
HOTP: An HMAC-based One Time Password Algorithm October 2004
Other AuthorsÆ contact information: Other Authors' contact information:
Mihir Bellare Mihir Bellare
Dept of Computer Science and Engineering, Mail Code 0114 Dept of Computer Science and Engineering, Mail Code 0114
University of California at San Diego University of California at San Diego
9500 Gilman Drive 9500 Gilman Drive
La Jolla, CA 92093, USA Email: mihir@cs.ucsd.edu La Jolla, CA 92093, USA Email: mihir@cs.ucsd.edu
Frank Hoornaert Frank Hoornaert
VASCO Data Security, Inc. VASCO Data Security, Inc.
Koningin Astridlaan 164 Koningin Astridlaan 164
skipping to change at page 14, line 46 skipping to change at page 15, line 5
The security analysis of the HOTP algorithm is summarized in this The security analysis of the HOTP algorithm is summarized in this
section. We first detail the best attack strategies, and then section. We first detail the best attack strategies, and then
elaborate on the security under various assumptions, the impact of elaborate on the security under various assumptions, the impact of
the truncation and some recommendations regarding the number of the truncation and some recommendations regarding the number of
digits. digits.
We focus this analysis on the case where Digit = 6, i.e. an HOTP 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 function that produces 6-digit values, which is the bare minimum
recommended in this draft. recommended in this draft.
HOTP: An HMAC-based One Time Password Algorithm October 2004
A.1 Definitions and Notations A.1 Definitions and Notations
We denote by {0,1}^l the set of all strings of length l. We denote by {0,1}^l the set of all strings of length l.
Let Z_{n} = {0,.., n - 1}. Let Z_{n} = {0,.., n - 1}.
HOTP: An HMAC-based One Time Password Algorithm October 2004
Let IntDiv(a,b) denote the integer division algorithm that takes Let IntDiv(a,b) denote the integer division algorithm that takes
input integers a, b where a >= b >= 1 and returns integers (q,r) input integers a, b where a >= b >= 1 and returns integers (q,r)
the quotient and remainder, respectively, of the division of a by the quotient and remainder, respectively, of the division of a by
b. (Thus a = bq + r and 0 <= r < b.) 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 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 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 H(K,C). (In the case of HOTP, H is HMAC-SHA-1; we use this formal
definition for generalizing our proof of security) definition for generalizing our proof of security)
A.2 The idealized algorithm: HOTP-IDEAL A.2 The idealized algorithm: HOTP-IDEAL
We now define an idealized counterpart of the HOTP algorithm. In We now define an idealized counterpart of the HOTP algorithm. In
this algorithm, the role of H is played by a random function that this algorithm, the role of H is played by a random function that
forms the key. forms the key.
To be more precise, let Maps(c,n) denote the set of all functions 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 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 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) 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 to be drawn at random. It is not feasible to implement this
idealized algorithm, since the key, being a function from is way idealized algorithm, since the key, being a function from is way
too large to even store. So why consider it? too large to even store. So why consider it?
Our security analysis will show that as long as H satisfies a Our security analysis will show that as long as H satisfies a
certain well-accepted assumption, the security of the actual and certain well-accepted assumption, the security of the actual and
idealized algorithms is for all practical purposes the same. The idealized algorithms is for all practical purposes the same. The
task that really faces us, then, is to assess the security of the task that really faces us, then, is to assess the security of the
idealized algorithm. idealized algorithm.
In analyzing the idealized algorithm, we are concentrating on In analyzing the idealized algorithm, we are concentrating on
assessing the quality of the design of the algorithm itself, assessing the quality of the design of the algorithm itself,
independently of HMAC-SHA-1. This is in fact the important issue. independently of HMAC-SHA-1. This is in fact the important issue.
A.3 Model of Security A.3 Model of Security
The model exhibits the type of threats or attacks that are being The model exhibits the type of threats or attacks that are being
considered and enables to asses the security of HOTP and HOTP- considered and enables to asses the security of HOTP and
IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the purpose HOTP-IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the
of this security analysis. purpose of this security analysis.
The scenario we are considering is that a user and server share a 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 key K for ALG. Both maintain a counter C, initially zero, and the
HOTP: An HMAC-based One Time Password Algorithm October 2004
user authenticates itself by sending ALG(K,C) to the server. The user authenticates itself by sending ALG(K,C) to the server. The
latter accepts if this value is correct. latter accepts if this value is correct.
In order to protect against accidental increment of the user In order to protect against accidental increment of the user
counter, the server, upon receiving a value z, will accept as long counter, the server, upon receiving a value z, will accept as long
HOTP: An HMAC-based One Time Password Algorithm October 2004
as z equals ALG(K,i) for some i in the range C,...,C + s-1, where s 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 is the resynchronization parameter and C is the server counter. If
it accepts with some value of i, it then increments its counter to 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. 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 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 needs to achieve in order to "win." First, the adversary is assumed
to be able to eavesdrop, meaning see the authenticator transmitted to be able to eavesdrop, meaning see the authenticator transmitted
by the user. Second, the adversary wins if it can get the server to 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 accept an authenticator relative to a counter value for which the
user has never transmitted an authenticator. user has never transmitted an authenticator.
The formal adversary, which we denote by B, starts out knowing The formal adversary, which we denote by B, starts out knowing
which algorithm ALG is being used, knowing the system design and which algorithm ALG is being used, knowing the system design and
knowing all system parameters. The one and only thing it is not 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. 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 The model gives B full control of the scheduling of events. It has
access to an authenticator oracle representing the user. By calling access to an authenticator oracle representing the user. By calling
this oracle, the adversary can ask the user to authenticate itself this oracle, the adversary can ask the user to authenticate itself
and get back the authenticator in return. It can call this oracle 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 as often as it wants and when it wants, using the authenticators it
accumulates to perhaps ôlearnö how to make authenticators itself. accumulates to perhaps "learn" how to make authenticators itself.
At any time, it may also call a verification oracle, supplying the At any time, it may also call a verification oracle, supplying the
latter with a candidate authenticator of its choice. It wins if the latter with a candidate authenticator of its choice. It wins if the
server accepts this accumulator. server accepts this accumulator.
Consider the following game involving an adversary B that is Consider the following game involving an adversary B that is
attempting to compromise the security of an authentication attempting to compromise the security of an authentication
algorithm ALG: K x {0,1}^c --> R. algorithm ALG: K x {0,1}^c --> R.
Initializations - A key K is selected at random from K, a counter C 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. is initialized to 0, and the Boolean value win is set to false.
skipping to change at page 16, line 50 skipping to change at page 17, line 4
Game execution - Adversary B is provided with the two following Game execution - Adversary B is provided with the two following
oracles: oracles:
Oracle AuthO() Oracle AuthO()
O = ALG(K,C) O = ALG(K,C)
C = C + 1 C = C + 1
Return O to B Return O to B
Oracle VerO() Oracle VerO()
i = C i = C
HOTP: An HMAC-based One Time Password Algorithm October 2004
While (i <= C + s - 1 and Win = FALSE) do While (i <= C + s - 1 and Win = FALSE) do
If O = ALG(K,i) then Win = TRUE; C = i + 1 If O = ALG(K,i) then Win = TRUE; C = i + 1
Else i = i + 1 Else i = i + 1
Return Win to B Return Win to B
HOTP: An HMAC-based One Time Password Algorithm October 2004
AuthO() is the authenticator oracle and VerO() is the verification AuthO() is the authenticator oracle and VerO() is the verification
oracle. oracle.
Upon execution, B queries the two oracles at will. Let Adv(B) be 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 the probability that win gets set to true in the above game. This
is the probability that the adversary successfully impersonates the is the probability that the adversary successfully impersonates the
user. user.
Our goal is to assess how large this value can be as a function of Our goal is to assess how large this value can be as a function of
skipping to change at page 17, line 50 skipping to change at page 18, line 5
Then for any z in Z_{m} Then for any z in Z_{m}
P_{N,m}(z) = (q + 1) / N if 0 <= z < r P_{N,m}(z) = (q + 1) / N if 0 <= z < r
q / N if r <= z < m q / N if r <= z < m
Proof of Lemma 1 Proof of Lemma 1
Let the random variable X be uniformly distributed over Z_{N}. Let the random variable X be uniformly distributed over Z_{N}.
Then: Then:
HOTP: An HMAC-based One Time Password Algorithm October 2004
P_{N,m}(z) = Pr [X mod m = z] P_{N,m}(z) = Pr [X mod m = z]
= Pr [X < mq] ¸ Pr [X mod m = z| X < mq] = Pr [X < mq] * Pr [X mod m = z| X < mq]
+ Pr [mq <= X < N] ¸ Pr [X mod m = z| mq <= X < N] + Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N]
HOTP: An HMAC-based One Time Password Algorithm October 2004
= mq/N ¸ 1/m + = mq/N * 1/m +
(N - mq)/N ¸ 1 / (N û mq) if 0 <= z < N û mq (N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq
0 if N û mq <= z <= m 0 if N - mq <= z <= m
= q/N + = q/N +
r/N ¸ 1 / r if 0 <= z < N û mq r/N * 1 / r if 0 <= z < N - mq
0 if r <= z <= m 0 if r <= z <= m
Simplifying yields the claimed equation. Simplifying yields the claimed equation.
Let N = 2^31, d = 6 and m = 10^d. If x is chosen at random from 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 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 6-digit number by taking x mod m does not yield a random 6-digit
number. number.
Rather, x mod m is distributed as shown in the following table: Rather, x mod m is distributed as shown in the following table:
skipping to change at page 18, line 50 skipping to change at page 19, line 5
force attack using v verification attempts would succeed with force attack using v verification attempts would succeed with
probability sv/10^Digit. probability sv/10^Digit.
However, an adversary can exploit the bias in the outputs of HOTP- However, an adversary can exploit the bias in the outputs of HOTP-
IDEAL, predicted by Lemma 1, to mount a slightly better attack. IDEAL, predicted by Lemma 1, to mount a slightly better attack.
Namely, it makes authentication attempts with authenticators which Namely, it makes authentication attempts with authenticators which
are the most likely values, meaning the ones in the range 0,...,r - are the most likely values, meaning the ones in the range 0,...,r -
1, where (q,r) = IntDiv(2^31,10^Digit). 1, where (q,r) = IntDiv(2^31,10^Digit).
HOTP: An HMAC-based One Time Password Algorithm October 2004
The following specifies an adversary in our model of security that The following specifies an adversary in our model of security that
mounts the attack. It estimates the success probability as a mounts the attack. It estimates the success probability as a
function of the number of verification queries. function of the number of verification queries.
HOTP: An HMAC-based One Time Password Algorithm October 2004
For simplicity, we assume the number of verification queries is at For simplicity, we assume the number of verification queries is at
most r. With N = 2^31 and m = 10^6 we have r = 483,648, and the 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 throttle value is certainly less than this, so this assumption is
not much of a restriction. not much of a restriction.
Proposition 1 Proposition 1
Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume 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 s <= m. The brute-force attack adversary B-bf attacks HOTP using v
<= r verification oracle queries. This adversary makes no <= r verification oracle queries. This adversary makes no
authenticator oracle queries, and succeeds with probability authenticator oracle queries, and succeeds with probability
Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s
which is roughly equals to which is roughly equals to
sv ¸ (q+1)/2^31 sv * (q+1)/2^31
With m = 10^6 we get q = 2,147. In that case, the brute force With m = 10^6 we get q = 2,147. In that case, the brute force
attack using v verification attempts succeeds with probability attack using v verification attempts succeeds with probability
Adv(B-bf) roughly = sv ¸ 2148/2^31 = sv ¸ 1.00024045/10^6 Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6
As this equation shows, the resynchronization parameter s has a As this equation shows, the resynchronization parameter s has a
significant impact in that the adversaryÆs success probability is significant impact in that the adversary's success probability is
proportional to s. This means that s cannot be made too large proportional to s. This means that s cannot be made too large
without compromising security. without compromising security.
A.4.3 Brute force attacks are the best possible attacks A.4.3 Brute force attacks are the best possible attacks
A central question is whether there are attacks any better than the A central question is whether there are attacks any better than the
brute force one. In particular, the brute force attack did not brute force one. In particular, the brute force attack did not
attempt to collect authenticators sent by the user and try to attempt to collect authenticators sent by the user and try to
cryptanalyze them in an attempt to learn how to better construct cryptanalyze them in an attempt to learn how to better construct
authenticators. Would doing this help? Is there some way to ôlearnö authenticators. Would doing this help? Is there some way to "learn"
how to build authenticators that result in a higher success rate how to build authenticators that result in a higher success rate
than given by the brute-force attack? than given by the brute-force attack?
The following says the answer to these questions is no. No matter 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 what strategy the adversary uses, and even if it sees, and tries to
exploit, the authenticators from authentication attempts of the exploit, the authenticators from authentication attempts of the
user, its success probability will not be above that of the brute user, its success probability will not be above that of the brute
force attack - this is true as long as the number of force attack - this is true as long as the number of
authentications it observes is not incredibly large. This is authentications it observes is not incredibly large. This is
valuable information regarding the security of the scheme. valuable information regarding the security of the scheme.
HOTP: An HMAC-based One Time Password Algorithm October 2004
Proposition 2 Proposition 2
Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B 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 be any adversary attacking HOTP-IDEAL using v verification oracle
queries and a <= 2^c û s authenticator oracle queries. Then queries and a <= 2^c - s authenticator oracle queries. Then
HOTP: An HMAC-based One Time Password Algorithm October 2004
Adv(B) < = sv ¸ (q+1)/ 2^31 Adv(B) < = sv * (q+1)/ 2^31
Note: This result is conditional on the adversary not seeing more Note: This result is conditional on the adversary not seeing more
than 2^c - s authentications performed by the user, which is hardly than 2^c - s authentications performed by the user, which is hardly
restrictive as long as c is large enough. restrictive as long as c is large enough.
With m = 10^6 we get q = 2,147. In that case, Proposition 2 says 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 that any adversary B attacking HOTP-IDEAL and making v verification
attempts succeeds with probability at most attempts succeeds with probability at most
Equation 1 Equation 1
sv ¸ 2148/2^31 roughly = sv ¸ 1.00024045/10^6 sv * 2148/2^31 roughly = sv * 1.00024045/10^6
Meaning, BÆs success rate is not more than that achieved by the Meaning, B's success rate is not more than that achieved by the
brute force attack. brute force attack.
A.5 Security Analysis of HOTP A.5 Security Analysis of HOTP
We have analyzed in the previous sections, the security of the We have analyzed in the previous sections, the security of the
idealized counterparts HOTP-IDEAL of the actual authentication idealized counterparts HOTP-IDEAL of the actual authentication
algorithm HOTP. We now show that, under appropriate and well- algorithm HOTP. We now show that, under appropriate and
believed assumption on H, the security of the actual algorithms is well-believed assumption on H, the security of the actual
essentially the same as that of its idealized counterpart. algorithms is essentially the same as that of its idealized
counterpart.
The assumption in question is that H is a secure pseudorandom The assumption in question is that H is a secure pseudorandom
function, or PRF, meaning that its input-output values are function, or PRF, meaning that its input-output values are
indistinguishable from those of a random function in practice. indistinguishable from those of a random function in practice.
Consider an adversary A that is given an oracle for a function f: 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) {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 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 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. 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 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 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 computation of H, its prf-advantage from this attack turns out to
be (t/T)2^-k . Another possible attack is a birthday one [3], be (t/T)2^-k . Another possible attack is a birthday one [3],
whereby A can attain advantage p^2/2^n in p oracle queries and whereby A can attain advantage p^2/2^n in p oracle queries and
running time about pT. running time about pT.
HOTP: An HMAC-based One Time Password Algorithm October 2004
Our assumption is that these are the best possible attacks. This Our assumption is that these are the best possible attacks. This
translates into the following. translates into the following.
Assumption 1 Assumption 1
Let T denotes the time to perform one computation of H. Then if A Let T denotes the time to perform one computation of H. Then if A
is any adversary with running time at most t and making at most p is any adversary with running time at most t and making at most p
oracle queries, oracle queries,
HOTP: An HMAC-based One Time Password Algorithm October 2004
Adv(A) <= (t/T)/2^k + p^2/2^n Adv(A) <= (t/T)/2^k + p^2/2^n
In practice this assumption means that H is very secure as PRF. For In practice this assumption means that H is very secure as PRF. For
example, given that k = n = 160, an attacker with running time 2^60 example, given that k = n = 160, an attacker with running time 2^60
and making 2^40 oracle queries has advantage at most (about) 2^-80. and making 2^40 oracle queries has advantage at most (about) 2^-80.
Theorem 1 Theorem 1
Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B
be any adversary attacking HOTP using v verification oracle be any adversary attacking HOTP using v verification oracle
queries, a <= 2^c - s authenticator oracle queries, and running queries, a <= 2^c - s authenticator oracle queries, and running
time t. Let T denote the time to perform one computation of H. If time t. Let T denote the time to perform one computation of H. If
Assumption 1 is true then Assumption 1 is true then
Adv(B) <= sv ¸ (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n Adv(B) <= sv * (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n
In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller
than the sv(q + 1)/2^n term, so that the above says that for all than the sv(q + 1)/2^n term, so that the above says that for all
practical purposes the success rate of an adversary attacking HOTP practical purposes the success rate of an adversary attacking HOTP
is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP
algorithm is in practice essentially as good as its idealized algorithm is in practice essentially as good as its idealized
counterpart. counterpart.
In the case m = 10^6 of a 6-digit output this means that an In the case m = 10^6 of a 6-digit output this means that an
adversary making v authentication attempts will have a success rate adversary making v authentication attempts will have a success rate
skipping to change at page 21, line 47 skipping to change at page 22, line 5
by Equation 1. by Equation 1.
We can safely assume sv <= 2^40 due to the throttling and bounds on We can safely assume sv <= 2^40 due to the throttling and bounds on
s. So: s. So:
(t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160 (t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160
roughly <= 2^-78 roughly <= 2^-78
which is much smaller than the success probability of Equation 1 which is much smaller than the success probability of Equation 1
and negligible compared to it. and negligible compared to it.
HOTP: An HMAC-based One Time Password Algorithm October 2004
Full Copyright Statement Full Copyright Statement
Copyright (C) The Internet Society 2004. This document is subject Copyright (C) The Internet Society 2004. This document is subject
to the rights, licenses and restrictions contained in BCP 78, and to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights. except as set forth therein, the authors retain all their rights.
HOTP: An HMAC-based One Time Password Algorithm October 2004
This document and the information contained herein are provided on This document and the information contained herein are provided on
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT
THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR
ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
PARTICULAR PURPOSE. PARTICULAR PURPOSE.
 End of changes. 66 change blocks. 
90 lines changed or deleted 102 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/