< draft-mraihi-oath-hmac-otp   rfc4226.txt 
Internet Draft D. M'Raihi Network Working Group D. M'Raihi
Category: Informational VeriSign Request for Comments: 4226 VeriSign
Document: draft-mraihi-oath-hmac-otp-04.txt M. Bellare Category: Informational M. Bellare
Expires: April 2005 UCSD UCSD
F. Hoornaert F. Hoornaert
Vasco Vasco
D. Naccache D. Naccache
Gemplus Gemplus
O. Ranen O. Ranen
Aladdin Aladdin
October 2004 December 2005
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, each author represents that any This memo provides information for the Internet community. It does
applicable patent or other IPR claims of which he or she is aware not specify an Internet standard of any kind. Distribution of this
have been or will be disclosed, and any of which he or she becomes memo is unlimited.
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Copyright Notice
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Copyright (C) The Internet Society (2005).
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as "work in
progress".
The list of current Internet-Drafts can be accessed at Abstract
http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
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 document describes an algorithm to generate one-time password This work is a joint effort by the OATH (Open AuTHentication)
values, based on HMAC [BCK1]. A security analysis of the algorithm membership to specify an algorithm that can be freely distributed to
is presented, and important parameters related to the secure the technical community. The authors believe that a common and
deployment of the algorithm are discussed. The proposed algorithm shared algorithm will facilitate adoption of two-factor
can be used across a wide range of network applications ranging authentication on the Internet by enabling interoperability across
from remote VPN access, Wi-Fi network logon to transaction-oriented commercial and open-source implementations.
Web applications.
This work is a joint effort by the OATH (Open AuTHentication) Table of Contents
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
Table of Contents
1. Overview...................................................3 1. Overview ........................................................3
2. Introduction...............................................3 2. Introduction ....................................................3
3. Requirements Terminology...................................4 3. Requirements Terminology ........................................4
4. Algorithm Requirements.....................................4 4. Algorithm Requirements ..........................................4
5. HOTP Algorithm.............................................5 5. HOTP Algorithm ..................................................5
5.1 Notation and Symbols.......................................5 5.1. Notation and Symbols .......................................5
5.2 Description................................................5 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 Considerations....................................7 6. Security Considerations .........................................8
6.1 Authentication Protocol Requirements.......................8 7. Security Requirements ...........................................9
6.2 Validation of HOTP values..................................8 7.1. Authentication Protocol Requirements .......................9
6.3 Bi-directional Authentication..............................9 7.2. Validation of HOTP Values .................................10
6.4 Throttling at the server...................................9 7.3. Throttling at the Server ..................................10
6.5 Resynchronization of the counter...........................9 7.4. Resynchronization of the Counter ..........................11
6.6 Management of Shared Secrets..............................10 7.5. Management of Shared Secrets ..............................11
7. HOTP Algorithm Security: Overview.........................12 8. Composite Shared Secrets .......................................14
8. Composite Shared Secrets..................................13 9. Bi-Directional Authentication ..................................14
9. IANA Considerations.......................................13 10. Conclusion ....................................................15
10. Conclusion................................................13 11. Acknowledgements ..............................................15
11. Acknowledgements..........................................13 12. Contributors ..................................................15
12. Contributors..............................................13 13. References ....................................................15
13. References................................................14 13.1. Normative References .....................................15
12.1 Normative...............................................14 13.2. Informative References ...................................16
12.2 Informative.............................................14 Appendix A - HOTP Algorithm Security: Detailed Analysis ...........17
14. Authors' Addresses........................................15 A.1. Definitions and Notations .................................17
15. Full Copyright Statement...................................15 A.2. The Idealized Algorithm: HOTP-IDEAL .......................17
16. Intellectual Property......................................16 A.3. Model of Security .........................................18
Appendix A - HOTP Algorithm Security: Detailed Analysis........16 A.4. Security of the Ideal Authentication Algorithm ............19
A.1 Definitions and Notations..................................16 A.4.1. From Bits to Digits ................................19
A.2 The idealized algorithm: HOTP-IDEAL........................17 A.4.2. Brute Force Attacks ................................21
A.3 Model of Security..........................................17 A.4.3. Brute force attacks are the best possible attacks ..22
A.4 Security of the ideal authentication algorithm.............19 A.5. Security Analysis of HOTP .................................23
A.4.1 From bits to digits......................................19 Appendix B - SHA-1 Attacks ........................................25
A.4.2 Brute force attacks......................................20 B.1. SHA-1 Status ..............................................25
A.4.3 Brute force attacks are the best possible attacks........21 B.2. HMAC-SHA-1 Status .........................................26
A.5 Security Analysis of HOTP..................................22 B.3. HOTP Status ...............................................26
Appendix B - SHA-1 Attacks.....................................23 Appendix C - HOTP Algorithm: Reference Implementation .............27
B.1 SHA-1 status...............................................23 Appendix D - HOTP Algorithm: Test Values ..........................32
B.2 HMAC-SHA-1 status..........................................24 Appendix E - Extensions ...........................................33
B.3 HOTP status................................................25 E.1. Number of Digits ..........................................33
Appendix C - HOTP Algorithm: Reference Implementation..........25 E.2. Alphanumeric Values .......................................33
Appendix D - HOTP Algorithm: Test Values.......................29 E.3. Sequence of HOTP values ...................................34
Appendix E - Extensions........................................29 E.4. A Counter-Based Resynchronization Method ..................34
E.1 Number of Digits..........................................30 E.5. Data Field ................................................35
E.2 Alpha-numeric Values......................................30
E.3 Sequence of HOTP values...................................30
E.4 A Counter-based Re-Synchronization Method.................31
E.5 Data Field................................................31
1. Overview
The document introduces first the context around the HOTP 1. Overview
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 9 concludes this document. The
interested reader will find in the Appendix a detailed, full-fledge
analysis of the algorithm security: an idealized version of the
algorithm is evaluated, and then the HOTP algorithm security is
analyzed.
2. Introduction 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.
Today, deployment of two-factor authentication remains extremely 2. Introduction
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 Today, deployment of two-factor authentication remains extremely
exposed the inadequacies of static passwords as the primary mean of limited in scope and scale. Despite increasingly higher levels of
authentication on the Internet. At the same time, the current threats and attacks, most Internet applications still rely on weak
approach that requires an end-user to carry an expensive, authentication schemes for policing user access. The lack of
single-function device that is only used to authenticate to the interoperability among hardware and software technology vendors has
network is clearly not the right answer. For two factor been a limiting factor in the adoption of two-factor authentication
authentication to propagate on the Internet, it will have to be technology. In particular, the absence of open specifications has
embedded in more flexible devices that can work across a wide range led to solutions where hardware and software components are tightly
of applications. coupled through proprietary technology, resulting in high-cost
solutions, poor adoption, and limited innovation.
The ability to embed this base technology while ensuring broad In the last two years, the rapid rise of network threats has exposed
interoperability require that it be made freely available to the the inadequacies of static passwords as the primary mean of
broad technical community of hardware and software developers. Only authentication on the Internet. At the same time, the current
an open system approach will ensure that basic two-factor approach that requires an end user to carry an expensive, single-
authentication primitives can be built into the next-generation of function device that is only used to authenticate to the network is
consumer devices such USB mass storage devices, IP phones, and clearly not the right answer. For two-factor authentication to
personal digital assistants). propagate on the Internet, it will have to be embedded in more
flexible devices that can work across a wide range of applications.
One Time Password is certainly one of the simplest and most popular The ability to embed this base technology while ensuring broad
forms of two-factor authentication for securing network access. For interoperability requires that it be made freely available to the
example, in large enterprises, Virtual Private Network access often broad technical community of hardware and software developers. Only
requires the use of One Time Password tokens for remote user an open-system approach will ensure that basic two-factor
authentication. One Time Passwords are often preferred to stronger authentication primitives can be built into the next generation of
forms of authentication such as PKI or biometrics because an consumer devices such as USB mass storage devices, IP phones, and
air-gap device does not require the installation of any client personal digital assistants.
desktop software on the user machine, therefore allowing them to
roam across multiple machines including home computers, kiosks and
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.
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 [RFC3668].
The authors of this document are members of the Open AuTHentication One-Time Password is certainly one of the simplest and most popular
initiative [OATH]. The initiative was created in 2004 to facilitate forms of two-factor authentication for securing network access. For
collaboration among strong authentication technology providers. 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.
3. Requirements Terminology 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 key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The authors of this document are members of the Open AuTHentication
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in initiative [OATH]. The initiative was created in 2004 to facilitate
this document are to be interpreted as described in RFC 2119. collaboration among strong authentication technology providers.
4. Algorithm Requirements 3. Requirements Terminology
This section presents the main requirements that drove this The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
algorithm design. A lot of emphasis was placed on end-consumer "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
usability as well as the ability for the algorithm to be document are to be interpreted as described in [RFC2119].
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
pre-requisite.
R1 - The algorithm MUST be sequence or counter-based: One of the 4. Algorithm Requirements
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 This section presents the main requirements that drove this algorithm
minimizing requirements on battery, number of buttons, design. A lot of emphasis was placed on end-consumer usability as
computational horsepower, and size of LCD display. 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.
R3 - The algorithm MUST work with tokens that do not supports any R1 - The algorithm MUST be sequence- or counter-based: one of the
numeric input, but MAY also be used with more sophisticated devices goals is to have the HOTP algorithm embedded in high-volume devices
such as secure PIN-pads. such as Java smart cards, USB dongles, and GSM SIM cards.
R4 - The value displayed on the token MUST be easily read and R2 - The algorithm SHOULD be economical to implement in hardware by
entered by the user: This requires the HOTP value to be of minimizing requirements on battery, number of buttons, computational
reasonable length. The HOTP value must be at least a 6-digit value. horsepower, and size of LCD display.
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 R3 - The algorithm MUST work with tokens that do not support any
resynchronize the counter. The sections 6.4 and 8.4 detail the numeric input, but MAY also be used with more sophisticated devices
resynchronization mechanism proposed in this draft. such as secure PIN-pads.
R6 - The algorithm MUST use a strong shared secret. The length of R4 - The value displayed on the token MUST be easily read and entered
the shared secret MUST be at least 128 bits. This draft RECOMMENDs by the user: This requires the HOTP value to be of reasonable length.
a shared secret length of 160 bits.
5. HOTP Algorithm 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.
In this section, we introduce the notation and describe the HOTP R5 - There MUST be user-friendly mechanisms available to
algorithm basic blocks - the base function to compute an HMAC-SHA-1 resynchronize the counter. Section 7.4 and Appendix E.4 details the
value and the truncation method to extract an HOTP value. resynchronization mechanism proposed in this document
5.1 Notation and Symbols 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.
A string always means a binary string, meaning a sequence of zeros 5. HOTP Algorithm
and ones.
If s is a string then |s| denotes its length. 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.
If n is a number then |n| denotes its absolute value. 5.1. Notation and Symbols
If s is a string then s[i] denotes its i-th bit. We start numbering A string always means a binary string, meaning a sequence of zeros
the bits at 0, so s = s[0]s[1]..s[n-1] where n = |s| is the length and ones.
of s.
Let StToNum (String to Number) denote the function which as input a If s is a string, then |s| denotes its length.
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. If n is a number, then |n| denotes its absolute value.
Symbol Represents 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
C 8-byte counter value, the moving factor. This counter of s.
MUST be synchronized between the HOTP generator (client)
and the HOTP validator (server);
K shared secret between client and server; each HOTP Let StToNum (String to Number) denote the function that as input a
generator has a different and unique secret K; string s returns the number whose binary representation is s. (For
example, StToNum(110) = 6.)
T throttling parameter: the server will refuse connections Here is a list of symbols used in this document.
from a user after T unsuccessful authentication attempts;
s resynchronization parameter: the server will attempt to Symbol Represents
verify a received authenticator across s consecutive -------------------------------------------------------------------
counter values; C 8-byte counter value, the moving factor. This counter
MUST be synchronized between the HOTP generator (client)
and the HOTP validator (server).
Digit number of digits in an HOTP value; system parameter. K shared secret between client and server; each HOTP
generator has a different and unique secret K.
5.2 Description T throttling parameter: the server will refuse connections
from a user after T unsuccessful authentication attempts.
The HOTP algorithm is based on an increasing counter value and a s resynchronization parameter: the server will attempt to
static symmetric key known only to the token and the validation verify a received authenticator across s consecutive
HMAC-SHA-1 algorithm, as defined in RFC 2104 [BCK2]. counter values.
As the output of the HMAC-SHA1 calculation is 160 bits, we must Digit number of digits in an HOTP value; system parameter.
truncate this value to something that can be easily entered by a
user. 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)) 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.
The Key (K), the Counter (C) and Data values are hashed high-order The Key (K), the Counter (C), and Data values are hashed high-order
byte first. byte first.
The HOTP values generated by the HOTP generator are treated as big The HOTP values generated by the HOTP generator are treated as big
endian. endian.
5.3 Generating an HOTP value 5.3. Generating an HOTP Value
We can describe the operations in 3 distinct steps: We can describe the operations in 3 distinct steps:
Step 1: Generate an HMAC-SHA-1 value Step 1: Generate an HMAC-SHA-1 value Let HS = HMAC-SHA-1(K,C) // HS
Let HS = HMAC-SHA-1(K,C) // HS is a 20 byte string is a 20-byte string
Step 2: Generate a 4-byte string (Dynamic Truncation) Step 2: Generate a 4-byte string (Dynamic Truncation)
Let Sbits = DT(HS) // DT, defined in Section 6.3.1 Let Sbits = DT(HS) // DT, defined below,
// returns a 31 bit string // returns a 31-bit string
Step 3: Compute an HOTP value Step 3: Compute an HOTP value
Let Snum = StToNum(S) // Convert S to a number in Let Snum = StToNum(Sbits) // Convert S to a number in
0...2^{31}-1 0...2^{31}-1
Return D = Snum mod 10^Digit // D is a number in the range Return D = Snum mod 10^Digit // D is a number in the range
0...10^{Digit}-1 0...10^{Digit}-1
The Truncate function performs Step 2 and Step 3, i.e. the dynamic The Truncate function performs Step 2 and Step 3, i.e., the dynamic
truncation and then the reduction modulo 10^Digit. The purpose of truncation and then the reduction modulo 10^Digit. The purpose of
the dynamic offset truncation technique is to extract a 4-byte the dynamic offset truncation technique is to extract a 4-byte
dynamic binary code from a 160-bit (20-byte) HMAC-SHA1 result. dynamic binary code from a 160-bit (20-byte) HMAC-SHA-1 result.
DT(String) // String = String[0]...String[19] DT(String) // String = String[0]...String[19]
Let OffsetBits be the low order four bits of String[19] Let OffsetBits be the low-order 4 bits of String[19]
Offset = StToNum(OffSetBits) // 0 <= OffSet <= 15 Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
Let P = String[OffSet]...String[OffSet+3] Let P = String[OffSet]...String[OffSet+3]
Return the Last 31 bits of P Return the Last 31 bits of P
The reason for masking the most significant bit of P is to avoid The reason for masking the most significant bit of P is to avoid
confusion about signed vs. unsigned modulo computations. Different confusion about signed vs. unsigned modulo computations. Different
processors perform these operations differently, and masking out processors perform these operations differently, and masking out the
the signed bit removes all ambiguity. signed bit removes all ambiguity.
Implementations MUST extract a 6-digit code at a minimum and Implementations MUST extract a 6-digit code at a minimum and possibly
possibly 7 and 8-digit code. Depending on security requirements, 7 and 8-digit code. Depending on security requirements, Digit = 7 or
Digit = 7 or more SHOULD be considered in order to extract a longer 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 binary code given that hmac_result is a byte array with the HMAC-
HMAC-SHA1 result: SHA-1 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)
------------------------------------------------------------- -------------------------------------------------------------
| Byte Number | | Byte Number |
------------------------------------------------------------- -------------------------------------------------------------
|00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19| |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
------------------------------------------------------------- -------------------------------------------------------------
| Byte Value | | Byte Value |
------------------------------------------------------------- -------------------------------------------------------------
|1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a| |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.
* The last byte (byte 19) has the hex value 0x5a. We treat the dynamic binary code as a 31-bit, unsigned, big-endian
* The value of the lower four bits is 0xa (the offset value). integer; the first byte is masked with a 0x7f.
* 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 We then take this number modulo 1,000,000 (10^6) to generate the 6-
integer; the first byte is masked with a 0x7f. digit HOTP value 872921 decimal.
We then take this number modulo 1,000,000 (10^6) to generate the 6. Security Considerations
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.
Any One-Time Password algorithm is only as secure as the The security analysis then details the impact of the conversion from
Therefore, this section discusses the critical security a string to an integer and the final reduction modulo 10^Digit, where
requirements that our choice of algorithm imposes on the Digit is the number of digits in an HOTP value.
authentication protocol and validation software.
The parameters T and s discussed in this section have a significant The analysis demonstrates that these final steps introduce a
impact on the security - further details in Section 7 elaborate on negligible bias, which does not impact the security of the HOTP
the relations between these parameters and their impact on the algorithm, in the sense that the best possible attack against the
system security. HOTP function is the brute force attack.
It is also important to remark that the HOTP algorithm is not a Assuming an adversary is able to observe numerous protocol exchanges
substitute for encryption and does not provide for the privacy of and collect sequences of successful authentication values. This
data transmission. Other mechanisms should be used to defeat 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.
6.1 Authentication Protocol Requirements 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.
We introduce in this section some requirements for a protocol P Considering the security analysis in the Appendix of this document,
implementing HOTP as the authentication method between a prover and without loss of generality, we can approximate closely the security
a verifier. of the HOTP algorithm by the following formula:
RP1 - P MUST be two-factor, i.e. something you know (secret code Sec = sv/10^Digit
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 Where:
implies that a throttling/lockout scheme is RECOMMENDED on the - Sec is the probability of success of the adversary;
validation server side. - s is the look-ahead synchronization window size;
- v is the number of verification attempts;
- Digit is the number of digits in HOTP values.
RP3 - P SHOULD be implemented with respect to the state of the art Obviously, we can play with s, T (the Throttling parameter that would
in terms of security, in order to avoid the usual attacks and risks limit the number of attempts by an attacker), and Digit until
associated with the transmission of sensitive data over a public achieving a certain level of security, still preserving the system
network (privacy, replay attacks, etc.) usability.
6.2 Validation of HOTP values 7. Security Requirements
The HOTP client (hardware or software token) increments its counter Any One-Time Password algorithm is only as secure as the application
and then calculates the next HOTP value HOTP-client. If the value and the authentication protocols that implement it. Therefore, this
received by the authentication server matches the value calculated section discusses the critical security requirements that our choice
by the client, then the HOTP value is validated. In this case, the of algorithm imposes on the authentication protocol and validation
server increments the counter value by one. software.
If the value received by the server does not match the value The parameters T and s discussed in this section have a significant
calculated by the client, the server initiate the resynch protocol impact on the security -- further details in Section 6 elaborate on
(look-ahead window) before it requests another pass. the relations between these parameters and their impact on the system
security.
If the resynch fails, the server asks then for another It is also important to remark that the HOTP algorithm is not a
authentication pass of the protocol to take place, until the substitute for encryption and does not provide for the privacy of
maximum number of authorized attempts is reached. data transmission. Other mechanisms should be used to defeat attacks
aimed at breaking confidentiality and privacy of transactions.
If and when the maximum number of authorized attempts is reached, 7.1. Authentication Protocol Requirements
the server SHOULD lock out the account and initiate a procedure to
inform the user.
6.3 Bi-directional Authentication We introduce in this section some requirements for a protocol P
implementing HOTP as the authentication method between a prover and a
verifier.
Interestingly enough, the HOTP client could also be used to RP1 - P MUST support two-factor authentication, i.e., the
authenticate the validation server, claiming that it is a genuine communication and verification of something you know (secret code
entity knowing the shared secret. 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).
Since the HOTP client and the server are synchronized and share the RP2 - P SHOULD NOT be vulnerable to brute force attacks. This
same secret (or a method to recompute it) a simple 3-pass protocol implies that a throttling/lockout scheme is RECOMMENDED on the
could be put in place: validation server side.
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 RP3 - P SHOULD be implemented over a secure channel in order to
to take place over secure https (SSL) connections. protect users' privacy and avoid replay attacks.
6.4 Throttling at the server 7.2. Validation of HOTP Values
Truncating the HMAC-SHA1 value to a shorter value makes a brute The HOTP client (hardware or software token) increments its counter
force attack possible. Therefore, the authentication server needs and then calculates the next HOTP value HOTP client. If the value
to detect and stop brute force attacks. 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.
We RECOMMEND setting a throttling parameter T, which defines the If the value received by the server does not match the value
maximum number of possible attempts for One-Time-Password calculated by the client, the server initiate the resynch protocol
validation. The validation server manages individual counters per (look-ahead window) before it requests another pass.
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 usability is not significantly impacted.
Another option would be to implement a delay scheme to avoid a If the resynch fails, the server asks then for another
brute force attack. After each failed attempt A, the authentication authentication pass of the protocol to take place, until the
server would wait for an increased T*A number of seconds, e.g. say maximum number of authorized attempts is reached.
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 If and when the maximum number of authorized attempts is reached, the
prevent attacks based on multiple parallel guessing techniques. server SHOULD lock out the account and initiate a procedure to inform
the user.
6.5 Resynchronization of the counter 7.3. Throttling at the Server
Although the server's counter value is only incremented after a Truncating the HMAC-SHA-1 value to a shorter value makes a brute
successful HOTP authentication, the counter on the token is force attack possible. Therefore, the authentication server needs to
incremented every time a new HOTP is requested by the user. Because detect and stop brute force attacks.
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 We RECOMMEND setting a throttling parameter T, which defines the
defines the size of the look-ahead window. In a nutshell, the maximum number of possible attempts for One-Time Password validation.
server can recalculate the next s HOTP-server values, and check The validation server manages individual counters per HOTP device in
them against the received HOTP-client. 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.
Synchronization of counters in this scenario simply requires the Another option would be to implement a delay scheme to avoid a brute
server to calculate the next HOTP values and determine if there is force attack. After each failed attempt A, the authentication server
a match. Optionally, the system MAY require the user to send a would wait for an increased T*A number of seconds, e.g., say T = 5,
sequence of (say 2, 3) HOTP values for resynchronization purpose, then after 1 attempt, the server waits for 5 seconds, at the second
since forging a sequence of consecutive HOTP values is even more failed attempt, it waits for 5*2 = 10 seconds, etc.
difficult than guessing a single HOTP value.
The upper bound set by the parameter s ensures the server does not The delay or lockout schemes MUST be across login sessions to prevent
go on checking HOTP values forever (causing a DoS attack) and also attacks based on multiple parallel guessing techniques.
restricts the space of possible solutions for an attacker trying to
manufacture HOTP values. s SHOULD be set as low as possible, while
still ensuring usability is not impacted.
6.6 Management of Shared Secrets 7.4. Resynchronization of the Counter
The operations dealing with the shared secrets used to generate and Although the server's counter value is only incremented after a
verify OTP values must be performed securely, in order to mitigate successful HOTP authentication, the counter on the token is
risks of any leakage of sensitive information. We describe in this incremented every time a new HOTP is requested by the user. Because
section different modes of operations and techniquest to perform of this, the counter values on the server and on the token might be
these different operations with respect of the state of the art in out of synchronization.
terms of data security.
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
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:
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 * Deterministic Generation: secrets are derived from a master
seed, both at provisioning and verification stages and generated seed, both at provisioning and verification stages and generated
on-the-fly whenever it is required; on-the-fly whenever it is required.
* Random Generation: secrets are generated randomly at * Random Generation: secrets are generated randomly at
provisioning stage, and must be stored immediately and kept secure provisioning stage and must be stored immediately and kept
during their life cycle. secure during their life cycle.
Deterministic Generation Deterministic Generation
------------------------ ------------------------
A possible strategy is to derive the shared secrets from a master A possible strategy is to derive the shared secrets from a master
secret. The master secret will be stored at the server only. A secret. The master secret will be stored at the server only. A
tamper resistant device MUST be used to store the master key and tamper-resistant device MUST be used to store the master key and
derive the shared secrets from the master key and some public derive the shared secrets from the master key and some public
information. The main benefit would be to avoid the exposure of the information. The main benefit would be to avoid the exposure of the
shared secrets at any time and also avoid specific requirements on shared secrets at any time and also avoid specific requirements on
storage, since the shared secrets could be generated on-demand when storage, since the shared secrets could be generated on-demand when
needed at provisioning and validation time. needed at provisioning and validation time.
We distinguish two different cases: We distinguish two different cases:
- A single master key MK is used to derive the shared secrets;
- 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) each HOTP device has a different secret, K_i = SHA-1 (MK,i)
where i stands for a public piece of information that where i stands for a public piece of information that identifies
token ID, etc.; obviously, this is in the context of an uniquely the HOTP device such as a serial number, a token ID,
application or service - different application or service etc. Obviously, this is in the context of an application or
providers will have different secrets and settings; service -- different application or service providers will have
- Several master keys MK_i are used and each HOTP device stores a 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 set of different derived secrets, {K_i,j = SHA-1(MK_i,j)} where
j stands for a public piece of information identifying the j stands for a public piece of information identifying the
device. The idea would be to store ONLY the active master key device. The idea would be to store ONLY the active master key
at the validation server, in the HSM, and keep in a safe place, at the validation server, in the Hardware Security Module (HSM),
using secret sharing methods such as [Shamir] for instance. In and keep in a safe place, using secret sharing methods such as
this case, if a master secret MK_i is compromised, then it is [Shamir] for instance. In this case, if a master secret MK_i is
possible to switch to another secret without replacing all the compromised, then it is possible to switch to another secret
devices. without replacing all the devices.
The drawback in the deterministic case is that the exposure of the The drawback in the deterministic case is that the exposure of the
master secret would obviously enable an attacker to rebuild any master secret would obviously enable an attacker to rebuild any
shared secret based on correct public information. The revocation shared secret based on correct public information. The revocation of
of all secrets would be required, or switching to a new set of all secrets would be required, or switching to a new set of secrets
secrets in the case of multiple master keys. in the case of multiple master keys.
On the other hand, the device used to store the master key(s) and On the other hand, the device used to store the master key(s) and
generate the shared secrets MUST be tamper resistant. Furthermore, generate the shared secrets MUST be tamper resistant. Furthermore,
the HSM will not be exposed outside the security perimeter of the the HSM will not be exposed outside the security perimeter of the
validation system, therefore reducing the risk of leakage. validation system, therefore reducing the risk of leakage.
Random Generation Random Generation
----------------- -----------------
The shared secrets are randomly generated. We RECOMMEND to follow The shared secrets are randomly generated. We RECOMMEND following
the recommendations in [RFC1750] and to select a good and secure the recommendations in [RFC4086] and selecting a good and secure
random source for generating these secrets. A (true) random random source for generating these secrets. A (true) random
generator requires a naturally occurring source of randomness. generator requires a naturally occurring source of randomness.
Practically, there are two possible avenues to consider for the Practically, there are two possible avenues to consider for the
generation of the shared secrets: generation of the shared secrets:
* Hardware-based generators: they exploit the randomness which * Hardware-based generators: they exploit the randomness that
occurs in physical phenomena. A nice implementation can be based on occurs in physical phenomena. A nice implementation can be based on
oscillators, and built in such ways that active attacks are more oscillators and built in such ways that active attacks are more
difficult to perform. difficult to perform.
* Software-based generators: designing a good software random * Software-based generators: designing a good software random
generator is not an easy task. A simple, but efficient, generator is not an easy task. A simple, but efficient,
implementation should be based on various sources, and apply to the implementation should be based on various sources and apply to the
sampled sequence a one-way function such as SHA-1. sampled sequence a one-way function such as SHA-1.
We RECOMMEND to select proven products, being hardware or software We RECOMMEND selecting proven products, being hardware or software
generators for the computation of shared secrets. generators, for the computation of shared secrets.
We also RECOMMEND storing the shared secrets securely, and more We also RECOMMEND storing the shared secrets securely, and more
specifically encrypting the shared secrets when stored using specifically encrypting the shared secrets when stored using tamper-
tamper-resistant hardware encryption, and exposing them only when resistant hardware encryption and exposing them only when required:
required: e.g. the shared secret is decrypted when needed to verify for example, the shared secret is decrypted when needed to verify an
an HOTP value, and re-encrypted immediately to limit exposure in HOTP value, and re-encrypted immediately to limit exposure in the RAM
shared secrets MUST be in a secure area, to avoid as much as for a short period of time. The data store holding the shared
possible direct attack on the validation system and secrets secrets MUST be in a secure area, to avoid as much as possible direct
database. attack on the validation system and secrets database.
Particularly, access to the shared secrets should be limited to Particularly, access to the shared secrets should be limited to
programs and processes required by the validation system only. We programs and processes required by the validation system only. We
will not elaborate on the different security mechanisms to put in will not elaborate on the different security mechanisms to put in
place, but obviously, the protection of shared secrets is of the place, but obviously, the protection of shared secrets is of the
uttermost importance. uttermost importance.
7. HOTP Algorithm Security: Overview 8. Composite Shared Secrets
The conclusion of the security analysis detailed in the Appendix It may be desirable to include additional authentication factors in
section is that, for all practical purposes, the outputs of the the shared secret K. These additional factors can consist of any
dynamic truncation (DT) on distinct counter inputs are uniformly data known at the token but not easily obtained by others. Examples
and independently distributed 31-bit strings. of such data include:
The security analysis then details the impact of the conversion * PIN or Password obtained as user input at the token
from a string to an integer and the final reduction modulo * Phone number
10^Digit, where Digit is the number of digits in an HOTP value. * Any unique identifier programmatically available at the token
The analysis demonstrates that these final steps introduce a In this scenario, the composite shared secret K is constructed during
negligible bias, which does not impact the security of the HOTP the provisioning process from a random seed value combined with one
algorithm, in the sense that the best possible attack against the or more additional authentication factors. The server could either
HOTP function is the brute force attack. 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.
Assuming an adversary is able to observe numerous protocol The use of composite shared secrets can strengthen HOTP-based
exchanges and collect sequences of successful authentication authentication systems through the inclusion of additional
values. This adversary, trying to build a function F to generate authentication factors at the token. To the extent that the token is
HOTP values based on his observations, will not have a significant a trusted device, this approach has the further benefit of not
advantage over a random guess. requiring exposure of the authentication factors (such as the user
input PIN) to other devices.
The logical conclusion is simply that is best strategy will once 9. Bi-Directional Authentication
again be to perform a brute force attack to enumerate and try all
the possible values.
Considering the security analysis in the Appendix section of this Interestingly enough, the HOTP client could also be used to
document, without loss of generality, we can approximate closely authenticate the validation server, claiming that it is a genuine
the security of the HOTP algorithm by the following formula: entity knowing the shared secret.
Sec = sv/10^Digit 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.
Where: Obviously, as indicated previously, all the OTP communications have
- Sec is the probability of success of the adversary to take place over a secure channel, e.g., SSL/TLS, IPsec
- s stands for the look-ahead synchronization window size; connections.
- v stands for the number of verification attempts;
- Digit stands for the number of digits in HOTP values.
Obviously, we can play with s, T (the Throttling parameter that 10. Conclusion
would limit the number of attempts by an attacker) and Digit until
achieving a certain level of security, still preserving the system
usability.
8. Composite Shared Secrets 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.
It may be desirable to include additional authentication factors in The document also exhibits elements of security and demonstrates that
the shared secret K. These additional factors can consist of any the HOTP algorithm is practical and sound, the best possible attack
data known at the token but not easily obtained by others. Examples being a brute force attack that can be prevented by careful
of such data include: implementation of countermeasures in the validation server.
* 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 Eventually, several enhancements have been proposed, in order to
during the provisioning process from a random seed value combined improve security if needed for specific applications.
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 11. Acknowledgements
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. IANA Considerations 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.
This document has no actions for IANA. 12. Contributors
10. Conclusion The authors of this document would like to emphasize the role of
three persons who have made a key contribution to this document:
This draft describes HOTP, a HMAC-based One-Time Password - Laszlo Elteto is system architect with SafeNet, Inc.
algorithm. It also recommends the preferred implementation and
related modes of operations for deploying the algorithm.
The draft also exhibits elements of security and demonstrates that - Ernesto Frutos is director of Engineering with Authenex, Inc.
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 - Fred McClain is Founder and CTO with Boojum Mobile, Inc.
improve security if needed for specific applications.
11. Acknowledgements Without their advice and valuable inputs, this document would not be
the same.
The authors would like to thank Siddharth Bajaj, Alex Deacon, Loren 13. References
Hart and Nico Popp for their help during the conception and
redaction of this document.
12. Contributors 13.1. Normative References
The authors of this draft 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. [BCK1] M. Bellare, R. Canetti and H. Krawczyk, "Keyed Hash
Functions and Message Authentication", Proceedings of
Crypto'96, LNCS Vol. 1109, pp. 1-15.
- Ernesto Frutos is director of Engineering with Authenex, Inc. [BCK2] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
Hashing for Message Authentication", RFC 2104, February
1997.
- Fred McClain is Founder and CTO with Boojum Mobile, Inc. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
Without their advice and valuable inputs, this draft would not be [RFC3979] Bradner, S., "Intellectual Property Rights in IETF
the same. Technology", BCP 79, RFC 3979, March 2005.
13. References [RFC4086] Eastlake, D., 3rd, Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106, RFC 4086,
June 2005.
12.1 Normative 13.2. Informative References
[BCK1] M. Bellare, R. Canetti and H. Krawczyk, "Keyed Hash [OATH] Initiative for Open AuTHentication
Functions and Message Authentication", Proceedings of http://www.openauthentication.org
Crypto'96, LNCS Vol. 1109, pp. 1-15.
[BCK2] M. Bellare, R. Canetti and H. Krawczyk, "HMAC: [PrOo] B. Preneel and P. van Oorschot, "MD-x MAC and building
Keyed-Hashing for Message Authentication", IETF Network fast MACs from hash functions", Advances in Cryptology
Working Group, RFC 2104, February 1997. CRYPTO '95, Lecture Notes in Computer Science Vol. 963, D.
Coppersmith ed., Springer-Verlag, 1995.
[RFC1750] D. Eastlake, 3rd., S. Crocker and J. Schiller, [Crack] Crack in SHA-1 code 'stuns' security gurus
"Randomness Recommendantions for Security", IETF http://www.eetimes.com/showArticle.jhtml?
Network Working Group, RFC 1750, December 2004. articleID=60402150
[RFC2119] S. Bradner, "Key words for use in RFCs to Indicate [Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005.
Requirement Levels", BCP 14, RFC 2119, March 1997. http://www.schneier.com/blog/archives/2005/02/
sha1_broken.html
[RFC3668] S. Bradner, "Intellectual Propery Rights in IETF [Res] Researchers: Digital encryption standard flawed
Technology", BCP 79, RFC 3668, February 2004. http://news.com.com/
Researchers+Digital+encryption+standard+flawed/
2100-1002-5579881.html?part=dht&tag=ntop&tag=nl.e703
12.2 Informative [Shamir] How to Share a Secret, by Adi Shamir. In Communications
of the ACM, Vol. 22, No. 11, pp. 612-613, November, 1979.
[OATH] Initiative for Open AuTHentication Appendix A - HOTP Algorithm Security: Detailed Analysis
http://www.openauthentication.org
[PrOo] B. Preneel and P. van Oorschot, "MD-x MAC and building The security analysis of the HOTP algorithm is summarized in this
fast MACs from hash functions", Advances in Cryptology section. We first detail the best attack strategies, and then
CRYPTO '95, Lecture Notes in Computer Science Vol. 963, elaborate on the security under various assumptions and the impact of
D. Coppersmith ed., Springer-Verlag, 1995. the truncation and make some recommendations regarding the number of
digits.
[Crack] Crack in SHA-1 code 'stuns' security gurus We focus this analysis on the case where Digit = 6, i.e., an HOTP
http://www.eetimes.com/showArticle.jhtml?articleID=60402150 function that produces 6-digit values, which is the bare minimum
recommended in this document.
[Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005. A.1. Definitions and Notations
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
[Res] Researchers: Digital encryption standard flawed We denote by {0,1}^l the set of all strings of length l.
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 Let Z_{n} = {0,.., n - 1}.
of the ACM, Vol. 22, No. 11, pp. 612-613, November, 1979.
14. Authors' Addresses Let IntDiv(a,b) denote the integer division algorithm that takes
input integers a, b where a >= b >= 1 and returns integers (q,r)
Primary point of contact (for sending comments and question): the quotient and remainder, respectively, of the division of a by b.
(Thus, a = bq + r and 0 <= r < b.)
David M'Raihi Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that takes
VeriSign, Inc. a k-bit key K and c-bit counter C and returns an n-bit output H(K,C).
685 E. Middlefield Road Phone: 1-650-426-3832 (In the case of HOTP, H is HMAC-SHA-1; we use this formal definition
Mountain View, CA 94043 USA Email: dmraihi@verisign.com for generalizing our proof of security.)
Other Authors' contact information: A.2. The Idealized Algorithm: HOTP-IDEAL
Mihir Bellare We now define an idealized counterpart of the HOTP algorithm. In
Dept of Computer Science and Engineering, Mail Code 0114 this algorithm, the role of H is played by a random function that
University of California at San Diego forms the key.
9500 Gilman Drive
La Jolla, CA 92093, USA Email: mihir@cs.ucsd.edu
Frank Hoornaert To be more precise, let Maps(c,n) denote the set of all functions
VASCO Data Security, Inc. mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key
Koningin Astridlaan 164 space Maps(c,n), so that a "key" for such an algorithm is a function
1780 Wemmel, Belgium Email: frh@vasco.com 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?
David Naccache Our security analysis will show that as long as H satisfies a certain
Gemplus Innovation well-accepted assumption, the security of the actual and idealized
34 rue Guynemer, 92447, algorithms is for all practical purposes the same. The task that
Issy les Moulineaux, France Email: david.naccache@gemplus.com really faces us, then, is to assess the security of the idealized
and algorithm.
Information Security Group,
Royal Holloway,
University of London, Egham,
Surrey TW20 0EX, UK Email: david.naccache@rhul.ac.uk
Ohad Ranen In analyzing the idealized algorithm, we are concentrating on
Aladdin Knowledge Systems Ltd. assessing the quality of the design of the algorithm itself,
15 Beit Oved Street independently of HMAC-SHA-1. This is in fact the important issue.
Tel Aviv, Israel 61110 Email: Ohad.Ranen@ealaddin.com
15. Full Copyright Statement A.3. Model of Security
Copyright (C) The Internet Society (2005). 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.
This document is subject to the rights, licenses and restrictions The scenario we are considering is that a user and server share a key
contained in BCP 78, and except as set forth therein, the authors K for ALG. Both maintain a counter C, initially zero, and the user
retain all their rights. authenticates itself by sending ALG(K,C) to the server. The latter
accepts if this value is correct.
This document and the information contained herein are provided on In order to protect against accidental increment of the user counter,
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE the server, upon receiving a value z, will accept as long as z equals
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND ALG(K,i) for some i in the range C,...,C + s-1, where s is the
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, resynchronization parameter and C is the server counter. If it
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT accepts with some value of i, it then increments its counter to i+1.
THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR If it does not accept, it does not change its counter value.
ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
PARTICULAR PURPOSE.
16. Intellectual Property 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 IETF takes no position regarding the validity or scope of any The formal adversary, which we denote by B, starts out knowing which
Intellectual Property Rights or other rights that might be claimed algorithm ALG is being used, knowing the system design, and knowing
to pertain to the implementation or use of the technology described all system parameters. The one and only thing it is not given a
in this document or the extent to which any license under such priori is the key K shared between the user and the server.
rights might or might not be available; nor does it represent that
it has made any independent effort to identify any such rights.
Information on the procedures with respect to rights in RFC
documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any The model gives B full control of the scheduling of events. It has
assurances of licenses to be made available, or the result of an access to an authenticator oracle representing the user. By calling
attempt made to obtain a general license or permission for the use this oracle, the adversary can ask the user to authenticate itself
of such proprietary rights by implementers or users of this and get back the authenticator in return. It can call this oracle as
specification can be obtained from the IETF on-line IPR repository often as it wants and when it wants, using the authenticators it
at http://www.ietf.org/ipr. 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.
The IETF invites any interested party to bring to its attention any Consider the following game involving an adversary B that is
copyrights, patents or patent applications, or other proprietary attempting to compromise the security of an authentication algorithm
rights that may cover technology that may be required to implement ALG: K x {0,1}^c --> R.
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Appendix A - HOTP Algorithm Security: Detailed Analysis 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.
The security analysis of the HOTP algorithm is summarized in this Game execution - Adversary B is provided with the two following
section. We first detail the best attack strategies, and then oracles:
elaborate on the security under various assumptions, the impact of
the truncation and some recommendations regarding the number of
digits.
We focus this analysis on the case where Digit = 6, i.e. an HOTP Oracle AuthO()
function that produces 6-digit values, which is the bare minimum --------------
recommended in this draft. A = ALG(K,C)
C = C + 1
Return O to B
A.1 Definitions and Notations 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
We denote by {0,1}^l the set of all strings of length l. AuthO() is the authenticator oracle and VerO(A) is the verification
oracle.
Let Z_{n} = {0,.., n - 1}. 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.
Let IntDiv(a,b) denote the integer division algorithm that takes Our goal is to assess how large this value can be as a function of
the quotient and remainder, respectively, of the division of a by the number v of verification queries made by B, the number a of
b. (Thus a = bq + r and 0 <= r < b.) 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.
Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that A.4. Security of the Ideal Authentication Algorithm
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 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.
We now define an idealized counterpart of the HOTP algorithm. In A.4.1. From Bits to Digits
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 The dynamic offset truncation of a random n-bit string yields a
mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key random 31-bit string. What happens to the distribution when it is
space Maps(c,n), so that a "key" for such an algorithm is a taken modulo m = 10^Digit, as done in HOTP?
function h from {0,1}^c to {0,1}^n. We imagine this key (function) The following lemma estimates the biases in the outputs in this case.
to be drawn at random. It is not feasible to implement this
idealized algorithm, since the key, being a function from is way
too large to even store. So why consider it?
Our security analysis will show that as long as H satisfies a Lemma 1
certain well-accepted assumption, the security of the actual and -------
idealized algorithms is for all practical purposes the same. The Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in
task that really faces us, then, is to assess the security of the Z_{m} let:
idealized algorithm.
In analyzing the idealized algorithm, we are concentrating on P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}]
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 Then for any z in Z_{m}
The model exhibits the type of threats or attacks that are being P_{N,m}(z) = (q + 1) / N if 0 <= z < r
considered and enables to asses the security of HOTP and q / N if r <= z < m
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 Proof of Lemma 1
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 Let the random variable X be uniformly distributed over Z_{N}. Then:
latter accepts if this value is correct.
In order to protect against accidental increment of the user P_{N,m}(z) = Pr [X mod m = z]
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 = Pr [X < mq] * Pr [X mod m = z| X < mq]
to be able to eavesdrop, meaning see the authenticator transmitted + Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N]
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 = mq/N * 1/m +
which algorithm ALG is being used, knowing the system design and (N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq
knowing all system parameters. The one and only thing it is not 0 if N - mq <= z <= m
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 = q/N +
access to an authenticator oracle representing the user. By calling r/N * 1 / r if 0 <= z < N - mq
this oracle, the adversary can ask the user to authenticate itself 0 if r <= z <= m
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 Simplifying yields the claimed equation.
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 Let N = 2^31, d = 6, and m = 10^d. If x is chosen at random from
is initialized to 0, and the Boolean value win is set to false. 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.
Game execution - Adversary B is provided with the two following Rather, x mod m is distributed as shown in the following table:
oracles:
Oracle AuthO() Values Probability that each appears as output
-------------- ----------------------------------------------------------------
A = ALG(K,C) 0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6
C = C + 1 483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6
Return O to B
Oracle VerO(A) If X is uniformly distributed over Z_{2^31} (meaning, is a random
-------------- 31-bit string), then the above shows the probabilities for different
i = C outputs of X mod 10^6. The first set of values appears with
While (i <= C + s - 1 and Win == FALSE) do probability slightly greater than 10^-6, the rest with probability
If A == ALG(K,i) then Win = TRUE; C = i + 1 slightly less, meaning that the distribution is slightly non-uniform.
Else i = i + 1
Return Win to B
AuthO() is the authenticator oracle and VerO(A) is the verification However, as the table above indicates, the bias is small, and as we
oracle. will see later, negligible: the probabilities are very close to
10^-6.
Upon execution, B queries the two oracles at will. Let Adv(B) be A.4.2. Brute Force Attacks
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 If the authenticator consisted of d random digits, then a brute force
the number v of verification queries made by B, the number a of attack using v verification attempts would succeed with probability
authenticator oracle queries made by B, and the running time t of sv/10^Digit.
B. This will tell us how to set the throttle, which effectively
upper bounds v.
A.4 Security of the ideal authentication algorithm However, an adversary can exploit the bias in the outputs of
HOTP-IDEAL, predicted by Lemma 1, to mount a slightly better attack.
This section summarizes the security analysis of HOTP-IDEAL, Namely, it makes authentication attempts with authenticators that are
starting with the impact of the conversion modulo 10^Digit and the most likely values, meaning the ones in the range 0,...,r - 1,
then, focusing on the different possible attacks. where (q,r) = IntDiv(2^31,10^Digit).
A.4.1 From bits to digits 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.
The dynamic offset truncation of a random n-bit string yields a For simplicity, we assume that the number of verification queries is
random 31-bit string. What happens to the distribution when it is at most r. With N = 2^31 and m = 10^6, we have r = 483,648, and the
taken modulo m = 10^Digit, as done in HOTP? throttle value is certainly less than this, so this assumption is not
much of a restriction.
The following lemma estimates the biases in the outputs in this Proposition 1
case. -------------
Lemma 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
Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in <= r verification oracle queries. This adversary makes no
Z_{m} let: authenticator oracle queries, and succeeds with probability
P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}] Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s
Then for any z in Z_{m} which is roughly equal to
P_{N,m}(z) = (q + 1) / N if 0 <= z < r sv * (q+1)/2^31
q / N if r <= z < m
Proof of Lemma 1 With m = 10^6 we get q = 2,147. In that case, the brute force attack
---------------- using v verification attempts succeeds with probability
Let the random variable X be uniformly distributed over Z_{N}.
Then:
P_{N,m}(z) = Pr [X mod m = z] Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6
= Pr [X < mq] * Pr [X mod m = z| X < mq] As this equation shows, the resynchronization parameter s has a
+ Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N] 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.
= mq/N * 1/m + A.4.3. Brute force attacks are the best possible attacks.
(N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq
0 if N - mq <= z <= m
= q/N + A central question is whether there are attacks any better than the
r/N * 1 / r if 0 <= z < N - mq brute force one. In particular, the brute force attack did not
0 if r <= z <= m attempt to collect authenticators sent by the user and try to
Let N = 2^31, d = 6 and m = 10^d. If x is chosen at random from cryptanalyze them in an attempt to learn how to better construct
Z_{N} (meaning, is a random 31-bit string), then reducing it to a authenticators. Would doing this help? Is there some way to "learn"
6-digit number by taking x mod m does not yield a random 6-digit how to build authenticators that result in a higher success rate than
number. given by the brute-force attack?
Rather, x mod m is distributed as shown in the following table: 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.
Values Probability that each appears as output Proposition 2 ------------- Suppose m = 10^Digit < 2^31, and let
---------------------------------------------------------------- (q,r) = IntDiv(2^31,m). Let B be any adversary attacking HOTP-IDEAL
0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6 using v verification oracle queries and a <= 2^c - s authenticator
483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6 oracle queries. Then
If X is uniformly distributed over Z_{2^31} (meaning is a random Adv(B) < = sv * (q+1)/ 2^31
31-bit string) then the above shows the probabilities for different
outputs of X mod 10^6. The first set of values appear with
probability slightly greater than 10^-6, the rest with probability
slightly less, meaning the distribution is slightly non-uniform.
However, as the Figure indicates, the bias is small and as we will Note: This result is conditional on the adversary not seeing more
see later, negligible: the probabilities are very close to 10^-6. than 2^c - s authentications performed by the user, which is hardly
restrictive as long as c is large enough.
A.4.2 Brute force attacks 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
If the authenticator consisted of d random digits, then a brute Equation 1
force attack using v verification attempts would succeed with ----------
probability sv/10^Digit. sv * 2148/2^31 roughly = sv * 1.00024045/10^6
However, an adversary can exploit the bias in the outputs of HOTP- Meaning, B's success rate is not more than that achieved by the brute
IDEAL, predicted by Lemma 1, to mount a slightly better attack. force attack.
Namely, it makes authentication attempts with authenticators which A.5. Security Analysis of HOTP
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 We have analyzed, in the previous sections, the security of the
mounts the attack. It estimates the success probability as a idealized counterparts HOTP-IDEAL of the actual authentication
function of the number of verification queries. 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.
For simplicity, we assume the number of verification queries is at The assumption in question is that H is a secure pseudorandom
most r. With N = 2^31 and m = 10^6 we have r = 483,648, and the function, or PRF, meaning that its input-output values are
throttle value is certainly less than this, so this assumption is indistinguishable from those of a random function in practice.
not much of a restriction.
Proposition 1 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)
Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume as the prf-advantage of A, which represents how well the adversary
s <= m. The brute-force attack adversary B-bf attacks HOTP using v does at distinguishing the case where its oracle is H(K,.) from the
<= r verification oracle queries. This adversary makes no case where its oracle is a random function of {0,1}^c to {0,1}^n.
authenticator oracle queries, and succeeds with probability
Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s One possible attack is based on exhaustive search for the key K. If
which is roughly equals to 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.
Another possible attack is a birthday one [PrOo], whereby A can
attain advantage p^2/2^n in p oracle queries and running time about
pT.
sv * (q+1)/2^31 Our assumption is that these are the best possible attacks. This
translates into the following.
With m = 10^6 we get q = 2,147. In that case, the brute force Assumption 1
attack using v verification attempts succeeds with probability ------------
Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6 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 oracle
queries,
As this equation shows, the resynchronization parameter s has a Adv(A) <= (t/T)/2^k + p^2/2^n
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 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
and making 2^40 oracle queries has advantage at most (about) 2^-80.
A central question is whether there are attacks any better than the Theorem 1
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 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B
what strategy the adversary uses, and even if it sees, and tries to be any adversary attacking HOTP using v verification oracle queries,
exploit, the authenticators from authentication attempts of the a <= 2^c - s authenticator oracle queries, and running time t. Let T
user, its success probability will not be above that of the brute denote the time to perform one computation of H. If Assumption 1 is
force attack - this is true as long as the number of true, then
authentications it observes is not incredibly large. This is
valuable information regarding the security of the scheme.
Proposition 2 Adv(B) <= sv * (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n
-------------
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 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
practical purposes the success rate of an adversary attacking 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 counterpart.
Note: This result is conditional on the adversary not seeing more In the case m = 10^6 of a 6-digit output, this means that an
than 2^c - s authentications performed by the user, which is hardly adversary making v authentication attempts will have a success rate
restrictive as long as c is large enough. that is at most that of Equation 1.
With m = 10^6 we get q = 2,147. In that case, Proposition 2 says For example, consider an adversary with running time at most 2^60
that any adversary B attacking HOTP-IDEAL and making v verification that sees at most 2^40 authentication attempts of the user. Both
attempts succeeds with probability at most these choices are very generous to the adversary, who will typically
not have these resources, but we are saying that even such a powerful
adversary will not have more success than indicated by Equation 1.
Equation 1 We can safely assume sv <= 2^40 due to the throttling and bounds on
---------- s. So:
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 (t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160
roughly <= 2^-78
We have analyzed in the previous sections, the security of the which is much smaller than the success probability of Equation 1 and
idealized counterparts HOTP-IDEAL of the actual authentication negligible compared to it.
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 Appendix B - SHA-1 Attacks
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: This sections addresses the impact of the recent attacks on SHA-1 on
{0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A) the security of the HMAC-SHA-1-based HOTP. We begin with some
as the prf-advantage of A, which represents how well the adversary discussion of the situation of SHA-1 and then discuss the relevance
does at distinguishing the case where its oracle is H(K,.) from the to HMAC-SHA-1 and HOTP. Cited references are in Section 13.
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 B.1. SHA-1 Status
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 . Another possible attack is a birthday one [PrOo],
whereby A can attain advantage p^2/2^n in p oracle queries and
running time about pT.
Our assumption is that these are the best possible attacks. This A collision for a hash function h means a pair x,y of different
translates into the following. inputs such that h(x)=h(y). Since SHA-1 outputs 160 bits, a birthday
attack finds a collision in 2^{80} trials. (A trial means one
computation of the function.) This was thought to be the best
possible until Wang, Yin, and Yu announced on February 15, 2005, that
they had an attack finding collisions in 2^{69} trials.
Assumption 1 Is SHA-1 broken? For most practical purposes, we would say probably
------------ not, since the resources needed to mount the attack are huge. Here
is one way to get a sense of it: we can estimate it is about the same
as the time we would need to factor a 760-bit RSA modulus, and this
is currently considered out of reach.
Let T denotes the time to perform one computation of H. Then if A Burr of NIST is quoted in [Crack] as saying "Large national
is any adversary with running time at most t and making at most p intelligence agencies could do this in a reasonable amount of time
oracle queries, with a few million dollars in computer time". However, the
computation may be out of reach of all but such well-funded agencies.
Adv(A) <= (t/T)/2^k + p^2/2^n One should also ask what impact finding SHA-1 collisions actually has
on security of real applications such as signatures. To exploit a
collision x,y to forge signatures, you need to somehow obtain a
signature of x and then you can forge a signature of y. How damaging
this is depends on the content of y: the y created by the attack may
not be meaningful in the application context. Also, one needs a
chosen-message attack to get the signature of x. This seems possible
in some contexts, but not others. Overall, it is not clear that the
impact on the security of signatures is significant.
In practice this assumption means that H is very secure as PRF. For Indeed, one can read in the press that SHA-1 is "broken" [Sha1] and
example, given that k = n = 160, an attacker with running time 2^60 that encryption and SSL are "broken" [Res]. The media have a
and making 2^40 oracle queries has advantage at most (about) 2^-80. tendency to magnify events: it would hardly be interesting to
announce in the news that a team of cryptanalysts did very
interesting theoretical work in attacking SHA-1.
Theorem 1 Cryptographers are excited too. But mainly because this is an
--------- important theoretical breakthrough. Attacks can only get better with
Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B time: it is therefore important to monitor any progress in hash
be any adversary attacking HOTP using v verification oracle functions cryptanalysis and be prepared for any really practical
queries, a <= 2^c - s authenticator oracle queries, and running break with a sound migration plan for the future.
time t. Let T denote the time to perform one computation of H. If
Assumption 1 is true then
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 B.2. HMAC-SHA-1 Status
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
is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP
algorithm is in practice essentially as good as its idealized
counterpart.
In the case m = 10^6 of a 6-digit output this means that an The new attacks on SHA-1 have no impact on the security of
adversary making v authentication attempts will have a success rate HMAC-SHA-1. The best attack on the latter remains one needing a
that is at most that of Equation 1. sender to authenticate 2^{80} messages before an adversary can create
a forgery. Why?
For example, consider an adversary with running time at most 2^60 HMAC is not a hash function. It is a message authentication code
that sees at most 2^40 authentication attempts of the user. Both (MAC) that uses a hash function internally. A MAC depends on a
these choices are very generous to the adversary, who will secret key, while hash functions don't. What one needs to worry
typically not have these resources, but we are saying that even about with a MAC is forgery, not collisions. HMAC was designed so
such a powerful adversary will not have more success than indicated that collisions in the hash function (here SHA-1) do not yield
by Equation 1. forgeries for HMAC.
We can safely assume sv <= 2^40 due to the throttling and bounds on Recall that HMAC-SHA-1(K,x) = SHA-1(K_o,SHA-1(K_i,x)) where the keys
s. So: K_o,K_i are derived from K. Suppose the attacker finds a pair x,y
(t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160 such that SHA-1(K_i,x) = SHA-1(K_i,y). (Call this a hidden-key
roughly <= 2^-78 collision.) Then if it can obtain the MAC of x (itself a tall
order), it can forge the MAC of y. (These values are the same.) But
finding hidden-key collisions is harder than finding collisions,
because the attacker does not know the hidden key K_i. All it may
have is some outputs of HMAC-SHA-1 with key K. To date, there are no
claims or evidence that the recent attacks on SHA-1 extend to find
hidden-key collisions.
which is much smaller than the success probability of Equation 1 Historically, the HMAC design has already proven itself in this
and negligible compared to it. regard. MD5 is considered broken in that collisions in this hash
function can be found relatively easily. But there is still no
attack on HMAC-MD5 better than the trivial 2^{64} time birthday one.
(MD5 outputs 128 bits, not 160.) We are seeing this strength of HMAC
coming into play again in the SHA-1 context.
Appendix B - SHA-1 Attacks B.3. HOTP Status
This sections addresses the impact of the recent attacks on SHA-1 Since no new weakness has surfaced in HMAC-SHA-1, there is no impact
on the security of the HMAC-SHA-1 based HOTP. We begin with some on HOTP. The best attacks on HOTP remain those described in the
discussion of the situation of SHA-1 and then discuss the relevance document, namely, to try to guess output values.
to HMAC-SHA-1 and HOTP. Cited references are at the bottom of the
document.
B.1 SHA-1 status The security proof of HOTP requires that HMAC-SHA-1 behave like a
pseudorandom function. The quality of HMAC-SHA-1 as a pseudorandom
function is not impacted by the new attacks on SHA-1, and so neither
is this proven guarantee.
A collision for a hash function h means a pair x,y of different Appendix C - HOTP Algorithm: Reference Implementation
inputs such that h(x)=h(y). Since SHA-1 outputs 160 bits, a
birthday attack finds a collision in 2^{80} trials. (A trial means
one computation of the function.) This was thought to be the best
possible until Wang, Yin and Yu announced on February 15, 2005 that
they had an attack finding collisions in 2^{69} trials.
Is SHA-1 broken? For most practical purposes we would say probably /*
not, since the resources needed to mount the attack are huge. Here * OneTimePasswordAlgorithm.java
is one way to get a sense of it: we can estimate it is about the * OATH Initiative,
same as the time we would need to factor a 760-bit RSA modulus, and * HOTP one-time password algorithm
this is currently considered out of reach. *
*/
Burr of NIST is quoted [Crack] as saying ``Large national /* Copyright (C) 2004, OATH. All rights reserved.
intelligence agencies could do this in a reasonable amount of time *
with a few million dollars in computer time.'' However, the * License to copy and use this software is granted provided that it
computation may be out of reach of all but such well-funded * is identified as the "OATH HOTP Algorithm" in all material
agencies. * mentioning or referencing this software or this function.
*
* License is also granted to make and use derivative works provided
* that such works are identified as
* "derived from OATH HOTP algorithm"
* in all material mentioning or referencing the derived work.
*
* OATH (Open AuTHentication) and its members make no
* representations concerning either the merchantability of this
* software or the suitability of this software for any particular
* purpose.
*
* It is provided "as is" without express or implied warranty
* of any kind and OATH AND ITS MEMBERS EXPRESSaLY DISCLAIMS
* ANY WARRANTY OR LIABILITY OF ANY KIND relating to this software.
*
* These notices must be retained in any copies of any part of this
* documentation and/or software.
*/
One should also ask what impact finding SHA-1 collisions actually package org.openauthentication.otp;
has on security of real applications such as signatures. To exploit
a collision x,y to forge signatures, you need to somehow obtain a
signature of x and then you can forge a signature of y. How
damaging this is depends on the content of y: the y created by the
attack may not be meaningful in the application context. Also, one
needs a chosen-message attack to get the signature of x. This seems
possible in some contexts, but not others. Overall, it is not clear
the impact on the security of signatures is significant.
Indeed, one can read that SHA-1 is ``broken,'' [Sha1], that import java.io.IOException;
encryption and SSL are ``broken'' [Res], in the press. The media import java.io.File;
have a tendency to magnify events: it would hardly be interesting import java.io.DataInputStream;
to announce in the news that a team of cryptanalysts did very import java.io.FileInputStream ;
interesting theoretical work in attacking SHA-1. import java.lang.reflect.UndeclaredThrowableException;
Cryptographers are excited too. But mainly because this is an import java.security.GeneralSecurityException;
important theoretical breakthrough. Attacks can only get beter with import java.security.NoSuchAlgorithmException;
time: it is therefore important to monitor any progress in hash import java.security.InvalidKeyException;
functions cryptanalysis and be prepared for any really practical
break with a sound migration plan for the future.
B.2 HMAC-SHA-1 status import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
/**
* This class contains static methods that are used to calculate the
* One-Time Password (OTP) using
* JCE to provide the HMAC-SHA-1.
*
* @author Loren Hart
* @version 1.0
*/
public class OneTimePasswordAlgorithm {
private OneTimePasswordAlgorithm() {}
The new attacks on SHA-1 have no impact on the security of HMAC- // These are used to calculate the check-sum digits.
SHA-1. The best attack on the latter remains one needing a sender // 0 1 2 3 4 5 6 7 8 9
to authenticate 2^{80} messages before an adversary can create a private static final int[] doubleDigits =
forgery. Why? { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
HMAC is not a hash function. It is a message authentication code /**
(MAC) that uses a hash function internally. A MAC depends on a * Calculates the checksum using the credit card algorithm.
secret key, while hash functions don't. What one needs to worry * This algorithm has the advantage that it detects any single
about with a MAC is forgery, not collisions. HMAC was designed so * mistyped digit and any single transposition of
that collisions in the hash function (here SHA-1) do not yield * adjacent digits.
forgeries for HMAC. *
* @param num the number to calculate the checksum for
* @param digits number of significant places in the number
*
* @return the checksum of num
*/
public static int calcChecksum(long num, int digits) {
boolean doubleDigit = true;
int total = 0;
while (0 < digits--) {
int digit = (int) (num % 10);
num /= 10;
if (doubleDigit) {
digit = doubleDigits[digit];
}
total += digit;
doubleDigit = !doubleDigit;
}
int result = total % 10;
if (result > 0) {
result = 10 - result;
}
return result;
}
Recall that HMAC-SHA-1(K,x) = SHA-1(K_o,SHA-1(K_i,x)) where the /**
keys K_o,K_i are derived from K. Suppose the attacker finds a pair * This method uses the JCE to provide the HMAC-SHA-1
x,y such that SHA-1(K_i,x)=SHA-1(K_i,y). (Call this a hidden-key * algorithm.
collision.) Then if it can obtain the MAC of x (itself a tall * HMAC computes a Hashed Message Authentication Code and
order), it can forge the MAC of y. (These values are the same.) But * in this case SHA1 is the hash algorithm used.
finding hidden-key collisions is harder than finding collisions, *
because the attacker does not know the hidden key K_i. All it may * @param keyBytes the bytes to use for the HMAC-SHA-1 key
have is some outputs of HMAC-SHA-1 with key K. To date there are no * @param text the message or text to be authenticated.
claims or evidence that the recent attacks on SHA-1 extend to find *
hidden-key collisions. * @throws NoSuchAlgorithmException if no provider makes
* either HmacSHA1 or HMAC-SHA-1
* digest algorithms available.
* @throws InvalidKeyException
* The secret provided was not a valid HMAC-SHA-1 key.
*
*/
Historically, the HMAC design has already proven itself in this public static byte[] hmac_sha1(byte[] keyBytes, byte[] text)
regard. MD5 is considered broken in that collisions in this hash throws NoSuchAlgorithmException, InvalidKeyException
function can be found relatively easily. But there is still no {
attack on HMAC-MD5 better than the trivial 2^{64} time birthday // try {
one. (MD5 outputs 128 bits, not 160.) We are seeing this strength Mac hmacSha1;
of HMAC coming into play again in the SHA-1 context. try {
hmacSha1 = Mac.getInstance("HmacSHA1");
} catch (NoSuchAlgorithmException nsae) {
hmacSha1 = Mac.getInstance("HMAC-SHA-1");
}
SecretKeySpec macKey =
new SecretKeySpec(keyBytes, "RAW");
hmacSha1.init(macKey);
return hmacSha1.doFinal(text);
// } catch (GeneralSecurityException gse) {
// throw new UndeclaredThrowableException(gse);
// }
}
B.3 HOTP status private static final int[] DIGITS_POWER
// 0 1 2 3 4 5 6 7 8
= {1,10,100,1000,10000,100000,1000000,10000000,100000000};
Since no new weakness has surfaced in HMAC-SHA-1, there is no /**
impact on HOTP. The best attacks on HOTP remain those described in * This method generates an OTP value for the given
the document, namely to try to guess output values. * set of parameters.
*
* @param secret the shared secret
* @param movingFactor the counter, time, or other value that
* changes on a per use basis.
* @param codeDigits the number of digits in the OTP, not
* including the checksum, if any.
* @param addChecksum a flag that indicates if a checksum digit
* should be appended to the OTP.
* @param truncationOffset the offset into the MAC result to
* begin truncation. If this value is out of
* the range of 0 ... 15, then dynamic
* truncation will be used.
* Dynamic truncation is when the last 4
* bits of the last byte of the MAC are
* used to determine the start offset.
* @throws NoSuchAlgorithmException if no provider makes
* either HmacSHA1 or HMAC-SHA-1
* digest algorithms available.
* @throws InvalidKeyException
* The secret provided was not
* a valid HMAC-SHA-1 key.
*
* @return A numeric String in base 10 that includes
* {@link codeDigits} digits plus the optional checksum
* digit if requested.
*/
static public String generateOTP(byte[] secret,
long movingFactor,
int codeDigits,
boolean addChecksum,
int truncationOffset)
throws NoSuchAlgorithmException, InvalidKeyException
{
// put movingFactor value into text byte array
String result = null;
int digits = addChecksum ? (codeDigits + 1) : codeDigits;
byte[] text = new byte[8];
for (int i = text.length - 1; i >= 0; i--) {
text[i] = (byte) (movingFactor & 0xff);
movingFactor >>= 8;
}
The security proof of HOTP requires that HMAC-SHA-1 behave like a // compute hmac hash
pseudorandom function. The quality of HMAC-SHA-1 as a pseudorandom byte[] hash = hmac_sha1(secret, text);
function is not impacted by the new attacks on SHA-1, and so
neither is this proven guarantee.
Appendix C - HOTP Algorithm: Reference Implementation // put selected bytes into result int
int offset = hash[hash.length - 1] & 0xf;
if ( (0<=truncationOffset) &&
(truncationOffset<(hash.length-4)) ) {
offset = truncationOffset;
}
int binary =
((hash[offset] & 0x7f) << 24)
| ((hash[offset + 1] & 0xff) << 16)
| ((hash[offset + 2] & 0xff) << 8)
| (hash[offset + 3] & 0xff);
/* int otp = binary % DIGITS_POWER[codeDigits];
* OneTimePasswordAlgorithm.java if (addChecksum) {
* OATH Initiative, otp = (otp * 10) + calcChecksum(otp, codeDigits);
* HOTP one-time password algorithm }
* result = Integer.toString(otp);
*/ while (result.length() < digits) {
result = "0" + result;
}
return result;
}
}
/* Copyright (C) 2004, OATH. All rights reserved. Appendix D - HOTP Algorithm: Test Values
*
* License to copy and use this software is granted provided that it
* is identified as the "OATH HOTP Algorithm" in all material
* mentioning or referencing this software or this function.
*
* License is also granted to make and use derivative works provided
* that such works are identified as
* "derived from OATH HOTP algorithm"
* in all material mentioning or referencing the derived work.
*
* OATH (Open AuTHentication) and its members make no
* representations concerning either the merchantability of this
* software or the suitability of this software for any particular
* purpose.
*
* It is provided "as is" without express or implied warranty
* of any kind and OATH AND ITS MEMBERS EXPRESSELY DISCLAIMS
* ANY WARRANTY OR LIABILITY OF ANY KIND relating to this software.
*
* These notices must be retained in any copies of any part of this
* documentation and/or software.
*/
import java.io.IOException;
import java.io.File;
import java.io.DataInputStream;
import java.io.FileInputStream ;
import java.lang.reflect.UndeclaredThrowableException;
import java.security.GeneralSecurityException; The following test data uses the ASCII string
import java.security.NoSuchAlgorithmException; "12345678901234567890" for the secret:
import java.security.InvalidKeyException;
import javax.crypto.Mac; Secret = 0x3132333435363738393031323334353637383930
import javax.crypto.spec.SecretKeySpec;
/** Table 1 details for each count, the intermediate HMAC value.
* This class contains static methods that are used to calculate the
* One-Time Password (OTP) using
* JCE to provide the HMAC-SHA1.
*
* @author Loren Hart
* @version 1.0
*/
public class OneTimePasswordAlgorithm {
private OneTimePasswordAlgorithm() {}
// These are used to calculate the check-sum digits. Count Hexadecimal HMAC-SHA-1(secret, count)
// 0 1 2 3 4 5 6 7 8 9 0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0
private static final int[] doubleDigits = 1 75a48a19d4cbe100644e8ac1397eea747a2d33ab
{ 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }; 2 0bacb7fa082fef30782211938bc1c5e70416ff44
3 66c28227d03a2d5529262ff016a1e6ef76557ece
4 a904c900a64b35909874b33e61c5938a8e15ed1c
5 a37e783d7b7233c083d4f62926c7a25f238d0316
6 bc9cd28561042c83f219324d3c607256c03272ae
7 a4fb960c0bc06e1eabb804e5b397cdc4b45596fa
8 1b3c89f65e6c9e883012052823443f048b4332db
9 1637409809a679dc698207310c8c7fc07290d9e5
/** Table 2 details for each count the truncated values (both in
* Calculates the checksum using the credit card algorithm. hexadecimal and decimal) and then the HOTP value.
* This algorithm has the advantage that it detects any single
* mistyped digit and any single transposition of
* adjacent digits.
*
* @param num the number to calculate the checksum for
* @param digits number of significant places in the number
*
* @return the checksum of num
*/
public static int calcChecksum(long num, int digits) {
boolean doubleDigit = true;
int total = 0;
while (0 < digits--) {
int digit = (int) (num % 10);
num /= 10;
if (doubleDigit) {
digit = doubleDigits[digit];
}
total += digit;
doubleDigit = !doubleDigit;
int result = total % 10;
if (result > 0) {
result = 10 - result;
}
return result;
}
/** Truncated
* This method uses the JCE to provide the HMAC-SHA1 Count Hexadecimal Decimal HOTP
* algorithm. 0 4c93cf18 1284755224 755224
* HMAC computes a Hashed Message Authentication Code and 1 41397eea 1094287082 287082
* in this case SHA1 is the hash algorithm used. 2 82fef30 137359152 359152
* 3 66ef7655 1726969429 969429
* @param keyBytes the bytes to use for the HMAC-SHA1 key 4 61c5938a 1640338314 338314
* @param text the message or text to be authenticated. 5 33c083d4 868254676 254676
* 6 7256c032 1918287922 287922
* @throws NoSuchAlgorithmException if no provider makes 7 4e5b397 82162583 162583
* either HmacSHA1 or HMAC-SHA1 8 2823443f 673399871 399871
* digest algorithms available. 9 2679dc69 645520489 520489
* @throws InvalidKeyException
* The secret provided was not a valid HMAC-SHA1 key.
*
*/
public static byte[] hmac_sha1(byte[] keyBytes, byte[] text) Appendix E - Extensions
throws NoSuchAlgorithmException, InvalidKeyException
{
// try {
Mac hmacSha1;
try {
hmacSha1 = Mac.getInstance("HmacSHA1");
} catch (NoSuchAlgorithmException nsae) {
hmacSha1 = Mac.getInstance("HMAC-SHA1");
}
SecretKeySpec macKey =
new SecretKeySpec(keyBytes, "RAW");
hmacSha1.init(macKey);
return hmacSha1.doFinal(text);
// } catch (GeneralSecurityException gse) {
// throw new UndeclaredThrowableException(gse);
// }
}
private static final int[] DIGITS_POWER We introduce in this section several enhancements to the HOTP
// 0 1 2 3 4 5 6 7 8 algorithm. These are not recommended extensions or part of the
= {1,10,100,1000,10000,100000,1000000,10000000,100000000}; standard algorithm, but merely variations that could be used for
customized implementations.
/** E.1. Number of Digits
* This method generates an OTP value for the given
* set of parameters.
*
* @param secret the shared secret
* changes on a per use basis.
* @param codeDigits the number of digits in the OTP, not
* including the checksum, if any.
* @param addChecksum a flag that indicates if a checksum digit
* should be appended to the OTP.
* @param truncationOffset the offset into the MAC result to
* begin truncation. If this value is out of
* the range of 0 ... 15, then dynamic
* truncation will be used.
* Dynamic truncation is when the last 4
* bits of the last byte of the MAC are
* used to determine the start offset.
* @throws NoSuchAlgorithmException if no provider makes
* either HmacSHA1 or HMAC-SHA1
* digest algorithms available.
* @throws InvalidKeyException
* The secret provided was not
* a valid HMAC-SHA1 key.
*
* @return A numeric String in base 10 that includes
* {@link codeDigits} digits plus the optional checksum
* digit if requested.
*/
static public String generateOTP(byte[] secret,
long movingFactor,
int codeDigits,
boolean addChecksum,
int truncationOffset)
throws NoSuchAlgorithmException, InvalidKeyException
{
// put movingFactor value into text byte array
String result = null;
int digits = addChecksum ? (codeDigits + 1) : codeDigits;
byte[] text = new byte[8];
for (int i = text.length - 1; i >= 0; i--) {
text[i] = (byte) (movingFactor & 0xff);
movingFactor >>= 8;
}
// compute hmac hash A simple enhancement in terms of security would be to extract more
byte[] hash = hmac_sha1(secret, text); digits from the HMAC-SHA-1 value.
// put selected bytes into result int For instance, calculating the HOTP value modulo 10^8 to build an 8-
int offset = hash[hash.length - 1] & 0xf; digit HOTP value would reduce the probability of success of the
if ( (0<=truncationOffset) && adversary from sv/10^6 to sv/10^8.
(truncationOffset<(hash.length-4)) ) {
offset = truncationOffset;
}
int binary =
((hash[offset] & 0x7f) << 24)
| ((hash[offset + 1] & 0xff) << 16)
| ((hash[offset + 2] & 0xff) << 8)
int otp = binary % DIGITS_POWER[codeDigits];
if (addChecksum) {
otp = (otp * 10) + calcChecksum(otp, codeDigits);
}
result = Integer.toString(otp);
while (result.length() < digits) {
result = "0" + result;
}
return result;
}
}
Appendix D - HOTP Algorithm: Test Values This could give the opportunity to improve usability, e.g., by
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
is the theoretical optimum for 6-digit code when s = 1.
The following test data uses the ASCII string E.2. Alphanumeric Values
"123456787901234567890" for the secret:
Secret = 0x3132333435363738393031323334353637383930 Another option is to use A-Z and 0-9 values; or rather a subset of 32
symbols taken from the alphanumerical alphabet in order to avoid any
confusion between characters: 0, O, and Q as well as l, 1, and I are
very similar, and can look the same on a small display.
Table 1 details for each count, the intermediate hmac value. The immediate consequence is that the security is now in the order of
sv/32^6 for a 6-digit HOTP value and sv/32^8 for an 8-digit HOTP
value.
Count Hexadecimal HMAC-SHA1(secret, count) 32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is slightly
0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0 better than a 9-digit HOTP value, which is the maximum length of an
1 75a48a19d4cbe100644e8ac1397eea747a2d33ab HOTP code supported by the proposed algorithm.
2 0bacb7fa082fef30782211938bc1c5e70416ff44
3 66c28227d03a2d5529262ff016a1e6ef76557ece
4 a904c900a64b35909874b33e61c5938a8e15ed1c
5 a37e783d7b7233c083d4f62926c7a25f238d0316
6 bc9cd28561042c83f219324d3c607256c03272ae
7 a4fb960c0bc06e1eabb804e5b397cdc4b45596fa
8 1b3c89f65e6c9e883012052823443f048b4332db
9 1637409809a679dc698207310c8c7fc07290d9e5
Table details for each count the truncated values (both in 32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is
hexadecimal and decimal) and then the HOTP value. significantly better than a 9-digit HOTP value.
Truncated Depending on the application and token/interface used for displaying
Count Hexadecimal Decimal HOTP and entering the HOTP value, the choice of alphanumeric values could
0 4c93cf18 1284755224 755224 be a simple and efficient way to improve security at a reduced cost
1 41397eea 1094287082 287082 and impact on users.
2 82fef30 137359152 359152
3 66ef7655 1726969429 969429
4 61c5938a 1640338314 338314
5 33c083d4 868254676 254676
6 7256c032 1918287922 287922
7 4e5b397 82162583 162583
8 2823443f 673399871 399871
9 2679dc69 645520489 520489
Appendix E - Extensions E.3. Sequence of HOTP Values
We introduce in this section several enhancements to the HOTP
algorithm. These are not recommended extensions or part of the
standard algorithm, but merely variations that could be used for
customized implementations.
E.1 Number of Digits 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
protocol, and add a parameter L that would define the length of the
HOTP sequence to enter.
A simple enhancement in terms of security would be to extract more Per default, the value L SHOULD be set to 1, but if security needs to
digits from the HMAC-SHA1 value. be increased, users might be asked (possibly for a short period of
time, or a specific operation) to enter L HOTP values.
For instance, calculating the HOTP value modulo 10^8 to build an This is another way, without increasing the HOTP length or using
8-digit HOTP value would reduce the probability of success of the alphanumeric values to tighten security.
adversary from sv/10^6 to sv/10^8.
This could give the opportunity to improve usability, e.g. by Note: The system MAY also be programmed to request synchronization on
increasing T and/or s, while still achieving a better security a regular basis (e.g., every night, twice a week, etc.) and to
overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which achieve this purpose, ask for a sequence of L HOTP values.
is the theoretical optimum for 6-digit code when s = 1.
E.2 Alpha-numeric Values E.4. A Counter-Based Resynchronization Method
Another option is to use A-Z and 0-9 values; or rather a subset of In this case, we assume that the client can access and send not only
32 symbols taken from the alphanumerical alphabet in order to avoid the HOTP value but also other information, more specifically, the
any confusion between characters: 0, O and Q as well as l, 1 and I counter value.
are very similar, and can look the same on a small display.
The immediate consequence is that the security is now in the order A more efficient and secure method for resynchronization is possible
of sv/32^6 for a 6-digit HOTP value and sv/32^8 for an 8-digit HOTP in this case. The client application will not send the HOTP-client
value. value only, but the HOTP-client and the related C-client counter
value, the HOTP value acting as a message authentication code of the
counter.
32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is Resynchronization Counter-based Protocol (RCP)
slightly better than a 9-digit HOTP value, which is the maximum ----------------------------------------------
length of an HOTP code supported by the proposed algorithm.
32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is The server accepts if the following are all true, where C-server is
significantly better than a 9-digit HOTP value. its own current counter value:
Depending on the application and token/interface used for 1) C-client >= C-server
displaying and entering the HOTP value, the choice of alphanumeric 2) C-client - C-server <= s
values could be a simple and efficient way to improve security at a 3) Check that HOTP client is valid HOTP(K,C-Client)
reduced cost and impact on users. 4) If true, the server sets C to C-client + 1 and client is
authenticated
E.3 Sequence of HOTP values 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
or roughly v in one million. A side benefit is obviously to be able
to increase s "infinitely" and therefore improve the system usability
without impacting the security.
As we suggested for the resynchronization to enter a short sequence This resynchronization protocol SHOULD be used whenever the related
(say 2 or 3) of HOTP values, we could generalize the concept to the impact on the client and server applications is deemed acceptable.
protocol, and add a parameter L that would define the length of the
HOTP sequence to enter.
Per default, the value L SHOULD be set to 1, but if security needs E.5. Data Field
to be increased, users might be asked (possibly for a short period
of time, or a specific operation) to enter L HOTP values.
This is another way, without increasing the HOTP length or using Another interesting option is the introduction of a Data field, which
alphanumeric values to tighten security. would be used for generating the One-Time Password values: HOTP (K,
C, [Data]) where Data is an optional field that can be the
concatenation of various pieces of identity-related information,
e.g., Data = Address | PIN.
Note: The system MAY also be programmed to request synchronization We could also use a Timer, either as the only moving factor or in
on a regular basis (e.g. every night, or twice a week, etc.) and to combination with the Counter -- in this case, e.g., Data = Timer,
achieve this purpose, ask for a sequence of L HOTP values. where Timer could be the UNIX-time (GMT seconds since 1/1/1970)
divided by some factor (8, 16, 32, etc.) in order to give a specific
time step. The time window for the One-Time Password is then equal
to the time step multiplied by the resynchronization parameter as
defined before. For example, if we take 64 seconds as the time step
and 7 for the resynchronization parameter, we obtain an acceptance
window of +/- 3 minutes.
E.4 A Counter-based Re-Synchronization Method Using a Data field opens for more flexibility in the algorithm
implementation, provided that the Data field is clearly specified.
In this case, we assume that the client can access and send not Authors' Addresses
only the HOTP value but also other information, more specifically
the counter value.
A more efficient and secure method for resynchronization is David M'Raihi (primary contact for sending comments and questions)
possible in this case. The client application will not send the VeriSign, Inc.
HOTP-client value only, but the HOTP-client and the related 685 E. Middlefield Road
C-client counter value, the HOTP value acting as a message Mountain View, CA 94043 USA
authentication code of the counter.
Resynchronization Counter-based Protocol (RCP) Phone: 1-650-426-3832
---------------------------------------------- EMail: dmraihi@verisign.com
The server accepts if the following are all true, where C-server is Mihir Bellare
its own current counter value: Dept of Computer Science and Engineering, Mail Code 0114
University of California at San Diego
9500 Gilman Drive
La Jolla, CA 92093, USA
1) C-client >= C-server EMail: mihir@cs.ucsd.edu
2) C-client - C-server <= s
3) Check that HOTP-client is valid HOTP(K,C-Client)
4) If true, the server sets C to C-client + 1 and client is
authenticated
In this case, there is no need for managing a look-ahead window Frank Hoornaert
anymore. The probability of success of the adversary is only v/10^6 VASCO Data Security, Inc.
or roughly v in one million. A side benefit is obviously to be able Koningin Astridlaan 164
to increase s "infinitely" and therefore improve the system 1780 Wemmel, Belgium
usability without impacting the security.
This resynchronization protocol SHOULD be use whenever the related EMail: frh@vasco.com
impact on the client and server applications is deemed acceptable.
E.5 Data Field David Naccache
Gemplus Innovation
34 rue Guynemer, 92447,
Issy les Moulineaux, France
and
Information Security Group,
Royal Holloway,
University of London, Egham,
Surrey TW20 0EX, UK
Another interesting option is the introduction of a Data field, EMail: david.naccache@gemplus.com, david.naccache@rhul.ac.uk
that would be used for generating the One-Time password values:
HOTP (K, C, [Data]) where Data is an optional field that can be the
concatenation of various pieces of identity-related information -
e.g. Data = Address | PIN.
We could also use a Timer, either as the only moving factor or in Ohad Ranen
combination with the Counter - in this case, e.g. Data = Timer, Aladdin Knowledge Systems Ltd.
where Timer could be the UNIX-time (GMT seconds since 1/1/1970) 15 Beit Oved Street
divided by some factor (8, 16, 32, etc.) in order to give a Tel Aviv, Israel 61110
then equal to the time step multiplied by the resynchronization
parameter as defined before - e.g. if we take 64 seconds as the
time step and 7 for the resynchronization parameter, we obtain an
acceptance window of +/- 3 minutes.
Using a Data field opens for more flexibility in the algorithm EMail: Ohad.Ranen@ealaddin.com
implementation, provided that the Data field is clearly specified.
Full Copyright Statement
Copyright (C) The Internet Society (2005).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
 End of changes. 318 change blocks. 
1270 lines changed or deleted 1242 lines changed or added

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