--- /dev/null
+
+
+
+
+
+
+Network Working Group D. M'Raihi
+Request for Comments: 4226 VeriSign
+Category: Informational M. Bellare
+ UCSD
+ F. Hoornaert
+ Vasco
+ D. Naccache
+ Gemplus
+ O. Ranen
+ Aladdin
+ December 2005
+
+
+ HOTP: An HMAC-Based One-Time Password Algorithm
+
+Status of This Memo
+
+ This memo provides information for the Internet community. It does
+ not specify an Internet standard of any kind. Distribution of this
+ memo is unlimited.
+
+Copyright Notice
+
+ Copyright (C) The Internet Society (2005).
+
+Abstract
+
+ This document describes an algorithm to generate one-time password
+ values, based on Hashed Message Authentication Code (HMAC). A
+ security analysis of the algorithm is presented, and important
+ parameters related to the secure deployment of the algorithm are
+ discussed. The proposed algorithm can be used across a wide range of
+ network applications ranging from remote Virtual Private Network
+ (VPN) access, Wi-Fi network logon to transaction-oriented Web
+ applications.
+
+ This work is a joint effort by the OATH (Open AuTHentication)
+ membership to specify an algorithm that can be freely distributed to
+ the technical community. The authors believe that a common and
+ shared algorithm will facilitate adoption of two-factor
+ authentication on the Internet by enabling interoperability across
+ commercial and open-source implementations.
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 1]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+Table of Contents
+
+ 1. Overview ........................................................3
+ 2. Introduction ....................................................3
+ 3. Requirements Terminology ........................................4
+ 4. Algorithm Requirements ..........................................4
+ 5. HOTP Algorithm ..................................................5
+ 5.1. Notation and Symbols .......................................5
+ 5.2. Description ................................................6
+ 5.3. Generating an HOTP Value ...................................6
+ 5.4. Example of HOTP Computation for Digit = 6 ..................7
+ 6. Security Considerations .........................................8
+ 7. Security Requirements ...........................................9
+ 7.1. Authentication Protocol Requirements .......................9
+ 7.2. Validation of HOTP Values .................................10
+ 7.3. Throttling at the Server ..................................10
+ 7.4. Resynchronization of the Counter ..........................11
+ 7.5. Management of Shared Secrets ..............................11
+ 8. Composite Shared Secrets .......................................14
+ 9. Bi-Directional Authentication ..................................14
+ 10. Conclusion ....................................................15
+ 11. Acknowledgements ..............................................15
+ 12. Contributors ..................................................15
+ 13. References ....................................................15
+ 13.1. Normative References .....................................15
+ 13.2. Informative References ...................................16
+ Appendix A - HOTP Algorithm Security: Detailed Analysis ...........17
+ A.1. Definitions and Notations .................................17
+ A.2. The Idealized Algorithm: HOTP-IDEAL .......................17
+ A.3. Model of Security .........................................18
+ A.4. Security of the Ideal Authentication Algorithm ............19
+ A.4.1. From Bits to Digits ................................19
+ A.4.2. Brute Force Attacks ................................21
+ A.4.3. Brute force attacks are the best possible attacks ..22
+ A.5. Security Analysis of HOTP .................................23
+ Appendix B - SHA-1 Attacks ........................................25
+ B.1. SHA-1 Status ..............................................25
+ B.2. HMAC-SHA-1 Status .........................................26
+ B.3. HOTP Status ...............................................26
+ Appendix C - HOTP Algorithm: Reference Implementation .............27
+ Appendix D - HOTP Algorithm: Test Values ..........................32
+ Appendix E - Extensions ...........................................33
+ E.1. Number of Digits ..........................................33
+ E.2. Alphanumeric Values .......................................33
+ E.3. Sequence of HOTP values ...................................34
+ E.4. A Counter-Based Resynchronization Method ..................34
+ E.5. Data Field ................................................35
+
+
+
+
+M'Raihi, et al. Informational [Page 2]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+1. Overview
+
+ The document introduces first the context around an algorithm that
+ generates one-time password values based on HMAC [BCK1] and, thus, is
+ named the HMAC-Based One-Time Password (HOTP) algorithm. In Section
+ 4, the algorithm requirements are listed and in Section 5, the HOTP
+ algorithm is described. Sections 6 and 7 focus on the algorithm
+ security. Section 8 proposes some extensions and improvements, and
+ Section 10 concludes this document. In Appendix A, the interested
+ reader will find a detailed, full-fledged analysis of the algorithm
+ security: an idealized version of the algorithm is evaluated, and
+ then the HOTP algorithm security is analyzed.
+
+2. Introduction
+
+ Today, deployment of two-factor authentication remains extremely
+ limited in scope and scale. Despite increasingly higher levels of
+ threats and attacks, most Internet applications still rely on weak
+ authentication schemes for policing user access. The lack of
+ interoperability among hardware and software technology vendors has
+ been a limiting factor in the adoption of two-factor authentication
+ technology. In particular, the absence of open specifications has
+ led to solutions where hardware and software components are tightly
+ coupled through proprietary technology, resulting in high-cost
+ solutions, poor adoption, and limited innovation.
+
+ In the last two years, the rapid rise of network threats has exposed
+ the inadequacies of static passwords as the primary mean of
+ authentication on the Internet. At the same time, the current
+ approach that requires an end user to carry an expensive, single-
+ function device that is only used to authenticate to the network is
+ clearly not the right answer. For two-factor authentication to
+ propagate on the Internet, it will have to be embedded in more
+ flexible devices that can work across a wide range of applications.
+
+ The ability to embed this base technology while ensuring broad
+ interoperability requires that it be made freely available to the
+ broad technical community of hardware and software developers. Only
+ an open-system approach will ensure that basic two-factor
+ authentication primitives can be built into the next generation of
+ consumer devices such as USB mass storage devices, IP phones, and
+ personal digital assistants.
+
+ One-Time Password is certainly one of the simplest and most popular
+ forms of two-factor authentication for securing network access. For
+ example, in large enterprises, Virtual Private Network access often
+ requires the use of One-Time Password tokens for remote user
+ authentication. One-Time Passwords are often preferred to stronger
+
+
+
+M'Raihi, et al. Informational [Page 3]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ forms of authentication such as Public-Key Infrastructure (PKI) or
+ biometrics because an air-gap device does not require the
+ installation of any client desktop software on the user machine,
+ therefore allowing them to roam across multiple machines including
+ home computers, kiosks, and personal digital assistants.
+
+ This document proposes a simple One-Time Password algorithm that can
+ be implemented by any hardware manufacturer or software developer to
+ create interoperable authentication devices and software agents. The
+ algorithm is event-based so that it can be embedded in high-volume
+ devices such as Java smart cards, USB dongles, and GSM SIM cards.
+ The presented algorithm is made freely available to the developer
+ community under the terms and conditions of the IETF Intellectual
+ Property Rights [RFC3979].
+
+ The authors of this document are members of the Open AuTHentication
+ initiative [OATH]. The initiative was created in 2004 to facilitate
+ collaboration among strong authentication technology providers.
+
+3. Requirements Terminology
+
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
+ document are to be interpreted as described in [RFC2119].
+
+4. Algorithm Requirements
+
+ This section presents the main requirements that drove this algorithm
+ design. A lot of emphasis was placed on end-consumer usability as
+ well as the ability for the algorithm to be implemented by low-cost
+ hardware that may provide minimal user interface capabilities. In
+ particular, the ability to embed the algorithm into high-volume SIM
+ and Java cards was a fundamental prerequisite.
+
+ R1 - The algorithm MUST be sequence- or counter-based: one of the
+ goals is to have the HOTP algorithm embedded in high-volume devices
+ such as Java smart cards, USB dongles, and GSM SIM cards.
+
+ R2 - The algorithm SHOULD be economical to implement in hardware by
+ minimizing requirements on battery, number of buttons, computational
+ horsepower, and size of LCD display.
+
+ R3 - The algorithm MUST work with tokens that do not support any
+ numeric input, but MAY also be used with more sophisticated devices
+ such as secure PIN-pads.
+
+ R4 - The value displayed on the token MUST be easily read and entered
+ by the user: This requires the HOTP value to be of reasonable length.
+
+
+
+M'Raihi, et al. Informational [Page 4]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ The HOTP value must be at least a 6-digit value. It is also
+ desirable that the HOTP value be 'numeric only' so that it can be
+ easily entered on restricted devices such as phones.
+
+ R5 - There MUST be user-friendly mechanisms available to
+ resynchronize the counter. Section 7.4 and Appendix E.4 details the
+ resynchronization mechanism proposed in this document
+
+ R6 - The algorithm MUST use a strong shared secret. The length of
+ the shared secret MUST be at least 128 bits. This document
+ RECOMMENDs a shared secret length of 160 bits.
+
+5. HOTP Algorithm
+
+ In this section, we introduce the notation and describe the HOTP
+ algorithm basic blocks -- the base function to compute an HMAC-SHA-1
+ value and the truncation method to extract an HOTP value.
+
+5.1. Notation and Symbols
+
+ A string always means a binary string, meaning a sequence of zeros
+ and ones.
+
+ If s is a string, then |s| denotes its length.
+
+ If n is a number, then |n| denotes its absolute value.
+
+ If s is a string, then s[i] denotes its i-th bit. We start numbering
+ the bits at 0, so s = s[0]s[1]...s[n-1] where n = |s| is the length
+ of s.
+
+ Let StToNum (String to Number) denote the function that as input a
+ string s returns the number whose binary representation is s. (For
+ example, StToNum(110) = 6.)
+
+ Here is a list of symbols used in this document.
+
+ Symbol Represents
+ -------------------------------------------------------------------
+ C 8-byte counter value, the moving factor. This counter
+ MUST be synchronized between the HOTP generator (client)
+ and the HOTP validator (server).
+
+ K shared secret between client and server; each HOTP
+ generator has a different and unique secret K.
+
+ T throttling parameter: the server will refuse connections
+ from a user after T unsuccessful authentication attempts.
+
+
+
+M'Raihi, et al. Informational [Page 5]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+
+ s resynchronization parameter: the server will attempt to
+ verify a received authenticator across s consecutive
+ counter values.
+
+ Digit number of digits in an HOTP value; system parameter.
+
+5.2. Description
+
+ The HOTP algorithm is based on an increasing counter value and a
+ static symmetric key known only to the token and the validation
+ service. In order to create the HOTP value, we will use the HMAC-
+ SHA-1 algorithm, as defined in RFC 2104 [BCK2].
+
+ As the output of the HMAC-SHA-1 calculation is 160 bits, we must
+ truncate this value to something that can be easily entered by a
+ user.
+
+ HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
+
+ Where:
+
+ - Truncate represents the function that converts an HMAC-SHA-1
+ value into an HOTP value as defined in Section 5.3.
+
+ The Key (K), the Counter (C), and Data values are hashed high-order
+ byte first.
+
+ The HOTP values generated by the HOTP generator are treated as big
+ endian.
+
+5.3. Generating an HOTP Value
+
+ We can describe the operations in 3 distinct steps:
+
+ Step 1: Generate an HMAC-SHA-1 value Let HS = HMAC-SHA-1(K,C) // HS
+ is a 20-byte string
+
+ Step 2: Generate a 4-byte string (Dynamic Truncation)
+ Let Sbits = DT(HS) // DT, defined below,
+ // returns a 31-bit string
+
+ Step 3: Compute an HOTP value
+ Let Snum = StToNum(Sbits) // Convert S to a number in
+ 0...2^{31}-1
+ Return D = Snum mod 10^Digit // D is a number in the range
+ 0...10^{Digit}-1
+
+
+
+
+M'Raihi, et al. Informational [Page 6]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ The Truncate function performs Step 2 and Step 3, i.e., the dynamic
+ truncation and then the reduction modulo 10^Digit. The purpose of
+ the dynamic offset truncation technique is to extract a 4-byte
+ dynamic binary code from a 160-bit (20-byte) HMAC-SHA-1 result.
+
+ DT(String) // String = String[0]...String[19]
+ Let OffsetBits be the low-order 4 bits of String[19]
+ Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
+ Let P = String[OffSet]...String[OffSet+3]
+ Return the Last 31 bits of P
+
+ The reason for masking the most significant bit of P is to avoid
+ confusion about signed vs. unsigned modulo computations. Different
+ processors perform these operations differently, and masking out the
+ signed bit removes all ambiguity.
+
+ Implementations MUST extract a 6-digit code at a minimum and possibly
+ 7 and 8-digit code. Depending on security requirements, Digit = 7 or
+ more SHOULD be considered in order to extract a longer HOTP value.
+
+ The following paragraph is an example of using this technique for
+ Digit = 6, i.e., that a 6-digit HOTP value is calculated from the
+ HMAC value.
+
+5.4. Example of HOTP Computation for Digit = 6
+
+ The following code example describes the extraction of a dynamic
+ binary code given that hmac_result is a byte array with the HMAC-
+ SHA-1 result:
+
+ int offset = hmac_result[19] & 0xf ;
+ int bin_code = (hmac_result[offset] & 0x7f) << 24
+ | (hmac_result[offset+1] & 0xff) << 16
+ | (hmac_result[offset+2] & 0xff) << 8
+ | (hmac_result[offset+3] & 0xff) ;
+
+ SHA-1 HMAC Bytes (Example)
+
+ -------------------------------------------------------------
+ | Byte Number |
+ -------------------------------------------------------------
+ |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
+ -------------------------------------------------------------
+ | Byte Value |
+ -------------------------------------------------------------
+ |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a|
+ -------------------------------***********----------------++|
+
+
+
+
+M'Raihi, et al. Informational [Page 7]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ * The last byte (byte 19) has the hex value 0x5a.
+ * The value of the lower 4 bits is 0xa (the offset value).
+ * The offset value is byte 10 (0xa).
+ * The value of the 4 bytes starting at byte 10 is 0x50ef7f19,
+ which is the dynamic binary code DBC1.
+ * The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19 .
+ * HOTP = DBC2 modulo 10^6 = 872921.
+
+ We treat the dynamic binary code as a 31-bit, unsigned, big-endian
+ integer; the first byte is masked with a 0x7f.
+
+ We then take this number modulo 1,000,000 (10^6) to generate the 6-
+ digit HOTP value 872921 decimal.
+
+6. Security Considerations
+
+ The conclusion of the security analysis detailed in the Appendix is
+ that, for all practical purposes, the outputs of the Dynamic
+ Truncation (DT) on distinct counter inputs are uniformly and
+ independently distributed 31-bit strings.
+
+ The security analysis then details the impact of the conversion from
+ a string to an integer and the final reduction modulo 10^Digit, where
+ Digit is the number of digits in an HOTP value.
+
+ The analysis demonstrates that these final steps introduce a
+ negligible bias, which does not impact the security of the HOTP
+ algorithm, in the sense that the best possible attack against the
+ HOTP function is the brute force attack.
+
+ Assuming an adversary is able to observe numerous protocol exchanges
+ and collect sequences of successful authentication values. This
+ adversary, trying to build a function F to generate HOTP values based
+ on his observations, will not have a significant advantage over a
+ random guess.
+
+ The logical conclusion is simply that the best strategy will once
+ again be to perform a brute force attack to enumerate and try all the
+ possible values.
+
+ Considering the security analysis in the Appendix of this document,
+ without loss of generality, we can approximate closely the security
+ of the HOTP algorithm by the following formula:
+
+ Sec = sv/10^Digit
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 8]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ Where:
+ - Sec is the probability of success of the adversary;
+ - s is the look-ahead synchronization window size;
+ - v is the number of verification attempts;
+ - Digit is the number of digits in HOTP values.
+
+ Obviously, we can play with s, T (the Throttling parameter that would
+ limit the number of attempts by an attacker), and Digit until
+ achieving a certain level of security, still preserving the system
+ usability.
+
+7. Security Requirements
+
+ Any One-Time Password algorithm is only as secure as the application
+ and the authentication protocols that implement it. Therefore, this
+ section discusses the critical security requirements that our choice
+ of algorithm imposes on the authentication protocol and validation
+ software.
+
+ The parameters T and s discussed in this section have a significant
+ impact on the security -- further details in Section 6 elaborate on
+ the relations between these parameters and their impact on the system
+ security.
+
+ It is also important to remark that the HOTP algorithm is not a
+ substitute for encryption and does not provide for the privacy of
+ data transmission. Other mechanisms should be used to defeat attacks
+ aimed at breaking confidentiality and privacy of transactions.
+
+7.1. Authentication Protocol Requirements
+
+ We introduce in this section some requirements for a protocol P
+ implementing HOTP as the authentication method between a prover and a
+ verifier.
+
+ RP1 - P MUST support two-factor authentication, i.e., the
+ communication and verification of something you know (secret code
+ such as a Password, Pass phrase, PIN code, etc.) and something you
+ have (token). The secret code is known only to the user and usually
+ entered with the One-Time Password value for authentication purpose
+ (two-factor authentication).
+
+ RP2 - P SHOULD NOT be vulnerable to brute force attacks. This
+ implies that a throttling/lockout scheme is RECOMMENDED on the
+ validation server side.
+
+ RP3 - P SHOULD be implemented over a secure channel in order to
+ protect users' privacy and avoid replay attacks.
+
+
+
+M'Raihi, et al. Informational [Page 9]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+7.2. Validation of HOTP Values
+
+ The HOTP client (hardware or software token) increments its counter
+ and then calculates the next HOTP value HOTP client. If the value
+ received by the authentication server matches the value calculated by
+ the client, then the HOTP value is validated. In this case, the
+ server increments the counter value by one.
+
+ If the value received by the server does not match the value
+ calculated by the client, the server initiate the resynch protocol
+ (look-ahead window) before it requests another pass.
+
+ If the resynch fails, the server asks then for another
+ authentication pass of the protocol to take place, until the
+ maximum number of authorized attempts is reached.
+
+ If and when the maximum number of authorized attempts is reached, the
+ server SHOULD lock out the account and initiate a procedure to inform
+ the user.
+
+7.3. Throttling at the Server
+
+ Truncating the HMAC-SHA-1 value to a shorter value makes a brute
+ force attack possible. Therefore, the authentication server needs to
+ detect and stop brute force attacks.
+
+ We RECOMMEND setting a throttling parameter T, which defines the
+ maximum number of possible attempts for One-Time Password validation.
+ The validation server manages individual counters per HOTP device in
+ order to take note of any failed attempt. We RECOMMEND T not to be
+ too large, particularly if the resynchronization method used on the
+ server is window-based, and the window size is large. T SHOULD be
+ set as low as possible, while still ensuring that usability is not
+ significantly impacted.
+
+ Another option would be to implement a delay scheme to avoid a brute
+ force attack. After each failed attempt A, the authentication server
+ would wait for an increased T*A number of seconds, e.g., say T = 5,
+ then after 1 attempt, the server waits for 5 seconds, at the second
+ failed attempt, it waits for 5*2 = 10 seconds, etc.
+
+ The delay or lockout schemes MUST be across login sessions to prevent
+ attacks based on multiple parallel guessing techniques.
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 10]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+7.4. Resynchronization of the Counter
+
+ Although the server's counter value is only incremented after a
+ successful HOTP authentication, the counter on the token is
+ incremented every time a new HOTP is requested by the user. Because
+ of this, the counter values on the server and on the token might be
+ out of synchronization.
+
+ We RECOMMEND setting a look-ahead parameter s on the server, which
+ defines the size of the look-ahead window. In a nutshell, the server
+ can recalculate the next s HOTP-server values, and check them against
+ the received HOTP client.
+
+ Synchronization of counters in this scenario simply requires the
+ server to calculate the next HOTP values and determine if there is a
+ match. Optionally, the system MAY require the user to send a
+ sequence of (say, 2, 3) HOTP values for resynchronization purpose,
+ since forging a sequence of consecutive HOTP values is even more
+ difficult than guessing a single HOTP value.
+
+ The upper bound set by the parameter s ensures the server does not go
+ on checking HOTP values forever (causing a denial-of-service attack)
+ and also restricts the space of possible solutions for an attacker
+ trying to manufacture HOTP values. s SHOULD be set as low as
+ possible, while still ensuring that usability is not impacted.
+
+7.5. Management of Shared Secrets
+
+ The operations dealing with the shared secrets used to generate and
+ verify OTP values must be performed securely, in order to mitigate
+ risks of any leakage of sensitive information. We describe in this
+ section different modes of operations and techniques to perform these
+ different operations with respect to the state of the art in data
+ security.
+
+ We can consider two different avenues for generating and storing
+ (securely) shared secrets in the Validation system:
+
+ * Deterministic Generation: secrets are derived from a master
+ seed, both at provisioning and verification stages and generated
+ on-the-fly whenever it is required.
+ * Random Generation: secrets are generated randomly at
+ provisioning stage and must be stored immediately and kept
+ secure during their life cycle.
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 11]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ Deterministic Generation
+ ------------------------
+
+ A possible strategy is to derive the shared secrets from a master
+ secret. The master secret will be stored at the server only. A
+ tamper-resistant device MUST be used to store the master key and
+ derive the shared secrets from the master key and some public
+ information. The main benefit would be to avoid the exposure of the
+ shared secrets at any time and also avoid specific requirements on
+ storage, since the shared secrets could be generated on-demand when
+ needed at provisioning and validation time.
+
+ We distinguish two different cases:
+
+ - A single master key MK is used to derive the shared secrets;
+ each HOTP device has a different secret, K_i = SHA-1 (MK,i)
+ where i stands for a public piece of information that identifies
+ uniquely the HOTP device such as a serial number, a token ID,
+ etc. Obviously, this is in the context of an application or
+ service -- different application or service providers will have
+ different secrets and settings.
+ - Several master keys MK_i are used and each HOTP device stores a
+ set of different derived secrets, {K_i,j = SHA-1(MK_i,j)} where
+ j stands for a public piece of information identifying the
+ device. The idea would be to store ONLY the active master key
+ at the validation server, in the Hardware Security Module (HSM),
+ and keep in a safe place, using secret sharing methods such as
+ [Shamir] for instance. In this case, if a master secret MK_i is
+ compromised, then it is possible to switch to another secret
+ without replacing all the devices.
+
+ The drawback in the deterministic case is that the exposure of the
+ master secret would obviously enable an attacker to rebuild any
+ shared secret based on correct public information. The revocation of
+ all secrets would be required, or switching to a new set of secrets
+ in the case of multiple master keys.
+
+ On the other hand, the device used to store the master key(s) and
+ generate the shared secrets MUST be tamper resistant. Furthermore,
+ the HSM will not be exposed outside the security perimeter of the
+ validation system, therefore reducing the risk of leakage.
+
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 12]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ Random Generation
+ -----------------
+
+ The shared secrets are randomly generated. We RECOMMEND following
+ the recommendations in [RFC4086] and selecting a good and secure
+ random source for generating these secrets. A (true) random
+ generator requires a naturally occurring source of randomness.
+ Practically, there are two possible avenues to consider for the
+ generation of the shared secrets:
+
+ * Hardware-based generators: they exploit the randomness that
+ occurs in physical phenomena. A nice implementation can be based on
+ oscillators and built in such ways that active attacks are more
+ difficult to perform.
+
+ * Software-based generators: designing a good software random
+ generator is not an easy task. A simple, but efficient,
+ implementation should be based on various sources and apply to the
+ sampled sequence a one-way function such as SHA-1.
+
+ We RECOMMEND selecting proven products, being hardware or software
+ generators, for the computation of shared secrets.
+
+ We also RECOMMEND storing the shared secrets securely, and more
+ specifically encrypting the shared secrets when stored using tamper-
+ resistant hardware encryption and exposing them only when required:
+ for example, the shared secret is decrypted when needed to verify an
+ HOTP value, and re-encrypted immediately to limit exposure in the RAM
+ for a short period of time. The data store holding the shared
+ secrets MUST be in a secure area, to avoid as much as possible direct
+ attack on the validation system and secrets database.
+
+ Particularly, access to the shared secrets should be limited to
+ programs and processes required by the validation system only. We
+ will not elaborate on the different security mechanisms to put in
+ place, but obviously, the protection of shared secrets is of the
+ uttermost importance.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 13]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+8. Composite Shared Secrets
+
+ It may be desirable to include additional authentication factors in
+ the shared secret K. These additional factors can consist of any
+ data known at the token but not easily obtained by others. Examples
+ of such data include:
+
+ * PIN or Password obtained as user input at the token
+ * Phone number
+ * Any unique identifier programmatically available at the token
+
+ In this scenario, the composite shared secret K is constructed during
+ the provisioning process from a random seed value combined with one
+ or more additional authentication factors. The server could either
+ build on-demand or store composite secrets -- in any case, depending
+ on implementation choice, the token only stores the seed value. When
+ the token performs the HOTP calculation, it computes K from the seed
+ value and the locally derived or input values of the other
+ authentication factors.
+
+ The use of composite shared secrets can strengthen HOTP-based
+ authentication systems through the inclusion of additional
+ authentication factors at the token. To the extent that the token is
+ a trusted device, this approach has the further benefit of not
+ requiring exposure of the authentication factors (such as the user
+ input PIN) to other devices.
+
+9. Bi-Directional Authentication
+
+ Interestingly enough, the HOTP client could also be used to
+ authenticate the validation server, claiming that it is a genuine
+ entity knowing the shared secret.
+
+ Since the HOTP client and the server are synchronized and share the
+ same secret (or a method to recompute it), a simple 3-pass protocol
+ could be put in place:
+ 1- The end user enter the TokenID and a first OTP value OTP1;
+ 2- The server checks OTP1 and if correct, sends back OTP2;
+ 3- The end user checks OTP2 using his HOTP device and if correct,
+ uses the web site.
+
+ Obviously, as indicated previously, all the OTP communications have
+ to take place over a secure channel, e.g., SSL/TLS, IPsec
+ connections.
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 14]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+10. Conclusion
+
+ This document describes HOTP, a HMAC-based One-Time Password
+ algorithm. It also recommends the preferred implementation and
+ related modes of operations for deploying the algorithm.
+
+ The document also exhibits elements of security and demonstrates that
+ the HOTP algorithm is practical and sound, the best possible attack
+ being a brute force attack that can be prevented by careful
+ implementation of countermeasures in the validation server.
+
+ Eventually, several enhancements have been proposed, in order to
+ improve security if needed for specific applications.
+
+11. Acknowledgements
+
+ The authors would like to thank Siddharth Bajaj, Alex Deacon, Loren
+ Hart, and Nico Popp for their help during the conception and
+ redaction of this document.
+
+12. Contributors
+
+ The authors of this document would like to emphasize the role of
+ three persons who have made a key contribution to this document:
+
+ - Laszlo Elteto is system architect with SafeNet, Inc.
+
+ - Ernesto Frutos is director of Engineering with Authenex, Inc.
+
+ - Fred McClain is Founder and CTO with Boojum Mobile, Inc.
+
+ Without their advice and valuable inputs, this document would not be
+ the same.
+
+13. References
+
+13.1. Normative References
+
+ [BCK1] M. Bellare, R. Canetti and H. Krawczyk, "Keyed Hash
+ Functions and Message Authentication", Proceedings of
+ Crypto'96, LNCS Vol. 1109, pp. 1-15.
+
+ [BCK2] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
+ Hashing for Message Authentication", RFC 2104, February
+ 1997.
+
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
+ Requirement Levels", BCP 14, RFC 2119, March 1997.
+
+
+
+M'Raihi, et al. Informational [Page 15]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ [RFC3979] Bradner, S., "Intellectual Property Rights in IETF
+ Technology", BCP 79, RFC 3979, March 2005.
+
+ [RFC4086] Eastlake, D., 3rd, Schiller, J., and S. Crocker,
+ "Randomness Requirements for Security", BCP 106, RFC 4086,
+ June 2005.
+
+13.2. Informative References
+
+ [OATH] Initiative for Open AuTHentication
+ http://www.openauthentication.org
+
+ [PrOo] B. Preneel and P. van Oorschot, "MD-x MAC and building
+ fast MACs from hash functions", Advances in Cryptology
+ CRYPTO '95, Lecture Notes in Computer Science Vol. 963, D.
+ Coppersmith ed., Springer-Verlag, 1995.
+
+ [Crack] Crack in SHA-1 code 'stuns' security gurus
+ http://www.eetimes.com/showArticle.jhtml?
+ articleID=60402150
+
+ [Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005.
+ http://www.schneier.com/blog/archives/2005/02/
+ sha1_broken.html
+
+ [Res] Researchers: Digital encryption standard flawed
+ http://news.com.com/
+ Researchers+Digital+encryption+standard+flawed/
+ 2100-1002-5579881.html?part=dht&tag=ntop&tag=nl.e703
+
+ [Shamir] How to Share a Secret, by Adi Shamir. In Communications
+ of the ACM, Vol. 22, No. 11, pp. 612-613, November, 1979.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 16]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+Appendix A - HOTP Algorithm Security: Detailed Analysis
+
+ The security analysis of the HOTP algorithm is summarized in this
+ section. We first detail the best attack strategies, and then
+ elaborate on the security under various assumptions and the impact of
+ the truncation and make some recommendations regarding the number of
+ digits.
+
+ We focus this analysis on the case where Digit = 6, i.e., an HOTP
+ function that produces 6-digit values, which is the bare minimum
+ recommended in this document.
+
+A.1. Definitions and Notations
+
+ We denote by {0,1}^l the set of all strings of length l.
+
+ Let Z_{n} = {0,.., n - 1}.
+
+ Let IntDiv(a,b) denote the integer division algorithm that takes
+ input integers a, b where a >= b >= 1 and returns integers (q,r)
+
+ the quotient and remainder, respectively, of the division of a by b.
+ (Thus, a = bq + r and 0 <= r < b.)
+
+ Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that takes
+ a k-bit key K and c-bit counter C and returns an n-bit output H(K,C).
+ (In the case of HOTP, H is HMAC-SHA-1; we use this formal definition
+ for generalizing our proof of security.)
+
+A.2. The Idealized Algorithm: HOTP-IDEAL
+
+ We now define an idealized counterpart of the HOTP algorithm. In
+ this algorithm, the role of H is played by a random function that
+ forms the key.
+
+ To be more precise, let Maps(c,n) denote the set of all functions
+ mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key
+ space Maps(c,n), so that a "key" for such an algorithm is a function
+ h from {0,1}^c to {0,1}^n. We imagine this key (function) to be
+ drawn at random. It is not feasible to implement this idealized
+ algorithm, since the key, being a function from {0,1}^c to {0,1}^n,
+ is way too large to even store. So why consider it?
+
+ Our security analysis will show that as long as H satisfies a certain
+ well-accepted assumption, the security of the actual and idealized
+ algorithms is for all practical purposes the same. The task that
+ really faces us, then, is to assess the security of the idealized
+ algorithm.
+
+
+
+M'Raihi, et al. Informational [Page 17]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ In analyzing the idealized algorithm, we are concentrating on
+ assessing the quality of the design of the algorithm itself,
+ independently of HMAC-SHA-1. This is in fact the important issue.
+
+A.3. Model of Security
+
+ The model exhibits the type of threats or attacks that are being
+ considered and enables one to assess the security of HOTP and HOTP-
+ IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the purpose of
+ this security analysis.
+
+ The scenario we are considering is that a user and server share a key
+ K for ALG. Both maintain a counter C, initially zero, and the user
+ authenticates itself by sending ALG(K,C) to the server. The latter
+ accepts if this value is correct.
+
+ In order to protect against accidental increment of the user counter,
+ the server, upon receiving a value z, will accept as long as z equals
+ ALG(K,i) for some i in the range C,...,C + s-1, where s is the
+ resynchronization parameter and C is the server counter. If it
+ accepts with some value of i, it then increments its counter to i+1.
+ If it does not accept, it does not change its counter value.
+
+ The model we specify captures what an adversary can do and what it
+ needs to achieve in order to "win". First, the adversary is assumed
+ to be able to eavesdrop, meaning, to see the authenticator
+ transmitted by the user. Second, the adversary wins if it can get
+ the server to accept an authenticator relative to a counter value for
+ which the user has never transmitted an authenticator.
+
+ The formal adversary, which we denote by B, starts out knowing which
+ algorithm ALG is being used, knowing the system design, and knowing
+ all system parameters. The one and only thing it is not given a
+ priori is the key K shared between the user and the server.
+
+ The model gives B full control of the scheduling of events. It has
+ access to an authenticator oracle representing the user. By calling
+ this oracle, the adversary can ask the user to authenticate itself
+ and get back the authenticator in return. It can call this oracle as
+ often as it wants and when it wants, using the authenticators it
+ accumulates to perhaps "learn" how to make authenticators itself. At
+ any time, it may also call a verification oracle, supplying the
+ latter with a candidate authenticator of its choice. It wins if the
+ server accepts this accumulator.
+
+ Consider the following game involving an adversary B that is
+ attempting to compromise the security of an authentication algorithm
+ ALG: K x {0,1}^c --> R.
+
+
+
+M'Raihi, et al. Informational [Page 18]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ Initializations - A key K is selected at random from K, a counter C
+ is initialized to 0, and the Boolean value win is set to false.
+
+ Game execution - Adversary B is provided with the two following
+ oracles:
+
+ Oracle AuthO()
+ --------------
+ A = ALG(K,C)
+ C = C + 1
+ Return O to B
+
+ Oracle VerO(A)
+ --------------
+ i = C
+ While (i <= C + s - 1 and Win == FALSE) do
+ If A == ALG(K,i) then Win = TRUE; C = i + 1
+ Else i = i + 1
+ Return Win to B
+
+ AuthO() is the authenticator oracle and VerO(A) is the verification
+ oracle.
+
+ Upon execution, B queries the two oracles at will. Let Adv(B) be the
+ probability that win gets set to true in the above game. This is the
+ probability that the adversary successfully impersonates the user.
+
+ Our goal is to assess how large this value can be as a function of
+ the number v of verification queries made by B, the number a of
+ authenticator oracle queries made by B, and the running time t of B.
+ This will tell us how to set the throttle, which effectively upper
+ bounds v.
+
+A.4. Security of the Ideal Authentication Algorithm
+
+ This section summarizes the security analysis of HOTP-IDEAL, starting
+ with the impact of the conversion modulo 10^Digit and then focusing
+ on the different possible attacks.
+
+A.4.1. From Bits to Digits
+
+ The dynamic offset truncation of a random n-bit string yields a
+ random 31-bit string. What happens to the distribution when it is
+ taken modulo m = 10^Digit, as done in HOTP?
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 19]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ The following lemma estimates the biases in the outputs in this case.
+
+ Lemma 1
+ -------
+ Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in
+ Z_{m} let:
+
+ P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}]
+
+ Then for any z in Z_{m}
+
+ P_{N,m}(z) = (q + 1) / N if 0 <= z < r
+ q / N if r <= z < m
+
+ Proof of Lemma 1
+ ----------------
+ Let the random variable X be uniformly distributed over Z_{N}. Then:
+
+ P_{N,m}(z) = Pr [X mod m = z]
+
+ = Pr [X < mq] * Pr [X mod m = z| X < mq]
+ + Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N]
+
+ = mq/N * 1/m +
+ (N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq
+ 0 if N - mq <= z <= m
+
+ = q/N +
+ r/N * 1 / r if 0 <= z < N - mq
+ 0 if r <= z <= m
+
+ Simplifying yields the claimed equation.
+
+ Let N = 2^31, d = 6, and m = 10^d. If x is chosen at random from
+ Z_{N} (meaning, is a random 31-bit string), then reducing it to a 6-
+ digit number by taking x mod m does not yield a random 6-digit
+ number.
+
+ Rather, x mod m is distributed as shown in the following table:
+
+ Values Probability that each appears as output
+ ----------------------------------------------------------------
+ 0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6
+ 483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6
+
+ If X is uniformly distributed over Z_{2^31} (meaning, is a random
+ 31-bit string), then the above shows the probabilities for different
+ outputs of X mod 10^6. The first set of values appears with
+
+
+
+M'Raihi, et al. Informational [Page 20]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ probability slightly greater than 10^-6, the rest with probability
+ slightly less, meaning that the distribution is slightly non-uniform.
+
+ However, as the table above indicates, the bias is small, and as we
+ will see later, negligible: the probabilities are very close to
+ 10^-6.
+
+A.4.2. Brute Force Attacks
+
+ If the authenticator consisted of d random digits, then a brute force
+ attack using v verification attempts would succeed with probability
+ sv/10^Digit.
+
+ However, an adversary can exploit the bias in the outputs of
+ HOTP-IDEAL, predicted by Lemma 1, to mount a slightly better attack.
+
+ Namely, it makes authentication attempts with authenticators that are
+ the most likely values, meaning the ones in the range 0,...,r - 1,
+ where (q,r) = IntDiv(2^31,10^Digit).
+
+ The following specifies an adversary in our model of security that
+ mounts the attack. It estimates the success probability as a
+ function of the number of verification queries.
+
+ For simplicity, we assume that the number of verification queries is
+ at most r. With N = 2^31 and m = 10^6, we have r = 483,648, and the
+ throttle value is certainly less than this, so this assumption is not
+ much of a restriction.
+
+ Proposition 1
+ -------------
+
+ Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume
+ s <= m. The brute-force-attack adversary B-bf attacks HOTP using v
+ <= r verification oracle queries. This adversary makes no
+ authenticator oracle queries, and succeeds with probability
+
+ Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s
+
+ which is roughly equal to
+
+ sv * (q+1)/2^31
+
+ With m = 10^6 we get q = 2,147. In that case, the brute force attack
+ using v verification attempts succeeds with probability
+
+ Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6
+
+
+
+
+M'Raihi, et al. Informational [Page 21]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ As this equation shows, the resynchronization parameter s has a
+ significant impact in that the adversary's success probability is
+ proportional to s. This means that s cannot be made too large
+ without compromising security.
+
+A.4.3. Brute force attacks are the best possible attacks.
+
+ A central question is whether there are attacks any better than the
+ brute force one. In particular, the brute force attack did not
+ attempt to collect authenticators sent by the user and try to
+ cryptanalyze them in an attempt to learn how to better construct
+ authenticators. Would doing this help? Is there some way to "learn"
+ how to build authenticators that result in a higher success rate than
+ given by the brute-force attack?
+
+ The following says the answer to these questions is no. No matter
+ what strategy the adversary uses, and even if it sees, and tries to
+ exploit, the authenticators from authentication attempts of the user,
+ its success probability will not be above that of the brute force
+ attack -- this is true as long as the number of authentications it
+ observes is not incredibly large. This is valuable information
+ regarding the security of the scheme.
+
+ Proposition 2 ------------- Suppose m = 10^Digit < 2^31, and let
+ (q,r) = IntDiv(2^31,m). Let B be any adversary attacking HOTP-IDEAL
+ using v verification oracle queries and a <= 2^c - s authenticator
+ oracle queries. Then
+
+ Adv(B) < = sv * (q+1)/ 2^31
+
+ Note: This result is conditional on the adversary not seeing more
+ than 2^c - s authentications performed by the user, which is hardly
+ restrictive as long as c is large enough.
+
+ With m = 10^6, we get q = 2,147. In that case, Proposition 2 says
+ that any adversary B attacking HOTP-IDEAL and making v verification
+ attempts succeeds with probability at most
+
+ Equation 1
+ ----------
+ sv * 2148/2^31 roughly = sv * 1.00024045/10^6
+
+ Meaning, B's success rate is not more than that achieved by the brute
+ force attack.
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 22]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+A.5. Security Analysis of HOTP
+
+ We have analyzed, in the previous sections, the security of the
+ idealized counterparts HOTP-IDEAL of the actual authentication
+ algorithm HOTP. We now show that, under appropriate and well-
+ believed assumption on H, the security of the actual algorithms is
+ essentially the same as that of its idealized counterpart.
+
+ The assumption in question is that H is a secure pseudorandom
+ function, or PRF, meaning that its input-output values are
+ indistinguishable from those of a random function in practice.
+
+ Consider an adversary A that is given an oracle for a function f:
+ {0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A)
+ as the prf-advantage of A, which represents how well the adversary
+ does at distinguishing the case where its oracle is H(K,.) from the
+ case where its oracle is a random function of {0,1}^c to {0,1}^n.
+
+ One possible attack is based on exhaustive search for the key K. If
+ A runs for t steps and T denotes the time to perform one computation
+ of H, its prf-advantage from this attack turns out to be (t/T)2^-k.
+ 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
+ translates into the following.
+
+ Assumption 1
+ ------------
+
+ 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,
+
+ Adv(A) <= (t/T)/2^k + p^2/2^n
+
+ 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.
+
+ Theorem 1
+ ---------
+
+ Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B
+ be any adversary attacking HOTP using v verification oracle queries,
+
+
+
+
+
+M'Raihi, et al. Informational [Page 23]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ a <= 2^c - s authenticator oracle queries, and running 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
+ 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
+ adversary making v authentication attempts will have a success rate
+ that is at most that of Equation 1.
+
+ For example, consider an adversary with running time at most 2^60
+ that sees at most 2^40 authentication attempts of the user. Both
+ 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.
+
+ We can safely assume sv <= 2^40 due to the throttling and bounds on
+ s. So:
+
+ (t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160
+ roughly <= 2^-78
+
+ which is much smaller than the success probability of Equation 1 and
+ negligible compared to it.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 24]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+Appendix B - SHA-1 Attacks
+
+ This sections addresses the impact of the recent attacks on SHA-1 on
+ the security of the HMAC-SHA-1-based HOTP. We begin with some
+ discussion of the situation of SHA-1 and then discuss the relevance
+ to HMAC-SHA-1 and HOTP. Cited references are in Section 13.
+
+B.1. SHA-1 Status
+
+ A collision for a hash function h means a pair x,y of different
+ 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
+ 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.
+
+ Burr of NIST is quoted in [Crack] as saying "Large national
+ intelligence agencies could do this in a reasonable amount of time
+ with a few million dollars in computer time". However, the
+ computation may be out of reach of all but such well-funded agencies.
+
+ 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.
+
+ Indeed, one can read in the press that SHA-1 is "broken" [Sha1] and
+ that encryption and SSL are "broken" [Res]. The media have a
+ 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.
+
+ Cryptographers are excited too. But mainly because this is an
+ important theoretical breakthrough. Attacks can only get better with
+ time: it is therefore important to monitor any progress in hash
+ functions cryptanalysis and be prepared for any really practical
+ break with a sound migration plan for the future.
+
+
+
+M'Raihi, et al. Informational [Page 25]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+B.2. HMAC-SHA-1 Status
+
+ The new attacks on SHA-1 have no impact on the security of
+ HMAC-SHA-1. The best attack on the latter remains one needing a
+ sender to authenticate 2^{80} messages before an adversary can create
+ a forgery. Why?
+
+ HMAC is not a hash function. It is a message authentication code
+ (MAC) that uses a hash function internally. A MAC depends on a
+ secret key, while hash functions don't. What one needs to worry
+ about with a MAC is forgery, not collisions. HMAC was designed so
+ that collisions in the hash function (here SHA-1) do not yield
+ forgeries for HMAC.
+
+ 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 x,y
+ such that SHA-1(K_i,x) = SHA-1(K_i,y). (Call this a hidden-key
+ 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.
+
+ Historically, the HMAC design has already proven itself in this
+ 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.
+
+B.3. HOTP Status
+
+ 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 the
+ document, namely, to try to guess output values.
+
+ 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.
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 26]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+Appendix C - HOTP Algorithm: Reference Implementation
+
+ /*
+ * OneTimePasswordAlgorithm.java
+ * OATH Initiative,
+ * HOTP one-time password algorithm
+ *
+ */
+
+ /* Copyright (C) 2004, OATH. All rights reserved.
+ *
+ * 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 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.
+ */
+
+ package org.openauthentication.otp;
+
+ 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;
+ import java.security.NoSuchAlgorithmException;
+ import java.security.InvalidKeyException;
+
+ import javax.crypto.Mac;
+ import javax.crypto.spec.SecretKeySpec;
+
+
+
+
+M'Raihi, et al. Informational [Page 27]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ /**
+ * 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() {}
+
+ // These are used to calculate the check-sum digits.
+ // 0 1 2 3 4 5 6 7 8 9
+ private static final int[] doubleDigits =
+ { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
+
+ /**
+ * Calculates the checksum using the credit card algorithm.
+ * 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;
+ }
+
+ /**
+ * This method uses the JCE to provide the HMAC-SHA-1
+
+
+
+M'Raihi, et al. Informational [Page 28]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ * algorithm.
+ * HMAC computes a Hashed Message Authentication Code and
+ * in this case SHA1 is the hash algorithm used.
+ *
+ * @param keyBytes the bytes to use for the HMAC-SHA-1 key
+ * @param text the message or text to be authenticated.
+ *
+ * @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.
+ *
+ */
+
+ public static byte[] hmac_sha1(byte[] keyBytes, byte[] text)
+ throws NoSuchAlgorithmException, InvalidKeyException
+ {
+ // try {
+ Mac hmacSha1;
+ 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);
+ // }
+ }
+
+ private static final int[] DIGITS_POWER
+ // 0 1 2 3 4 5 6 7 8
+ = {1,10,100,1000,10000,100000,1000000,10000000,100000000};
+
+ /**
+ * This method generates an OTP value for the given
+ * 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
+
+
+
+M'Raihi, et al. Informational [Page 29]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ * 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;
+ }
+
+ // compute hmac hash
+ byte[] hash = hmac_sha1(secret, text);
+
+ // 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)
+
+
+
+M'Raihi, et al. Informational [Page 30]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ | (hash[offset + 3] & 0xff);
+
+ 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;
+ }
+ }
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 31]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+Appendix D - HOTP Algorithm: Test Values
+
+ The following test data uses the ASCII string
+ "12345678901234567890" for the secret:
+
+ Secret = 0x3132333435363738393031323334353637383930
+
+ Table 1 details for each count, the intermediate HMAC value.
+
+ Count Hexadecimal HMAC-SHA-1(secret, count)
+ 0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0
+ 1 75a48a19d4cbe100644e8ac1397eea747a2d33ab
+ 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
+ hexadecimal and decimal) and then the HOTP value.
+
+ Truncated
+ Count Hexadecimal Decimal HOTP
+ 0 4c93cf18 1284755224 755224
+ 1 41397eea 1094287082 287082
+ 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
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 32]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+Appendix E - Extensions
+
+
+ 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
+
+ A simple enhancement in terms of security would be to extract more
+ digits from the HMAC-SHA-1 value.
+
+ For instance, calculating the HOTP value modulo 10^8 to build an 8-
+ digit HOTP value would reduce the probability of success of the
+ adversary from sv/10^6 to sv/10^8.
+
+ 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.
+
+E.2. Alphanumeric Values
+
+ 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.
+
+ 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.
+
+ 32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is 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
+ significantly better than a 9-digit HOTP value.
+
+ Depending on the application and token/interface used for displaying
+ and entering the HOTP value, the choice of alphanumeric values could
+ be a simple and efficient way to improve security at a reduced cost
+ and impact on users.
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 33]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+E.3. Sequence of HOTP Values
+
+ 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.
+
+ Per default, the value L SHOULD be set to 1, but if security needs to
+ be increased, users might be asked (possibly for a short period of
+ time, or a specific operation) to enter L HOTP values.
+
+ This is another way, without increasing the HOTP length or using
+ alphanumeric values to tighten security.
+
+ Note: The system MAY also be programmed to request synchronization on
+ a regular basis (e.g., every night, twice a week, etc.) and to
+ achieve this purpose, ask for a sequence of L HOTP values.
+
+E.4. A Counter-Based Resynchronization Method
+
+ In this case, we assume that the client can access and send not only
+ the HOTP value but also other information, more specifically, the
+ counter value.
+
+ A more efficient and secure method for resynchronization is possible
+ in this case. The client application will not send the HOTP-client
+ 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.
+
+ Resynchronization Counter-based Protocol (RCP)
+ ----------------------------------------------
+
+ The server accepts if the following are all true, where C-server is
+ its own current counter value:
+
+ 1) C-client >= C-server
+ 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
+ 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.
+
+
+
+
+M'Raihi, et al. Informational [Page 34]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+ This resynchronization protocol SHOULD be used whenever the related
+ impact on the client and server applications is deemed acceptable.
+
+E.5. Data Field
+
+ Another interesting option is the introduction of a Data field, which
+ 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
+ combination with the Counter -- in this case, e.g., Data = Timer,
+ 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.
+
+ Using a Data field opens for more flexibility in the algorithm
+ implementation, provided that the Data field is clearly specified.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 35]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+Authors' Addresses
+
+ David M'Raihi (primary contact for sending comments and questions)
+ VeriSign, Inc.
+ 685 E. Middlefield Road
+ Mountain View, CA 94043 USA
+
+ Phone: 1-650-426-3832
+ EMail: dmraihi@verisign.com
+
+
+ Mihir Bellare
+ Dept of Computer Science and Engineering, Mail Code 0114
+ University of California at San Diego
+ 9500 Gilman Drive
+ La Jolla, CA 92093, USA
+
+ EMail: mihir@cs.ucsd.edu
+
+
+ Frank Hoornaert
+ VASCO Data Security, Inc.
+ Koningin Astridlaan 164
+ 1780 Wemmel, Belgium
+
+ EMail: frh@vasco.com
+
+
+ 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
+
+ EMail: david.naccache@gemplus.com, david.naccache@rhul.ac.uk
+
+
+ Ohad Ranen
+ Aladdin Knowledge Systems Ltd.
+ 15 Beit Oved Street
+ Tel Aviv, Israel 61110
+
+ EMail: Ohad.Ranen@ealaddin.com
+
+
+
+
+M'Raihi, et al. Informational [Page 36]
+\f
+RFC 4226 HOTP Algorithm December 2005
+
+
+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.
+
+
+
+
+
+
+
+M'Raihi, et al. Informational [Page 37]
+\f
projects / squeep-totp / blobdiff