idnits 2.17.00 (12 Aug 2021) /tmp/idnits23214/draft-mraihi-oath-hmac-otp-03.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 21. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1598. ** 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. (A line matching the expected section header was found, but with an unexpected indentation: ' 6. Security Considerations' ) ** 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 263 has weird spacing: '... Digit num...' == Line 1436 has weird spacing: '...eyBytes the ...' == Line 1479 has weird spacing: '...eDigits the ...' == Line 1481 has weird spacing: '...hecksum a fla...' == Line 1486 has weird spacing: '...ncation will ...' -- 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? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Missing reference section? 'BCK1' on line 783 looks like a reference -- Missing reference section? 'RFC3668' on line 794 looks like a reference -- Missing reference section? 'OATH' on line 799 looks like a reference -- Missing reference section? '0' on line 311 looks like a reference -- Missing reference section? '1' on line 236 looks like a reference -- Missing reference section? 'BCK2' on line 787 looks like a reference -- Missing reference section? '19' on line 337 looks like a reference -- Missing reference section? 'OffSet' on line 314 looks like a reference -- Missing reference section? 'Data' on line 726 looks like a reference -- Missing reference section? 'RFC2119' on line 791 looks like a reference -- Missing reference section? 'PrOo' on line 1175 looks like a reference -- Missing reference section? 'Crack' on line 1258 looks like a reference -- Missing reference section? 'Sha1' on line 1274 looks like a reference -- Missing reference section? 'Res' on line 1275 looks like a reference -- Missing reference section? '8' on line 1513 looks like a reference Summary: 14 errors (**), 0 flaws (~~), 6 warnings (==), 20 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft D. M'Raihi 3 Category: Informational VeriSign 4 Document: draft-mraihi-oath-hmac-otp-03.txt M. Bellare 5 Expires: April 2005 UCSD 6 F. Hoornaert 7 Vasco 8 D. Naccache 9 Gemplus 10 O. Ranen 11 Aladdin 12 October 2004 14 HOTP: An HMAC-based One Time Password Algorithm 16 Status of this Memo 18 By submitting this Internet-Draft, I certify that any applicable 19 patent or other IPR claims of which I am aware have been disclosed, 20 or will be disclosed, and any of which I become aware will be 21 disclosed, in accordance with RFC 3668. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as 26 Internet-Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six 29 months and may be updated, replaced, or obsoleted by other 30 documents at any time. It is inappropriate to use Internet-Drafts 31 as reference material or to cite them other than a "work in 32 progress". 34 The list of current Internet-Drafts can be accessed at 35 http://www.ietf.org/1id-abstracts.html 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html 39 Abstract 41 This document describes an algorithm to generate one-time password 42 values, based on HMAC [BCK1]. A security analysis of the algorithm 43 is presented, and important parameters related to the secure 44 deployment of the algorithm are discussed. The proposed algorithm 45 can be used across a wide range of network applications ranging 46 from remote VPN access, Wi-Fi network logon to transaction-oriented 47 Web applications. 49 This work is a joint effort by the OATH (Open AuTHentication) 50 membership to specify an algorithm that can be freely distributed 51 to the technical community. The authors believe that a common and 52 HOTP: An HMAC-based One Time Password Algorithm October 2004 54 shared algorithm will facilitate adoption of two-factor 55 authentication on the Internet by enabling interoperability across 56 commercial and open-source implementations. 58 Table of Contents 60 1. Overview....................................................3 61 2. Introduction................................................3 62 3. Requirements Terminology....................................4 63 4. Algorithm Requirements......................................4 64 5. HOTP Algorithm..............................................5 65 5.1 Notation and Symbols.......................................5 66 5.2 Description................................................6 67 5.3 Generating an HOTP value...................................6 68 5.4 Example of HOTP computation for Digit = 6..................7 69 6. Security Considerations.....................................8 70 6.1 Authentication Protocol Requirements.......................8 71 6.2 Validation of HOTP values..................................9 72 6.3 Throttling at the server...................................9 73 6.4 Resynchronization of the counter...........................9 74 6.5 Management of Shared Secrets..............................10 75 7. HOTP Algorithm Security: Overview..........................12 76 8. Protocol Extensions and Improvements.......................12 77 8.1 Number of Digits..........................................13 78 8.2 Alpha-numeric Values......................................13 79 8.3 Sequence of HOTP values...................................13 80 8.4 A Counter-based Re-Synchronization Method.................14 81 8.5 Composite Shared Secrets..................................14 82 8.6 Data Field................................................15 83 9. Conclusion.................................................15 84 10. Acknowledgements...........................................16 85 11. Contributors...............................................16 86 12. References.................................................16 87 12.1 Normative.................................................16 88 12.2 Informative...............................................16 89 13. Authors' Addresses........................................17 90 Appendix A - HOTP Algorithm Security: Detailed Analysis........18 91 A.1 Definitions and Notations..................................18 92 A.2 The idealized algorithm: HOTP-IDEAL........................18 93 A.3 Model of Security..........................................19 94 A.4 Security of the ideal authentication algorithm.............20 95 A.4.1 From bits to digits......................................21 96 A.4.2 Brute force attacks......................................22 97 A.4.3 Brute force attacks are the best possible attacks........23 98 A.5 Security Analysis of HOTP..................................24 99 Appendix B - SHA-1 Attacks.....................................25 100 B.1 SHA-1 status...............................................25 101 B.2 HMAC-SHA-1 status..........................................26 102 B.3 HOTP status................................................27 103 HOTP: An HMAC-based One Time Password Algorithm October 2004 105 Appendix C - HOTP Algorithm: Reference Implementation..........27 106 Appendix D - HOTP Algorithm: Test Values.......................31 108 1. Overview 110 The document introduces first the context around the HOTP 111 algorithm. In section 4, the algorithm requirements are listed and 112 in section 5, the HOTP algorithm is described. Sections 6 and 7 113 focus on the algorithm security. Section 8 proposes some extensions 114 and improvements, and Section 9 concludes this document. The 115 interested reader will find in the Appendix a detailed, full-fledge 116 analysis of the algorithm security: an idealized version of the 117 algorithm is evaluated, and then the HOTP algorithm security is 118 analyzed. 120 2. Introduction 122 Today, deployment of two-factor authentication remains extremely 123 limited in scope and scale. Despite increasingly higher levels of 124 threats and attacks, most Internet applications still rely on weak 125 authentication schemes for policing user access. The lack of 126 interoperability among hardware and software technology vendors has 127 been a limiting factor in the adoption of two-factor authentication 128 technology. In particular, the absence of open specifications has 129 led to solutions where hardware and software components are tightly 130 coupled through proprietary technology, resulting in high cost 131 solutions, poor adoption and limited innovation. 133 In the last two years, the rapid rise of network threats has 134 exposed the inadequacies of static passwords as the primary mean of 135 authentication on the Internet. At the same time, the current 136 approach that requires an end-user to carry an expensive, 137 single-function device that is only used to authenticate to the 138 network is clearly not the right answer. For two factor 139 authentication to propagate on the Internet, it will have to be 140 embedded in more flexible devices that can work across a wide range 141 of applications. 143 The ability to embed this base technology while ensuring broad 144 interoperability require that it be made freely available to the 145 broad technical community of hardware and software developers. Only 146 an open system approach will ensure that basic two-factor 147 authentication primitives can be built into the next-generation of 148 consumer devices such USB mass storage devices, IP phones, and 149 personal digital assistants). 151 One Time Password is certainly one of the simplest and most popular 152 forms of two-factor authentication for securing network access. For 153 example, in large enterprises, Virtual Private Network access often 154 HOTP: An HMAC-based One Time Password Algorithm October 2004 156 requires the use of One Time Password tokens for remote user 157 authentication. One Time Passwords are often preferred to stronger 158 forms of authentication such as PKI or biometrics because an 159 air-gap device does not require the installation of any client 160 desktop software on the user machine, therefore allowing them to 161 roam across multiple machines including home computers, kiosks and 162 personal digital assistants. 164 This draft proposes a simple One Time Password algorithm that can 165 be implemented by any hardware manufacturer or software developer 166 to create interoperable authentication devices and software agents. 167 The algorithm is event-based so that it can be embedded in high 168 volume devices such as Java smart cards, USB dongles and GSM SIM 169 cards. The presented algorithm is made freely available to the 170 developer community under the terms and conditions of the IETF 171 Intellectual Property Rights [RFC3668]. 173 The authors of this document are members of the Open AuTHentication 174 initiative [OATH]. The initiative was created in 2004 to facilitate 175 collaboration among strong authentication technology providers. 177 3. Requirements Terminology 179 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 180 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 181 this document are to be interpreted as described in RFC 2119. 183 4. Algorithm Requirements 185 This section presents the main requirements that drove this 186 algorithm design. A lot of emphasis was placed on end-consumer 187 usability as well as the ability for the algorithm to be 188 implemented by low cost hardware that may provide minimal user 189 interface capabilities. In particular, the ability to embed the 190 algorithm into high volume SIM and Java cards was a fundamental 191 pre-requisite. 193 R1 - The algorithm MUST be sequence or counter-based: One of the 194 goals is to have the HOTP algorithm embedded in high volume devices 195 such as Java smart cards, USB dongles and GSM SIM cards. 197 R2 - The algorithm SHOULD be economical to implement in hardware by 198 minimizing requirements on battery, number of buttons, 199 computational horsepower, and size of LCD display. The algorithm 200 MUST work with tokens that do not supports any numeric input, but 201 MAY also be used with more sophisticated devices such as secure 202 PIN-pads. 204 HOTP: An HMAC-based One Time Password Algorithm October 2004 206 R3 - The value displayed on the token MUST be easily read and 207 entered by the user: This requires the HOTP value to be of 208 reasonable length. The HOTP value must be at least a 6-digit value. 209 It is also desirable that the HOTP value be 'numeric only' so that 210 it can be easily entered on restricted devices such as phones. 212 R4 - There MUST be user-friendly mechanisms available to 213 resynchronize the counter. The sections 6.4 and 8.4 detail the 214 resynchronization mechanism proposed in this draft. 216 R5 - The algorithm MUST use a strong shared secret. The length of 217 the shared secret MUST be at least 128 bits. This draft RECOMMENDs 218 a shared secret length of 160 bits. 220 5. HOTP Algorithm 222 In this section, we introduce the notation and describe the HOTP 223 algorithm basic blocks - the base function to compute an HMAC-SHA-1 224 value and the truncation method to extract an HOTP value. 226 5.1 Notation and Symbols 228 A string always means a binary string, meaning a sequence of zeros 229 and ones. 231 If s is a string then |s| denotes its length. 233 If n is a number then |n| denotes its absolute value. 235 If s is a string then s[i] denotes its i-th bit. We start numbering 236 the bits at 0, so s = s[0]s[1]..s[n-1] where n = |s| is the length 237 of s. 239 Let StToNum (String to Number) denote the function which as input a 240 string s returns the number whose binary representation is s. 241 (For example StToNum(110) = 6). 243 Here is a list of symbols used in this document. 245 Symbol Represents 246 ------------------------------------------------------------------- 247 C 8-byte counter value, the moving factor. This counter 248 MUST be synchronized between the HOTP generator (client) 249 and the HOTP validator (server); 251 K shared secret between client and server; each HOTP 252 generator has a different and unique secret K; 254 T throttling parameter: the server will refuse connections 255 HOTP: An HMAC-based One Time Password Algorithm October 2004 257 from a user after T unsuccessful authentication attempts; 259 s resynchronization parameter: the server will attempt to 260 verify a received authenticator across s consecutive 261 counter values; 263 Digit number of digits in an HOTP value; system parameter. 265 5.2 Description 267 The HOTP algorithm is based on an increasing counter value and a 268 static symmetric key known only to the token and the validation 269 service. In order to create the HOTP value, we will use the 270 HMAC-SHA-1 algorithm, as defined in RFC 2104 [BCK2]. 272 As the output of the HMAC-SHA1 calculation is 160 bits, we must 273 truncate this value to something that can be easily entered by a 274 user. 276 HOTP(K,C) = Truncate(HMAC-SHA-1(K,C)) 278 Where: 279 - Truncate represents the function that converts an HMAC-SHA-1 280 value into an HOTP value as defined in Section 5.3. 282 The Key (K) and the Counter (C) values are hashed high-order byte 283 first. 285 The HOTP values generated by the HOTP generator are treated as big 286 endian. 288 5.3 Generating an HOTP value 290 We can describe the operations in 3 distinct steps: 292 Step 1: Generate an HMAC-SHA-1 value 293 Let HS = HMAC-SHA-1(K,C) // HS is a 20 byte string 295 Step 2: Generate a 4-byte string (Dynamic Truncation) 296 Let Sbits = DT(HS) // DT, defined in Section 6.3.1 297 // returns a 31 bit string 299 Step 3: Compute an HOTP value 300 Let Snum = StToNum(S) // Convert S to a number in 301 0...2^{31}-1 302 Return D = Snum mod 10^Digit // D is a number in the range 303 0...10^{Digit}-1 304 HOTP: An HMAC-based One Time Password Algorithm October 2004 306 The Truncate function performs Step 2 and Step 3, i.e. the dynamic 307 truncation and then the reduction modulo 10^Digit. The purpose of 308 the dynamic offset truncation technique is to extract a 4-byte 309 dynamic binary code from a 160-bit (20-byte) HMAC-SHA1 result. 311 DT(String) // String = String[0]...String[19] 312 Let OffsetBits be the low order four bits of String[19] 313 Offset = StToNum(OffSetBits) // 0 <= OffSet <= 15 314 Let P = String[OffSet]...String[OffSet+3] 315 Return the Last 31 bits of P 317 The reason for masking the most significant bit of P is to avoid 318 confusion about signed vs. unsigned modulo computations. Different 319 processors perform these operations differently, and masking out 320 the signed bit removes all ambiguity. 322 Implementations MUST extract a 6-digit code at a minimum and 323 possibly 7 and 8-digit code. Depending on security requirements, 324 Digit = 7 or more SHOULD be considered in order to extract a longer 325 HOTP value. 327 The following paragraph is an example of using this technique for 328 Digit = 6, i.e. that a 6-digit HOTP value is calculated from the 329 HMAC value. 331 5.4 Example of HOTP computation for Digit = 6 333 The following code example describes the extraction of a dynamic 334 binary code given that hmac_result is a byte array with the 335 HMAC-SHA1 result: 337 int offset = hmac_result[19] & 0xf ; 338 int bin_code = (hmac_result[offset] & 0x7f) << 24 339 | (hmac_result[offset+1] & 0xff) << 16 340 | (hmac_result[offset+2] & 0xff) << 8 341 | (hmac_result[offset+3] & 0xff) ; 343 SHA-1 HMAC Bytes (Example) 345 ------------------------------------------------------------- 346 | Byte Number | 347 ------------------------------------------------------------- 348 |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19| 349 ------------------------------------------------------------- 350 | Byte Value | 351 ------------------------------------------------------------- 352 |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a| 353 -------------------------------***********----------------++| 354 HOTP: An HMAC-based One Time Password Algorithm October 2004 356 * The last byte (byte 19) has the hex value 0x5a. 357 * The value of the lower four bits is 0xa (the offset value). 358 * The offset value is byte 10 (0xa). 359 * The value of the 4 bytes starting at byte 10 is 0x50ef7f19, 360 which is the dynamic binary code DBC1 361 * The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19 362 * HOTP = DBC2 modulo 10^6 = 872921. 364 We treat the dynamic binary code as a 31-bit, unsigned, big-endian 365 integer; the first byte is masked with a 0x7f. 367 We then take this number modulo 1,000,000 (10^6) to generate the 368 6-digit HOTP value 872921 decimal. 370 6. Security Considerations 372 Any One-Time Password algorithm is only as secure as the 373 application and the authentication protocols that implement it. 374 Therefore, this section discusses the critical security 375 requirements that our choice of algorithm imposes on the 376 authentication protocol and validation software. 378 The parameters T and s discussed in this section have a significant 379 impact on the security - further details in Section 7 elaborate on 380 the relations between these parameters and their impact on the 381 system security. 383 6.1 Authentication Protocol Requirements 385 We introduce in this section some requirements for a protocol P 386 implementing HOTP as the authentication method between a prover and 387 a verifier. 389 RP1 - P MUST be two-factor, i.e. something you know (secret code 390 such as a Password, Pass phrase, PIN code, etc.) and something you 391 have (token). The secret code is known only to the user and usually 392 entered with the one-time password value for authentication purpose 393 (two-factor authentication). 395 RP3 - P MUST NOT be vulnerable to brute force attacks. This implies 396 that a throttling/lockout scheme is REQUIRED on the validation 397 server side. 399 RP4 - P SHOULD be implemented with respect to the state of the art 400 in terms of security, in order to avoid the usual attacks and risks 401 associated with the transmission of sensitive data over a public 402 network (privacy, replay attacks, etc.) 403 HOTP: An HMAC-based One Time Password Algorithm October 2004 405 6.2 Validation of HOTP values 407 The HOTP client (hardware or software token) increments its counter 408 and then calculates the next HOTP value HOTP-client. If the value 409 received by the authentication server matches the value calculated 410 by the client, then the HOTP value is validated. In this case, the 411 server increments the counter value by one. 413 If the value received by the server does not match the value 414 calculated by the client, the server initiate the resynch protocol 415 (look-ahead window) before it requests another pass. 417 If the resynch fails, the server asks then for another 418 authentication pass of the protocol to take place, until the 419 maximum number of authorized attempts is reached. 421 If and when the maximum number of authorized attempts is reached, 422 the server SHOULD lock out the account and initiate a procedure to 423 inform the user. 425 6.3 Throttling at the server 427 Truncating the HMAC-SHA1 value to a shorter value makes a brute 428 force attack possible. Therefore, the authentication server needs 429 to detect and stop brute force attacks. 431 We RECOMMEND setting a throttling parameter T, which defines the 432 maximum number of possible attempts for One-Time-Password 433 validation. The validation server manages individual counters per 434 HOTP device in order to take note of any failed attempt. We 435 RECOMMEND T not to be too large, particularly if the 436 resynchronization method used on the server is window-based, and 437 the window size is large. T SHOULD be set as low as possible, while 438 still ensuring usability is not significantly impacted. 440 6.4 Resynchronization of the counter 442 Although the server's counter value is only incremented after a 443 successful HOTP authentication, the counter on the token is 444 incremented every time a new HOTP is requested by the user. Because 445 of this, the counter values on the server and on the token might be 446 out of synchronization. 448 We RECOMMEND setting a look-ahead parameter s on the server, which 449 defines the size of the look-ahead window. In a nutshell, the 450 server can recalculate the next s HOTP-server values, and check 451 them against the received HOTP-client. 453 HOTP: An HMAC-based One Time Password Algorithm October 2004 455 Synchronization of counters in this scenario simply requires the 456 server to calculate the next HOTP values and determine if there is 457 a match. Optionally, the system MAY require the user to send a 458 sequence of (say 2, 3) HOTP values for resynchronization purpose, 459 since forging a sequence of consecutive HOTP values is even more 460 difficult than guessing a single HOTP value. 462 The upper bound set by the parameter s ensures the server does not 463 go on checking HOTP values forever (causing a DoS attack) and also 464 restricts the space of possible solutions for an attacker trying to 465 manufacture HOTP values. s SHOULD be set as low as possible, while 466 still ensuring usability is not impacted. 468 6.5 Management of Shared Secrets 470 The operations dealing with the shared secrets used to generate and 471 verify OTP values must be performed securely, in order to mitigate 472 risks of any leakage of sensitive information. We describe in this 473 section different modes of operations and techniquest to perform 474 these different operations with respect of the state of the art in 475 terms of data security. 477 We can consider two different avenues for generating and storing 478 (securely) shared secrets in the Validation system: 479 * Deterministic Generation: secrets are derived from a master 480 seed, both at provisioning and verification stages and generated 481 on-the-fly whenever it is required; 482 * Random Generation: secrets are generated randomly at 483 provisioning stage, and must be stored immediately and kept secure 484 during their life cycle. 486 Deterministic Generation 487 ------------------------ 489 A possible strategy is to derive the shared secrets from a master 490 secret. In this case, a tamper resistant device SHOULD be 491 generating the shared secrets based on the master seed and some 492 public information. The main benefit would be to avoid the exposure 493 of the shared secrets at any time and also avoid specific 494 requirements on storage, since the shared secrets could be 495 generated on-demand when needed at provisioning and validation 496 time. 498 The drawback in this case is that the exposure of the master secret 499 would obviously enable an attacker to rebuild any shared secret 500 based on correct public information. On the other hand, the device 501 being tamper resistant, and also, obvioulsly not exposed outside 502 HOTP: An HMAC-based One Time Password Algorithm October 2004 504 the security perimeter of the validation system, the risk of such a 505 break-out could be reduced. 507 Another option to mitigate the risk, would be to use a series of 508 master secrets, say MS1 to MS5, and generate a set of shared 509 secrets to be stored in the OTP generator devices. In this case, if 510 a master secret was compromised, then the system could switch to 511 another shared secret by selecting the proper secret in the device. 512 This is probably not applicable in all situations, and therefore, 513 the random generation method describes hereafter might be more 514 suited in some cases. 516 Random Generation 517 ----------------- 519 The shared secrets are randomly generated. We RECOMMEND the usage 520 of a good random source for generating them. A (true) random 521 generator requires a naturally occurring source of randomness. 522 Practically, there are two possible avenues to consider for the 523 generation of the shared secrets: 525 * Hardware-based generators: they exploit the randomness which 526 occurs in physical phenomena. A nice implementation can be based on 527 oscillators, and built in such ways that active attacks are more 528 difficult to perform. 530 * Software-based generators: designing a good software random 531 generator is not an easy task. A simple, but efficient, 532 implementation should be based on various sources, and apply to the 533 sampled sequence a one-way function such as SHA-1. 535 We RECOMMEND to select proven products, being hardware or software 536 generators for the computation of shared secrets. 538 We also RECOMMEND storing the shared secrets securely, and more 539 specifically encrypting the shared secrets when stored using 540 tamper-resistant hardware encryption, and exposing them only when 541 required: e.g. the shared secret is decrypted when needed to verify 542 an HOTP value, and re-encrypted immediately to limit exposure in 543 the RAM for a short period of time. The data store holding the 544 shared secrets MUST be in a secure area, to avoid as much as 545 possible direct attack on the validation system and secrets 546 database. 548 Particularly, access to the shared secrets should be limited to 549 programs and processes required by the validation system only. We 550 will not elaborate on the different security mechanisms to put in 551 place, but obviously, the protection of shared secrets is of the 552 uttermost importance. 554 HOTP: An HMAC-based One Time Password Algorithm October 2004 556 7. HOTP Algorithm Security: Overview 558 The conclusion of the security analysis detailed in the Appendix 559 section is that, for all practical purposes, the outputs of the 560 dynamic truncation (DT) on distinct counter inputs are uniformly 561 and independently distributed 31-bit strings. 563 The security analysis then details the impact of the conversion 564 from a string to an integer and the final reduction modulo 565 10^Digit, where Digit is the number of digits in an HOTP value. 567 The analysis demonstrates that these final steps introduce a 568 negligible bias, which does not impact the security of the HOTP 569 algorithm, in the sense that the best possible attack against the 570 HOTP function is the brute force attack. 572 Assuming an adversary is able to observe numerous protocol 573 exchanges and collect sequences of successful authentication 574 values. This adversary, trying to build a function F to generate 575 HOTP values based on his observations, will not have a significant 576 advantage over a random guess. 578 The logical conclusion is simply that is best strategy will once 579 again be to perform a brute force attack to enumerate and try all 580 the possible values. 582 Considering the security analysis in the Appendix section of this 583 document, without loss of generality, we can approximate closely 584 the security of the HOTP algorithm by the following formula: 586 Sec = sv/10^Digit 588 Where: 589 - Sec is the probability of success of the adversary 590 - s stands for the look-ahead synchronization window size; 591 - v stands for the number of verification attempts; 592 - Digit stands for the number of digits in HOTP values. 594 Obviously, we can play with s, T (the Throttling parameter that 595 would limit the number of attempts by an attacker) and Digit until 596 achieving a certain level of security, still preserving the system 597 usability. 599 8. Protocol Extensions and Improvements 601 We introduce in this section several enhancements and suggestions 602 to further improve the security of the algorithm HOTP 603 HOTP: An HMAC-based One Time Password Algorithm October 2004 605 8.1 Number of Digits 607 A simple enhancement in terms of security would be to extract more 608 digits from the HMAC-SHA1 value. 610 For instance, calculating the HOTP value modulo 10^8 to build an 611 8-digit HOTP value would reduce the probability of success of the 612 adversary from sv/10^6 to sv/10^8. 614 This could give the opportunity to improve usability, e.g. by 615 increasing T and/or s, while still achieving a better security 616 overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which 617 is the theoretical optimum for 6-digit code when s = 1. 619 8.2 Alpha-numeric Values 621 Another option is to use A-Z and 0-9 values; or rather a subset of 622 32 symbols taken from the alphanumerical alphabet in order to avoid 623 any confusion between characters: 0, O and Q as well as l, 1 and I 624 are very similar, and can look the same on a small display. 626 The immediate consequence is that the security is now in the order 627 of sv/32^6 for a 6-digit HOTP value and sv/32^8 for an 8-digit HOTP 628 value. 630 32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is 631 slightly better than a 9-digit HOTP value, which is the maximum 632 length of an HOTP code supported by the proposed algorithm. 634 32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is 635 significantly better than a 9-digit HOTP value. 637 Depending on the application and token/interface used for 638 displaying and entering the HOTP value, the choice of alphanumeric 639 values could be a simple and efficient way to improve security at a 640 reduced cost and impact on users. 642 8.3 Sequence of HOTP values 644 As we suggested for the resynchronization to enter a short sequence 645 (say 2 or 3) of HOTP values, we could generalize the concept to the 646 protocol, and add a parameter L that would define the length of the 647 HOTP sequence to enter. 649 Per default, the value L SHOULD be set to 1, but if security needs 650 to be increased, users might be asked (possibly for a short period 651 of time, or a specific operation) to enter L HOTP values. 653 HOTP: An HMAC-based One Time Password Algorithm October 2004 655 This is another way, without increasing the HOTP length or using 656 alphanumeric values to tighten security. 658 Note: The system MAY also be programmed to request synchronization 659 on a regular basis (e.g. every night, or twice a week, etc.) and to 660 achieve this purpose, ask for a sequence of L HOTP values. 662 8.4 A Counter-based Re-Synchronization Method 664 In this case, we assume that the client can access and send not 665 only the HOTP value but also other information, more specifically 666 the counter value. 668 A more efficient and secure method for resynchronization is 669 possible in this case. The client application will not send the 670 HOTP-client value only, but the HOTP-client and the related 671 C-client counter value, the HOTP value acting as a message 672 authentication code of the counter. 674 Resynchronization Counter-based Protocol (RCP) 675 ---------------------------------------------- 677 The server accepts if the following are all true, where C-server is 678 its own current counter value: 680 1) C-client >= C-server 681 2) C-client - C-server <= s 682 3) Check that HOTP-client is valid HOTP(K,C-Client) 683 4) If true, the server sets C to C-client + 1 and client is 684 authenticated 686 In this case, there is no need for managing a look-ahead window 687 anymore. The probability of success of the adversary is only v/10^6 688 or roughly v in one million. A side benefit is obviously to be able 689 to increase s "infinitely" and therefore improve the system 690 usability without impacting the security. 692 This resynchronization protocol SHOULD be use whenever the related 693 impact on the client and server applications is deemed acceptable. 695 8.5 Composite Shared Secrets 697 It may be desirable to include additional authentication factors in 698 the shared secret K. These additional factors can consist of any 699 data known at the token but not easily obtained by others. Examples 700 of such data include: 701 * PIN or Password obtained as user input at the token 702 * Phone number 703 * Any unique identifier programmatically available at the token 704 HOTP: An HMAC-based One Time Password Algorithm October 2004 706 In this scenario the composite shared secret K is constructed 707 during the provisioning process from a random seed value combined 708 with one or more additional authentication factors. The server 709 could either build on-demand or store composite secrets - in any 710 case, depending on implementation choice, the token only stores the 711 seed value. When the token performs the HOTP calculation it 712 computes K from the seed value and the locally derived or input 713 values of the other authentication factors. 715 The use of composite shared secrets can strengthen HOTP based 716 authentication systems through the inclusion of additional 717 authentication factors at the token. To the extent that the token 718 is a trusted device this approach has the further benefit of not 719 requiring exposure of the authentication factors (such as the user 720 input PIN) to other devices. 722 8.6 Data Field 724 Another possibility would be to introduce the notion of a Data 725 field, that would be used for generating the One-Time password 726 values: HOTP (K, C, [Data]) where Data is an optional field that 727 can be the concatenation of various pieces of identity-related 728 information - e.g. Data = Address | PIN. 730 We could also use a Timer, either as the only moving factor or in 731 combination with the Counter - in this case, e.g. Data = Timer, 732 where Timer could be the UNIX-time (GMT seconds since 1/1/1970) 733 divided by some factor (8, 16, 32, etc.) in order to give a 734 specific time step. The time window for the One-Time Password is 735 then equal to the time step multiplied by the resynchronization 736 parameter as defined before - e.g. if we take 64 seconds as the 737 time step and 7 for the resynchronization parameter, we obtain an 738 acceptance window of +/- 3 minutes. 740 Using a Data field opens for more flexibility in the algorithm 741 implementation, provided that the Data field is clearly specified. 743 9. Conclusion 745 This draft describes HOTP, a HMAC-based One-Time Password 746 algorithm. It also recommends the preferred implementation and 747 related modes of operations for deploying the algorithm. 749 The draft also exhibits elements of security and demonstrates that 750 the HOTP algorithm is practical and sound, the best possible attack 751 being a brute force attack that can be prevented by careful 752 implementation of countermeasures in the validation server. 754 HOTP: An HMAC-based One Time Password Algorithm October 2004 756 Eventually, several enhancements have been proposed, in order to 757 improve security if needed for specific applications. 759 10. Acknowledgements 761 The authors would like to thank Siddharth Bajaj, Alex Deacon, Loren 762 Hart and Nico Popp for their help during the conception and 763 redaction of this document. 765 11. Contributors 767 The authors of this draft would like to emphasize the role of three 768 persons who have made a key contribution to this document: 770 - Laszlo Elteto is system architect with SafeNet, Inc. 772 - Ernesto Frutos is director of Engineering with Authenex, Inc. 774 - Fred McClain is Founder and CTO with Boojum Mobile, Inc. 776 Without their advice and valuable inputs, this draft would not be 777 the same. 779 12. References 781 12.1 Normative 783 [BCK1] M. Bellare, R. Canetti and H. Krawczyk, "Keyed Hash 784 Functions and Message Authentication", Proceedings of 785 Crypto'96, LNCS Vol. 1109, pp. 1-15. 787 [BCK2] M. Bellare, R. Canetti and H. Krawczyk, "HMAC: 788 Keyed-Hashing for Message Authentication", IETF Network 789 Working Group, RFC 2104, February 1997. 791 [RFC2119] S. Bradner, "Key words for use in RFCs to Indicate 792 Requirement Levels", BCP 14, RFC 2119, March 1997. 794 [RFC3668] S. Bradner, "Intellectual Propery Rights in IETF 795 Technology", BCP 79, RFC 3668, February 2004. 797 12.2 Informative 799 [OATH] Initiative for Open AuTHentication 800 http://www.openauthentication.org 802 [PrOo] B. Preneel and P. van Oorschot, "MD-x MAC and building 803 fast MACs from hash functions", Advances in Cryptology 804 HOTP: An HMAC-based One Time Password Algorithm October 2004 806 CRYPTO '95, Lecture Notes in Computer Science Vol. 963, 807 D. Coppersmith ed., Springer-Verlag, 1995. 809 [Crack] Crack in SHA-1 code 'stuns' security gurus 810 http://www.eetimes.com/showArticle.jhtml?articleID=60402150 812 [Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005. 813 http://www.schneier.com/blog/archives/2005/02/sha1_broken.html 815 [Res] Researchers: Digital encryption standard flawed 816 http://news.com.com/Researchers+Digital+encryption+standard+flawed/ 817 2100-1002-5579881.html?part=dht&tag=ntop&tag=nl.e703 819 13. Authors' Addresses 821 Primary point of contact (for sending comments and question): 823 David M'Raihi 824 VeriSign, Inc. 825 685 E. Middlefield Road Phone: 1-650-426-3832 826 Mountain View, CA 94043 USA Email: dmraihi@verisign.com 828 Other Authors' contact information: 830 Mihir Bellare 831 Dept of Computer Science and Engineering, Mail Code 0114 832 University of California at San Diego 833 9500 Gilman Drive 834 La Jolla, CA 92093, USA Email: mihir@cs.ucsd.edu 836 Frank Hoornaert 837 VASCO Data Security, Inc. 838 Koningin Astridlaan 164 839 1780 Wemmel, Belgium Email: frh@vasco.com 841 David Naccache 842 Gemplus Innovation 843 34 rue Guynemer, 92447, 844 Issy les Moulineaux, France Email: david.naccache@gemplus.com 845 and 846 Information Security Group, 847 Royal Holloway, 848 University of London, Egham, 849 Surrey TW20 0EX, UK Email: david.naccache@rhul.ac.uk 851 Ohad Ranen 852 Aladdin Knowledge Systems Ltd. 853 15 Beit Oved Street 854 HOTP: An HMAC-based One Time Password Algorithm October 2004 856 Tel Aviv, Israel 61110 Email: Ohad.Ranen@ealaddin.com 858 Appendix A - HOTP Algorithm Security: Detailed Analysis 860 The security analysis of the HOTP algorithm is summarized in this 861 section. We first detail the best attack strategies, and then 862 elaborate on the security under various assumptions, the impact of 863 the truncation and some recommendations regarding the number of 864 digits. 866 We focus this analysis on the case where Digit = 6, i.e. an HOTP 867 function that produces 6-digit values, which is the bare minimum 868 recommended in this draft. 870 A.1 Definitions and Notations 872 We denote by {0,1}^l the set of all strings of length l. 874 Let Z_{n} = {0,.., n - 1}. 876 Let IntDiv(a,b) denote the integer division algorithm that takes 877 input integers a, b where a >= b >= 1 and returns integers (q,r) 878 the quotient and remainder, respectively, of the division of a by 879 b. (Thus a = bq + r and 0 <= r < b.) 881 Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that 882 takes a k-bit key K and c-bit counter C and returns an n-bit output 883 H(K,C). (In the case of HOTP, H is HMAC-SHA-1; we use this formal 884 definition for generalizing our proof of security) 886 A.2 The idealized algorithm: HOTP-IDEAL 888 We now define an idealized counterpart of the HOTP algorithm. In 889 this algorithm, the role of H is played by a random function that 890 forms the key. 892 To be more precise, let Maps(c,n) denote the set of all functions 893 mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key 894 space Maps(c,n), so that a "key" for such an algorithm is a 895 function h from {0,1}^c to {0,1}^n. We imagine this key (function) 896 to be drawn at random. It is not feasible to implement this 897 idealized algorithm, since the key, being a function from is way 898 too large to even store. So why consider it? 900 Our security analysis will show that as long as H satisfies a 901 certain well-accepted assumption, the security of the actual and 902 idealized algorithms is for all practical purposes the same. The 903 HOTP: An HMAC-based One Time Password Algorithm October 2004 905 task that really faces us, then, is to assess the security of the 906 idealized algorithm. 908 In analyzing the idealized algorithm, we are concentrating on 909 assessing the quality of the design of the algorithm itself, 910 independently of HMAC-SHA-1. This is in fact the important issue. 912 A.3 Model of Security 914 The model exhibits the type of threats or attacks that are being 915 considered and enables to asses the security of HOTP and 916 HOTP-IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the 917 purpose of this security analysis. 919 The scenario we are considering is that a user and server share a 920 key K for ALG. Both maintain a counter C, initially zero, and the 921 user authenticates itself by sending ALG(K,C) to the server. The 922 latter accepts if this value is correct. 924 In order to protect against accidental increment of the user 925 counter, the server, upon receiving a value z, will accept as long 926 as z equals ALG(K,i) for some i in the range C,...,C + s-1, where s 927 is the resynchronization parameter and C is the server counter. If 928 it accepts with some value of i, it then increments its counter to 929 i+ 1. If it does not accept, it does not change its counter value. 931 The model we specify captures what an adversary can do and what it 932 needs to achieve in order to "win." First, the adversary is assumed 933 to be able to eavesdrop, meaning see the authenticator transmitted 934 by the user. Second, the adversary wins if it can get the server to 935 accept an authenticator relative to a counter value for which the 936 user has never transmitted an authenticator. 938 The formal adversary, which we denote by B, starts out knowing 939 which algorithm ALG is being used, knowing the system design and 940 knowing all system parameters. The one and only thing it is not 941 given a priori is the key K shared between the user and the server. 943 The model gives B full control of the scheduling of events. It has 944 access to an authenticator oracle representing the user. By calling 945 this oracle, the adversary can ask the user to authenticate itself 946 and get back the authenticator in return. It can call this oracle 947 as often as it wants and when it wants, using the authenticators it 948 accumulates to perhaps "learn" how to make authenticators itself. 949 At any time, it may also call a verification oracle, supplying the 950 latter with a candidate authenticator of its choice. It wins if the 951 server accepts this accumulator. 953 HOTP: An HMAC-based One Time Password Algorithm October 2004 955 Consider the following game involving an adversary B that is 956 attempting to compromise the security of an authentication 957 algorithm ALG: K x {0,1}^c --> R. 959 Initializations - A key K is selected at random from K, a counter C 960 is initialized to 0, and the Boolean value win is set to false. 962 Game execution - Adversary B is provided with the two following 963 oracles: 965 Oracle AuthO() 966 -------------- 967 A = ALG(K,C) 968 C = C + 1 969 Return O to B 971 Oracle VerO(A) 972 -------------- 973 i = C 974 While (i <= C + s - 1 and Win == FALSE) do 975 If A == ALG(K,i) then Win = TRUE; C = i + 1 976 Else i = i + 1 977 Return Win to B 979 AuthO() is the authenticator oracle and VerO(A) is the verification 980 oracle. 982 Upon execution, B queries the two oracles at will. Let Adv(B) be 983 the probability that win gets set to true in the above game. This 984 is the probability that the adversary successfully impersonates the 985 user. 987 Our goal is to assess how large this value can be as a function of 988 the number v of verification queries made by B, the number a of 989 authenticator oracle queries made by B, and the running time t of 990 B. This will tell us how to set the throttle, which effectively 991 upper bounds v. 993 A.4 Security of the ideal authentication algorithm 995 This section summarizes the security analysis of HOTP-IDEAL, 996 starting with the impact of the conversion modulo 10^Digit and 997 then, focusing on the different possible attacks. 999 HOTP: An HMAC-based One Time Password Algorithm October 2004 1001 A.4.1 From bits to digits 1003 The dynamic offset truncation of a random n-bit string yields a 1004 random 31-bit string. What happens to the distribution when it is 1005 taken modulo m = 10^Digit, as done in HOTP? 1007 The following lemma estimates the biases in the outputs in this 1008 case. 1010 Lemma 1 1011 ------- 1012 Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in 1013 Z_{m} let: 1015 P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}] 1017 Then for any z in Z_{m} 1019 P_{N,m}(z) = (q + 1) / N if 0 <= z < r 1020 q / N if r <= z < m 1022 Proof of Lemma 1 1023 ---------------- 1024 Let the random variable X be uniformly distributed over Z_{N}. 1025 Then: 1027 P_{N,m}(z) = Pr [X mod m = z] 1029 = Pr [X < mq] * Pr [X mod m = z| X < mq] 1030 + Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N] 1032 = mq/N * 1/m + 1033 (N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq 1034 0 if N - mq <= z <= m 1036 = q/N + 1037 r/N * 1 / r if 0 <= z < N - mq 1038 0 if r <= z <= m 1040 Simplifying yields the claimed equation. 1042 Let N = 2^31, d = 6 and m = 10^d. If x is chosen at random from 1043 Z_{N} (meaning, is a random 31-bit string), then reducing it to a 1044 6-digit number by taking x mod m does not yield a random 6-digit 1045 number. 1047 Rather, x mod m is distributed as shown in the following table: 1049 Values Probability that each appears as output 1050 HOTP: An HMAC-based One Time Password Algorithm October 2004 1052 ---------------------------------------------------------------- 1053 0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6 1054 483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6 1056 If X is uniformly distributed over Z_{2^31} (meaning is a random 1057 31-bit string) then the above shows the probabilities for different 1058 outputs of X mod 10^6. The first set of values appear with 1059 probability slightly greater than 10^-6, the rest with probability 1060 slightly less, meaning the distribution is slightly non-uniform. 1062 However, as the Figure indicates, the bias is small and as we will 1063 see later, negligible: the probabilities are very close to 10^-6. 1065 A.4.2 Brute force attacks 1067 If the authenticator consisted of d random digits, then a brute 1068 force attack using v verification attempts would succeed with 1069 probability sv/10^Digit. 1071 However, an adversary can exploit the bias in the outputs of HOTP- 1072 IDEAL, predicted by Lemma 1, to mount a slightly better attack. 1074 Namely, it makes authentication attempts with authenticators which 1075 are the most likely values, meaning the ones in the range 0,...,r - 1076 1, where (q,r) = IntDiv(2^31,10^Digit). 1078 The following specifies an adversary in our model of security that 1079 mounts the attack. It estimates the success probability as a 1080 function of the number of verification queries. 1082 For simplicity, we assume the number of verification queries is at 1083 most r. With N = 2^31 and m = 10^6 we have r = 483,648, and the 1084 throttle value is certainly less than this, so this assumption is 1085 not much of a restriction. 1087 Proposition 1 1088 ------------- 1089 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume 1090 s <= m. The brute-force attack adversary B-bf attacks HOTP using v 1091 <= r verification oracle queries. This adversary makes no 1092 authenticator oracle queries, and succeeds with probability 1094 Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s 1096 which is roughly equals to 1098 sv * (q+1)/2^31 1099 HOTP: An HMAC-based One Time Password Algorithm October 2004 1101 With m = 10^6 we get q = 2,147. In that case, the brute force 1102 attack using v verification attempts succeeds with probability 1104 Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6 1106 As this equation shows, the resynchronization parameter s has a 1107 significant impact in that the adversary's success probability is 1108 proportional to s. This means that s cannot be made too large 1109 without compromising security. 1111 A.4.3 Brute force attacks are the best possible attacks 1113 A central question is whether there are attacks any better than the 1114 brute force one. In particular, the brute force attack did not 1115 attempt to collect authenticators sent by the user and try to 1116 cryptanalyze them in an attempt to learn how to better construct 1117 authenticators. Would doing this help? Is there some way to "learn" 1118 how to build authenticators that result in a higher success rate 1119 than given by the brute-force attack? 1121 The following says the answer to these questions is no. No matter 1122 what strategy the adversary uses, and even if it sees, and tries to 1123 exploit, the authenticators from authentication attempts of the 1124 user, its success probability will not be above that of the brute 1125 force attack - this is true as long as the number of 1126 authentications it observes is not incredibly large. This is 1127 valuable information regarding the security of the scheme. 1129 Proposition 2 1130 ------------- 1131 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B 1132 be any adversary attacking HOTP-IDEAL using v verification oracle 1133 queries and a <= 2^c - s authenticator oracle queries. Then 1135 Adv(B) < = sv * (q+1)/ 2^31 1137 Note: This result is conditional on the adversary not seeing more 1138 than 2^c - s authentications performed by the user, which is hardly 1139 restrictive as long as c is large enough. 1141 With m = 10^6 we get q = 2,147. In that case, Proposition 2 says 1142 that any adversary B attacking HOTP-IDEAL and making v verification 1143 attempts succeeds with probability at most 1145 Equation 1 1146 ---------- 1147 sv * 2148/2^31 roughly = sv * 1.00024045/10^6 1148 HOTP: An HMAC-based One Time Password Algorithm October 2004 1150 Meaning, B's success rate is not more than that achieved by the 1151 brute force attack. 1153 A.5 Security Analysis of HOTP 1155 We have analyzed in the previous sections, the security of the 1156 idealized counterparts HOTP-IDEAL of the actual authentication 1157 algorithm HOTP. We now show that, under appropriate and 1158 well-believed assumption on H, the security of the actual 1159 algorithms is essentially the same as that of its idealized 1160 counterpart. 1162 The assumption in question is that H is a secure pseudorandom 1163 function, or PRF, meaning that its input-output values are 1164 indistinguishable from those of a random function in practice. 1166 Consider an adversary A that is given an oracle for a function f: 1167 {0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A) 1168 as the prf-advantage of A, which represents how well the adversary 1169 does at distinguishing the case where its oracle is H(K,.) from the 1170 case where its oracle is a random function of {0,1}^c to {0,1}^n. 1172 One possible attack is based on exhaustive search for the key K. If 1173 A runs for t steps and T denotes the time to perform one 1174 computation of H, its prf-advantage from this attack turns out to 1175 be (t/T)2^-k . Another possible attack is a birthday one [PrOo], 1176 whereby A can attain advantage p^2/2^n in p oracle queries and 1177 running time about pT. 1179 Our assumption is that these are the best possible attacks. This 1180 translates into the following. 1182 Assumption 1 1183 ------------ 1185 Let T denotes the time to perform one computation of H. Then if A 1186 is any adversary with running time at most t and making at most p 1187 oracle queries, 1189 Adv(A) <= (t/T)/2^k + p^2/2^n 1191 In practice this assumption means that H is very secure as PRF. For 1192 example, given that k = n = 160, an attacker with running time 2^60 1193 and making 2^40 oracle queries has advantage at most (about) 2^-80. 1195 Theorem 1 1196 --------- 1197 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B 1198 be any adversary attacking HOTP using v verification oracle 1199 HOTP: An HMAC-based One Time Password Algorithm October 2004 1201 queries, a <= 2^c - s authenticator oracle queries, and running 1202 time t. Let T denote the time to perform one computation of H. If 1203 Assumption 1 is true then 1205 Adv(B) <= sv * (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n 1207 In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller 1208 than the sv(q + 1)/2^n term, so that the above says that for all 1209 practical purposes the success rate of an adversary attacking HOTP 1210 is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP 1211 algorithm is in practice essentially as good as its idealized 1212 counterpart. 1214 In the case m = 10^6 of a 6-digit output this means that an 1215 adversary making v authentication attempts will have a success rate 1216 that is at most that of Equation 1. 1218 For example, consider an adversary with running time at most 2^60 1219 that sees at most 2^40 authentication attempts of the user. Both 1220 these choices are very generous to the adversary, who will 1221 typically not have these resources, but we are saying that even 1222 such a powerful adversary will not have more success than indicated 1223 by Equation 1. 1225 We can safely assume sv <= 2^40 due to the throttling and bounds on 1226 s. So: 1227 (t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160 1228 roughly <= 2^-78 1230 which is much smaller than the success probability of Equation 1 1231 and negligible compared to it. 1233 Appendix B - SHA-1 Attacks 1235 This sections addresses the impact of the recent attacks on SHA-1 1236 on the security of the HMAC-SHA-1 based HOTP. We begin with some 1237 discussion of the situation of SHA-1 and then discuss the relevance 1238 to HMAC-SHA-1 and HOTP. Cited references are at the bottom of the 1239 document. 1241 B.1 SHA-1 status 1243 A collision for a hash function h means a pair x,y of different 1244 inputs such that h(x)=h(y). Since SHA-1 outputs 160 bits, a 1245 birthday attack finds a collision in 2^{80} trials. (A trial means 1246 one computation of the function.) This was thought to be the best 1247 possible until Wang, Yin and Yu announced on February 15, 2005 that 1248 they had an attack finding collisions in 2^{69} trials. 1250 HOTP: An HMAC-based One Time Password Algorithm October 2004 1252 Is SHA-1 broken? For most practical purposes we would say probably 1253 not, since the resources needed to mount the attack are huge. Here 1254 is one way to get a sense of it: we can estimate it is about the 1255 same as the time we would need to factor a 760-bit RSA modulus, and 1256 this is currently considered out of reach. 1258 Burr of NIST is quoted [Crack] as saying ``Large national 1259 intelligence agencies could do this in a reasonable amount of time 1260 with a few million dollars in computer time.'' However, the 1261 computation may be out of reach of all but such well-funded 1262 agencies. 1264 One should also ask what impact finding SHA-1 collisions actually 1265 has on security of real applications such as signatures. To exploit 1266 a collision x,y to forge signatures, you need to somehow obtain a 1267 signature of x and then you can forge a signature of y. How 1268 damaging this is depends on the content of y: the y created by the 1269 attack may not be meaningful in the application context. Also, one 1270 needs a chosen-message attack to get the signature of x. This seems 1271 possible in some contexts, but not others. Overall, it is not clear 1272 the impact on the security of signatures is significant. 1274 Indeed, one can read that SHA-1 is ``broken,'' [Sha1], that 1275 encryption and SSL are ``broken'' [Res], in the press. The media 1276 have a tendency to magnify events: it would hardly be interesting 1277 to announce in the news that a team of cryptanalysts did very 1278 interesting theoretical work in attacking SHA-1. 1280 Cryptographers are excited too. But mainly because this is an 1281 important theoretical breakthrough. Attacks can only get beter with 1282 time: it is therefore important to monitor any progress in hash 1283 functions cryptanalysis and be prepared for any really practical 1284 break with a sound migration plan for the future. 1286 B.2 HMAC-SHA-1 status 1288 The new attacks on SHA-1 have no impact on the security of HMAC- 1289 SHA-1. The best attack on the latter remains one needing a sender 1290 to authenticate 2^{80} messages before an adversary can create a 1291 forgery. Why? 1293 HMAC is not a hash function. It is a message authentication code 1294 (MAC) that uses a hash function internally. A MAC depends on a 1295 secret key, while hash functions don't. What one needs to worry 1296 about with a MAC is forgery, not collisions. HMAC was designed so 1297 that collisions in the hash function (here SHA-1) do not yield 1298 forgeries for HMAC. 1300 HOTP: An HMAC-based One Time Password Algorithm October 2004 1302 Recall that HMAC-SHA-1(K,x) = SHA-1(K_o,SHA-1(K_i,x)) where the 1303 keys K_o,K_i are derived from K. Suppose the attacker finds a pair 1304 x,y such that SHA-1(K_i,x)=SHA-1(K_i,y). (Call this a hidden-key 1305 collision.) Then if it can obtain the MAC of x (itself a tall 1306 order), it can forge the MAC of y. (These values are the same.) But 1307 finding hidden-key collisions is harder than finding collisions, 1308 because the attacker does not know the hidden key K_i. All it may 1309 have is some outputs of HMAC-SHA-1 with key K. To date there are no 1310 claims or evidence that the recent attacks on SHA-1 extend to find 1311 hidden-key collisions. 1313 Historically, the HMAC design has already proven itself in this 1314 regard. MD5 is considered broken in that collisions in this hash 1315 function can be found relatively easily. But there is still no 1316 attack on HMAC-MD5 better than the trivial 2^{64} time birthday 1317 one. (MD5 outputs 128 bits, not 160.) We are seeing this strength 1318 of HMAC coming into play again in the SHA-1 context. 1320 B.3 HOTP status 1322 Since no new weakness has surfaced in HMAC-SHA-1, there is no 1323 impact on HOTP. The best attacks on HOTP remain those described in 1324 the document, namely to try to guess output values. 1326 The security proof of HOTP requires that HMAC-SHA-1 behave like a 1327 pseudorandom function. The quality of HMAC-SHA-1 as a pseudorandom 1328 function is not impacted by the new attacks on SHA-1, and so 1329 neither is this proven guarantee. 1331 Appendix C - HOTP Algorithm: Reference Implementation 1333 /* 1334 * OneTimePasswordAlgorithm.java 1335 * OATH Initiative, 1336 * HOTP one-time password algorithm 1337 * 1338 */ 1340 /* Copyright (C) 2004, OATH. All rights reserved. 1341 * 1342 * License to copy and use this software is granted provided that it 1343 * is identified as the "OATH HOTP Algorithm" in all material 1344 * mentioning or referencing this software or this function. 1345 * 1346 * License is also granted to make and use derivative works provided 1347 * that such works are identified as 1348 * "derived from OATH HOTP algorithm" 1349 * in all material mentioning or referencing the derived work. 1351 HOTP: An HMAC-based One Time Password Algorithm October 2004 1353 * 1354 * OATH (Open AuTHentication) and its members make no 1355 * representations concerning either the merchantability of this 1356 * software or the suitability of this software for any particular 1357 * purpose. 1358 * 1359 * It is provided "as is" without express or implied warranty 1360 * of any kind and OATH AND ITS MEMBERS EXPRESSELY DISCLAIMS 1361 * ANY WARRANTY OR LIABILITY OF ANY KIND relating to this software. 1362 * 1363 * These notices must be retained in any copies of any part of this 1364 * documentation and/or software. 1365 */ 1367 package org.openauthentication.otp; 1369 import java.io.IOException; 1370 import java.io.File; 1371 import java.io.DataInputStream; 1372 import java.io.FileInputStream ; 1373 import java.lang.reflect.UndeclaredThrowableException; 1375 import java.security.GeneralSecurityException; 1376 import java.security.NoSuchAlgorithmException; 1377 import java.security.InvalidKeyException; 1379 import javax.crypto.Mac; 1380 import javax.crypto.spec.SecretKeySpec; 1382 /** 1383 * This class contains static methods that are used to calculate the 1384 * One-Time Password (OTP) using 1385 * JCE to provide the HMAC-SHA1. 1386 * 1387 * @author Loren Hart 1388 * @version 1.0 1389 */ 1390 public class OneTimePasswordAlgorithm { 1391 private OneTimePasswordAlgorithm() {} 1393 // These are used to calculate the check-sum digits. 1394 // 0 1 2 3 4 5 6 7 8 9 1395 private static final int[] doubleDigits = 1396 { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }; 1398 /** 1399 * Calculates the checksum using the credit card algorithm. 1400 * This algorithm has the advantage that it detects any single 1401 * mistyped digit and any single transposition of 1402 HOTP: An HMAC-based One Time Password Algorithm October 2004 1404 * adjacent digits. 1405 * 1406 * @param num the number to calculate the checksum for 1407 * @param digits number of significant places in the number 1408 * 1409 * @return the checksum of num 1410 */ 1411 public static int calcChecksum(long num, int digits) { 1412 boolean doubleDigit = true; 1413 int total = 0; 1414 while (0 < digits--) { 1415 int digit = (int) (num % 10); 1416 num /= 10; 1417 if (doubleDigit) { 1418 digit = doubleDigits[digit]; 1419 } 1420 total += digit; 1421 doubleDigit = !doubleDigit; 1422 } 1423 int result = total % 10; 1424 if (result > 0) { 1425 result = 10 - result; 1426 } 1427 return result; 1428 } 1430 /** 1431 * This method uses the JCE to provide the HMAC-SHA1 1432 * algorithm. 1433 * HMAC computes a Hashed Message Authentication Code and 1434 * in this case SHA1 is the hash algorithm used. 1435 * 1436 * @param keyBytes the bytes to use for the HMAC-SHA1 key 1437 * @param text the message or text to be authenticated. 1438 * 1439 * @throws NoSuchAlgorithmException if no provider makes 1440 * either HmacSHA1 or HMAC-SHA1 1441 * digest algorithms available. 1442 * @throws InvalidKeyException 1443 * The secret provided was not a valid HMAC-SHA1 key. 1444 * 1445 */ 1447 public static byte[] hmac_sha1(byte[] keyBytes, byte[] text) 1448 throws NoSuchAlgorithmException, InvalidKeyException 1449 { 1450 // try { 1451 Mac hmacSha1; 1452 try { 1453 HOTP: An HMAC-based One Time Password Algorithm October 2004 1455 hmacSha1 = Mac.getInstance("HmacSHA1"); 1456 } catch (NoSuchAlgorithmException nsae) { 1457 hmacSha1 = Mac.getInstance("HMAC-SHA1"); 1458 } 1459 SecretKeySpec macKey = 1460 new SecretKeySpec(keyBytes, "RAW"); 1461 hmacSha1.init(macKey); 1462 return hmacSha1.doFinal(text); 1463 // } catch (GeneralSecurityException gse) { 1464 // throw new UndeclaredThrowableException(gse); 1465 // } 1466 } 1468 private static final int[] DIGITS_POWER 1469 // 0 1 2 3 4 5 6 7 8 1470 = {1,10,100,1000,10000,100000,1000000,10000000,100000000}; 1472 /** 1473 * This method generates an OTP value for the given 1474 * set of parameters. 1475 * 1476 * @param secret the shared secret 1477 * @param movingFactor the counter, time, or other value that 1478 * changes on a per use basis. 1479 * @param codeDigits the number of digits in the OTP, not 1480 * including the checksum, if any. 1481 * @param addChecksum a flag that indicates if a checksum digit 1482 * should be appended to the OTP. 1483 * @param truncationOffset the offset into the MAC result to 1484 * begin truncation. If this value is out of 1485 * the range of 0 ... 15, then dynamic 1486 * truncation will be used. 1487 * Dynamic truncation is when the last 4 1488 * bits of the last byte of the MAC are 1489 * used to determine the start offset. 1490 * @throws NoSuchAlgorithmException if no provider makes 1491 * either HmacSHA1 or HMAC-SHA1 1492 * digest algorithms available. 1493 * @throws InvalidKeyException 1494 * The secret provided was not 1495 * a valid HMAC-SHA1 key. 1496 * 1497 * @return A numeric String in base 10 that includes 1498 * {@link codeDigits} digits plus the optional checksum 1499 * digit if requested. 1500 */ 1501 static public String generateOTP(byte[] secret, 1502 long movingFactor, 1503 int codeDigits, 1504 HOTP: An HMAC-based One Time Password Algorithm October 2004 1506 boolean addChecksum, 1507 int truncationOffset) 1508 throws NoSuchAlgorithmException, InvalidKeyException 1509 { 1510 // put movingFactor value into text byte array 1511 String result = null; 1512 int digits = addChecksum ? (codeDigits + 1) : codeDigits; 1513 byte[] text = new byte[8]; 1514 for (int i = text.length - 1; i >= 0; i--) { 1515 text[i] = (byte) (movingFactor & 0xff); 1516 movingFactor >>= 8; 1517 } 1519 // compute hmac hash 1520 byte[] hash = hmac_sha1(secret, text); 1522 // put selected bytes into result int 1523 int offset = hash[hash.length - 1] & 0xf; 1524 if ( (0<=truncationOffset) && 1525 (truncationOffset<(hash.length-4)) ) { 1526 offset = truncationOffset; 1527 } 1528 int binary = 1529 ((hash[offset] & 0x7f) << 24) 1530 | ((hash[offset + 1] & 0xff) << 16) 1531 | ((hash[offset + 2] & 0xff) << 8) 1532 | (hash[offset + 3] & 0xff); 1534 int otp = binary % DIGITS_POWER[codeDigits]; 1535 if (addChecksum) { 1536 otp = (otp * 10) + calcChecksum(otp, codeDigits); 1537 } 1538 result = Integer.toString(otp); 1539 while (result.length() < digits) { 1540 result = "0" + result; 1541 } 1542 return result; 1543 } 1544 } 1546 Appendix D - HOTP Algorithm: Test Values 1548 The following test data uses the ASCII string 1549 "123456787901234567890" for the secret: 1551 Secret = 0x3132333435363738393031323334353637383930 1553 Table 1 details for each count, the intermediate hmac value. 1555 HOTP: An HMAC-based One Time Password Algorithm October 2004 1557 Count Hexadecimal HMAC-SHA1(secret, count) 1558 0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0 1559 1 75a48a19d4cbe100644e8ac1397eea747a2d33ab 1560 2 0bacb7fa082fef30782211938bc1c5e70416ff44 1561 3 66c28227d03a2d5529262ff016a1e6ef76557ece 1562 4 a904c900a64b35909874b33e61c5938a8e15ed1c 1563 5 a37e783d7b7233c083d4f62926c7a25f238d0316 1564 6 bc9cd28561042c83f219324d3c607256c03272ae 1565 7 a4fb960c0bc06e1eabb804e5b397cdc4b45596fa 1566 8 1b3c89f65e6c9e883012052823443f048b4332db 1567 9 1637409809a679dc698207310c8c7fc07290d9e5 1569 Table details for each count the truncated values (both in 1570 hexadecimal and decimal) and then the HOTP value. 1572 Truncated 1573 Count Hexadecimal Decimal HOTP 1574 0 4c93cf18 1284755224 755224 1575 1 41397eea 1094287082 287082 1576 2 82fef30 137359152 359152 1577 3 66ef7655 1726969429 969429 1578 4 61c5938a 1640338314 338314 1579 5 33c083d4 868254676 254676 1580 6 7256c032 1918287922 287922 1581 7 4e5b397 82162583 162583 1582 8 2823443f 673399871 399871 1583 9 2679dc69 645520489 520489 1585 Full Copyright Statement 1587 Copyright (C) The Internet Society 2004. This document is subject 1588 to the rights, licenses and restrictions contained in BCP 78, and 1589 except as set forth therein, the authors retain all their rights. 1591 This document and the information contained herein are provided on 1592 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 1593 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND 1594 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, 1595 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT 1596 THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 1597 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 1598 PARTICULAR PURPOSE.