idnits 2.17.00 (12 Aug 2021) /tmp/idnits21086/draft-mraihi-oath-hmac-otp-01.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 1072. ** 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? 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.) ** The document seems to lack an Authors' Addresses Section. ** 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 == Line 252 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 633 looks like a reference -- Missing reference section? 'RFC3668' on line 644 looks like a reference -- Missing reference section? 'OATH' on line 649 looks like a reference -- Missing reference section? '0' on line 298 looks like a reference -- Missing reference section? '1' on line 226 looks like a reference -- Missing reference section? 'BCK2' on line 637 looks like a reference -- Missing reference section? '19' on line 325 looks like a reference -- Missing reference section? 'OffSet' on line 301 looks like a reference -- Missing reference section? 'RFC2119' on line 641 looks like a reference -- Missing reference section? '3' on line 1002 looks like a reference Summary: 14 errors (**), 0 flaws (~~), 2 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-01.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 25 Internet-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........................................11 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.................................15 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, 127 single-function device that is only used to authenticate to the 128 network is clearly not the right answer. For two factor 129 authentication to propagate on the Internet, it will have to be 130 embedded in more flexible devices that can work across a wide range 131 of applications. 133 The ability to embed this base technology while ensuring broad 134 interoperability require that it be made freely available to the 135 broad technical community of hardware and software developers. Only 136 an open system approach will ensure that basic two-factor 137 authentication primitives can be built into the next-generation of 138 consumer devices such USB mass storage devices, IP phones, and 139 personal digital assistants). 141 One Time Password is certainly one of the simplest and most popular 142 forms of two-factor authentication for securing network access. For 143 example, in large enterprises, Virtual Private Network access often 144 requires the use of One Time Password tokens for remote user 145 authentication. One Time Passwords are often preferred to stronger 146 forms of authentication such as PKI or biometrics because an 147 air-gap device does not require the installation of any client 148 desktop software on the user machine, therefore allowing them to 149 roam across multiple machines including home computers, kiosks and 150 personal digital assistants. 152 HOTP: An HMAC-based One Time Password Algorithm October 2004 154 This draft proposes a simple One Time Password algorithm that can 155 be implemented by any hardware manufacturer or software developer 156 to create interoperable authentication devices and software agents. 157 The algorithm is event-based so that it can be embedded in high 158 volume devices such as Java smart cards, USB dongles and GSM SIM 159 cards. The presented algorithm is made freely available to the 160 developer community under the terms and conditions of the IETF 161 Intellectual Property Rights [RFC3668]. 163 The authors of this document are members of the Open AuTHentication 164 initiative [OATH]. The initiative was created in 2004 to facilitate 165 collaboration among strong authentication technology providers. 167 3. Requirements Terminology 169 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 170 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 171 this document are to be interpreted as described in RFC 2119. 173 4. Algorithm Requirements 175 This section presents the main requirements that drove this 176 algorithm design. A lot of emphasis was placed on end-consumer 177 usability as well as the ability for the algorithm to be 178 implemented by low cost hardware that may provide minimal user 179 interface capabilities. In particular, the ability to embed the 180 algorithm into high volume SIM and Java cards was a fundamental 181 pre-requisite. 183 R1 - The algorithm MUST be sequence or counter-based: One of the 184 goals is to have the HOTP algorithm embedded in high volume devices 185 such as Java smart cards, USB dongles and GSM SIM cards. 187 R2 - The algorithm SHOULD be economical to implement in hardware by 188 minimizing requirements on battery, number of buttons, 189 computational horsepower, and size of LCD display. The algorithm 190 MUST work with tokens that do not supports any numeric input, but 191 MAY also be used with more sophisticated devices such as secure 192 PIN-pads. 194 R3 - The value displayed on the token MUST be easily read and 195 entered by the user: This requires the HOTP value to be of 196 reasonable length. The HOTP value must be at least a 6-digit value. 197 It is also desirable that the HOTP value be 'numeric only' so that 198 it can be easily entered on restricted devices such as phones. 200 R4 - There MUST be user-friendly mechanisms available to 201 resynchronize the counter. The sections 6.4 and 8.4 detail the 202 resynchronization mechanism proposed in this draft. 204 HOTP: An HMAC-based One Time Password Algorithm October 2004 206 R5 - The algorithm MUST use a strong shared secret. The length of 207 the shared secret MUST be at least 128 bits. This draft RECOMMENDs 208 a shared secret length of 160 bits. 210 5. HOTP Algorithm 212 In this section, we introduce the notation and describe the HOTP 213 algorithm basic blocks - the base function to compute an HMAC-SHA-1 214 value and the truncation method to extract an HOTP value. 216 5.1 Notation and Symbols 218 A string always means a binary string, meaning a sequence of zeros 219 and ones. 221 If s is a string then |s| denotes its length. 223 If n is a number then |n| denotes its absolute value. 225 If s is a string then s[i] denotes its i-th bit. We start numbering 226 the bits at 0, so s = s[0]s[1]..s[n-1] where n = |s| is the length 227 of s. 229 Let StToNum (String to Number) denote the function which as input a 230 string s returns the number whose binary representation is s. 231 (For example StToNum(110) = 6). 233 Here is a list of symbols used in this document. 235 Symbol Represents 236 ------------------------------------------------------------------- 237 C 8-byte (Little Endian) counter value, which is 238 The moving factor. This counter MUST be synchronized 239 between the HOTP generator (client) and the 240 HOTP validator (server); 242 K shared secret between client and server; each HOTP 243 generator has a different and unique secret K; 245 T throttling parameter: the server will refuse connections 246 from a user after T unsuccessful authentication attempts; 248 s resynchronization parameter: the server will attempt to 249 verify a received authenticator across s consecutive 250 counter values; 252 Digit number of digits in an HOTP value; system parameter. 254 HOTP: An HMAC-based One Time Password Algorithm October 2004 256 5.2 Description 258 The HOTP algorithm is based on an increasing counter value and a 259 static symmetric key known only to the token and the validation 260 service. In order to create the HOTP value, we will use the 261 HMAC-SHA-1 algorithm, as defined in RFC 2104 [BCK2]. 263 As the output of the HMAC-SHA1 calculation is 160 bits, we must 264 truncate this value to something that can be easily entered by a 265 user. 267 HOTP(K,C) = Truncate(HMAC-SHA-1(K,C)) 269 Where: 270 - Truncate represents the function that converts an HMAC-SHA-1 271 value into an HOTP value as defined in Section 5.3. 273 The HOTP values generated by the HOTP generator are treated as big 274 endian. 276 5.3 Generating an HOTP value 278 We can describe the operations in 3 distinct steps: 280 Step 1: Generate an HMAC-SHA-1 value 281 Let HS = HMAC-SHA-1(K,C) // HS is a 20 byte string 283 Step 2: Generate a 4-byte string (Dynamic Truncation) 284 Let Sbits = DT(HS) // DT, defined in Section 6.3.1 285 // returns a 31 bit string 287 Step 3: Compute an HOTP value 288 Let Snum = StToNum(S) // Convert S to a number in 289 0...2^{31}-1 290 Return D = Snum mod 10^Digit // D is a number in the range 291 0...10^{Digit}-1 293 The Truncate function performs Step 2 and Step 3, i.e. the dynamic 294 truncation and then the reduction modulo 10^Digit. The purpose of 295 the dynamic offset truncation technique is to extract a 4-byte 296 dynamic binary code from a 160-bit (20-byte) HMAC-SHA1 result. 298 DT(String) // String = String[0]...String[19] 299 Let OffsetBits be the low order four bits of String[19] 300 Offset = StToNum(OffSetBits) // 0 <= OffSet <= 15 301 Let P = String[OffSet]...String[OffSet+3] 302 Return the Last 31 bits of P 303 HOTP: An HMAC-based One Time Password Algorithm October 2004 305 The reason for masking the most significant bit of P is to avoid 306 confusion about signed vs. unsigned modulo computations. Different 307 processors perform these operations differently, and masking out 308 the signed bit removes all ambiguity. 310 Implementations MUST extract a 6-digit code at a minimum and 311 possibly 7 and 8-digit code. Depending on security requirements, 312 Digit = 7 or more SHOULD be considered in order to extract a longer 313 HOTP value. 315 The following paragraph is an example of using this technique for 316 Digit = 6, i.e. that a 6-digit HOTP value is calculated from the 317 HMAC value. 319 5.4 Example of HOTP computation for Digit = 6 321 The following code example describes the extraction of a dynamic 322 binary code given that hmac_result is a byte array with the 323 HMAC-SHA1 result: 325 int offset = hmac_result[19] & 0xf ; 326 int bin_code = (hmac_result[offset] & 0x7f) << 24 327 | (hmac_result[offset+1] & 0xff) << 16 328 | (hmac_result[offset+2] & 0xff) << 8 329 | (hmac_result[offset+3] & 0xff) ; 331 SHA-1 HMAC Bytes (Example) 333 ------------------------------------------------------------- 334 | Byte Number | 335 ------------------------------------------------------------- 336 |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19| 337 ------------------------------------------------------------- 338 | Byte Value | 339 ------------------------------------------------------------- 340 |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a| 341 -------------------------------***********----------------++| 343 * The last byte (byte 19) has the hex value 0x5a. 344 * The value of the lower four bits is 0xa (the offset value). 345 * The offset value is byte 10 (0xa). 346 * The value of the 4 bytes starting at byte 10 is 0x50ef7f19, 347 which is the dynamic binary code DBC1 348 * The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19 349 * HOTP = DBC2 modulo 10^6 = 872921. 351 We treat the dynamic binary code as a 31-bit, unsigned, big-endian 352 integer; the first byte is masked with a 0x7f. 354 HOTP: An HMAC-based One Time Password Algorithm October 2004 356 We then take this number modulo 1,000,000 (10^6) to generate the 357 6-digit HOTP value 872921 decimal. 359 6. Security and Deployment Considerations 361 Any One-Time Password algorithm is only as secure as the 362 application and the authentication protocols that implement it. 363 Therefore, this section discusses the critical security 364 requirements that our choice of algorithm imposes on the 365 authentication protocol and validation software. The parameters T 366 and s discussed in this section have a significant impact on the 367 security - further details in Section 7 elaborate on the relations 368 between these parameters and their impact on the system security. 370 6.1 Authentication Protocol Requirements 372 We introduce in this section some requirements for a protocol P 373 implementing HOTP as the authentication method between a prover and 374 a verifier. 376 RP1 - P MUST be two-factor, i.e. something you know (secret code 377 such as a Password, Pass phrase, PIN code, etc.) and something you 378 have (token). The secret code is known only to the user and usually 379 entered with the one-time password value for authentication purpose 380 (two-factor authentication). 382 RP3 - P MUST NOT be vulnerable to brute force attacks. This implies 383 that a throttling/lockout scheme is REQUIRED on the validation 384 server side. 386 RP4 - P SHOULD be implemented with respect to the state of the art 387 in terms of security, in order to avoid the usual attacks and risks 388 associated with the transmission of sensitive data over a public 389 network (privacy, replay attacks, etc.) 391 6.2 Validation of HOTP values 393 The HOTP client (hardware or software token) increments its counter 394 and then calculates the next HOTP value HOTP-client. If the value 395 received by the authentication server matches the value calculated 396 by the client, then the HOTP value is validated. In this case, the 397 server increments the counter value by one. 399 If the value received by the server does not match the value 400 calculated by the client, the server initiate the resynch protocol 401 (look-ahead window) before it requests another pass. 403 HOTP: An HMAC-based One Time Password Algorithm October 2004 405 If the resynch fails, the server asks then for another 406 authentication pass of the protocol to take place, until the 407 maximum number of authorized attempts is reached. 409 If and when the maximum number of authorized attempts is reached, 410 the server SHOULD lock out the account and initiate a procedure to 411 inform the user. 413 6.3 Throttling at the server 415 Truncating the HMAC-SHA1 value to a shorter value makes a brute 416 force attack possible. Therefore, the authentication server needs 417 to detect and stop brute force attacks. 419 We RECOMMEND setting a throttling parameter T, which defines the 420 maximum number of possible attempts for One-Time-Password 421 validation. The validation server manages individual counters per 422 HOTP device in order to take note of any failed attempt. We 423 RECOMMEND T not to be too large, particularly if the 424 resynchronization method used on the server is window-based, and 425 the window size is large. T SHOULD be set as low as possible, while 426 still ensuring usability is not significantly impacted. 428 6.4 Resynchronization of the counter 430 Although the server's counter value is only incremented after a 431 successful HOTP authentication, the counter on the token is 432 incremented every time a new HOTP is requested by the user. Because 433 of this, the counter values on the server and on the token might be 434 out of synchronization. 436 We RECOMMEND setting a look-ahead parameter s on the server, which 437 defines the size of the look-ahead window. In a nutshell, the 438 server can recalculate the next s HOTP-server values, and check 439 them against the received HOTP-client. 441 Synchronization of counters in this scenario simply requires the 442 server to calculate the next HOTP values and determine if there is 443 a match. Optionally, the system MAY require the user to send a 444 sequence of (say 2, 3) HOTP values for resynchronization purpose, 445 since forging a sequence of consecutive HOTP values is even more 446 difficult than guessing a single HOTP value. 448 The upper bound set by the parameter s ensures the server does not 449 go on checking HOTP values forever (causing a DoS attack) and also 450 restricts the space of possible solutions for an attacker trying to 451 manufacture HOTP values. s SHOULD be set as low as possible, while 452 still ensuring usability is not impacted. 454 HOTP: An HMAC-based One Time Password Algorithm October 2004 456 7. HOTP Algorithm Security: Overview 458 The conclusion of the security analysis detailed in the Appendix 459 section is that, for all practical purposes, the outputs of the 460 dynamic truncation (DT) on distinct counter inputs are uniformly 461 and independently distributed 31-bit strings. 463 The security analysis then details the impact of the conversion 464 from a string to an integer and the final reduction modulo 465 10^Digit, where Digit is the number of digits in an HOTP value. 467 The analysis demonstrates that these final steps introduce a 468 negligible bias, which does not impact the security of the HOTP 469 algorithm, in the sense that the best possible attack against the 470 HOTP function is the brute force attack. 472 Assuming an adversary is able to observe numerous protocol 473 exchanges and collect sequences of successful authentication 474 values. This adversary, trying to build a function F to generate 475 HOTP values based on his observations, will not have a significant 476 advantage over a random guess. 478 The logical conclusion is simply that is best strategy will once 479 again be to perform a brute force attack to enumerate and try all 480 the possible values. 482 Considering the security analysis in the Appendix section of this 483 document, without loss of generality, we can approximate closely 484 the security of the HOTP algorithm by the following formula: 486 Sec = sv/10^Digit 488 Where: 489 - Sec is the probability of success of the adversary 490 - s stands for the look-ahead synchronization window size; 491 - v stands for the number of verification attempts; 492 - Digit stands for the number of digits in HOTP values. 494 Obviously, we can play with s, T (the Throttling parameter that 495 would limit the number of attempts by an attacker) and Digit until 496 achieving a certain level of security, still preserving the system 497 usability. 499 8. Protocol Extensions and Improvements 501 We introduce in this section several enhancements and suggestions 502 to further improve the security of the algorithm HOTP 503 HOTP: An HMAC-based One Time Password Algorithm October 2004 505 8.1 Number of Digits 507 A simple enhancement in terms of security would be to extract more 508 digits from the HMAC-SHA1 value. 510 For instance, calculating the HOTP value modulo 10^8 to build an 511 8-digit HOTP value would reduce the probability of success of the 512 adversary from sv/10^6 to sv/10^8. 514 This could give the opportunity to improve usability, e.g. by 515 increasing T and/or s, while still achieving a better security 516 overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which 517 is the theoretical optimum for 6-digit code when s = 1. 519 8.2 Alpha-numeric Values 521 Another option is to use A-Z and 0-9 values; or rather a subset of 522 32 symbols taken from the alphanumerical alphabet in order to avoid 523 any confusion between characters: 0, O and Q as well as l, 1 and I 524 are very similar, and can look the same on a small display. 526 The immediate consequence is that the security is now in the order 527 of sv/32^6 for a 6-digit HOTP value and sv/32^8 for an 8-digit HOTP 528 value. 530 32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is 531 slightly better than a 9-digit HOTP value, which is the maximum 532 length of an HOTP code supported by the proposed algorithm. 534 32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is 535 significantly better than a 9-digit HOTP value. 537 Depending on the application and token/interface used for 538 displaying and entering the HOTP value, the choice of alphanumeric 539 values could be a simple and efficient way to improve security at a 540 reduced cost and impact on users. 542 8.3 Sequence of HOTP values 544 As we suggested for the resynchronization to enter a short sequence 545 (say 2 or 3) of HOTP values, we could generalize the concept to the 546 protocol, and add a parameter L that would define the length of the 547 HOTP sequence to enter. 549 Per default, the value L SHOULD be set to 1, but if security needs 550 to be increased, users might be asked (possibly for a short period 551 of time, or a specific operation) to enter L HOTP values. 553 HOTP: An HMAC-based One Time Password Algorithm October 2004 555 This is another way, without increasing the HOTP length or using 556 alphanumeric values to tighten security. 558 Note: The system MAY also be programmed to request synchronization 559 on a regular basis (e.g. every night, or twice a week, etc.) and to 560 achieve this purpose, ask for a sequence of L HOTP values. 562 8.4 A Counter-based Re-Synchronization Method 564 In this case, we assume that the client can access and send not 565 only the HOTP value but also other information, more specifically 566 the counter value. 568 A more efficient and secure method for resynchronization is 569 possible in this case. The client application will not send the 570 HOTP-client value only, but the HOTP-client and the related 571 C-client counter value, the HOTP value acting as a message 572 authentication code of the counter. 574 Resynchronization Counter-based Protocol (RCP) 575 ---------------------------------------------- 577 The server accepts if the following are all true, where C-server is 578 its own current counter value: 580 1) C-client >= C-server 581 2) C-client - C-server <= s 582 3) Check that HOTP-client is valid HOTP(K,C-Client) 583 4) If true, the server sets C to C-client + 1 and client 584 is authenticated 586 In this case, there is no need for managing a look-ahead window 587 anymore. The probability of success of the adversary is only v/10^6 588 or roughly v in one million. A side benefit is obviously to be able 589 to increase s "infinitely" and therefore improve the system 590 usability without impacting the security. 592 This resynchronization protocol SHOULD be use whenever the related 593 impact on the client and server applications is deemed acceptable. 595 9. Conclusion 597 This draft describes HOTP, a HMAC-based One-Time Password 598 algorithm. It also recommends the preferred implementation and 599 related modes of operations for deploying the algorithm. 601 The draft also exhibits elements of security and demonstrates that 602 the HOTP algorithm is practical and sound, the best possible attack 603 HOTP: An HMAC-based One Time Password Algorithm October 2004 605 being a brute force attack that can be prevented by careful 606 implementation of countermeasures in the validation server. 608 Eventually, several enhancements have been proposed, in order to 609 improve security if needed for specific applications. 611 10. Acknowledgements 613 The authors would like to thank Siddharth Bajaj, Alex Deacon and 614 Nico Popp for their help during the conception and redaction of 615 this document. 617 11. Contributors 619 The authors of this draft would like to emphasize the role of two 620 persons who have made a key contribution to this document: 622 - Laszlo Elteto is system architect with SafeNet, Inc. 624 - Ernesto Frutos is director of Engineering with Authenex, Inc. 626 Without their advice and valuable inputs, this draft would not be 627 the same. 629 12. References 631 12.1 Normative 633 [BCK1] M. Bellare, R. Canetti, and H. Krawczyk, Keyed Hash 634 Functions and Message Authentication, Proceedings of 635 Crypto'96, LNCS Vol. 1109, pp. 1-15. 637 [BCK2] M. Bellare, R. Canetti, and H. Krawczyk, HMAC: 638 Keyed-Hashing for Message Authentication, IETF Network 639 Working Group, RFC 2104, February 1997. 641 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 642 Requirement Levels", BCP 14, RFC 2119, March 1997. 644 [RFC3668] Bradner, S., "Intellectual Propery Rights in IETF 645 Technology", BCP 79, RFC 3668, February 2004. 647 12.2 Informative 649 [OATH] www.openauthentication.org, Initiative for Open 650 AuTHentication 652 13. Authors' Addresses 653 HOTP: An HMAC-based One Time Password Algorithm October 2004 655 Primary point of contact (for sending comments and question): 657 David M'Raihi 658 VeriSign, Inc. 659 685 E. Middlefield Road Phone: 1-650-426-3832 660 Mountain View, CA 94043 USA Email: dmraihi@verisign.com 662 Other Authors' contact information: 664 Mihir Bellare 665 Dept of Computer Science and Engineering, Mail Code 0114 666 University of California at San Diego 667 9500 Gilman Drive 668 La Jolla, CA 92093, USA Email: mihir@cs.ucsd.edu 670 Frank Hoornaert 671 VASCO Data Security, Inc. 672 Koningin Astridlaan 164 673 1780 Wemmel, Belgium Email: frh@vasco.com 675 David Naccache 676 Gemplus Innovation 677 34 rue Guynemer, 92447, 678 Issy les Moulineaux, France Email: david.naccache@gemplus.com 679 and 680 Information Security Group, 681 Royal Holloway, 682 University of London, Egham, 683 Surrey TW20 0EX, UK Email: david.naccache@rhul.ac.uk 685 Ohad Ranen 686 Aladdin Knowledge Systems Ltd. 687 15 Beit Oved Street 688 Tel Aviv, Israel 61110 Email: Ohad.Ranen@ealaddin.com 690 Appendix - HOTP Algorithm Security: Detailed Analysis 692 The security analysis of the HOTP algorithm is summarized in this 693 section. We first detail the best attack strategies, and then 694 elaborate on the security under various assumptions, the impact of 695 the truncation and some recommendations regarding the number of 696 digits. 698 We focus this analysis on the case where Digit = 6, i.e. an HOTP 699 function that produces 6-digit values, which is the bare minimum 700 recommended in this draft. 702 HOTP: An HMAC-based One Time Password Algorithm October 2004 704 A.1 Definitions and Notations 706 We denote by {0,1}^l the set of all strings of length l. 708 Let Z_{n} = {0,.., n - 1}. 710 Let IntDiv(a,b) denote the integer division algorithm that takes 711 input integers a, b where a >= b >= 1 and returns integers (q,r) 712 the quotient and remainder, respectively, of the division of a by 713 b. (Thus a = bq + r and 0 <= r < b.) 715 Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that 716 takes a k-bit key K and c-bit counter C and returns an n-bit output 717 H(K,C). (In the case of HOTP, H is HMAC-SHA-1; we use this formal 718 definition for generalizing our proof of security) 720 A.2 The idealized algorithm: HOTP-IDEAL 722 We now define an idealized counterpart of the HOTP algorithm. In 723 this algorithm, the role of H is played by a random function that 724 forms the key. 726 To be more precise, let Maps(c,n) denote the set of all functions 727 mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key 728 space Maps(c,n), so that a "key" for such an algorithm is a 729 function h from {0,1}^c to {0,1}^n. We imagine this key (function) 730 to be drawn at random. It is not feasible to implement this 731 idealized algorithm, since the key, being a function from is way 732 too large to even store. So why consider it? 734 Our security analysis will show that as long as H satisfies a 735 certain well-accepted assumption, the security of the actual and 736 idealized algorithms is for all practical purposes the same. The 737 task that really faces us, then, is to assess the security of the 738 idealized algorithm. 740 In analyzing the idealized algorithm, we are concentrating on 741 assessing the quality of the design of the algorithm itself, 742 independently of HMAC-SHA-1. This is in fact the important issue. 744 A.3 Model of Security 746 The model exhibits the type of threats or attacks that are being 747 considered and enables to asses the security of HOTP and 748 HOTP-IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the 749 purpose of this security analysis. 751 The scenario we are considering is that a user and server share a 752 key K for ALG. Both maintain a counter C, initially zero, and the 753 HOTP: An HMAC-based One Time Password Algorithm October 2004 755 user authenticates itself by sending ALG(K,C) to the server. The 756 latter accepts if this value is correct. 758 In order to protect against accidental increment of the user 759 counter, the server, upon receiving a value z, will accept as long 760 as z equals ALG(K,i) for some i in the range C,...,C + s-1, where s 761 is the resynchronization parameter and C is the server counter. If 762 it accepts with some value of i, it then increments its counter to 763 i+ 1. If it does not accept, it does not change its counter value. 765 The model we specify captures what an adversary can do and what it 766 needs to achieve in order to "win." First, the adversary is assumed 767 to be able to eavesdrop, meaning see the authenticator transmitted 768 by the user. Second, the adversary wins if it can get the server to 769 accept an authenticator relative to a counter value for which the 770 user has never transmitted an authenticator. 772 The formal adversary, which we denote by B, starts out knowing 773 which algorithm ALG is being used, knowing the system design and 774 knowing all system parameters. The one and only thing it is not 775 given a priori is the key K shared between the user and the server. 777 The model gives B full control of the scheduling of events. It has 778 access to an authenticator oracle representing the user. By calling 779 this oracle, the adversary can ask the user to authenticate itself 780 and get back the authenticator in return. It can call this oracle 781 as often as it wants and when it wants, using the authenticators it 782 accumulates to perhaps "learn" how to make authenticators itself. 783 At any time, it may also call a verification oracle, supplying the 784 latter with a candidate authenticator of its choice. It wins if the 785 server accepts this accumulator. 787 Consider the following game involving an adversary B that is 788 attempting to compromise the security of an authentication 789 algorithm ALG: K x {0,1}^c --> R. 791 Initializations - A key K is selected at random from K, a counter C 792 is initialized to 0, and the Boolean value win is set to false. 794 Game execution - Adversary B is provided with the two following 795 oracles: 797 Oracle AuthO() 798 O = ALG(K,C) 799 C = C + 1 800 Return O to B 802 Oracle VerO() 803 i = C 804 HOTP: An HMAC-based One Time Password Algorithm October 2004 806 While (i <= C + s - 1 and Win = FALSE) do 807 If O = ALG(K,i) then Win = TRUE; C = i + 1 808 Else i = i + 1 809 Return Win to B 811 AuthO() is the authenticator oracle and VerO() is the verification 812 oracle. 814 Upon execution, B queries the two oracles at will. Let Adv(B) be 815 the probability that win gets set to true in the above game. This 816 is the probability that the adversary successfully impersonates the 817 user. 819 Our goal is to assess how large this value can be as a function of 820 the number v of verification queries made by B, the number a of 821 authenticator oracle queries made by B, and the running time t of 822 B. This will tell us how to set the throttle, which effectively 823 upper bounds v. 825 A.4 Security of the ideal authentication algorithm 827 This section summarizes the security analysis of HOTP-IDEAL, 828 starting with the impact of the conversion modulo 10^Digit and 829 then, focusing on the different possible attacks. 831 A.4.1 From bits to digits 833 The dynamic offset truncation of a random n-bit string yields a 834 random 31-bit string. What happens to the distribution when it is 835 taken modulo m = 10^Digit, as done in HOTP? 837 The following lemma estimates the biases in the outputs in this 838 case. 840 Lemma 1 841 Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in 842 Z_{m} let: 844 P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}] 846 Then for any z in Z_{m} 848 P_{N,m}(z) = (q + 1) / N if 0 <= z < r 849 q / N if r <= z < m 851 Proof of Lemma 1 852 Let the random variable X be uniformly distributed over Z_{N}. 853 Then: 855 HOTP: An HMAC-based One Time Password Algorithm October 2004 857 P_{N,m}(z) = Pr [X mod m = z] 859 = Pr [X < mq] * Pr [X mod m = z| X < mq] 860 + Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N] 862 = mq/N * 1/m + 863 (N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq 864 0 if N - mq <= z <= m 866 = q/N + 867 r/N * 1 / r if 0 <= z < N - mq 868 0 if r <= z <= m 870 Simplifying yields the claimed equation. 872 Let N = 2^31, d = 6 and m = 10^d. If x is chosen at random from 873 Z_{N} (meaning, is a random 31-bit string), then reducing it to a 874 6-digit number by taking x mod m does not yield a random 6-digit 875 number. 877 Rather, x mod m is distributed as shown in the following table: 879 Values Probability that each appears as output 880 ---------------------------------------------------------------- 881 0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6 882 483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6 884 If X is uniformly distributed over Z_{2^31} (meaning is a random 885 31-bit string) then the above shows the probabilities for different 886 outputs of X mod 10^6. The first set of values appear with 887 probability slightly greater than 10^-6, the rest with probability 888 slightly less, meaning the distribution is slightly non-uniform. 890 However, as the Figure indicates, the bias is small and as we will 891 see later, negligible: the probabilities are very close to 10^-6. 893 A.4.2 Brute force attacks 895 If the authenticator consisted of d random digits, then a brute 896 force attack using v verification attempts would succeed with 897 probability sv/10^Digit. 899 However, an adversary can exploit the bias in the outputs of HOTP- 900 IDEAL, predicted by Lemma 1, to mount a slightly better attack. 902 Namely, it makes authentication attempts with authenticators which 903 are the most likely values, meaning the ones in the range 0,...,r - 904 1, where (q,r) = IntDiv(2^31,10^Digit). 906 HOTP: An HMAC-based One Time Password Algorithm October 2004 908 The following specifies an adversary in our model of security that 909 mounts the attack. It estimates the success probability as a 910 function of the number of verification queries. 912 For simplicity, we assume the number of verification queries is at 913 most r. With N = 2^31 and m = 10^6 we have r = 483,648, and the 914 throttle value is certainly less than this, so this assumption is 915 not much of a restriction. 917 Proposition 1 918 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume 919 s <= m. The brute-force attack adversary B-bf attacks HOTP using v 920 <= r verification oracle queries. This adversary makes no 921 authenticator oracle queries, and succeeds with probability 923 Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s 925 which is roughly equals to 927 sv * (q+1)/2^31 929 With m = 10^6 we get q = 2,147. In that case, the brute force 930 attack using v verification attempts succeeds with probability 932 Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6 934 As this equation shows, the resynchronization parameter s has a 935 significant impact in that the adversary's success probability is 936 proportional to s. This means that s cannot be made too large 937 without compromising security. 939 A.4.3 Brute force attacks are the best possible attacks 941 A central question is whether there are attacks any better than the 942 brute force one. In particular, the brute force attack did not 943 attempt to collect authenticators sent by the user and try to 944 cryptanalyze them in an attempt to learn how to better construct 945 authenticators. Would doing this help? Is there some way to "learn" 946 how to build authenticators that result in a higher success rate 947 than given by the brute-force attack? 949 The following says the answer to these questions is no. No matter 950 what strategy the adversary uses, and even if it sees, and tries to 951 exploit, the authenticators from authentication attempts of the 952 user, its success probability will not be above that of the brute 953 force attack - this is true as long as the number of 954 authentications it observes is not incredibly large. This is 955 valuable information regarding the security of the scheme. 957 HOTP: An HMAC-based One Time Password Algorithm October 2004 959 Proposition 2 960 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B 961 be any adversary attacking HOTP-IDEAL using v verification oracle 962 queries and a <= 2^c - s authenticator oracle queries. Then 964 Adv(B) < = sv * (q+1)/ 2^31 966 Note: This result is conditional on the adversary not seeing more 967 than 2^c - s authentications performed by the user, which is hardly 968 restrictive as long as c is large enough. 970 With m = 10^6 we get q = 2,147. In that case, Proposition 2 says 971 that any adversary B attacking HOTP-IDEAL and making v verification 972 attempts succeeds with probability at most 974 Equation 1 975 sv * 2148/2^31 roughly = sv * 1.00024045/10^6 977 Meaning, B's success rate is not more than that achieved by the 978 brute force attack. 980 A.5 Security Analysis of HOTP 982 We have analyzed in the previous sections, the security of the 983 idealized counterparts HOTP-IDEAL of the actual authentication 984 algorithm HOTP. We now show that, under appropriate and 985 well-believed assumption on H, the security of the actual 986 algorithms is essentially the same as that of its idealized 987 counterpart. 989 The assumption in question is that H is a secure pseudorandom 990 function, or PRF, meaning that its input-output values are 991 indistinguishable from those of a random function in practice. 993 Consider an adversary A that is given an oracle for a function f: 994 {0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A) 995 as the prf-advantage of A, which represents how well the adversary 996 does at distinguishing the case where its oracle is H(K,.) from the 997 case where its oracle is a random function of {0,1}^c to {0,1}^n. 999 One possible attack is based on exhaustive search for the key K. If 1000 A runs for t steps and T denotes the time to perform one 1001 computation of H, its prf-advantage from this attack turns out to 1002 be (t/T)2^-k . Another possible attack is a birthday one [3], 1003 whereby A can attain advantage p^2/2^n in p oracle queries and 1004 running time about pT. 1006 HOTP: An HMAC-based One Time Password Algorithm October 2004 1008 Our assumption is that these are the best possible attacks. This 1009 translates into the following. 1011 Assumption 1 1012 Let T denotes the time to perform one computation of H. Then if A 1013 is any adversary with running time at most t and making at most p 1014 oracle queries, 1016 Adv(A) <= (t/T)/2^k + p^2/2^n 1018 In practice this assumption means that H is very secure as PRF. For 1019 example, given that k = n = 160, an attacker with running time 2^60 1020 and making 2^40 oracle queries has advantage at most (about) 2^-80. 1022 Theorem 1 1023 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B 1024 be any adversary attacking HOTP using v verification oracle 1025 queries, a <= 2^c - s authenticator oracle queries, and running 1026 time t. Let T denote the time to perform one computation of H. If 1027 Assumption 1 is true then 1029 Adv(B) <= sv * (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n 1031 In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller 1032 than the sv(q + 1)/2^n term, so that the above says that for all 1033 practical purposes the success rate of an adversary attacking HOTP 1034 is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP 1035 algorithm is in practice essentially as good as its idealized 1036 counterpart. 1038 In the case m = 10^6 of a 6-digit output this means that an 1039 adversary making v authentication attempts will have a success rate 1040 that is at most that of Equation 1. 1042 For example, consider an adversary with running time at most 2^60 1043 that sees at most 2^40 authentication attempts of the user. Both 1044 these choices are very generous to the adversary, who will 1045 typically not have these resources, but we are saying that even 1046 such a powerful adversary will not have more success than indicated 1047 by Equation 1. 1049 We can safely assume sv <= 2^40 due to the throttling and bounds on 1050 s. So: 1051 (t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160 1052 roughly <= 2^-78 1054 which is much smaller than the success probability of Equation 1 1055 and negligible compared to it. 1057 HOTP: An HMAC-based One Time Password Algorithm October 2004 1059 Full Copyright Statement 1061 Copyright (C) The Internet Society 2004. This document is subject 1062 to the rights, licenses and restrictions contained in BCP 78, and 1063 except as set forth therein, the authors retain all their rights. 1065 This document and the information contained herein are provided on 1066 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 1067 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND 1068 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, 1069 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT 1070 THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 1071 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 1072 PARTICULAR PURPOSE.