7 Network Working Group D. M'Raihi
8 Request for Comments: 4226 VeriSign
9 Category: Informational M. Bellare
20 HOTP: An HMAC-Based One-Time Password Algorithm
24 This memo provides information for the Internet community. It does
25 not specify an Internet standard of any kind. Distribution of this
30 Copyright (C) The Internet Society (2005).
34 This document describes an algorithm to generate one-time password
35 values, based on Hashed Message Authentication Code (HMAC). A
36 security analysis of the algorithm is presented, and important
37 parameters related to the secure deployment of the algorithm are
38 discussed. The proposed algorithm can be used across a wide range of
39 network applications ranging from remote Virtual Private Network
40 (VPN) access, Wi-Fi network logon to transaction-oriented Web
43 This work is a joint effort by the OATH (Open AuTHentication)
44 membership to specify an algorithm that can be freely distributed to
45 the technical community. The authors believe that a common and
46 shared algorithm will facilitate adoption of two-factor
47 authentication on the Internet by enabling interoperability across
48 commercial and open-source implementations.
58 M'Raihi, et al. Informational [Page 1]
60 RFC 4226 HOTP Algorithm December 2005
65 1. Overview ........................................................3
66 2. Introduction ....................................................3
67 3. Requirements Terminology ........................................4
68 4. Algorithm Requirements ..........................................4
69 5. HOTP Algorithm ..................................................5
70 5.1. Notation and Symbols .......................................5
71 5.2. Description ................................................6
72 5.3. Generating an HOTP Value ...................................6
73 5.4. Example of HOTP Computation for Digit = 6 ..................7
74 6. Security Considerations .........................................8
75 7. Security Requirements ...........................................9
76 7.1. Authentication Protocol Requirements .......................9
77 7.2. Validation of HOTP Values .................................10
78 7.3. Throttling at the Server ..................................10
79 7.4. Resynchronization of the Counter ..........................11
80 7.5. Management of Shared Secrets ..............................11
81 8. Composite Shared Secrets .......................................14
82 9. Bi-Directional Authentication ..................................14
83 10. Conclusion ....................................................15
84 11. Acknowledgements ..............................................15
85 12. Contributors ..................................................15
86 13. References ....................................................15
87 13.1. Normative References .....................................15
88 13.2. Informative References ...................................16
89 Appendix A - HOTP Algorithm Security: Detailed Analysis ...........17
90 A.1. Definitions and Notations .................................17
91 A.2. The Idealized Algorithm: HOTP-IDEAL .......................17
92 A.3. Model of Security .........................................18
93 A.4. Security of the Ideal Authentication Algorithm ............19
94 A.4.1. From Bits to Digits ................................19
95 A.4.2. Brute Force Attacks ................................21
96 A.4.3. Brute force attacks are the best possible attacks ..22
97 A.5. Security Analysis of HOTP .................................23
98 Appendix B - SHA-1 Attacks ........................................25
99 B.1. SHA-1 Status ..............................................25
100 B.2. HMAC-SHA-1 Status .........................................26
101 B.3. HOTP Status ...............................................26
102 Appendix C - HOTP Algorithm: Reference Implementation .............27
103 Appendix D - HOTP Algorithm: Test Values ..........................32
104 Appendix E - Extensions ...........................................33
105 E.1. Number of Digits ..........................................33
106 E.2. Alphanumeric Values .......................................33
107 E.3. Sequence of HOTP values ...................................34
108 E.4. A Counter-Based Resynchronization Method ..................34
109 E.5. Data Field ................................................35
114 M'Raihi, et al. Informational [Page 2]
116 RFC 4226 HOTP Algorithm December 2005
121 The document introduces first the context around an algorithm that
122 generates one-time password values based on HMAC [BCK1] and, thus, is
123 named the HMAC-Based One-Time Password (HOTP) algorithm. In Section
124 4, the algorithm requirements are listed and in Section 5, the HOTP
125 algorithm is described. Sections 6 and 7 focus on the algorithm
126 security. Section 8 proposes some extensions and improvements, and
127 Section 10 concludes this document. In Appendix A, the interested
128 reader will find a detailed, full-fledged analysis of the algorithm
129 security: an idealized version of the algorithm is evaluated, and
130 then the HOTP algorithm security is analyzed.
134 Today, deployment of two-factor authentication remains extremely
135 limited in scope and scale. Despite increasingly higher levels of
136 threats and attacks, most Internet applications still rely on weak
137 authentication schemes for policing user access. The lack of
138 interoperability among hardware and software technology vendors has
139 been a limiting factor in the adoption of two-factor authentication
140 technology. In particular, the absence of open specifications has
141 led to solutions where hardware and software components are tightly
142 coupled through proprietary technology, resulting in high-cost
143 solutions, poor adoption, and limited innovation.
145 In the last two years, the rapid rise of network threats has exposed
146 the inadequacies of static passwords as the primary mean of
147 authentication on the Internet. At the same time, the current
148 approach that requires an end user to carry an expensive, single-
149 function device that is only used to authenticate to the network is
150 clearly not the right answer. For two-factor authentication to
151 propagate on the Internet, it will have to be embedded in more
152 flexible devices that can work across a wide range of applications.
154 The ability to embed this base technology while ensuring broad
155 interoperability requires that it be made freely available to the
156 broad technical community of hardware and software developers. Only
157 an open-system approach will ensure that basic two-factor
158 authentication primitives can be built into the next generation of
159 consumer devices such as USB mass storage devices, IP phones, and
160 personal digital assistants.
162 One-Time Password is certainly one of the simplest and most popular
163 forms of two-factor authentication for securing network access. For
164 example, in large enterprises, Virtual Private Network access often
165 requires the use of One-Time Password tokens for remote user
166 authentication. One-Time Passwords are often preferred to stronger
170 M'Raihi, et al. Informational [Page 3]
172 RFC 4226 HOTP Algorithm December 2005
175 forms of authentication such as Public-Key Infrastructure (PKI) or
176 biometrics because an air-gap device does not require the
177 installation of any client desktop software on the user machine,
178 therefore allowing them to roam across multiple machines including
179 home computers, kiosks, and personal digital assistants.
181 This document proposes a simple One-Time Password algorithm that can
182 be implemented by any hardware manufacturer or software developer to
183 create interoperable authentication devices and software agents. The
184 algorithm is event-based so that it can be embedded in high-volume
185 devices such as Java smart cards, USB dongles, and GSM SIM cards.
186 The presented algorithm is made freely available to the developer
187 community under the terms and conditions of the IETF Intellectual
188 Property Rights [RFC3979].
190 The authors of this document are members of the Open AuTHentication
191 initiative [OATH]. The initiative was created in 2004 to facilitate
192 collaboration among strong authentication technology providers.
194 3. Requirements Terminology
196 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
197 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
198 document are to be interpreted as described in [RFC2119].
200 4. Algorithm Requirements
202 This section presents the main requirements that drove this algorithm
203 design. A lot of emphasis was placed on end-consumer usability as
204 well as the ability for the algorithm to be implemented by low-cost
205 hardware that may provide minimal user interface capabilities. In
206 particular, the ability to embed the algorithm into high-volume SIM
207 and Java cards was a fundamental prerequisite.
209 R1 - The algorithm MUST be sequence- or counter-based: one of the
210 goals is to have the HOTP algorithm embedded in high-volume devices
211 such as Java smart cards, USB dongles, and GSM SIM cards.
213 R2 - The algorithm SHOULD be economical to implement in hardware by
214 minimizing requirements on battery, number of buttons, computational
215 horsepower, and size of LCD display.
217 R3 - The algorithm MUST work with tokens that do not support any
218 numeric input, but MAY also be used with more sophisticated devices
219 such as secure PIN-pads.
221 R4 - The value displayed on the token MUST be easily read and entered
222 by the user: This requires the HOTP value to be of reasonable length.
226 M'Raihi, et al. Informational [Page 4]
228 RFC 4226 HOTP Algorithm December 2005
231 The HOTP value must be at least a 6-digit value. It is also
232 desirable that the HOTP value be 'numeric only' so that it can be
233 easily entered on restricted devices such as phones.
235 R5 - There MUST be user-friendly mechanisms available to
236 resynchronize the counter. Section 7.4 and Appendix E.4 details the
237 resynchronization mechanism proposed in this document
239 R6 - The algorithm MUST use a strong shared secret. The length of
240 the shared secret MUST be at least 128 bits. This document
241 RECOMMENDs a shared secret length of 160 bits.
245 In this section, we introduce the notation and describe the HOTP
246 algorithm basic blocks -- the base function to compute an HMAC-SHA-1
247 value and the truncation method to extract an HOTP value.
249 5.1. Notation and Symbols
251 A string always means a binary string, meaning a sequence of zeros
254 If s is a string, then |s| denotes its length.
256 If n is a number, then |n| denotes its absolute value.
258 If s is a string, then s[i] denotes its i-th bit. We start numbering
259 the bits at 0, so s = s[0]s[1]...s[n-1] where n = |s| is the length
262 Let StToNum (String to Number) denote the function that as input a
263 string s returns the number whose binary representation is s. (For
264 example, StToNum(110) = 6.)
266 Here is a list of symbols used in this document.
269 -------------------------------------------------------------------
270 C 8-byte counter value, the moving factor. This counter
271 MUST be synchronized between the HOTP generator (client)
272 and the HOTP validator (server).
274 K shared secret between client and server; each HOTP
275 generator has a different and unique secret K.
277 T throttling parameter: the server will refuse connections
278 from a user after T unsuccessful authentication attempts.
282 M'Raihi, et al. Informational [Page 5]
284 RFC 4226 HOTP Algorithm December 2005
288 s resynchronization parameter: the server will attempt to
289 verify a received authenticator across s consecutive
292 Digit number of digits in an HOTP value; system parameter.
296 The HOTP algorithm is based on an increasing counter value and a
297 static symmetric key known only to the token and the validation
298 service. In order to create the HOTP value, we will use the HMAC-
299 SHA-1 algorithm, as defined in RFC 2104 [BCK2].
301 As the output of the HMAC-SHA-1 calculation is 160 bits, we must
302 truncate this value to something that can be easily entered by a
305 HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
309 - Truncate represents the function that converts an HMAC-SHA-1
310 value into an HOTP value as defined in Section 5.3.
312 The Key (K), the Counter (C), and Data values are hashed high-order
315 The HOTP values generated by the HOTP generator are treated as big
318 5.3. Generating an HOTP Value
320 We can describe the operations in 3 distinct steps:
322 Step 1: Generate an HMAC-SHA-1 value Let HS = HMAC-SHA-1(K,C) // HS
325 Step 2: Generate a 4-byte string (Dynamic Truncation)
326 Let Sbits = DT(HS) // DT, defined below,
327 // returns a 31-bit string
329 Step 3: Compute an HOTP value
330 Let Snum = StToNum(Sbits) // Convert S to a number in
332 Return D = Snum mod 10^Digit // D is a number in the range
338 M'Raihi, et al. Informational [Page 6]
340 RFC 4226 HOTP Algorithm December 2005
343 The Truncate function performs Step 2 and Step 3, i.e., the dynamic
344 truncation and then the reduction modulo 10^Digit. The purpose of
345 the dynamic offset truncation technique is to extract a 4-byte
346 dynamic binary code from a 160-bit (20-byte) HMAC-SHA-1 result.
348 DT(String) // String = String[0]...String[19]
349 Let OffsetBits be the low-order 4 bits of String[19]
350 Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
351 Let P = String[OffSet]...String[OffSet+3]
352 Return the Last 31 bits of P
354 The reason for masking the most significant bit of P is to avoid
355 confusion about signed vs. unsigned modulo computations. Different
356 processors perform these operations differently, and masking out the
357 signed bit removes all ambiguity.
359 Implementations MUST extract a 6-digit code at a minimum and possibly
360 7 and 8-digit code. Depending on security requirements, Digit = 7 or
361 more SHOULD be considered in order to extract a longer HOTP value.
363 The following paragraph is an example of using this technique for
364 Digit = 6, i.e., that a 6-digit HOTP value is calculated from the
367 5.4. Example of HOTP Computation for Digit = 6
369 The following code example describes the extraction of a dynamic
370 binary code given that hmac_result is a byte array with the HMAC-
373 int offset = hmac_result[19] & 0xf ;
374 int bin_code = (hmac_result[offset] & 0x7f) << 24
375 | (hmac_result[offset+1] & 0xff) << 16
376 | (hmac_result[offset+2] & 0xff) << 8
377 | (hmac_result[offset+3] & 0xff) ;
379 SHA-1 HMAC Bytes (Example)
381 -------------------------------------------------------------
383 -------------------------------------------------------------
384 |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
385 -------------------------------------------------------------
387 -------------------------------------------------------------
388 |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a|
389 -------------------------------***********----------------++|
394 M'Raihi, et al. Informational [Page 7]
396 RFC 4226 HOTP Algorithm December 2005
399 * The last byte (byte 19) has the hex value 0x5a.
400 * The value of the lower 4 bits is 0xa (the offset value).
401 * The offset value is byte 10 (0xa).
402 * The value of the 4 bytes starting at byte 10 is 0x50ef7f19,
403 which is the dynamic binary code DBC1.
404 * The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19 .
405 * HOTP = DBC2 modulo 10^6 = 872921.
407 We treat the dynamic binary code as a 31-bit, unsigned, big-endian
408 integer; the first byte is masked with a 0x7f.
410 We then take this number modulo 1,000,000 (10^6) to generate the 6-
411 digit HOTP value 872921 decimal.
413 6. Security Considerations
415 The conclusion of the security analysis detailed in the Appendix is
416 that, for all practical purposes, the outputs of the Dynamic
417 Truncation (DT) on distinct counter inputs are uniformly and
418 independently distributed 31-bit strings.
420 The security analysis then details the impact of the conversion from
421 a string to an integer and the final reduction modulo 10^Digit, where
422 Digit is the number of digits in an HOTP value.
424 The analysis demonstrates that these final steps introduce a
425 negligible bias, which does not impact the security of the HOTP
426 algorithm, in the sense that the best possible attack against the
427 HOTP function is the brute force attack.
429 Assuming an adversary is able to observe numerous protocol exchanges
430 and collect sequences of successful authentication values. This
431 adversary, trying to build a function F to generate HOTP values based
432 on his observations, will not have a significant advantage over a
435 The logical conclusion is simply that the best strategy will once
436 again be to perform a brute force attack to enumerate and try all the
439 Considering the security analysis in the Appendix of this document,
440 without loss of generality, we can approximate closely the security
441 of the HOTP algorithm by the following formula:
450 M'Raihi, et al. Informational [Page 8]
452 RFC 4226 HOTP Algorithm December 2005
456 - Sec is the probability of success of the adversary;
457 - s is the look-ahead synchronization window size;
458 - v is the number of verification attempts;
459 - Digit is the number of digits in HOTP values.
461 Obviously, we can play with s, T (the Throttling parameter that would
462 limit the number of attempts by an attacker), and Digit until
463 achieving a certain level of security, still preserving the system
466 7. Security Requirements
468 Any One-Time Password algorithm is only as secure as the application
469 and the authentication protocols that implement it. Therefore, this
470 section discusses the critical security requirements that our choice
471 of algorithm imposes on the authentication protocol and validation
474 The parameters T and s discussed in this section have a significant
475 impact on the security -- further details in Section 6 elaborate on
476 the relations between these parameters and their impact on the system
479 It is also important to remark that the HOTP algorithm is not a
480 substitute for encryption and does not provide for the privacy of
481 data transmission. Other mechanisms should be used to defeat attacks
482 aimed at breaking confidentiality and privacy of transactions.
484 7.1. Authentication Protocol Requirements
486 We introduce in this section some requirements for a protocol P
487 implementing HOTP as the authentication method between a prover and a
490 RP1 - P MUST support two-factor authentication, i.e., the
491 communication and verification of something you know (secret code
492 such as a Password, Pass phrase, PIN code, etc.) and something you
493 have (token). The secret code is known only to the user and usually
494 entered with the One-Time Password value for authentication purpose
495 (two-factor authentication).
497 RP2 - P SHOULD NOT be vulnerable to brute force attacks. This
498 implies that a throttling/lockout scheme is RECOMMENDED on the
499 validation server side.
501 RP3 - P SHOULD be implemented over a secure channel in order to
502 protect users' privacy and avoid replay attacks.
506 M'Raihi, et al. Informational [Page 9]
508 RFC 4226 HOTP Algorithm December 2005
511 7.2. Validation of HOTP Values
513 The HOTP client (hardware or software token) increments its counter
514 and then calculates the next HOTP value HOTP client. If the value
515 received by the authentication server matches the value calculated by
516 the client, then the HOTP value is validated. In this case, the
517 server increments the counter value by one.
519 If the value received by the server does not match the value
520 calculated by the client, the server initiate the resynch protocol
521 (look-ahead window) before it requests another pass.
523 If the resynch fails, the server asks then for another
524 authentication pass of the protocol to take place, until the
525 maximum number of authorized attempts is reached.
527 If and when the maximum number of authorized attempts is reached, the
528 server SHOULD lock out the account and initiate a procedure to inform
531 7.3. Throttling at the Server
533 Truncating the HMAC-SHA-1 value to a shorter value makes a brute
534 force attack possible. Therefore, the authentication server needs to
535 detect and stop brute force attacks.
537 We RECOMMEND setting a throttling parameter T, which defines the
538 maximum number of possible attempts for One-Time Password validation.
539 The validation server manages individual counters per HOTP device in
540 order to take note of any failed attempt. We RECOMMEND T not to be
541 too large, particularly if the resynchronization method used on the
542 server is window-based, and the window size is large. T SHOULD be
543 set as low as possible, while still ensuring that usability is not
544 significantly impacted.
546 Another option would be to implement a delay scheme to avoid a brute
547 force attack. After each failed attempt A, the authentication server
548 would wait for an increased T*A number of seconds, e.g., say T = 5,
549 then after 1 attempt, the server waits for 5 seconds, at the second
550 failed attempt, it waits for 5*2 = 10 seconds, etc.
552 The delay or lockout schemes MUST be across login sessions to prevent
553 attacks based on multiple parallel guessing techniques.
562 M'Raihi, et al. Informational [Page 10]
564 RFC 4226 HOTP Algorithm December 2005
567 7.4. Resynchronization of the Counter
569 Although the server's counter value is only incremented after a
570 successful HOTP authentication, the counter on the token is
571 incremented every time a new HOTP is requested by the user. Because
572 of this, the counter values on the server and on the token might be
573 out of synchronization.
575 We RECOMMEND setting a look-ahead parameter s on the server, which
576 defines the size of the look-ahead window. In a nutshell, the server
577 can recalculate the next s HOTP-server values, and check them against
578 the received HOTP client.
580 Synchronization of counters in this scenario simply requires the
581 server to calculate the next HOTP values and determine if there is a
582 match. Optionally, the system MAY require the user to send a
583 sequence of (say, 2, 3) HOTP values for resynchronization purpose,
584 since forging a sequence of consecutive HOTP values is even more
585 difficult than guessing a single HOTP value.
587 The upper bound set by the parameter s ensures the server does not go
588 on checking HOTP values forever (causing a denial-of-service attack)
589 and also restricts the space of possible solutions for an attacker
590 trying to manufacture HOTP values. s SHOULD be set as low as
591 possible, while still ensuring that usability is not impacted.
593 7.5. Management of Shared Secrets
595 The operations dealing with the shared secrets used to generate and
596 verify OTP values must be performed securely, in order to mitigate
597 risks of any leakage of sensitive information. We describe in this
598 section different modes of operations and techniques to perform these
599 different operations with respect to the state of the art in data
602 We can consider two different avenues for generating and storing
603 (securely) shared secrets in the Validation system:
605 * Deterministic Generation: secrets are derived from a master
606 seed, both at provisioning and verification stages and generated
607 on-the-fly whenever it is required.
608 * Random Generation: secrets are generated randomly at
609 provisioning stage and must be stored immediately and kept
610 secure during their life cycle.
618 M'Raihi, et al. Informational [Page 11]
620 RFC 4226 HOTP Algorithm December 2005
623 Deterministic Generation
624 ------------------------
626 A possible strategy is to derive the shared secrets from a master
627 secret. The master secret will be stored at the server only. A
628 tamper-resistant device MUST be used to store the master key and
629 derive the shared secrets from the master key and some public
630 information. The main benefit would be to avoid the exposure of the
631 shared secrets at any time and also avoid specific requirements on
632 storage, since the shared secrets could be generated on-demand when
633 needed at provisioning and validation time.
635 We distinguish two different cases:
637 - A single master key MK is used to derive the shared secrets;
638 each HOTP device has a different secret, K_i = SHA-1 (MK,i)
639 where i stands for a public piece of information that identifies
640 uniquely the HOTP device such as a serial number, a token ID,
641 etc. Obviously, this is in the context of an application or
642 service -- different application or service providers will have
643 different secrets and settings.
644 - Several master keys MK_i are used and each HOTP device stores a
645 set of different derived secrets, {K_i,j = SHA-1(MK_i,j)} where
646 j stands for a public piece of information identifying the
647 device. The idea would be to store ONLY the active master key
648 at the validation server, in the Hardware Security Module (HSM),
649 and keep in a safe place, using secret sharing methods such as
650 [Shamir] for instance. In this case, if a master secret MK_i is
651 compromised, then it is possible to switch to another secret
652 without replacing all the devices.
654 The drawback in the deterministic case is that the exposure of the
655 master secret would obviously enable an attacker to rebuild any
656 shared secret based on correct public information. The revocation of
657 all secrets would be required, or switching to a new set of secrets
658 in the case of multiple master keys.
660 On the other hand, the device used to store the master key(s) and
661 generate the shared secrets MUST be tamper resistant. Furthermore,
662 the HSM will not be exposed outside the security perimeter of the
663 validation system, therefore reducing the risk of leakage.
674 M'Raihi, et al. Informational [Page 12]
676 RFC 4226 HOTP Algorithm December 2005
682 The shared secrets are randomly generated. We RECOMMEND following
683 the recommendations in [RFC4086] and selecting a good and secure
684 random source for generating these secrets. A (true) random
685 generator requires a naturally occurring source of randomness.
686 Practically, there are two possible avenues to consider for the
687 generation of the shared secrets:
689 * Hardware-based generators: they exploit the randomness that
690 occurs in physical phenomena. A nice implementation can be based on
691 oscillators and built in such ways that active attacks are more
692 difficult to perform.
694 * Software-based generators: designing a good software random
695 generator is not an easy task. A simple, but efficient,
696 implementation should be based on various sources and apply to the
697 sampled sequence a one-way function such as SHA-1.
699 We RECOMMEND selecting proven products, being hardware or software
700 generators, for the computation of shared secrets.
702 We also RECOMMEND storing the shared secrets securely, and more
703 specifically encrypting the shared secrets when stored using tamper-
704 resistant hardware encryption and exposing them only when required:
705 for example, the shared secret is decrypted when needed to verify an
706 HOTP value, and re-encrypted immediately to limit exposure in the RAM
707 for a short period of time. The data store holding the shared
708 secrets MUST be in a secure area, to avoid as much as possible direct
709 attack on the validation system and secrets database.
711 Particularly, access to the shared secrets should be limited to
712 programs and processes required by the validation system only. We
713 will not elaborate on the different security mechanisms to put in
714 place, but obviously, the protection of shared secrets is of the
715 uttermost importance.
730 M'Raihi, et al. Informational [Page 13]
732 RFC 4226 HOTP Algorithm December 2005
735 8. Composite Shared Secrets
737 It may be desirable to include additional authentication factors in
738 the shared secret K. These additional factors can consist of any
739 data known at the token but not easily obtained by others. Examples
740 of such data include:
742 * PIN or Password obtained as user input at the token
744 * Any unique identifier programmatically available at the token
746 In this scenario, the composite shared secret K is constructed during
747 the provisioning process from a random seed value combined with one
748 or more additional authentication factors. The server could either
749 build on-demand or store composite secrets -- in any case, depending
750 on implementation choice, the token only stores the seed value. When
751 the token performs the HOTP calculation, it computes K from the seed
752 value and the locally derived or input values of the other
753 authentication factors.
755 The use of composite shared secrets can strengthen HOTP-based
756 authentication systems through the inclusion of additional
757 authentication factors at the token. To the extent that the token is
758 a trusted device, this approach has the further benefit of not
759 requiring exposure of the authentication factors (such as the user
760 input PIN) to other devices.
762 9. Bi-Directional Authentication
764 Interestingly enough, the HOTP client could also be used to
765 authenticate the validation server, claiming that it is a genuine
766 entity knowing the shared secret.
768 Since the HOTP client and the server are synchronized and share the
769 same secret (or a method to recompute it), a simple 3-pass protocol
770 could be put in place:
771 1- The end user enter the TokenID and a first OTP value OTP1;
772 2- The server checks OTP1 and if correct, sends back OTP2;
773 3- The end user checks OTP2 using his HOTP device and if correct,
776 Obviously, as indicated previously, all the OTP communications have
777 to take place over a secure channel, e.g., SSL/TLS, IPsec
786 M'Raihi, et al. Informational [Page 14]
788 RFC 4226 HOTP Algorithm December 2005
793 This document describes HOTP, a HMAC-based One-Time Password
794 algorithm. It also recommends the preferred implementation and
795 related modes of operations for deploying the algorithm.
797 The document also exhibits elements of security and demonstrates that
798 the HOTP algorithm is practical and sound, the best possible attack
799 being a brute force attack that can be prevented by careful
800 implementation of countermeasures in the validation server.
802 Eventually, several enhancements have been proposed, in order to
803 improve security if needed for specific applications.
807 The authors would like to thank Siddharth Bajaj, Alex Deacon, Loren
808 Hart, and Nico Popp for their help during the conception and
809 redaction of this document.
813 The authors of this document would like to emphasize the role of
814 three persons who have made a key contribution to this document:
816 - Laszlo Elteto is system architect with SafeNet, Inc.
818 - Ernesto Frutos is director of Engineering with Authenex, Inc.
820 - Fred McClain is Founder and CTO with Boojum Mobile, Inc.
822 Without their advice and valuable inputs, this document would not be
827 13.1. Normative References
829 [BCK1] M. Bellare, R. Canetti and H. Krawczyk, "Keyed Hash
830 Functions and Message Authentication", Proceedings of
831 Crypto'96, LNCS Vol. 1109, pp. 1-15.
833 [BCK2] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
834 Hashing for Message Authentication", RFC 2104, February
837 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
838 Requirement Levels", BCP 14, RFC 2119, March 1997.
842 M'Raihi, et al. Informational [Page 15]
844 RFC 4226 HOTP Algorithm December 2005
847 [RFC3979] Bradner, S., "Intellectual Property Rights in IETF
848 Technology", BCP 79, RFC 3979, March 2005.
850 [RFC4086] Eastlake, D., 3rd, Schiller, J., and S. Crocker,
851 "Randomness Requirements for Security", BCP 106, RFC 4086,
854 13.2. Informative References
856 [OATH] Initiative for Open AuTHentication
857 http://www.openauthentication.org
859 [PrOo] B. Preneel and P. van Oorschot, "MD-x MAC and building
860 fast MACs from hash functions", Advances in Cryptology
861 CRYPTO '95, Lecture Notes in Computer Science Vol. 963, D.
862 Coppersmith ed., Springer-Verlag, 1995.
864 [Crack] Crack in SHA-1 code 'stuns' security gurus
865 http://www.eetimes.com/showArticle.jhtml?
868 [Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005.
869 http://www.schneier.com/blog/archives/2005/02/
872 [Res] Researchers: Digital encryption standard flawed
874 Researchers+Digital+encryption+standard+flawed/
875 2100-1002-5579881.html?part=dht&tag=ntop&tag=nl.e703
877 [Shamir] How to Share a Secret, by Adi Shamir. In Communications
878 of the ACM, Vol. 22, No. 11, pp. 612-613, November, 1979.
898 M'Raihi, et al. Informational [Page 16]
900 RFC 4226 HOTP Algorithm December 2005
903 Appendix A - HOTP Algorithm Security: Detailed Analysis
905 The security analysis of the HOTP algorithm is summarized in this
906 section. We first detail the best attack strategies, and then
907 elaborate on the security under various assumptions and the impact of
908 the truncation and make some recommendations regarding the number of
911 We focus this analysis on the case where Digit = 6, i.e., an HOTP
912 function that produces 6-digit values, which is the bare minimum
913 recommended in this document.
915 A.1. Definitions and Notations
917 We denote by {0,1}^l the set of all strings of length l.
919 Let Z_{n} = {0,.., n - 1}.
921 Let IntDiv(a,b) denote the integer division algorithm that takes
922 input integers a, b where a >= b >= 1 and returns integers (q,r)
924 the quotient and remainder, respectively, of the division of a by b.
925 (Thus, a = bq + r and 0 <= r < b.)
927 Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that takes
928 a k-bit key K and c-bit counter C and returns an n-bit output H(K,C).
929 (In the case of HOTP, H is HMAC-SHA-1; we use this formal definition
930 for generalizing our proof of security.)
932 A.2. The Idealized Algorithm: HOTP-IDEAL
934 We now define an idealized counterpart of the HOTP algorithm. In
935 this algorithm, the role of H is played by a random function that
938 To be more precise, let Maps(c,n) denote the set of all functions
939 mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key
940 space Maps(c,n), so that a "key" for such an algorithm is a function
941 h from {0,1}^c to {0,1}^n. We imagine this key (function) to be
942 drawn at random. It is not feasible to implement this idealized
943 algorithm, since the key, being a function from {0,1}^c to {0,1}^n,
944 is way too large to even store. So why consider it?
946 Our security analysis will show that as long as H satisfies a certain
947 well-accepted assumption, the security of the actual and idealized
948 algorithms is for all practical purposes the same. The task that
949 really faces us, then, is to assess the security of the idealized
954 M'Raihi, et al. Informational [Page 17]
956 RFC 4226 HOTP Algorithm December 2005
959 In analyzing the idealized algorithm, we are concentrating on
960 assessing the quality of the design of the algorithm itself,
961 independently of HMAC-SHA-1. This is in fact the important issue.
963 A.3. Model of Security
965 The model exhibits the type of threats or attacks that are being
966 considered and enables one to assess the security of HOTP and HOTP-
967 IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the purpose of
968 this security analysis.
970 The scenario we are considering is that a user and server share a key
971 K for ALG. Both maintain a counter C, initially zero, and the user
972 authenticates itself by sending ALG(K,C) to the server. The latter
973 accepts if this value is correct.
975 In order to protect against accidental increment of the user counter,
976 the server, upon receiving a value z, will accept as long as z equals
977 ALG(K,i) for some i in the range C,...,C + s-1, where s is the
978 resynchronization parameter and C is the server counter. If it
979 accepts with some value of i, it then increments its counter to i+1.
980 If it does not accept, it does not change its counter value.
982 The model we specify captures what an adversary can do and what it
983 needs to achieve in order to "win". First, the adversary is assumed
984 to be able to eavesdrop, meaning, to see the authenticator
985 transmitted by the user. Second, the adversary wins if it can get
986 the server to accept an authenticator relative to a counter value for
987 which the user has never transmitted an authenticator.
989 The formal adversary, which we denote by B, starts out knowing which
990 algorithm ALG is being used, knowing the system design, and knowing
991 all system parameters. The one and only thing it is not given a
992 priori is the key K shared between the user and the server.
994 The model gives B full control of the scheduling of events. It has
995 access to an authenticator oracle representing the user. By calling
996 this oracle, the adversary can ask the user to authenticate itself
997 and get back the authenticator in return. It can call this oracle as
998 often as it wants and when it wants, using the authenticators it
999 accumulates to perhaps "learn" how to make authenticators itself. At
1000 any time, it may also call a verification oracle, supplying the
1001 latter with a candidate authenticator of its choice. It wins if the
1002 server accepts this accumulator.
1004 Consider the following game involving an adversary B that is
1005 attempting to compromise the security of an authentication algorithm
1006 ALG: K x {0,1}^c --> R.
1010 M'Raihi, et al. Informational [Page 18]
1012 RFC 4226 HOTP Algorithm December 2005
1015 Initializations - A key K is selected at random from K, a counter C
1016 is initialized to 0, and the Boolean value win is set to false.
1018 Game execution - Adversary B is provided with the two following
1030 While (i <= C + s - 1 and Win == FALSE) do
1031 If A == ALG(K,i) then Win = TRUE; C = i + 1
1035 AuthO() is the authenticator oracle and VerO(A) is the verification
1038 Upon execution, B queries the two oracles at will. Let Adv(B) be the
1039 probability that win gets set to true in the above game. This is the
1040 probability that the adversary successfully impersonates the user.
1042 Our goal is to assess how large this value can be as a function of
1043 the number v of verification queries made by B, the number a of
1044 authenticator oracle queries made by B, and the running time t of B.
1045 This will tell us how to set the throttle, which effectively upper
1048 A.4. Security of the Ideal Authentication Algorithm
1050 This section summarizes the security analysis of HOTP-IDEAL, starting
1051 with the impact of the conversion modulo 10^Digit and then focusing
1052 on the different possible attacks.
1054 A.4.1. From Bits to Digits
1056 The dynamic offset truncation of a random n-bit string yields a
1057 random 31-bit string. What happens to the distribution when it is
1058 taken modulo m = 10^Digit, as done in HOTP?
1066 M'Raihi, et al. Informational [Page 19]
1068 RFC 4226 HOTP Algorithm December 2005
1071 The following lemma estimates the biases in the outputs in this case.
1075 Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in
1078 P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}]
1080 Then for any z in Z_{m}
1082 P_{N,m}(z) = (q + 1) / N if 0 <= z < r
1087 Let the random variable X be uniformly distributed over Z_{N}. Then:
1089 P_{N,m}(z) = Pr [X mod m = z]
1091 = Pr [X < mq] * Pr [X mod m = z| X < mq]
1092 + Pr [mq <= X < N] * Pr [X mod m = z| mq <= X < N]
1095 (N - mq)/N * 1 / (N - mq) if 0 <= z < N - mq
1096 0 if N - mq <= z <= m
1099 r/N * 1 / r if 0 <= z < N - mq
1102 Simplifying yields the claimed equation.
1104 Let N = 2^31, d = 6, and m = 10^d. If x is chosen at random from
1105 Z_{N} (meaning, is a random 31-bit string), then reducing it to a 6-
1106 digit number by taking x mod m does not yield a random 6-digit
1109 Rather, x mod m is distributed as shown in the following table:
1111 Values Probability that each appears as output
1112 ----------------------------------------------------------------
1113 0,1,...,483647 2148/2^31 roughly equals to 1.00024045/10^6
1114 483648,...,999999 2147/2^31 roughly equals to 0.99977478/10^6
1116 If X is uniformly distributed over Z_{2^31} (meaning, is a random
1117 31-bit string), then the above shows the probabilities for different
1118 outputs of X mod 10^6. The first set of values appears with
1122 M'Raihi, et al. Informational [Page 20]
1124 RFC 4226 HOTP Algorithm December 2005
1127 probability slightly greater than 10^-6, the rest with probability
1128 slightly less, meaning that the distribution is slightly non-uniform.
1130 However, as the table above indicates, the bias is small, and as we
1131 will see later, negligible: the probabilities are very close to
1134 A.4.2. Brute Force Attacks
1136 If the authenticator consisted of d random digits, then a brute force
1137 attack using v verification attempts would succeed with probability
1140 However, an adversary can exploit the bias in the outputs of
1141 HOTP-IDEAL, predicted by Lemma 1, to mount a slightly better attack.
1143 Namely, it makes authentication attempts with authenticators that are
1144 the most likely values, meaning the ones in the range 0,...,r - 1,
1145 where (q,r) = IntDiv(2^31,10^Digit).
1147 The following specifies an adversary in our model of security that
1148 mounts the attack. It estimates the success probability as a
1149 function of the number of verification queries.
1151 For simplicity, we assume that the number of verification queries is
1152 at most r. With N = 2^31 and m = 10^6, we have r = 483,648, and the
1153 throttle value is certainly less than this, so this assumption is not
1154 much of a restriction.
1159 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume
1160 s <= m. The brute-force-attack adversary B-bf attacks HOTP using v
1161 <= r verification oracle queries. This adversary makes no
1162 authenticator oracle queries, and succeeds with probability
1164 Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s
1166 which is roughly equal to
1170 With m = 10^6 we get q = 2,147. In that case, the brute force attack
1171 using v verification attempts succeeds with probability
1173 Adv(B-bf) roughly = sv * 2148/2^31 = sv * 1.00024045/10^6
1178 M'Raihi, et al. Informational [Page 21]
1180 RFC 4226 HOTP Algorithm December 2005
1183 As this equation shows, the resynchronization parameter s has a
1184 significant impact in that the adversary's success probability is
1185 proportional to s. This means that s cannot be made too large
1186 without compromising security.
1188 A.4.3. Brute force attacks are the best possible attacks.
1190 A central question is whether there are attacks any better than the
1191 brute force one. In particular, the brute force attack did not
1192 attempt to collect authenticators sent by the user and try to
1193 cryptanalyze them in an attempt to learn how to better construct
1194 authenticators. Would doing this help? Is there some way to "learn"
1195 how to build authenticators that result in a higher success rate than
1196 given by the brute-force attack?
1198 The following says the answer to these questions is no. No matter
1199 what strategy the adversary uses, and even if it sees, and tries to
1200 exploit, the authenticators from authentication attempts of the user,
1201 its success probability will not be above that of the brute force
1202 attack -- this is true as long as the number of authentications it
1203 observes is not incredibly large. This is valuable information
1204 regarding the security of the scheme.
1206 Proposition 2 ------------- Suppose m = 10^Digit < 2^31, and let
1207 (q,r) = IntDiv(2^31,m). Let B be any adversary attacking HOTP-IDEAL
1208 using v verification oracle queries and a <= 2^c - s authenticator
1209 oracle queries. Then
1211 Adv(B) < = sv * (q+1)/ 2^31
1213 Note: This result is conditional on the adversary not seeing more
1214 than 2^c - s authentications performed by the user, which is hardly
1215 restrictive as long as c is large enough.
1217 With m = 10^6, we get q = 2,147. In that case, Proposition 2 says
1218 that any adversary B attacking HOTP-IDEAL and making v verification
1219 attempts succeeds with probability at most
1223 sv * 2148/2^31 roughly = sv * 1.00024045/10^6
1225 Meaning, B's success rate is not more than that achieved by the brute
1234 M'Raihi, et al. Informational [Page 22]
1236 RFC 4226 HOTP Algorithm December 2005
1239 A.5. Security Analysis of HOTP
1241 We have analyzed, in the previous sections, the security of the
1242 idealized counterparts HOTP-IDEAL of the actual authentication
1243 algorithm HOTP. We now show that, under appropriate and well-
1244 believed assumption on H, the security of the actual algorithms is
1245 essentially the same as that of its idealized counterpart.
1247 The assumption in question is that H is a secure pseudorandom
1248 function, or PRF, meaning that its input-output values are
1249 indistinguishable from those of a random function in practice.
1251 Consider an adversary A that is given an oracle for a function f:
1252 {0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A)
1253 as the prf-advantage of A, which represents how well the adversary
1254 does at distinguishing the case where its oracle is H(K,.) from the
1255 case where its oracle is a random function of {0,1}^c to {0,1}^n.
1257 One possible attack is based on exhaustive search for the key K. If
1258 A runs for t steps and T denotes the time to perform one computation
1259 of H, its prf-advantage from this attack turns out to be (t/T)2^-k.
1260 Another possible attack is a birthday one [PrOo], whereby A can
1261 attain advantage p^2/2^n in p oracle queries and running time about
1264 Our assumption is that these are the best possible attacks. This
1265 translates into the following.
1270 Let T denotes the time to perform one computation of H. Then if A is
1271 any adversary with running time at most t and making at most p oracle
1274 Adv(A) <= (t/T)/2^k + p^2/2^n
1276 In practice, this assumption means that H is very secure as PRF. For
1277 example, given that k = n = 160, an attacker with running time 2^60
1278 and making 2^40 oracle queries has advantage at most (about) 2^-80.
1283 Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B
1284 be any adversary attacking HOTP using v verification oracle queries,
1290 M'Raihi, et al. Informational [Page 23]
1292 RFC 4226 HOTP Algorithm December 2005
1295 a <= 2^c - s authenticator oracle queries, and running time t. Let T
1296 denote the time to perform one computation of H. If Assumption 1 is
1299 Adv(B) <= sv * (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n
1301 In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller
1302 than the sv(q + 1)/2^n term, so that the above says that for all
1303 practical purposes the success rate of an adversary attacking HOTP is
1304 sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP algorithm is
1305 in practice essentially as good as its idealized counterpart.
1307 In the case m = 10^6 of a 6-digit output, this means that an
1308 adversary making v authentication attempts will have a success rate
1309 that is at most that of Equation 1.
1311 For example, consider an adversary with running time at most 2^60
1312 that sees at most 2^40 authentication attempts of the user. Both
1313 these choices are very generous to the adversary, who will typically
1314 not have these resources, but we are saying that even such a powerful
1315 adversary will not have more success than indicated by Equation 1.
1317 We can safely assume sv <= 2^40 due to the throttling and bounds on
1320 (t/T)/2^k + ((sv + a)^2)/2^n <= 2^60/2^160 + (2^41)^2/2^160
1323 which is much smaller than the success probability of Equation 1 and
1324 negligible compared to it.
1346 M'Raihi, et al. Informational [Page 24]
1348 RFC 4226 HOTP Algorithm December 2005
1351 Appendix B - SHA-1 Attacks
1353 This sections addresses the impact of the recent attacks on SHA-1 on
1354 the security of the HMAC-SHA-1-based HOTP. We begin with some
1355 discussion of the situation of SHA-1 and then discuss the relevance
1356 to HMAC-SHA-1 and HOTP. Cited references are in Section 13.
1360 A collision for a hash function h means a pair x,y of different
1361 inputs such that h(x)=h(y). Since SHA-1 outputs 160 bits, a birthday
1362 attack finds a collision in 2^{80} trials. (A trial means one
1363 computation of the function.) This was thought to be the best
1364 possible until Wang, Yin, and Yu announced on February 15, 2005, that
1365 they had an attack finding collisions in 2^{69} trials.
1367 Is SHA-1 broken? For most practical purposes, we would say probably
1368 not, since the resources needed to mount the attack are huge. Here
1369 is one way to get a sense of it: we can estimate it is about the same
1370 as the time we would need to factor a 760-bit RSA modulus, and this
1371 is currently considered out of reach.
1373 Burr of NIST is quoted in [Crack] as saying "Large national
1374 intelligence agencies could do this in a reasonable amount of time
1375 with a few million dollars in computer time". However, the
1376 computation may be out of reach of all but such well-funded agencies.
1378 One should also ask what impact finding SHA-1 collisions actually has
1379 on security of real applications such as signatures. To exploit a
1380 collision x,y to forge signatures, you need to somehow obtain a
1381 signature of x and then you can forge a signature of y. How damaging
1382 this is depends on the content of y: the y created by the attack may
1383 not be meaningful in the application context. Also, one needs a
1384 chosen-message attack to get the signature of x. This seems possible
1385 in some contexts, but not others. Overall, it is not clear that the
1386 impact on the security of signatures is significant.
1388 Indeed, one can read in the press that SHA-1 is "broken" [Sha1] and
1389 that encryption and SSL are "broken" [Res]. The media have a
1390 tendency to magnify events: it would hardly be interesting to
1391 announce in the news that a team of cryptanalysts did very
1392 interesting theoretical work in attacking SHA-1.
1394 Cryptographers are excited too. But mainly because this is an
1395 important theoretical breakthrough. Attacks can only get better with
1396 time: it is therefore important to monitor any progress in hash
1397 functions cryptanalysis and be prepared for any really practical
1398 break with a sound migration plan for the future.
1402 M'Raihi, et al. Informational [Page 25]
1404 RFC 4226 HOTP Algorithm December 2005
1407 B.2. HMAC-SHA-1 Status
1409 The new attacks on SHA-1 have no impact on the security of
1410 HMAC-SHA-1. The best attack on the latter remains one needing a
1411 sender to authenticate 2^{80} messages before an adversary can create
1414 HMAC is not a hash function. It is a message authentication code
1415 (MAC) that uses a hash function internally. A MAC depends on a
1416 secret key, while hash functions don't. What one needs to worry
1417 about with a MAC is forgery, not collisions. HMAC was designed so
1418 that collisions in the hash function (here SHA-1) do not yield
1421 Recall that HMAC-SHA-1(K,x) = SHA-1(K_o,SHA-1(K_i,x)) where the keys
1422 K_o,K_i are derived from K. Suppose the attacker finds a pair x,y
1423 such that SHA-1(K_i,x) = SHA-1(K_i,y). (Call this a hidden-key
1424 collision.) Then if it can obtain the MAC of x (itself a tall
1425 order), it can forge the MAC of y. (These values are the same.) But
1426 finding hidden-key collisions is harder than finding collisions,
1427 because the attacker does not know the hidden key K_i. All it may
1428 have is some outputs of HMAC-SHA-1 with key K. To date, there are no
1429 claims or evidence that the recent attacks on SHA-1 extend to find
1430 hidden-key collisions.
1432 Historically, the HMAC design has already proven itself in this
1433 regard. MD5 is considered broken in that collisions in this hash
1434 function can be found relatively easily. But there is still no
1435 attack on HMAC-MD5 better than the trivial 2^{64} time birthday one.
1436 (MD5 outputs 128 bits, not 160.) We are seeing this strength of HMAC
1437 coming into play again in the SHA-1 context.
1441 Since no new weakness has surfaced in HMAC-SHA-1, there is no impact
1442 on HOTP. The best attacks on HOTP remain those described in the
1443 document, namely, to try to guess output values.
1445 The security proof of HOTP requires that HMAC-SHA-1 behave like a
1446 pseudorandom function. The quality of HMAC-SHA-1 as a pseudorandom
1447 function is not impacted by the new attacks on SHA-1, and so neither
1448 is this proven guarantee.
1458 M'Raihi, et al. Informational [Page 26]
1460 RFC 4226 HOTP Algorithm December 2005
1463 Appendix C - HOTP Algorithm: Reference Implementation
1466 * OneTimePasswordAlgorithm.java
1468 * HOTP one-time password algorithm
1472 /* Copyright (C) 2004, OATH. All rights reserved.
1474 * License to copy and use this software is granted provided that it
1475 * is identified as the "OATH HOTP Algorithm" in all material
1476 * mentioning or referencing this software or this function.
1478 * License is also granted to make and use derivative works provided
1479 * that such works are identified as
1480 * "derived from OATH HOTP algorithm"
1481 * in all material mentioning or referencing the derived work.
1483 * OATH (Open AuTHentication) and its members make no
1484 * representations concerning either the merchantability of this
1485 * software or the suitability of this software for any particular
1488 * It is provided "as is" without express or implied warranty
1489 * of any kind and OATH AND ITS MEMBERS EXPRESSaLY DISCLAIMS
1490 * ANY WARRANTY OR LIABILITY OF ANY KIND relating to this software.
1492 * These notices must be retained in any copies of any part of this
1493 * documentation and/or software.
1496 package org.openauthentication.otp;
1498 import java.io.IOException;
1499 import java.io.File;
1500 import java.io.DataInputStream;
1501 import java.io.FileInputStream ;
1502 import java.lang.reflect.UndeclaredThrowableException;
1504 import java.security.GeneralSecurityException;
1505 import java.security.NoSuchAlgorithmException;
1506 import java.security.InvalidKeyException;
1508 import javax.crypto.Mac;
1509 import javax.crypto.spec.SecretKeySpec;
1514 M'Raihi, et al. Informational [Page 27]
1516 RFC 4226 HOTP Algorithm December 2005
1520 * This class contains static methods that are used to calculate the
1521 * One-Time Password (OTP) using
1522 * JCE to provide the HMAC-SHA-1.
1524 * @author Loren Hart
1527 public class OneTimePasswordAlgorithm {
1528 private OneTimePasswordAlgorithm() {}
1530 // These are used to calculate the check-sum digits.
1531 // 0 1 2 3 4 5 6 7 8 9
1532 private static final int[] doubleDigits =
1533 { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
1536 * Calculates the checksum using the credit card algorithm.
1537 * This algorithm has the advantage that it detects any single
1538 * mistyped digit and any single transposition of
1541 * @param num the number to calculate the checksum for
1542 * @param digits number of significant places in the number
1544 * @return the checksum of num
1546 public static int calcChecksum(long num, int digits) {
1547 boolean doubleDigit = true;
1549 while (0 < digits--) {
1550 int digit = (int) (num % 10);
1553 digit = doubleDigits[digit];
1556 doubleDigit = !doubleDigit;
1558 int result = total % 10;
1560 result = 10 - result;
1566 * This method uses the JCE to provide the HMAC-SHA-1
1570 M'Raihi, et al. Informational [Page 28]
1572 RFC 4226 HOTP Algorithm December 2005
1576 * HMAC computes a Hashed Message Authentication Code and
1577 * in this case SHA1 is the hash algorithm used.
1579 * @param keyBytes the bytes to use for the HMAC-SHA-1 key
1580 * @param text the message or text to be authenticated.
1582 * @throws NoSuchAlgorithmException if no provider makes
1583 * either HmacSHA1 or HMAC-SHA-1
1584 * digest algorithms available.
1585 * @throws InvalidKeyException
1586 * The secret provided was not a valid HMAC-SHA-1 key.
1590 public static byte[] hmac_sha1(byte[] keyBytes, byte[] text)
1591 throws NoSuchAlgorithmException, InvalidKeyException
1596 hmacSha1 = Mac.getInstance("HmacSHA1");
1597 } catch (NoSuchAlgorithmException nsae) {
1598 hmacSha1 = Mac.getInstance("HMAC-SHA-1");
1600 SecretKeySpec macKey =
1601 new SecretKeySpec(keyBytes, "RAW");
1602 hmacSha1.init(macKey);
1603 return hmacSha1.doFinal(text);
1604 // } catch (GeneralSecurityException gse) {
1605 // throw new UndeclaredThrowableException(gse);
1609 private static final int[] DIGITS_POWER
1610 // 0 1 2 3 4 5 6 7 8
1611 = {1,10,100,1000,10000,100000,1000000,10000000,100000000};
1614 * This method generates an OTP value for the given
1615 * set of parameters.
1617 * @param secret the shared secret
1618 * @param movingFactor the counter, time, or other value that
1619 * changes on a per use basis.
1620 * @param codeDigits the number of digits in the OTP, not
1621 * including the checksum, if any.
1622 * @param addChecksum a flag that indicates if a checksum digit
1626 M'Raihi, et al. Informational [Page 29]
1628 RFC 4226 HOTP Algorithm December 2005
1631 * should be appended to the OTP.
1632 * @param truncationOffset the offset into the MAC result to
1633 * begin truncation. If this value is out of
1634 * the range of 0 ... 15, then dynamic
1635 * truncation will be used.
1636 * Dynamic truncation is when the last 4
1637 * bits of the last byte of the MAC are
1638 * used to determine the start offset.
1639 * @throws NoSuchAlgorithmException if no provider makes
1640 * either HmacSHA1 or HMAC-SHA-1
1641 * digest algorithms available.
1642 * @throws InvalidKeyException
1643 * The secret provided was not
1644 * a valid HMAC-SHA-1 key.
1646 * @return A numeric String in base 10 that includes
1647 * {@link codeDigits} digits plus the optional checksum
1648 * digit if requested.
1650 static public String generateOTP(byte[] secret,
1653 boolean addChecksum,
1654 int truncationOffset)
1655 throws NoSuchAlgorithmException, InvalidKeyException
1657 // put movingFactor value into text byte array
1658 String result = null;
1659 int digits = addChecksum ? (codeDigits + 1) : codeDigits;
1660 byte[] text = new byte[8];
1661 for (int i = text.length - 1; i >= 0; i--) {
1662 text[i] = (byte) (movingFactor & 0xff);
1666 // compute hmac hash
1667 byte[] hash = hmac_sha1(secret, text);
1669 // put selected bytes into result int
1670 int offset = hash[hash.length - 1] & 0xf;
1671 if ( (0<=truncationOffset) &&
1672 (truncationOffset<(hash.length-4)) ) {
1673 offset = truncationOffset;
1676 ((hash[offset] & 0x7f) << 24)
1677 | ((hash[offset + 1] & 0xff) << 16)
1678 | ((hash[offset + 2] & 0xff) << 8)
1682 M'Raihi, et al. Informational [Page 30]
1684 RFC 4226 HOTP Algorithm December 2005
1687 | (hash[offset + 3] & 0xff);
1689 int otp = binary % DIGITS_POWER[codeDigits];
1691 otp = (otp * 10) + calcChecksum(otp, codeDigits);
1693 result = Integer.toString(otp);
1694 while (result.length() < digits) {
1695 result = "0" + result;
1738 M'Raihi, et al. Informational [Page 31]
1740 RFC 4226 HOTP Algorithm December 2005
1743 Appendix D - HOTP Algorithm: Test Values
1745 The following test data uses the ASCII string
1746 "12345678901234567890" for the secret:
1748 Secret = 0x3132333435363738393031323334353637383930
1750 Table 1 details for each count, the intermediate HMAC value.
1752 Count Hexadecimal HMAC-SHA-1(secret, count)
1753 0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0
1754 1 75a48a19d4cbe100644e8ac1397eea747a2d33ab
1755 2 0bacb7fa082fef30782211938bc1c5e70416ff44
1756 3 66c28227d03a2d5529262ff016a1e6ef76557ece
1757 4 a904c900a64b35909874b33e61c5938a8e15ed1c
1758 5 a37e783d7b7233c083d4f62926c7a25f238d0316
1759 6 bc9cd28561042c83f219324d3c607256c03272ae
1760 7 a4fb960c0bc06e1eabb804e5b397cdc4b45596fa
1761 8 1b3c89f65e6c9e883012052823443f048b4332db
1762 9 1637409809a679dc698207310c8c7fc07290d9e5
1764 Table 2 details for each count the truncated values (both in
1765 hexadecimal and decimal) and then the HOTP value.
1768 Count Hexadecimal Decimal HOTP
1769 0 4c93cf18 1284755224 755224
1770 1 41397eea 1094287082 287082
1771 2 82fef30 137359152 359152
1772 3 66ef7655 1726969429 969429
1773 4 61c5938a 1640338314 338314
1774 5 33c083d4 868254676 254676
1775 6 7256c032 1918287922 287922
1776 7 4e5b397 82162583 162583
1777 8 2823443f 673399871 399871
1778 9 2679dc69 645520489 520489
1794 M'Raihi, et al. Informational [Page 32]
1796 RFC 4226 HOTP Algorithm December 2005
1799 Appendix E - Extensions
1802 We introduce in this section several enhancements to the HOTP
1803 algorithm. These are not recommended extensions or part of the
1804 standard algorithm, but merely variations that could be used for
1805 customized implementations.
1807 E.1. Number of Digits
1809 A simple enhancement in terms of security would be to extract more
1810 digits from the HMAC-SHA-1 value.
1812 For instance, calculating the HOTP value modulo 10^8 to build an 8-
1813 digit HOTP value would reduce the probability of success of the
1814 adversary from sv/10^6 to sv/10^8.
1816 This could give the opportunity to improve usability, e.g., by
1817 increasing T and/or s, while still achieving a better security
1818 overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which
1819 is the theoretical optimum for 6-digit code when s = 1.
1821 E.2. Alphanumeric Values
1823 Another option is to use A-Z and 0-9 values; or rather a subset of 32
1824 symbols taken from the alphanumerical alphabet in order to avoid any
1825 confusion between characters: 0, O, and Q as well as l, 1, and I are
1826 very similar, and can look the same on a small display.
1828 The immediate consequence is that the security is now in the order of
1829 sv/32^6 for a 6-digit HOTP value and sv/32^8 for an 8-digit HOTP
1832 32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is slightly
1833 better than a 9-digit HOTP value, which is the maximum length of an
1834 HOTP code supported by the proposed algorithm.
1836 32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is
1837 significantly better than a 9-digit HOTP value.
1839 Depending on the application and token/interface used for displaying
1840 and entering the HOTP value, the choice of alphanumeric values could
1841 be a simple and efficient way to improve security at a reduced cost
1842 and impact on users.
1850 M'Raihi, et al. Informational [Page 33]
1852 RFC 4226 HOTP Algorithm December 2005
1855 E.3. Sequence of HOTP Values
1857 As we suggested for the resynchronization to enter a short sequence
1858 (say, 2 or 3) of HOTP values, we could generalize the concept to the
1859 protocol, and add a parameter L that would define the length of the
1860 HOTP sequence to enter.
1862 Per default, the value L SHOULD be set to 1, but if security needs to
1863 be increased, users might be asked (possibly for a short period of
1864 time, or a specific operation) to enter L HOTP values.
1866 This is another way, without increasing the HOTP length or using
1867 alphanumeric values to tighten security.
1869 Note: The system MAY also be programmed to request synchronization on
1870 a regular basis (e.g., every night, twice a week, etc.) and to
1871 achieve this purpose, ask for a sequence of L HOTP values.
1873 E.4. A Counter-Based Resynchronization Method
1875 In this case, we assume that the client can access and send not only
1876 the HOTP value but also other information, more specifically, the
1879 A more efficient and secure method for resynchronization is possible
1880 in this case. The client application will not send the HOTP-client
1881 value only, but the HOTP-client and the related C-client counter
1882 value, the HOTP value acting as a message authentication code of the
1885 Resynchronization Counter-based Protocol (RCP)
1886 ----------------------------------------------
1888 The server accepts if the following are all true, where C-server is
1889 its own current counter value:
1891 1) C-client >= C-server
1892 2) C-client - C-server <= s
1893 3) Check that HOTP client is valid HOTP(K,C-Client)
1894 4) If true, the server sets C to C-client + 1 and client is
1897 In this case, there is no need for managing a look-ahead window
1898 anymore. The probability of success of the adversary is only v/10^6
1899 or roughly v in one million. A side benefit is obviously to be able
1900 to increase s "infinitely" and therefore improve the system usability
1901 without impacting the security.
1906 M'Raihi, et al. Informational [Page 34]
1908 RFC 4226 HOTP Algorithm December 2005
1911 This resynchronization protocol SHOULD be used whenever the related
1912 impact on the client and server applications is deemed acceptable.
1916 Another interesting option is the introduction of a Data field, which
1917 would be used for generating the One-Time Password values: HOTP (K,
1918 C, [Data]) where Data is an optional field that can be the
1919 concatenation of various pieces of identity-related information,
1920 e.g., Data = Address | PIN.
1922 We could also use a Timer, either as the only moving factor or in
1923 combination with the Counter -- in this case, e.g., Data = Timer,
1924 where Timer could be the UNIX-time (GMT seconds since 1/1/1970)
1925 divided by some factor (8, 16, 32, etc.) in order to give a specific
1926 time step. The time window for the One-Time Password is then equal
1927 to the time step multiplied by the resynchronization parameter as
1928 defined before. For example, if we take 64 seconds as the time step
1929 and 7 for the resynchronization parameter, we obtain an acceptance
1930 window of +/- 3 minutes.
1932 Using a Data field opens for more flexibility in the algorithm
1933 implementation, provided that the Data field is clearly specified.
1962 M'Raihi, et al. Informational [Page 35]
1964 RFC 4226 HOTP Algorithm December 2005
1969 David M'Raihi (primary contact for sending comments and questions)
1971 685 E. Middlefield Road
1972 Mountain View, CA 94043 USA
1974 Phone: 1-650-426-3832
1975 EMail: dmraihi@verisign.com
1979 Dept of Computer Science and Engineering, Mail Code 0114
1980 University of California at San Diego
1982 La Jolla, CA 92093, USA
1984 EMail: mihir@cs.ucsd.edu
1988 VASCO Data Security, Inc.
1989 Koningin Astridlaan 164
1990 1780 Wemmel, Belgium
1992 EMail: frh@vasco.com
1997 34 rue Guynemer, 92447,
1998 Issy les Moulineaux, France
2000 Information Security Group,
2002 University of London, Egham,
2005 EMail: david.naccache@gemplus.com, david.naccache@rhul.ac.uk
2009 Aladdin Knowledge Systems Ltd.
2011 Tel Aviv, Israel 61110
2013 EMail: Ohad.Ranen@ealaddin.com
2018 M'Raihi, et al. Informational [Page 36]
2020 RFC 4226 HOTP Algorithm December 2005
2023 Full Copyright Statement
2025 Copyright (C) The Internet Society (2005).
2027 This document is subject to the rights, licenses and restrictions
2028 contained in BCP 78, and except as set forth therein, the authors
2029 retain all their rights.
2031 This document and the information contained herein are provided on an
2032 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
2033 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
2034 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
2035 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
2036 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
2037 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
2039 Intellectual Property
2041 The IETF takes no position regarding the validity or scope of any
2042 Intellectual Property Rights or other rights that might be claimed to
2043 pertain to the implementation or use of the technology described in
2044 this document or the extent to which any license under such rights
2045 might or might not be available; nor does it represent that it has
2046 made any independent effort to identify any such rights. Information
2047 on the procedures with respect to rights in RFC documents can be
2048 found in BCP 78 and BCP 79.
2050 Copies of IPR disclosures made to the IETF Secretariat and any
2051 assurances of licenses to be made available, or the result of an
2052 attempt made to obtain a general license or permission for the use of
2053 such proprietary rights by implementers or users of this
2054 specification can be obtained from the IETF on-line IPR repository at
2055 http://www.ietf.org/ipr.
2057 The IETF invites any interested party to bring to its attention any
2058 copyrights, patents or patent applications, or other proprietary
2059 rights that may cover technology that may be required to implement
2060 this standard. Please address the information to the IETF at ietf-
2065 Funding for the RFC Editor function is currently provided by the
2074 M'Raihi, et al. Informational [Page 37]