X-Git-Url: https://git.squeep.com/?a=blobdiff_plain;f=reference%2Frfc4226.txt;fp=reference%2Frfc4226.txt;h=b852364fa856b43d0bc1775c249760d773137e7e;hb=2207e51e71606cbd1b4e3a688d450a79853dc8e9;hp=0000000000000000000000000000000000000000;hpb=2fdc701c2749c8d2817502c750f1011e99e21cc1;p=squeep-totp diff --git a/reference/rfc4226.txt b/reference/rfc4226.txt new file mode 100644 index 0000000..b852364 --- /dev/null +++ b/reference/rfc4226.txt @@ -0,0 +1,2075 @@ + + + + + + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] + +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] +