[Docs] [txt|pdf] [Tracker] [Email] [Nits] [IPR]

Versions: 00 01 02 03 04 RFC 4226

    Internet Draft                                           D. MÆRaihi
    Category: Informational                                    Verisign
    Document: draft-mraihi-oath-hmac-otp-00.txt              M. Bellare
    Expires: April 2005                                            UCSD
                                                           F. Hoornaert
                                                            D. Naccache
                                                               O. Ranen
                                                           October 2004
              HOTP: An HMAC-based One Time Password Algorithm
 Status of this Memo
    By submitting this Internet-Draft, I certify that any applicable
    patent or other IPR claims of which I am aware have been disclosed,
    or will be disclosed, and any of which I become aware will be
    disclosed, in accordance with RFC 3668.
    Internet-Drafts are working documents of the Internet Engineering
    Task Force (IETF), its areas, and its working groups. Note that
    other groups may also distribute working documents as Internet-
    Internet-Drafts are draft documents valid for a maximum of six
    months and may be updated, replaced, or obsoleted by other
    documents at any time. It is inappropriate to use Internet-Drafts
    as reference material or to cite them other than a "work in
    The list of current Internet-Drafts can be accessed at
    The list of Internet-Draft Shadow Directories can be accessed at
    This document describes an algorithm to generate one-time password
    values, based on HMAC [BCK1]. A security analysis of the algorithm
    is presented, and important parameters related to the secure
    deployment of the algorithm are discussed. The proposed algorithm
    can be used across a wide range of network applications ranging
    from remote VPN access, Wi-Fi network logon to transaction-oriented
    Web applications.
    This work is a joint effort by the OATH (Open AuTHentication)
    membership to specify an algorithm that can be freely distributed
    to the technical community. The authors believe that a common and
 OATH-HMAC-OTP            Expires - April 2005                 [Page 1]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    shared algorithm will facilitate adoption of two-factor
    authentication on the Internet by enabling interoperability across
    commercial and open-source implementations.
 Table of Contents
    1.   Overview...................................................2
    2.   Introduction...............................................3
    3.   Requirements Terminology...................................4
    4.   Algorithm Requirements.....................................4
    5.   HOTP Algorithm.............................................5
    5.1    Notation and Symbols.....................................5
    5.2    Description..............................................6
    5.3    Generating an HOTP value.................................6
    5.4    Example of HOTP computation for Digit = 6................7
    6.   Security and Deployment Considerations.....................8
    6.1    Authentication Protocol Requirements.....................8
    6.2    Validation of HOTP values................................8
    6.3    Throttling at the server.................................9
    6.4    Resynchronization of the counter.........................9
    7.   HOTP Algorithm Security: Overview.........................10
    8.   Protocol Extensions and Improvements......................10
    8.1    Number of Digits........................................10
    8.2    Alpha-numeric Values....................................11
    8.3    Sequence of HOTP values.................................11
    8.4    A Counter-based Re-Synchronization Method...............12
    9.   Conclusion................................................12
    10.  Acknowledgements..........................................13
    11.  Contributors..............................................13
    12.  References................................................13
    12.1   Normative...............................................13
    12.2   Informative.............................................13
    13.  AuthorsÆ Addresses........................................13
    Appendix - HOTP Algorithm Security: Detailed Analysis..........14
    A.1  Definitions and Notations.................................14
    A.2  The idealized algorithm: HOTP-IDEAL.......................15
    A.3  Model of Security.........................................15
    A.4  Security of the ideal authentication algorithm............17
    A.4.1  From bits to digits.....................................17
    A.4.2  Brute force attacks.....................................18
    A.4.3  Brute force attacks are the best possible attacks.......19
    A.5  Security Analysis of HOTP.................................20
   1. Overview
    The document introduces first the context around the HOTP
    algorithm. In section 4, the algorithm requirements are listed and
    in section 5, the HOTP algorithm is described. Sections 6 and 7
    focus on the algorithm security. Section 8 proposes some extensions
 OATH-HMAC-OTP            Expires - April 2005                 [Page 2]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    and improvements, and Section 9 concludes this document. The
    interested reader will find in the Appendix a detailed, full-fledge
    analysis of the algorithm security: an idealized version of the
    algorithm is evaluated, and then the HOTP algorithm security is
   2. Introduction
    Today, deployment of two-factor authentication remains extremely
    limited in scope and scale. Despite increasingly higher levels of
    threats and attacks, most Internet applications still rely on weak
    authentication schemes for policing user access. The lack of
    interoperability among hardware and software technology vendors has
    been a limiting factor in the adoption of two-factor authentication
    technology. In particular, the absence of open specifications has
    led to solutions where hardware and software components are tightly
    coupled through proprietary technology, resulting in high cost
    solutions, poor adoption and limited innovation.
    In the last two years, the rapid rise of network threats has
    exposed the inadequacies of static passwords as the primary mean of
    authentication on the Internet. At the same time, the current
    approach that requires an end-user to carry an expensive, single-
    function device that is only used to authenticate to the network is
    clearly not the right answer.  For two factor authentication to
    propagate on the Internet, it will have to be embedded in more
    flexible devices that can work across a wide range of applications.
    The ability to embed this base technology while ensuring broad
    interoperability require that it be made freely available to the
    broad technical community of hardware and software developers. Only
    an open system approach will ensure that basic two-factor
    authentication primitives can be built into the next-generation of
    consumer devices such USB mass storage devices, IP phones, and
    personal digital assistants).
    One Time Password is certainly one of the simplest and most popular
    forms of two-factor authentication for securing network access. For
    example, in large enterprises, Virtual Private Network access often
    requires the use of One Time Password tokens for remote user
    authentication. One Time Passwords are often preferred to stronger
    forms of authentication such as PKI or biometrics because an air-
    gap device does not require the installation of any client desktop
    software on the user machine, therefore allowing them to roam
    across multiple machines including home computers, kiosks and
    personal digital assistants.
    This draft proposes a simple One Time Password algorithm that can
    be implemented by any hardware manufacturer or software developer
 OATH-HMAC-OTP            Expires - April 2005                 [Page 3]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    to create interoperable authentication devices and software agents.
    The algorithm is event-based so that it can be embedded in high
    volume devices such as Java smart cards, USB dongles and GSM SIM
    cards. The presented algorithm is made freely available to the
    developer community under the terms and conditions of the IETF
    Intellectual Property Rights [RFC3668].
    The authors of this document are members of the Open AuTHentication
    initiative [OATH]. The initiative was created in 2004 to facilitate
    collaboration among strong authentication technology providers.
   3. Requirements Terminology
    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
    this document are to be interpreted as described in RFC 2119.
   4. Algorithm Requirements
    This section presents the main requirements that drove this
    algorithm design. A lot of emphasis was placed on end-consumer
    usability as well as the ability for the algorithm to be
    implemented by low cost hardware that may provide minimal user
    interface capabilities. In particular, the ability to embed the
    algorithm into high volume SIM and Java cards was a fundamental
    R1 - The algorithm MUST be sequence or counter-based: One of the
    goals is to have the HOTP algorithm embedded in high volume devices
    such as Java smart cards, USB dongles and GSM SIM cards.
    R2 - The algorithm SHOULD be economical to implement in hardware by
    minimizing requirements on battery, number of buttons,
    computational horsepower, and size of LCD display. The algorithm
    MUST work with tokens that do not supports any numeric input, but
    MAY also be used with more sophisticated devices such as secure
    R3 - The value displayed on the token MUST be easily read and
    entered by the user: This requires the HOTP value to be of
    reasonable length. The HOTP value must be at least a 6-digit value.
    It is also desirable that the HOTP value be 'numeric only' so that
    it can be easily entered on restricted devices such as phones.
    R4 - There MUST be user-friendly mechanisms available to
    resynchronize the counter. The sections 6.4 and 8.4 detail the
    resynchronization mechanism proposed in this draft.
 OATH-HMAC-OTP            Expires - April 2005                 [Page 4]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    R5- The algorithm MUST use a strong shared secret. The length of
    the shared secret MUST be at least 128 bits. This draft RECOMMENDs
    a shared secret length of 160 bits.
   5. HOTP Algorithm
    In this section, we introduce the notation and describe the HOTP
    algorithm basic blocks û the base function to compute an HMAC-SHA-1
    value and the truncation method to extract an HOTP value.
    5.1  Notation and Symbols
    A string always means a binary string, meaning a sequence of zeros
    and ones.
    If s is a string then |s| denotes its length.
    If n is a number then |n| denotes its absolute value.
    If s is a string then s[i] denotes its i-th bit. We start numbering
    the bits at 0, so s = s[0]s[1]..s[n-1] where n = |s| is the length
    of s.
    Let StToNum (String to Number) denote the function which as input a
    string s returns the number whose binary representation is s.
    (For example StToNum(110) = 6).
    Here is a list of symbols used in this document.
    Symbol   Represents
    C                     8-byte (Little Endian) counter value, which is the moving
             factor. This counter MUST be synchronized between the HOTP
             generator (client) and the HOTP validator (server);
    K        shared secret between the client and the server; each HOTP
             generator has a different and unique secret K;
    T        throttling parameter: the server will refuse connections
             from a user after T unsuccessful authentication attempts;
    s        resynchronization parameter: the server will attempt to
             verify a received authenticator across s consecutive
             counter values;
    Digit    number of digits in an HOTP value; system parameter.
 OATH-HMAC-OTP            Expires - April 2005                 [Page 5]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    5.2  Description
    The HOTP algorithm is based on an increasing counter value and a
    static symmetric key known only to the token and the validation
    service. In order to create the HOTP value, we will use the HMAC-
    SHA-1 algorithm, as defined in RFC 2104 [BCK2].
    As the output of the HMAC-SHA1 calculation is 160 bits, we must
    truncate this value to something that can be easily entered by a
                   HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
     - Truncate represents the function that converts an HMAC-SHA-1
        value into an HOTP value as defined in Section 5.3.
    The HOTP values generated by the HOTP generator are treated as big
    5.3  Generating an HOTP value
    We can describe the operations in 3 distinct steps:
    Step 1: Generate an HMAC-SHA-1 value
    Let HS = HMAC-SHA-1(K,C)  // HS is a 20 byte string
    Step 2: Generate a 4-byte string (Dynamic Truncation)
    Let Sbits = DT(HS)   //  DT, defined in Section 6.3.1
                         //  returns a 31 bit string
    Step 3: Compute an HOTP value
    Let Snum  = StToNum(S)        // Convert S to a number in
    Return D = Snum mod 10^Digit //  D is a number in the range
    The Truncate function performs Step 2 and Step 3, i.e. the dynamic
    truncation and then the reduction modulo 10^Digit. The purpose of
    the dynamic offset truncation technique is to extract a 4-byte
    dynamic binary code from a 160-bit (20-byte) HMAC-SHA1 result.
    DT(String) // String = String[0]...String[19]
     Let OffsetBits be the low order four bits of String[19]
     Offset = StToNum(OffSetBits) // 0 <= OffSet <= 15
     Let P = String[OffSet]...String[OffSet+3]
     Return the Last 31 bits of P
 OATH-HMAC-OTP            Expires - April 2005                 [Page 6]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    The reason for masking the most significant bit of P is to avoid
    confusion about signed vs. unsigned modulo computations. Different
    processors perform these operations differently, and masking out
    the signed bit removes all ambiguity.
    Implementations MUST extract a 6-digit code at a minimum and
    possibly 7 and 8-digit code. Depending on security requirements,
    Digit = 7 or more SHOULD be considered in order to extract a longer
    HOTP value.
    The following paragraph is an example of using this technique for
    Digit = 6, i.e. that a 6-digit HOTP value is calculated from the
    HMAC value.
    5.4  Example of HOTP computation for Digit = 6
    The following code example describes the extraction of a dynamic
    binary code given that hmac_result is a byte array with the HMAC-
    SHA1 result:
        int offset   =  hmac_result[19] & 0xf ;
        int bin_code = (hmac_result[offset]  & 0x7f) << 24
           | (hmac_result[offset+1] & 0xff) << 16
           | (hmac_result[offset+2] & 0xff) <<  8
           | (hmac_result[offset+3] & 0xff) ;
    SHA-1 HMAC Bytes (Example)
    | Byte Number                                               |
    | Byte Value                                                |
    * The last byte (byte 19) has the hex value 0x5a.
    * The value of the lower four bits is 0xa (the offset value).
    * The offset value is byte 10 (0xa).
    * The value of the 4 bytes starting at byte 10 is 0x50ef7f19,
      which is the dynamic binary code DBC1
    * The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19
    * HOTP = DBC2 modulo 10^6 = 872921.
    We treat the dynamic binary code as a 31-bit, unsigned, big-endian
    integer; the first byte is masked with a 0x7f.
 OATH-HMAC-OTP            Expires - April 2005                 [Page 7]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    We then take this number modulo 1,000,000 (10^6) to generate the 6-
    digit HOTP value 872921 decimal.
   6. Security and Deployment Considerations
    Any One-Time Password algorithm is only as secure as the
    application and the authentication protocols that implement it.
    Therefore, this section discusses the critical security
    requirements that our choice of algorithm imposes on the
    authentication protocol and validation software. The parameters T
    and s discussed in this section have a significant impact on the
    security û further details in Section 7 elaborate on the relations
    between these parameters and their impact on the system security.
    6.1  Authentication Protocol Requirements
    We introduce in this section some requirements for a protocol P
    implementing HOTP as the authentication method between a prover and
    a verifier.
    RP1 - P MUST be two-factor, i.e. something you know (secret code
    such as a Password, Pass phrase, PIN code, etc.) and something you
    have (token). The secret code is known only to the user and usually
    entered with the one-time password value for authentication purpose
    (two-factor authentication).
    RP3 - P MUST NOT be vulnerable to brute force attacks. This implies
    that a throttling/lockout scheme is REQUIRED on the validation
    server side.
    RP4 û P SHOULD be implemented with respect to the state of the art
    in terms of security, in order to avoid the usual attacks and risks
    associated with the transmission of sensitive data over a public
    network (privacy, replay attacks, etc.)
    6.2  Validation of HOTP values
    The HOTP client (hardware or software token) increments its counter
    and then calculates the next HOTP value HOTP-client. If the value
    received by the authentication server matches the value calculated
    by the client, then the HOTP value is validated. In this case, the
    server increments the counter value by one.
    If the value received by the server does not match the value
    calculated by the client, the server initiate the resynch protocol
    (look-ahead window) before it requests another pass.
 OATH-HMAC-OTP            Expires - April 2005                 [Page 8]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    If the resynch fails, the server asks then for another
    authentication pass of the protocol to take place, until the
    maximum number of authorized attempts is reached.
    If and when the maximum number of authorized attempts is reached,
    the server SHOULD lock out the account and initiate a procedure to
    inform the user.
    6.3  Throttling at the server
    Truncating the HMAC-SHA1 value to a shorter value makes a brute
    force attack possible. Therefore, the authentication server needs
    to detect and stop brute force attacks.
    We RECOMMEND setting a throttling parameter T, which defines the
    maximum number of possible attempts for One-Time-Password
    validation. The validation server manages individual counters per
    HOTP device in order to take note of any failed attempt. We
    RECOMMEND T not to be too large, particularly if the
    resynchronization method used on the server is window-based, and
    the window size is large. T SHOULD be set as low as possible, while
    still ensuring usability is not significantly impacted.
    6.4  Resynchronization of the counter
    Although the serverÆs counter value is only incremented after a
    successful HOTP authentication, the counter on the token is
    incremented every time a new HOTP is requested by the user. Because
    of this, the counter values on the server and on the token might be
    out of synchronization.
    We RECOMMEND setting a look-ahead parameter s on the server, which
    defines the size of the look-ahead window. In a nutshell, the
    server can recalculate the next s HOTP-server values, and check
    them against the received HOTP-client.
    Synchronization of counters in this scenario simply requires the
    server to calculate the next HOTP values and determine if there is
    a match. Optionally, the system MAY require the user to send a
    sequence of (say 2, 3) HOTP values for resynchronization purpose,
    since forging a sequence of consecutive HOTP values is even more
    difficult than guessing a single HOTP value.
    The upper bound set by the parameter s ensures the server does not
    go on checking HOTP values forever (causing a DoS attack) and also
    restricts the space of possible solutions for an attacker trying to
    manufacture HOTP values. s SHOULD be set as low as possible, while
    still ensuring usability is not impacted.
 OATH-HMAC-OTP            Expires - April 2005                 [Page 9]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
   7. HOTP Algorithm Security: Overview
    The conclusion of the security analysis detailed in the Appendix
    section is that, for all practical purposes, the outputs of HOTP on
    distinct counter inputs are uniformly and independently distributed
    As a result, the best possible attack against the HOTP function is
    the brute force attack.
    Assuming an adversary is able to observe numerous protocol
    exchanges and collect sequences of successful authentication
    values. This adversary, trying to build a function F to generate
    HOTP values based on his observations, will not have a significant
    advantage over a random guess.
    The logical conclusion is simply that is best strategy will once
    again be to perform a brute force attack to enumerate and try all
    the possible values.
    Considering the security analysis in the Appendix section of this
    document, without loss of generality, we can approximate closely
    the security of the HOTP algorithm by the following formula:
                             Sec = sv/10^Digit
     - Sec is the probability of success of the adversary
     - s stands for the look-ahead synchronization window size;
     - v stands for the number of verification attempts;
     - Digit stands for the number of digits in HOTP values.
    Obviously, we can play with s, T (the Throttling parameter that
    would limit the number of attempts by an attacker) and Digit until
    achieving a certain level of security, still preserving the system
 8. Protocol Extensions and Improvements
    We introduce in this section several enhancements and suggestions
    to further improve the security of the algorithm HOTP
   8.1  Number of Digits
    A simple enhancement in terms of security would be to extract more
    digits from the HMAC-SHA1 value.
 OATH-HMAC-OTP            Expires - April 2005                [Page 10]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    For instance, calculating the HOTP value modulo 10^8 to build an 8-
    digit HOTP value would reduce the probability of success of the
    adversary from sv/10^6 to sv/10^8.
    This could give the opportunity to improve usability, e.g. by
    increasing T and/or s, while still achieving a better security
    overall. For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which
    is the theoretical optimum for 6-digit code when s = 1.
   8.2  Alpha-numeric Values
    Another option is to use A-Z and 0-9 values; or rather a subset of
    32 symbols taken from the alphanumerical alphabet in order to avoid
    any confusion between characters: 0, O and Q as well as l, 1 and I
    are very similar, and can look the same on a small display.
    The immediate consequence is that the security is now in the order
    of sv/32^6 for a 6-digit HOTP value and sv/32^8 for an 8-digit HOTP
    32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is
    slightly better than a 9-digit HOTP value, which is the maximum
    length of an HOTP code supported by the proposed algorithm.
    32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is
    significantly better than a 9-digit HOTP value.
    Depending on the application and token/interface used for
    displaying and entering the HOTP value, the choice of alphanumeric
    values could be a simple and efficient way to improve security at a
    reduced cost and impact on users.
   8.3  Sequence of HOTP values
    As we suggested for the resynchronization to enter a short sequence
    (say 2 or 3) of HOTP values, we could generalize the concept to the
    protocol, and add a parameter L that would define the length of the
    HOTP sequence to enter.
    Per default, the value L SHOULD be set to 1, but if security needs
    to be increased, users might be asked (possibly for a short period
    of time, or a specific operation) to enter L HOTP values.
    This is another way, without increasing the HOTP length or using
    alphanumeric values to tighten security.
    Note: The system MAY also be programmed to request synchronization
    on a regular basis (e.g. every night, or twice a week, etc.) and to
    achieve this purpose, ask for a sequence of L HOTP values.
 OATH-HMAC-OTP            Expires - April 2005                [Page 11]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
   8.4  A Counter-based Re-Synchronization Method
    In this case, we assume that the client can access and send not
    only the HOTP value but also other information, more specifically
    the counter value.
    A more efficient and secure method for resynchronization is
    possible in this case. The client application will not send the
    HOTP-client value only, but the HOTP-client and the related C-
    client counter value, the HOTP value acting as a message
    authentication code of the counter.
    Resynchronization Counter-based Protocol (RCP)
    The server accepts if the following are all true, where C-server is
    its own current counter value:
    1) C-client >= C-server
    2) C-client û C-server <= s
    3) Check that HOTP-client is valid HOTP(K,C-Client)
    4) If true, the server sets C to C-client + 1 and client
       is authenticated
    In this case, there is no need for managing a look-ahead window
    anymore. The probability of success of the adversary is only v/10^6
    or roughly v in one million. A side benefit is obviously to be able
    to increase s ôinfinitelyö and therefore improve the system
    usability without impacting the security.
    This resynchronization protocol SHOULD be use whenever the related
    impact on the client and server applications is deemed acceptable.
   9. Conclusion
    This draft describes HOTP, a HMAC-based One-Time Password
    algorithm. It also recommends the preferred implementation and
    related modes of operations for deploying the algorithm.
    The draft also exhibits elements of security and demonstrates that
    the HOTP algorithm is practical and sound, the best possible attack
    being a brute force attack that can be prevented by careful
    implementation of countermeasures in the validation server.
    Eventually, several enhancements have been proposed, in order to
    improve security if needed for specific applications.
 OATH-HMAC-OTP            Expires - April 2005                [Page 12]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
   10. Acknowledgements
    The authors would like to thank Siddharth Bajaj, Alex Deacon and
    Nico Popp for their help during the conception and redaction of
    this document.
   11. Contributors
    The authors of this draft would like to emphasize the role of two
    persons who have made a key contribution to this document:
    - Laszlo Elteto is system architect with SafeNet, Inc.
    - Ernesto Frutos is director of Engineering with Authenex, Inc.
    Without their advice and valuable inputs, this draft would not be
    the same.
   12. References
    12.1 Normative
    [BCK1]      M. Bellare, R. Canetti, and H. Krawczyk, Keyed Hash
                Functions and Message Authentication, Proceedings of
                Crypto'96, LNCS Vol. 1109, pp. 1-15.
    [BCK2]      M. Bellare, R. Canetti, and H. Krawczyk, HMAC:
                Keyed-Hashing for Message Authentication, IETF Network
                Working Group, RFC 2104, February 1997.
    [RFC2119]   Bradner, S., "Key words for use in RFCs to Indicate
                Requirement Levels", BCP 14, RFC 2119, March 1997.
    [RFC3668]  Bradner, S., "Intellectual Propery Rights in IETF
                Technologyö, BCP 79, RFC 3668, February 2004.
    12.2 Informative
    [OATH]     www.openauthentication.org, Initiative for Open
   13. AuthorsÆ Addresses
    Primary point of contact (for sending comments and question):
    David M'Raihi
    VeriSign, Inc.
    685 E. Middlefield Road          Phone: 1-650-426-3832
    Mountain View, CA 94043 USA      Email: dmraihi@verisign.com
 OATH-HMAC-OTP            Expires - April 2005                [Page 13]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    Other AuthorsÆ contact information:
    Mihir Bellare
    Dept of Computer Science and Engineering, Mail Code 0114
    University of California at San Diego
    9500 Gilman Drive
    La Jolla, CA 92093, USA          Email: mihir@cs.ucsd.edu
    Frank Hoornaert
    VASCO Data Security, Inc.
    Koningin Astridlaan 164
    1780 Wemmel, Belgium             Email: frh@vasco.com
    David Naccache
    Gemplus Innovation
    34 rue Guynemer, 92447,
    Issy les Moulineaux, France      Email: david.naccache@gemplus.com
    Information Security Group,
    Royal Holloway,
    University of London, Egham,
    Surrey TW20 0EX, UK              Email: david.naccache@rhul.ac.uk
    Ohad Ranen
    Aladdin Knowledge Systems Ltd.
    15 Beit Oved Street
    Tel Aviv, Israel 61110           Email: Ohad.Ranen@ealaddin.com
 Appendix - HOTP Algorithm Security: Detailed Analysis
    The security analysis of the HOTP algorithm is summarized in this
    section. We first detail the best attack strategies, and then
    elaborate on the security under various assumptions, the impact of
    the truncation and some recommendations regarding the number of
    We focus this analysis on the case where Digit = 6, i.e. an HOTP
    function that produces 6-digit values, which is the bare minimum
    recommended in this draft.
   A.1 Definitions and Notations
    We denote by {0,1}^l the set of all strings of length l.
    Let Z_{n} = {0,.., n - 1}.
 OATH-HMAC-OTP            Expires - April 2005                [Page 14]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    Let IntDiv(a,b) denote the integer division algorithm that takes
    input integers a, b where a >= b >= 1 and returns integers (q,r)
    the quotient and remainder, respectively, of the division of a by
    b. (Thus a = bq + r and 0 <= r < b.)
    Let H: {0,1}^k x {0,1}^c --> {0,1}^n be the base function that
    takes a k-bit key K and c-bit counter C and returns an n-bit output
    H(K,C). (In the case of HOTP, H is HMAC-SHA-1; we use this formal
    definition for generalizing our proof of security)
   A.2 The idealized algorithm: HOTP-IDEAL
    We now define an idealized counterpart of the HOTP algorithm. In
    this algorithm, the role of H is played by a random function that
    forms the key.
    To be more precise, let Maps(c,n) denote the set of all functions
    mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key
    space Maps(c,n), so that a ôkeyö for such an algorithm is a
    function h from {0,1}^c to {0,1}^n. We imagine this key (function)
    to be drawn at random. It is not feasible to implement this
    idealized algorithm, since the key, being a function from is way
    too large to even store. So why consider it?
    Our security analysis will show that as long as H satisfies a
    certain well-accepted assumption, the security of the actual and
    idealized algorithms is for all practical purposes the same. The
    task that really faces us, then, is to assess the security of the
    idealized algorithm.
    In analyzing the idealized algorithm, we are concentrating on
    assessing the quality of the design of the algorithm itself,
    independently of HMAC-SHA-1. This is in fact the important issue.
   A.3 Model of Security
    The model exhibits the type of threats or attacks that are being
    considered and enables to asses the security of HOTP and HOTP-
    IDEAL. We denote ALG as either HOTP or HOTP-IDEAL for the purpose
    of this security analysis.
    The scenario we are considering is that a user and server share a
    key K for ALG. Both maintain a counter C, initially zero, and the
    user authenticates itself by sending ALG(K,C) to the server. The
    latter accepts if this value is correct.
    In order to protect against accidental increment of the user
    counter, the server, upon receiving a value z, will accept as long
 OATH-HMAC-OTP            Expires - April 2005                [Page 15]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    as z equals ALG(K,i) for some i in the range C,...,C + s-1, where s
    is the resynchronization parameter and C is the server counter. If
    it accepts with some value of i, it then increments its counter to
    i+ 1. If it does not accept, it does not change its counter value.
    The model we specify captures what an adversary can do and what it
    needs to achieve in order to ôwin.ö First, the adversary is assumed
    to be able to eavesdrop, meaning see the authenticator transmitted
    by the user. Second, the adversary wins if it can get the server to
    accept an authenticator relative to a counter value for which the
    user has never transmitted an authenticator.
    The formal adversary, which we denote by B, starts out knowing
    which algorithm ALG is being used, knowing the system design and
    knowing all system parameters. The one and only thing it is not
    given a priori is the key K shared between the user and the server.
    The model gives B full control of the scheduling of events. It has
    access to an authenticator oracle representing the user. By calling
    this oracle, the adversary can ask the user to authenticate itself
    and get back the authenticator in return. It can call this oracle
    as often as it wants and when it wants, using the authenticators it
    accumulates to perhaps ôlearnö how to make authenticators itself.
    At any time, it may also call a verification oracle, supplying the
    latter with a candidate authenticator of its choice. It wins if the
    server accepts this accumulator.
    Consider the following game involving an adversary B that is
    attempting to compromise the security of an authentication
    algorithm ALG: K x {0,1}^c --> R.
    Initializations - A key K is selected at random from K, a counter C
    is initialized to 0, and the Boolean value win is set to false.
    Game execution - Adversary B is provided with the two following
    Oracle AuthO()
       O = ALG(K,C)
       C = C + 1
       Return O to B
    Oracle VerO()
       i = C
       While (i <= C + s - 1 and Win = FALSE) do
          If O = ALG(K,i) then Win = TRUE; C = i + 1
          Else i = i + 1
       Return Win to B
 OATH-HMAC-OTP            Expires - April 2005                [Page 16]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    AuthO() is the authenticator oracle and VerO() is the verification
    Upon execution, B queries the two oracles at will. Let Adv(B) be
    the probability that win gets set to true in the above game. This
    is the probability that the adversary successfully impersonates the
    Our goal is to assess how large this value can be as a function of
    the number v of verification queries made by B, the number a of
    authenticator oracle queries made by B, and the running time t of
    B. This will tell us how to set the throttle, which effectively
    upper bounds v.
   A.4 Security of the ideal authentication algorithm
    This section summarizes the security analysis of HOTP-IDEAL,
    starting with the impact of the conversion modulo 10^Digit and
    then, focusing on the different possible attacks.
    A.4.1 From bits to digits
    The dynamic offset truncation of a random n-bit string yields a
    random 31-bit string. What happens to the distribution when it is
    taken modulo m = 10^Digit, as done in HOTP?
    The following lemma estimates the biases in the outputs in this
    Lemma 1
    Let N >= m >= 1 be integers, and let (q,r) = IntDiv(N,m). For z in
    Z_{m} let:
          P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}]
    Then for any z in Z_{m}
    P_{N,m}(z) =   (q + 1) / N    if 0 <= z < r
                   q / N          if r <= z < m
    Proof of Lemma 1
    Let the random variable X be uniformly distributed over Z_{N}.
    P_{N,m}(z)  = Pr [X mod m = z]
                = Pr [X < mq] ¸ Pr [X mod m = z| X < mq]
                + Pr [mq <= X < N] ¸ Pr [X mod m = z| mq <= X < N]
 OATH-HMAC-OTP            Expires - April 2005                [Page 17]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
                = mq/N ¸ 1/m +
                   (N - mq)/N ¸ 1 / (N û mq)     if 0 <= z < N û mq
                   0                             if N û mq <= z <= m
                = q/N +
                   r/N ¸ 1 / r                   if 0 <= z < N û mq
                   0                             if r <= z <= m
    Simplifying yields the claimed equation.
    Let N = 2^31, d = 6 and m = 10^d. If x is chosen at random from
    Z_{N} (meaning, is a random 31-bit string), then reducing it to a
    6-digit number by taking x mod m does not yield a random 6-digit
    Rather, x mod m is distributed as shown in the following table:
    Values               Probability that each appears as output
    0,1,...,483647       2148/2^31 roughly equals to 1.00024045/10^6
    483648,...,999999    2147/2^31 roughly equals to 0.99977478/10^6
    If X is uniformly distributed over Z_{2^31} (meaning is a random
    31-bit string) then the above shows the probabilities for different
    outputs of X mod 10^6. The first set of values appear with
    probability slightly greater than 10^-6, the rest with probability
    slightly less, meaning the distribution is slightly non-uniform.
    However, as the Figure indicates, the bias is small and as we will
    see later, negligible: the probabilities are very close to 10^-6.
    A.4.2 Brute force attacks
    If the authenticator consisted of d random digits, then a brute
    force attack using v verification attempts would succeed with
    probability sv/10^Digit.
    However, an adversary can exploit the bias in the outputs of HOTP-
    IDEAL, predicted by Lemma 1, to mount a slightly better attack.
    Namely, it makes authentication attempts with authenticators which
    are the most likely values, meaning the ones in the range 0,...,r -
    1, where (q,r) = IntDiv(2^31,10^Digit).
    The following specifies an adversary in our model of security that
    mounts the attack. It estimates the success probability as a
    function of the number of verification queries.
 OATH-HMAC-OTP            Expires - April 2005                [Page 18]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    For simplicity, we assume the number of verification queries is at
    most r. With N = 2^31 and m = 10^6 we have r = 483,648, and the
    throttle value is certainly less than this, so this assumption is
    not much of a restriction.
    Proposition 1
    Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Assume
    s <= m. The brute-force attack adversary B-bf attacks HOTP using v
    <= r verification oracle queries. This adversary makes no
    authenticator oracle queries, and succeeds with probability
                    Adv(B-bf) = 1 - (1 - v(q+1)/2^31)^s
    which is roughly equals to
                              sv ¸ (q+1)/2^31
    With m = 10^6 we get q = 2,147. In that case, the brute force
    attack using v verification attempts succeeds with probability
         Adv(B-bf) roughly = sv ¸ 2148/2^31 = sv ¸ 1.00024045/10^6
    As this equation shows, the resynchronization parameter s has a
    significant impact in that the adversaryÆs success probability is
    proportional to s. This means that s cannot be made too large
    without compromising security.
    A.4.3 Brute force attacks are the best possible attacks
    A central question is whether there are attacks any better than the
    brute force one. In particular, the brute force attack did not
    attempt to collect authenticators sent by the user and try to
    cryptanalyze them in an attempt to learn how to better construct
    authenticators. Would doing this help? Is there some way to ôlearnö
    how to build authenticators that result in a higher success rate
    than given by the brute-force attack?
    The following says the answer to these questions is no. No matter
    what strategy the adversary uses, and even if it sees, and tries to
    exploit, the authenticators from authentication attempts of the
    user, its success probability will not be above that of the brute
    force attack - this is true as long as the number of
    authentications it observes is not incredibly large. This is
    valuable information regarding the security of the scheme.
    Proposition 2
    Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B
    be any adversary attacking HOTP-IDEAL using v verification oracle
    queries and a <= 2^c û s authenticator oracle queries. Then
 OATH-HMAC-OTP            Expires - April 2005                [Page 19]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
                        Adv(B) < = sv ¸ (q+1)/ 2^31
    Note: This result is conditional on the adversary not seeing more
    than 2^c - s authentications performed by the user, which is hardly
    restrictive as long as c is large enough.
    With m = 10^6 we get q = 2,147. In that case, Proposition 2 says
    that any adversary B attacking HOTP-IDEAL and making v verification
    attempts succeeds with probability at most
    Equation 1
               sv ¸ 2148/2^31 roughly = sv ¸ 1.00024045/10^6
    Meaning, BÆs success rate is not more than that achieved by the
    brute force attack.
   A.5 Security Analysis of HOTP
    We have analyzed in the previous sections, the security of the
    idealized counterparts HOTP-IDEAL of the actual authentication
    algorithm HOTP. We now show that, under appropriate and well-
    believed assumption on H, the security of the actual algorithms is
    essentially the same as that of its idealized counterpart.
    The assumption in question is that H is a secure pseudorandom
    function, or PRF, meaning that its input-output values are
    indistinguishable from those of a random function in practice.
    Consider an adversary A that is given an oracle for a function f:
    {0,1}^c --> {0, 1}^n and eventually outputs a bit. We denote Adv(A)
    as the prf-advantage of A, which represents how well the adversary
    does at distinguishing the case where its oracle is H(K,.) from the
    case where its oracle is a random function of {0,1}^c to {0,1}^n.
    One possible attack is based on exhaustive search for the key K. If
    A runs for t steps and T denotes the time to perform one
    computation of H, its prf-advantage from this attack turns out to
    be (t/T)2^-k . Another possible attack is a birthday one [3],
    whereby A can attain advantage p^2/2^n in p oracle queries and
    running time about pT.
    Our assumption is that these are the best possible attacks. This
    translates into the following.
    Assumption 1
    Let T denotes the time to perform one computation of H. Then if A
    is any adversary with running time at most t and making at most p
    oracle queries,
 OATH-HMAC-OTP            Expires - April 2005                [Page 20]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
                       Adv(A) <= (t/T)/2^k + p^2/2^n
    In practice this assumption means that H is very secure as PRF. For
    example, given that k = n = 160, an attacker with running time 2^60
    and making 2^40 oracle queries has advantage at most (about) 2^-80.
    Theorem 1
    Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m). Let B
    be any adversary attacking HOTP using v verification oracle
    queries, a <= 2^c - s authenticator oracle queries, and running
    time t. Let T denote the time to perform one computation of H. If
    Assumption 1 is true then
         Adv(B) <= sv ¸ (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n
    In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller
    than the sv(q + 1)/2^n term, so that the above says that for all
    practical purposes the success rate of an adversary attacking HOTP
    is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP
    algorithm is in practice essentially as good as its idealized
    In the case m = 10^6 of a 6-digit output this means that an
    adversary making v authentication attempts will have a success rate
    that is at most that of Equation 1.
    For example, consider an adversary with running time at most 2^60
    that sees at most 2^40 authentication attempts of the user. Both
    these choices are very generous to the adversary, who will
    typically not have these resources, but we are saying that even
    such a powerful adversary will not have more success than indicated
    by Equation 1.
    We can safely assume sv <= 2^40 due to the throttling and bounds on
    s. So:
        (t/T)/2^k + ((sv + a)^2)/2^n  <= 2^60/2^160 + (2^41)^2/2^160
                                     roughly <= 2^-78
    which is much smaller than the success probability of Equation 1
    and negligible compared to it.
    Full Copyright Statement
    Copyright (C) The Internet Society 2004.  This document is subject
    to the rights, licenses and restrictions contained in BCP 78, and
    except as set forth therein, the authors retain all their rights.
 OATH-HMAC-OTP            Expires - April 2005                [Page 21]

 HOTP: An HMAC-based One Time Password Algorithm           October 2004
    This document and the information contained herein are provided on
 OATH-HMAC-OTP            Expires - April 2005                [Page 22]

Html markup produced by rfcmarkup 1.111, available from https://tools.ietf.org/tools/rfcmarkup/