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