idnits 2.17.00 (12 Aug 2021) /tmp/idnits22450/draft-mraihi-oath-hmac-otp-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3667, Section 5.1 on line 20. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1060. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == There are 29 instances of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. (A line matching the expected section header was found, but with an unexpected indentation: ' 2. Introduction' ) ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There is 1 instance of too long lines in the document, the longest one being 11 characters in excess of 72. ** The abstract seems to contain references ([BCK1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == The "Author's Address" (or "Authors' Addresses") section title is misspelled. == Line 250 has weird spacing: '... Digit num...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 2004) is 6426 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Missing reference section? 'BCK1' on line 626 looks like a reference -- Missing reference section? 'RFC3668' on line 637 looks like a reference -- Missing reference section? 'OATH' on line 642 looks like a reference -- Missing reference section? '0' on line 296 looks like a reference -- Missing reference section? '1' on line 225 looks like a reference -- Missing reference section? 'BCK2' on line 630 looks like a reference -- Missing reference section? '19' on line 323 looks like a reference -- Missing reference section? 'OffSet' on line 299 looks like a reference -- Missing reference section? 'RFC2119' on line 634 looks like a reference -- Missing reference section? '3' on line 991 looks like a reference Summary: 14 errors (**), 0 flaws (~~), 4 warnings (==), 14 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft D. MÆRaihi 2 Category: Informational Verisign 3 Document: draft-mraihi-oath-hmac-otp-00.txt M. Bellare 4 Expires: April 2005 UCSD 5 F. Hoornaert 6 Vasco 7 D. Naccache 8 Gemplus 9 O. Ranen 10 Aladdin 11 October 2004 13 HOTP: An HMAC-based One Time Password Algorithm 15 Status of this Memo 17 By submitting this Internet-Draft, I certify that any applicable 18 patent or other IPR claims of which I am aware have been disclosed, 19 or will be disclosed, and any of which I become aware will be 20 disclosed, in accordance with RFC 3668. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF), its areas, and its working groups. Note that 24 other groups may also distribute working documents as Internet- 25 Drafts. 27 Internet-Drafts are draft documents valid for a maximum of six 28 months and may be updated, replaced, or obsoleted by other 29 documents at any time. It is inappropriate to use Internet-Drafts 30 as reference material or to cite them other than a "work in 31 progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/1id-abstracts.html 35 The list of Internet-Draft Shadow Directories can be accessed at 36 http://www.ietf.org/shadow.html 38 Abstract 40 This document describes an algorithm to generate one-time password 41 values, based on HMAC [BCK1]. A security analysis of the algorithm 42 is presented, and important parameters related to the secure 43 deployment of the algorithm are discussed. The proposed algorithm 44 can be used across a wide range of network applications ranging 45 from remote VPN access, Wi-Fi network logon to transaction-oriented 46 Web applications. 48 This work is a joint effort by the OATH (Open AuTHentication) 49 membership to specify an algorithm that can be freely distributed 50 to the technical community. The authors believe that a common and 51 HOTP: An HMAC-based One Time Password Algorithm October 2004 53 shared algorithm will facilitate adoption of two-factor 54 authentication on the Internet by enabling interoperability across 55 commercial and open-source implementations. 57 Table of Contents 59 1. Overview...................................................2 60 2. Introduction...............................................3 61 3. Requirements Terminology...................................4 62 4. Algorithm Requirements.....................................4 63 5. HOTP Algorithm.............................................5 64 5.1 Notation and Symbols.....................................5 65 5.2 Description..............................................6 66 5.3 Generating an HOTP value.................................6 67 5.4 Example of HOTP computation for Digit = 6................7 68 6. Security and Deployment Considerations.....................8 69 6.1 Authentication Protocol Requirements.....................8 70 6.2 Validation of HOTP values................................8 71 6.3 Throttling at the server.................................9 72 6.4 Resynchronization of the counter.........................9 73 7. HOTP Algorithm Security: Overview.........................10 74 8. Protocol Extensions and Improvements......................10 75 8.1 Number of Digits........................................10 76 8.2 Alpha-numeric Values....................................11 77 8.3 Sequence of HOTP values.................................11 78 8.4 A Counter-based Re-Synchronization Method...............12 79 9. Conclusion................................................12 80 10. Acknowledgements..........................................13 81 11. Contributors..............................................13 82 12. References................................................13 83 12.1 Normative...............................................13 84 12.2 Informative.............................................13 85 13. AuthorsÆ Addresses........................................13 86 Appendix - HOTP Algorithm Security: Detailed Analysis..........14 87 A.1 Definitions and Notations.................................14 88 A.2 The idealized algorithm: HOTP-IDEAL.......................15 89 A.3 Model of Security.........................................15 90 A.4 Security of the ideal authentication algorithm............17 91 A.4.1 From bits to digits.....................................17 92 A.4.2 Brute force attacks.....................................18 93 A.4.3 Brute force attacks are the best possible attacks.......19 94 A.5 Security Analysis of HOTP.................................20 96 1. Overview 98 The document introduces first the context around the HOTP 99 algorithm. In section 4, the algorithm requirements are listed and 100 in section 5, the HOTP algorithm is described. Sections 6 and 7 101 focus on the algorithm security. Section 8 proposes some extensions 102 HOTP: An HMAC-based One Time Password Algorithm October 2004 104 and improvements, and Section 9 concludes this document. The 105 interested reader will find in the Appendix a detailed, full-fledge 106 analysis of the algorithm security: an idealized version of the 107 algorithm is evaluated, and then the HOTP algorithm security is 108 analyzed. 110 2. Introduction 112 Today, deployment of two-factor authentication remains extremely 113 limited in scope and scale. Despite increasingly higher levels of 114 threats and attacks, most Internet applications still rely on weak 115 authentication schemes for policing user access. The lack of 116 interoperability among hardware and software technology vendors has 117 been a limiting factor in the adoption of two-factor authentication 118 technology. In particular, the absence of open specifications has 119 led to solutions where hardware and software components are tightly 120 coupled through proprietary technology, resulting in high cost 121 solutions, poor adoption and limited innovation. 123 In the last two years, the rapid rise of network threats has 124 exposed the inadequacies of static passwords as the primary mean of 125 authentication on the Internet. At the same time, the current 126 approach that requires an end-user to carry an expensive, single- 127 function device that is only used to authenticate to the network is 128 clearly not the right answer. For two factor authentication to 129 propagate on the Internet, it will have to be embedded in more 130 flexible devices that can work across a wide range of applications. 132 The ability to embed this base technology while ensuring broad 133 interoperability require that it be made freely available to the 134 broad technical community of hardware and software developers. Only 135 an open system approach will ensure that basic two-factor 136 authentication primitives can be built into the next-generation of 137 consumer devices such USB mass storage devices, IP phones, and 138 personal digital assistants). 140 One Time Password is certainly one of the simplest and most popular 141 forms of two-factor authentication for securing network access. For 142 example, in large enterprises, Virtual Private Network access often 143 requires the use of One Time Password tokens for remote user 144 authentication. One Time Passwords are often preferred to stronger 145 forms of authentication such as PKI or biometrics because an air- 146 gap device does not require the installation of any client desktop 147 software on the user machine, therefore allowing them to roam 148 across multiple machines including home computers, kiosks and 149 personal digital assistants. 151 This draft proposes a simple One Time Password algorithm that can 152 be implemented by any hardware manufacturer or software developer 153 HOTP: An HMAC-based One Time Password Algorithm October 2004 155 to create interoperable authentication devices and software agents. 156 The algorithm is event-based so that it can be embedded in high 157 volume devices such as Java smart cards, USB dongles and GSM SIM 158 cards. The presented algorithm is made freely available to the 159 developer community under the terms and conditions of the IETF 160 Intellectual Property Rights [RFC3668]. 162 The authors of this document are members of the Open AuTHentication 163 initiative [OATH]. The initiative was created in 2004 to facilitate 164 collaboration among strong authentication technology providers. 166 3. Requirements Terminology 168 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 169 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 170 this document are to be interpreted as described in RFC 2119. 172 4. Algorithm Requirements 174 This section presents the main requirements that drove this 175 algorithm design. A lot of emphasis was placed on end-consumer 176 usability as well as the ability for the algorithm to be 177 implemented by low cost hardware that may provide minimal user 178 interface capabilities. In particular, the ability to embed the 179 algorithm into high volume SIM and Java cards was a fundamental 180 pre-requisite. 182 R1 - The algorithm MUST be sequence or counter-based: One of the 183 goals is to have the HOTP algorithm embedded in high volume devices 184 such as Java smart cards, USB dongles and GSM SIM cards. 186 R2 - The algorithm SHOULD be economical to implement in hardware by 187 minimizing requirements on battery, number of buttons, 188 computational horsepower, and size of LCD display. The algorithm 189 MUST work with tokens that do not supports any numeric input, but 190 MAY also be used with more sophisticated devices such as secure 191 PIN-pads. 193 R3 - The value displayed on the token MUST be easily read and 194 entered by the user: This requires the HOTP value to be of 195 reasonable length. The HOTP value must be at least a 6-digit value. 196 It is also desirable that the HOTP value be 'numeric only' so that 197 it can be easily entered on restricted devices such as phones. 199 R4 - There MUST be user-friendly mechanisms available to 200 resynchronize the counter. The sections 6.4 and 8.4 detail the 201 resynchronization mechanism proposed in this draft. 203 HOTP: An HMAC-based One Time Password Algorithm October 2004 205 R5- The algorithm MUST use a strong shared secret. The length of 206 the shared secret MUST be at least 128 bits. This draft RECOMMENDs 207 a shared secret length of 160 bits. 209 5. HOTP Algorithm 211 In this section, we introduce the notation and describe the HOTP 212 algorithm basic blocks û the base function to compute an HMAC-SHA-1 213 value and the truncation method to extract an HOTP value. 215 5.1 Notation and Symbols 217 A string always means a binary string, meaning a sequence of zeros 218 and ones. 220 If s is a string then |s| denotes its length. 222 If n is a number then |n| denotes its absolute value. 224 If s is a string then s[i] denotes its i-th bit. We start numbering 225 the bits at 0, so s = s[0]s[1]..s[n-1] where n = |s| is the length 226 of s. 228 Let StToNum (String to Number) denote the function which as input a 229 string s returns the number whose binary representation is s. 230 (For example StToNum(110) = 6). 232 Here is a list of symbols used in this document. 234 Symbol Represents 235 ------------------------------------------------------------------- 236 C 8-byte (Little Endian) counter value, which is the moving 237 factor. This counter MUST be synchronized between the HOTP 238 generator (client) and the HOTP validator (server); 240 K shared secret between the client and the server; each HOTP 241 generator has a different and unique secret K; 243 T throttling parameter: the server will refuse connections 244 from a user after T unsuccessful authentication attempts; 246 s resynchronization parameter: the server will attempt to 247 verify a received authenticator across s consecutive 248 counter values; 250 Digit number of digits in an HOTP value; system parameter. 252 HOTP: An HMAC-based One Time Password Algorithm October 2004 254 5.2 Description 256 The HOTP algorithm is based on an increasing counter value and a 257 static symmetric key known only to the token and the validation 258 service. In order to create the HOTP value, we will use the HMAC- 259 SHA-1 algorithm, as defined in RFC 2104 [BCK2]. 261 As the output of the HMAC-SHA1 calculation is 160 bits, we must 262 truncate this value to something that can be easily entered by a 263 user. 265 HOTP(K,C) = Truncate(HMAC-SHA-1(K,C)) 267 Where: 268 - Truncate represents the function that converts an HMAC-SHA-1 269 value into an HOTP value as defined in Section 5.3. 271 The HOTP values generated by the HOTP generator are treated as big 272 endian. 274 5.3 Generating an HOTP value 276 We can describe the operations in 3 distinct steps: 278 Step 1: Generate an HMAC-SHA-1 value 279 Let HS = HMAC-SHA-1(K,C) // HS is a 20 byte string 281 Step 2: Generate a 4-byte string (Dynamic Truncation) 282 Let Sbits = DT(HS) // DT, defined in Section 6.3.1 283 // returns a 31 bit string 285 Step 3: Compute an HOTP value 286 Let Snum = StToNum(S) // Convert S to a number in 287 0...2^{31}-1 288 Return D = Snum mod 10^Digit // D is a number in the range 289 0...10^{Digit}-1 291 The Truncate function performs Step 2 and Step 3, i.e. the dynamic 292 truncation and then the reduction modulo 10^Digit. The purpose of 293 the dynamic offset truncation technique is to extract a 4-byte 294 dynamic binary code from a 160-bit (20-byte) HMAC-SHA1 result. 296 DT(String) // String = String[0]...String[19] 297 Let OffsetBits be the low order four bits of String[19] 298 Offset = StToNum(OffSetBits) // 0 <= OffSet <= 15 299 Let P = String[OffSet]...String[OffSet+3] 300 Return the Last 31 bits of P 301 HOTP: An HMAC-based One Time Password Algorithm October 2004 303 The reason for masking the most significant bit of P is to avoid 304 confusion about signed vs. unsigned modulo computations. Different 305 processors perform these operations differently, and masking out 306 the signed bit removes all ambiguity. 308 Implementations MUST extract a 6-digit code at a minimum and 309 possibly 7 and 8-digit code. Depending on security requirements, 310 Digit = 7 or more SHOULD be considered in order to extract a longer 311 HOTP value. 313 The following paragraph is an example of using this technique for 314 Digit = 6, i.e. that a 6-digit HOTP value is calculated from the 315 HMAC value. 317 5.4 Example of HOTP computation for Digit = 6 319 The following code example describes the extraction of a dynamic 320 binary code given that hmac_result is a byte array with the HMAC- 321 SHA1 result: 323 int offset = hmac_result[19] & 0xf ; 324 int bin_code = (hmac_result[offset] & 0x7f) << 24 325 | (hmac_result[offset+1] & 0xff) << 16 326 | (hmac_result[offset+2] & 0xff) << 8 327 | (hmac_result[offset+3] & 0xff) ; 329 SHA-1 HMAC Bytes (Example) 331 ------------------------------------------------------------- 332 | Byte Number | 333 ------------------------------------------------------------- 334 |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19| 335 ------------------------------------------------------------- 336 | Byte Value | 337 ------------------------------------------------------------- 338 |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a| 339 -------------------------------***********----------------++| 341 * The last byte (byte 19) has the hex value 0x5a. 342 * The value of the lower four bits is 0xa (the offset value). 343 * The offset value is byte 10 (0xa). 344 * The value of the 4 bytes starting at byte 10 is 0x50ef7f19, 345 which is the dynamic binary code DBC1 346 * The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19 347 * HOTP = DBC2 modulo 10^6 = 872921. 349 We treat the dynamic binary code as a 31-bit, unsigned, big-endian 350 integer; the first byte is masked with a 0x7f. 352 HOTP: An HMAC-based One Time Password Algorithm October 2004 354 We then take this number modulo 1,000,000 (10^6) to generate the 6- 355 digit HOTP value 872921 decimal. 357 6. Security and Deployment Considerations 359 Any One-Time Password algorithm is only as secure as the 360 application and the authentication protocols that implement it. 361 Therefore, this section discusses the critical security 362 requirements that our choice of algorithm imposes on the 363 authentication protocol and validation software. The parameters T 364 and s discussed in this section have a significant impact on the 365 security û further details in Section 7 elaborate on the relations 366 between these parameters and their impact on the system security. 368 6.1 Authentication Protocol Requirements 370 We introduce in this section some requirements for a protocol P 371 implementing HOTP as the authentication method between a prover and 372 a verifier. 374 RP1 - P MUST be two-factor, i.e. something you know (secret code 375 such as a Password, Pass phrase, PIN code, etc.) and something you 376 have (token). The secret code is known only to the user and usually 377 entered with the one-time password value for authentication purpose 378 (two-factor authentication). 380 RP3 - P MUST NOT be vulnerable to brute force attacks. This implies 381 that a throttling/lockout scheme is REQUIRED on the validation 382 server side. 384 RP4 û P SHOULD be implemented with respect to the state of the art 385 in terms of security, in order to avoid the usual attacks and risks 386 associated with the transmission of sensitive data over a public 387 network (privacy, replay attacks, etc.) 389 6.2 Validation of HOTP values 391 The HOTP client (hardware or software token) increments its counter 392 and then calculates the next HOTP value HOTP-client. If the value 393 received by the authentication server matches the value calculated 394 by the client, then the HOTP value is validated. In this case, the 395 server increments the counter value by one. 397 If the value received by the server does not match the value 398 calculated by the client, the server initiate the resynch protocol 399 (look-ahead window) before it requests another pass. 401 HOTP: An HMAC-based One Time Password Algorithm October 2004 403 If the resynch fails, the server asks then for another 404 authentication pass of the protocol to take place, until the 405 maximum number of authorized attempts is reached. 407 If and when the maximum number of authorized attempts is reached, 408 the server SHOULD lock out the account and initiate a procedure to 409 inform the user. 411 6.3 Throttling at the server 413 Truncating the HMAC-SHA1 value to a shorter value makes a brute 414 force attack possible. Therefore, the authentication server needs 415 to detect and stop brute force attacks. 417 We RECOMMEND setting a throttling parameter T, which defines the 418 maximum number of possible attempts for One-Time-Password 419 validation. The validation server manages individual counters per 420 HOTP device in order to take note of any failed attempt. We 421 RECOMMEND T not to be too large, particularly if the 422 resynchronization method used on the server is window-based, and 423 the window size is large. T SHOULD be set as low as possible, while 424 still ensuring usability is not significantly impacted. 426 6.4 Resynchronization of the counter 428 Although the serverÆs counter value is only incremented after a 429 successful HOTP authentication, the counter on the token is 430 incremented every time a new HOTP is requested by the user. Because 431 of this, the counter values on the server and on the token might be 432 out of synchronization. 434 We RECOMMEND setting a look-ahead parameter s on the server, which 435 defines the size of the look-ahead window. In a nutshell, the 436 server can recalculate the next s HOTP-server values, and check 437 them against the received HOTP-client. 439 Synchronization of counters in this scenario simply requires the 440 server to calculate the next HOTP values and determine if there is 441 a match. Optionally, the system MAY require the user to send a 442 sequence of (say 2, 3) HOTP values for resynchronization purpose, 443 since forging a sequence of consecutive HOTP values is even more 444 difficult than guessing a single HOTP value. 446 The upper bound set by the parameter s ensures the server does not 447 go on checking HOTP values forever (causing a DoS attack) and also 448 restricts the space of possible solutions for an attacker trying to 449 manufacture HOTP values. s SHOULD be set as low as possible, while 450 still ensuring usability is not impacted. 452 HOTP: An HMAC-based One Time Password Algorithm October 2004 454 7. HOTP Algorithm Security: Overview 456 The conclusion of the security analysis detailed in the Appendix 457 section is that, for all practical purposes, the outputs of HOTP on 458 distinct counter inputs are uniformly and independently distributed 459 strings. 461 As a result, the best possible attack against the HOTP function is 462 the brute force attack. 464 Assuming an adversary is able to observe numerous protocol 465 exchanges and collect sequences of successful authentication 466 values. This adversary, trying to build a function F to generate 467 HOTP values based on his observations, will not have a significant 468 advantage over a random guess. 470 The logical conclusion is simply that is best strategy will once 471 again be to perform a brute force attack to enumerate and try all 472 the possible values. 474 Considering the security analysis in the Appendix section of this 475 document, without loss of generality, we can approximate closely 476 the security of the HOTP algorithm by the following formula: 478 Sec = sv/10^Digit 480 Where: 481 - Sec is the probability of success of the adversary 482 - s stands for the look-ahead synchronization window size; 483 - v stands for the number of verification attempts; 484 - Digit stands for the number of digits in HOTP values. 486 Obviously, we can play with s, T (the Throttling parameter that 487 would limit the number of attempts by an attacker) and Digit until 488 achieving a certain level of security, still preserving the system 489 usability. 491 8. Protocol Extensions and Improvements 493 We introduce in this section several enhancements and suggestions 494 to further improve the security of the algorithm HOTP 496 8.1 Number of Digits 498 A simple enhancement in terms of security would be to extract more 499 digits from the HMAC-SHA1 value. 501 HOTP: An HMAC-based One Time Password Algorithm October 2004 503 For instance, calculating the HOTP value modulo 10^8 to build an 8- 504 digit HOTP value would reduce the probability of success of the 505 adversary from sv/10^6 to sv/10^8. 507 This could give the opportunity to improve usability, e.g. by 508 increasing T and/or s, while still achieving a better security 509 overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which 510 is the theoretical optimum for 6-digit code when s = 1. 512 8.2 Alpha-numeric Values 514 Another option is to use A-Z and 0-9 values; or rather a subset of 515 32 symbols taken from the alphanumerical alphabet in order to avoid 516 any confusion between characters: 0, O and Q as well as l, 1 and I 517 are very similar, and can look the same on a small display. 519 The immediate consequence is that the security is now in the order 520 of sv/32^6 for a 6-digit HOTP value and sv/32^8 for an 8-digit HOTP 521 value. 523 32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is 524 slightly better than a 9-digit HOTP value, which is the maximum 525 length of an HOTP code supported by the proposed algorithm. 527 32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is 528 significantly better than a 9-digit HOTP value. 530 Depending on the application and token/interface used for 531 displaying and entering the HOTP value, the choice of alphanumeric 532 values could be a simple and efficient way to improve security at a 533 reduced cost and impact on users. 535 8.3 Sequence of HOTP values 537 As we suggested for the resynchronization to enter a short sequence 538 (say 2 or 3) of HOTP values, we could generalize the concept to the 539 protocol, and add a parameter L that would define the length of the 540 HOTP sequence to enter. 542 Per default, the value L SHOULD be set to 1, but if security needs 543 to be increased, users might be asked (possibly for a short period 544 of time, or a specific operation) to enter L HOTP values. 546 This is another way, without increasing the HOTP length or using 547 alphanumeric values to tighten security. 549 Note: The system MAY also be programmed to request synchronization 550 on a regular basis (e.g. every night, or twice a week, etc.) and to 551 achieve this purpose, ask for a sequence of L HOTP values. 553 HOTP: An HMAC-based One Time Password Algorithm October 2004 555 8.4 A Counter-based Re-Synchronization Method 557 In this case, we assume that the client can access and send not 558 only the HOTP value but also other information, more specifically 559 the counter value. 561 A more efficient and secure method for resynchronization is 562 possible in this case. The client application will not send the 563 HOTP-client value only, but the HOTP-client and the related C- 564 client counter value, the HOTP value acting as a message 565 authentication code of the counter. 567 Resynchronization Counter-based Protocol (RCP) 568 ---------------------------------------------- 570 The server accepts if the following are all true, where C-server is 571 its own current counter value: 573 1) C-client >= C-server 574 2) C-client û C-server <= s 575 3) Check that HOTP-client is valid HOTP(K,C-Client) 576 4) If true, the server sets C to C-client + 1 and client 577 is authenticated 579 In this case, there is no need for managing a look-ahead window 580 anymore. The probability of success of the adversary is only v/10^6 581 or roughly v in one million. A side benefit is obviously to be able 582 to increase s ôinfinitelyö and therefore improve the system 583 usability without impacting the security. 585 This resynchronization protocol SHOULD be use whenever the related 586 impact on the client and server applications is deemed acceptable. 588 9. Conclusion 590 This draft describes HOTP, a HMAC-based One-Time Password 591 algorithm. It also recommends the preferred implementation and 592 related modes of operations for deploying the algorithm. 594 The draft also exhibits elements of security and demonstrates that 595 the HOTP algorithm is practical and sound, the best possible attack 596 being a brute force attack that can be prevented by careful 597 implementation of countermeasures in the validation server. 599 Eventually, several enhancements have been proposed, in order to 600 improve security if needed for specific applications. 602 HOTP: An HMAC-based One Time Password Algorithm October 2004 604 10. Acknowledgements 606 The authors would like to thank Siddharth Bajaj, Alex Deacon and 607 Nico Popp for their help during the conception and redaction of 608 this document. 610 11. Contributors 612 The authors of this draft would like to emphasize the role of two 613 persons who have made a key contribution to this document: 615 - Laszlo Elteto is system architect with SafeNet, Inc. 617 - Ernesto Frutos is director of Engineering with Authenex, Inc. 619 Without their advice and valuable inputs, this draft would not be 620 the same. 622 12. References 624 12.1 Normative 626 [BCK1] M. Bellare, R. Canetti, and H. Krawczyk, Keyed Hash 627 Functions and Message Authentication, Proceedings of 628 Crypto'96, LNCS Vol. 1109, pp. 1-15. 630 [BCK2] M. Bellare, R. Canetti, and H. Krawczyk, HMAC: 631 Keyed-Hashing for Message Authentication, IETF Network 632 Working Group, RFC 2104, February 1997. 634 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 635 Requirement Levels", BCP 14, RFC 2119, March 1997. 637 [RFC3668] Bradner, S., "Intellectual Propery Rights in IETF 638 Technologyö, BCP 79, RFC 3668, February 2004. 640 12.2 Informative 642 [OATH] www.openauthentication.org, Initiative for Open 643 AuTHentication 645 13. AuthorsÆ Addresses 647 Primary point of contact (for sending comments and question): 649 David M'Raihi 650 VeriSign, Inc. 651 685 E. Middlefield Road Phone: 1-650-426-3832 652 Mountain View, CA 94043 USA Email: dmraihi@verisign.com 653 HOTP: An HMAC-based One Time Password Algorithm October 2004 655 Other AuthorsÆ contact information: 657 Mihir Bellare 658 Dept of Computer Science and Engineering, Mail Code 0114 659 University of California at San Diego 660 9500 Gilman Drive 661 La Jolla, CA 92093, USA Email: mihir@cs.ucsd.edu 663 Frank Hoornaert 664 VASCO Data Security, Inc. 665 Koningin Astridlaan 164 666 1780 Wemmel, Belgium Email: frh@vasco.com 668 David Naccache 669 Gemplus Innovation 670 34 rue Guynemer, 92447, 671 Issy les Moulineaux, France Email: david.naccache@gemplus.com 672 and 673 Information Security Group, 674 Royal Holloway, 675 University of London, Egham, 676 Surrey TW20 0EX, UK Email: david.naccache@rhul.ac.uk 678 Ohad Ranen 679 Aladdin Knowledge Systems Ltd. 680 15 Beit Oved Street 681 Tel Aviv, Israel 61110 Email: Ohad.Ranen@ealaddin.com 683 Appendix - HOTP Algorithm Security: Detailed Analysis 685 The security analysis of the HOTP algorithm is summarized in this 686 section. We first detail the best attack strategies, and then 687 elaborate on the security under various assumptions, the impact of 688 the truncation and some recommendations regarding the number of 689 digits. 691 We focus this analysis on the case where Digit = 6, i.e. an HOTP 692 function that produces 6-digit values, which is the bare minimum 693 recommended in this draft. 695 A.1 Definitions and Notations 697 We denote by {0,1}^l the set of all strings of length l. 699 Let Z_{n} = {0,.., n - 1}. 701 HOTP: An HMAC-based One Time Password Algorithm October 2004 703 Let IntDiv(a,b) denote the integer division algorithm that takes 704 input integers a, b where a >= b >= 1 and returns integers (q,r) 705 the quotient and remainder, respectively, of the division of a by 706 b. (Thus a = bq + r and 0 <= r < b.) 708 Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that 709 takes a k-bit key K and c-bit counter C and returns an n-bit output 710 H(K,C). (In the case of HOTP, H is HMAC-SHA-1; we use this formal 711 definition for generalizing our proof of security) 713 A.2 The idealized algorithm: HOTP-IDEAL 715 We now define an idealized counterpart of the HOTP algorithm. In 716 this algorithm, the role of H is played by a random function that 717 forms the key. 719 To be more precise, let Maps(c,n) denote the set of all functions 720 mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key 721 space Maps(c,n), so that a ôkeyö for such an algorithm is a 722 function h from {0,1}^c to {0,1}^n. We imagine this key (function) 723 to be drawn at random. It is not feasible to implement this 724 idealized algorithm, since the key, being a function from is way 725 too large to even store. So why consider it? 727 Our security analysis will show that as long as H satisfies a 728 certain well-accepted assumption, the security of the actual and 729 idealized algorithms is for all practical purposes the same. The 730 task that really faces us, then, is to assess the security of the 731 idealized algorithm. 733 In analyzing the idealized algorithm, we are concentrating on 734 assessing the quality of the design of the algorithm itself, 735 independently of HMAC-SHA-1. This is in fact the important issue. 737 A.3 Model of Security 739 The model exhibits the type of threats or attacks that are being 740 considered and enables to asses the security of HOTP and HOTP- 741 IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the purpose 742 of this security analysis. 744 The scenario we are considering is that a user and server share a 745 key K for ALG. Both maintain a counter C, initially zero, and the 746 user authenticates itself by sending ALG(K,C) to the server. The 747 latter accepts if this value is correct. 749 In order to protect against accidental increment of the user 750 counter, the server, upon receiving a value z, will accept as long 751 HOTP: An HMAC-based One Time Password Algorithm October 2004 753 as z equals ALG(K,i) for some i in the range C,...,C + s-1, where s 754 is the resynchronization parameter and C is the server counter. If 755 it accepts with some value of i, it then increments its counter to 756 i+ 1. If it does not accept, it does not change its counter value. 758 The model we specify captures what an adversary can do and what it 759 needs to achieve in order to ôwin.ö First, the adversary is assumed 760 to be able to eavesdrop, meaning see the authenticator transmitted 761 by the user. Second, the adversary wins if it can get the server to 762 accept an authenticator relative to a counter value for which the 763 user has never transmitted an authenticator. 765 The formal adversary, which we denote by B, starts out knowing 766 which algorithm ALG is being used, knowing the system design and 767 knowing all system parameters. The one and only thing it is not 768 given a priori is the key K shared between the user and the server. 770 The model gives B full control of the scheduling of events. It has 771 access to an authenticator oracle representing the user. By calling 772 this oracle, the adversary can ask the user to authenticate itself 773 and get back the authenticator in return. It can call this oracle 774 as often as it wants and when it wants, using the authenticators it 775 accumulates to perhaps ôlearnö how to make authenticators itself. 776 At any time, it may also call a verification oracle, supplying the 777 latter with a candidate authenticator of its choice. It wins if the 778 server accepts this accumulator. 780 Consider the following game involving an adversary B that is 781 attempting to compromise the security of an authentication 782 algorithm ALG: K x {0,1}^c --> R. 784 Initializations - A key K is selected at random from K, a counter C 785 is initialized to 0, and the Boolean value win is set to false. 787 Game execution - Adversary B is provided with the two following 788 oracles: 790 Oracle AuthO() 791 O = ALG(K,C) 792 C = C + 1 793 Return O to B 795 Oracle VerO() 796 i = C 797 While (i <= C + s - 1 and Win = FALSE) do 798 If O = ALG(K,i) then Win = TRUE; C = i + 1 799 Else i = i + 1 800 Return Win to B 801 HOTP: An HMAC-based One Time Password Algorithm October 2004 803 AuthO() is the authenticator oracle and VerO() is the verification 804 oracle. 806 Upon execution, B queries the two oracles at will. Let Adv(B) be 807 the probability that win gets set to true in the above game. This 808 is the probability that the adversary successfully impersonates the 809 user. 811 Our goal is to assess how large this value can be as a function of 812 the number v of verification queries made by B, the number a of 813 authenticator oracle queries made by B, and the running time t of 814 B. This will tell us how to set the throttle, which effectively 815 upper bounds v. 817 A.4 Security of the ideal authentication algorithm 819 This section summarizes the security analysis of HOTP-IDEAL, 820 starting with the impact of the conversion modulo 10^Digit and 821 then, focusing on the different possible attacks. 823 A.4.1 From bits to digits 825 The dynamic offset truncation of a random n-bit string yields a 826 random 31-bit string. What happens to the distribution when it is 827 taken modulo m = 10^Digit, as done in HOTP? 829 The following lemma estimates the biases in the outputs in this 830 case. 832 Lemma 1 833 Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in 834 Z_{m} let: 836 P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}] 838 Then for any z in Z_{m} 840 P_{N,m}(z) = (q + 1) / N if 0 <= z < r 841 q / N if r <= z < m 843 Proof of Lemma 1 844 Let the random variable X be uniformly distributed over Z_{N}. 845 Then: 847 P_{N,m}(z) = Pr [X mod m = z] 849 = Pr [X < mq] ¸ Pr [X mod m = z| X < mq] 850 + Pr [mq <= X < N] ¸ Pr [X mod m = z| mq <= X < N] 851 HOTP: An HMAC-based One Time Password Algorithm October 2004 853 = mq/N ¸ 1/m + 854 (N - mq)/N ¸ 1 / (N û mq) if 0 <= z < N û mq 855 0 if N û mq <= z <= m 857 = q/N + 858 r/N ¸ 1 / r if 0 <= z < N û mq 859 0 if r <= z <= m 861 Simplifying yields the claimed equation. 863 Let N = 2^31, d = 6 and m = 10^d. If x is chosen at random from 864 Z_{N} (meaning, is a random 31-bit string), then reducing it to a 865 6-digit number by taking x mod m does not yield a random 6-digit 866 number. 868 Rather, x mod m is distributed as shown in the following table: 870 Values Probability that each appears as output 871 ---------------------------------------------------------------- 872 0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6 873 483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6 875 If X is uniformly distributed over Z_{2^31} (meaning is a random 876 31-bit string) then the above shows the probabilities for different 877 outputs of X mod 10^6. The first set of values appear with 878 probability slightly greater than 10^-6, the rest with probability 879 slightly less, meaning the distribution is slightly non-uniform. 881 However, as the Figure indicates, the bias is small and as we will 882 see later, negligible: the probabilities are very close to 10^-6. 884 A.4.2 Brute force attacks 886 If the authenticator consisted of d random digits, then a brute 887 force attack using v verification attempts would succeed with 888 probability sv/10^Digit. 890 However, an adversary can exploit the bias in the outputs of HOTP- 891 IDEAL, predicted by Lemma 1, to mount a slightly better attack. 893 Namely, it makes authentication attempts with authenticators which 894 are the most likely values, meaning the ones in the range 0,...,r - 895 1, where (q,r) = IntDiv(2^31,10^Digit). 897 The following specifies an adversary in our model of security that 898 mounts the attack. It estimates the success probability as a 899 function of the number of verification queries. 901 HOTP: An HMAC-based One Time Password Algorithm October 2004 903 For simplicity, we assume the number of verification queries is at 904 most r. With N = 2^31 and m = 10^6 we have r = 483,648, and the 905 throttle value is certainly less than this, so this assumption is 906 not much of a restriction. 908 Proposition 1 909 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume 910 s <= m. The brute-force attack adversary B-bf attacks HOTP using v 911 <= r verification oracle queries. This adversary makes no 912 authenticator oracle queries, and succeeds with probability 914 Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s 916 which is roughly equals to 918 sv ¸ (q+1)/2^31 920 With m = 10^6 we get q = 2,147. In that case, the brute force 921 attack using v verification attempts succeeds with probability 923 Adv(B-bf) roughly = sv ¸ 2148/2^31 = sv ¸ 1.00024045/10^6 925 As this equation shows, the resynchronization parameter s has a 926 significant impact in that the adversaryÆs success probability is 927 proportional to s. This means that s cannot be made too large 928 without compromising security. 930 A.4.3 Brute force attacks are the best possible attacks 932 A central question is whether there are attacks any better than the 933 brute force one. In particular, the brute force attack did not 934 attempt to collect authenticators sent by the user and try to 935 cryptanalyze them in an attempt to learn how to better construct 936 authenticators. Would doing this help? Is there some way to ôlearnö 937 how to build authenticators that result in a higher success rate 938 than given by the brute-force attack? 940 The following says the answer to these questions is no. No matter 941 what strategy the adversary uses, and even if it sees, and tries to 942 exploit, the authenticators from authentication attempts of the 943 user, its success probability will not be above that of the brute 944 force attack - this is true as long as the number of 945 authentications it observes is not incredibly large. This is 946 valuable information regarding the security of the scheme. 948 Proposition 2 949 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B 950 be any adversary attacking HOTP-IDEAL using v verification oracle 951 queries and a <= 2^c û s authenticator oracle queries. Then 952 HOTP: An HMAC-based One Time Password Algorithm October 2004 954 Adv(B) < = sv ¸ (q+1)/ 2^31 956 Note: This result is conditional on the adversary not seeing more 957 than 2^c - s authentications performed by the user, which is hardly 958 restrictive as long as c is large enough. 960 With m = 10^6 we get q = 2,147. In that case, Proposition 2 says 961 that any adversary B attacking HOTP-IDEAL and making v verification 962 attempts succeeds with probability at most 964 Equation 1 965 sv ¸ 2148/2^31 roughly = sv ¸ 1.00024045/10^6 967 Meaning, BÆs success rate is not more than that achieved by the 968 brute force attack. 970 A.5 Security Analysis of HOTP 972 We have analyzed in the previous sections, the security of the 973 idealized counterparts HOTP-IDEAL of the actual authentication 974 algorithm HOTP. We now show that, under appropriate and well- 975 believed assumption on H, the security of the actual algorithms is 976 essentially the same as that of its idealized counterpart. 978 The assumption in question is that H is a secure pseudorandom 979 function, or PRF, meaning that its input-output values are 980 indistinguishable from those of a random function in practice. 982 Consider an adversary A that is given an oracle for a function f: 983 {0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A) 984 as the prf-advantage of A, which represents how well the adversary 985 does at distinguishing the case where its oracle is H(K,.) from the 986 case where its oracle is a random function of {0,1}^c to {0,1}^n. 988 One possible attack is based on exhaustive search for the key K. If 989 A runs for t steps and T denotes the time to perform one 990 computation of H, its prf-advantage from this attack turns out to 991 be (t/T)2^-k . Another possible attack is a birthday one [3], 992 whereby A can attain advantage p^2/2^n in p oracle queries and 993 running time about pT. 995 Our assumption is that these are the best possible attacks. This 996 translates into the following. 998 Assumption 1 999 Let T denotes the time to perform one computation of H. Then if A 1000 is any adversary with running time at most t and making at most p 1001 oracle queries, 1002 HOTP: An HMAC-based One Time Password Algorithm October 2004 1004 Adv(A) <= (t/T)/2^k + p^2/2^n 1006 In practice this assumption means that H is very secure as PRF. For 1007 example, given that k = n = 160, an attacker with running time 2^60 1008 and making 2^40 oracle queries has advantage at most (about) 2^-80. 1010 Theorem 1 1011 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B 1012 be any adversary attacking HOTP using v verification oracle 1013 queries, a <= 2^c - s authenticator oracle queries, and running 1014 time t. Let T denote the time to perform one computation of H. If 1015 Assumption 1 is true then 1017 Adv(B) <= sv ¸ (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n 1019 In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller 1020 than the sv(q + 1)/2^n term, so that the above says that for all 1021 practical purposes the success rate of an adversary attacking HOTP 1022 is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP 1023 algorithm is in practice essentially as good as its idealized 1024 counterpart. 1026 In the case m = 10^6 of a 6-digit output this means that an 1027 adversary making v authentication attempts will have a success rate 1028 that is at most that of Equation 1. 1030 For example, consider an adversary with running time at most 2^60 1031 that sees at most 2^40 authentication attempts of the user. Both 1032 these choices are very generous to the adversary, who will 1033 typically not have these resources, but we are saying that even 1034 such a powerful adversary will not have more success than indicated 1035 by Equation 1. 1037 We can safely assume sv <= 2^40 due to the throttling and bounds on 1038 s. So: 1039 (t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160 1040 roughly <= 2^-78 1042 which is much smaller than the success probability of Equation 1 1043 and negligible compared to it. 1045 Full Copyright Statement 1047 Copyright (C) The Internet Society 2004. This document is subject 1048 to the rights, licenses and restrictions contained in BCP 78, and 1049 except as set forth therein, the authors retain all their rights. 1051 HOTP: An HMAC-based One Time Password Algorithm October 2004 1053 This document and the information contained herein are provided on 1054 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 1055 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND 1056 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, 1057 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT 1058 THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 1059 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 1060 PARTICULAR PURPOSE.