directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tbenn...@apache.org
Subject svn commit: r486187 [21/49] - in /directory/trunks/triplesec: ./ admin-api/ admin-api/src/ admin-api/src/main/ admin-api/src/main/java/ admin-api/src/main/java/org/ admin-api/src/main/java/org/safehaus/ admin-api/src/main/java/org/safehaus/triplesec/ a...
Date Tue, 12 Dec 2006 15:24:14 GMT
Added: directory/trunks/triplesec/src/site/xdoc/drafts/draft-mraihi-oath-hmac-otp-01.txt
URL: http://svn.apache.org/viewvc/directory/trunks/triplesec/src/site/xdoc/drafts/draft-mraihi-oath-hmac-otp-01.txt?view=auto&rev=486187
==============================================================================
--- directory/trunks/triplesec/src/site/xdoc/drafts/draft-mraihi-oath-hmac-otp-01.txt (added)
+++ directory/trunks/triplesec/src/site/xdoc/drafts/draft-mraihi-oath-hmac-otp-01.txt Tue Dec 12 07:23:31 2006
@@ -0,0 +1,1207 @@
+    Internet Draft                                           D. M'Raihi 
+    Category: Informational                                    Verisign 
+    Document: draft-mraihi-oath-hmac-otp-01.txt              M. Bellare 
+    Expires: April 2005                                            UCSD 
+                                                           F. Hoornaert 
+                                                                  Vasco 
+                                                            D. Naccache 
+                                                                Gemplus 
+                                                               O. Ranen 
+                                                                Aladdin 
+                                                           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-Drafts. 
+     
+    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 
+    progress." 
+     
+    The list of current Internet-Drafts can be accessed at  
+    http://www.ietf.org/1id-abstracts.html 
+    The list of Internet-Draft Shadow Directories can be accessed at 
+    http://www.ietf.org/shadow.html 
+  
+ Abstract  
+     
+    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........................................11 
+    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.................................15 
+    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 
+    analyzed. 
+     
+   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. 
+     
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                 [Page 3] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+    This draft proposes a simple One Time Password algorithm that can 
+    be implemented by any hardware manufacturer or software developer 
+    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", 
+    "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 
+    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 
+    pre-requisite.  
+     
+    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 
+    PIN-pads. 
+     
+    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 client and 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 
+    user. 
+     
+                   HOTP(K,C) = Truncate(HMAC-SHA-1(K,C)) 
+     
+    Where: 
+     - 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 
+    endian. 
+     
+    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 
+                                     0...2^{31}-1 
+    Return D = Snum mod 10^Digit //  D is a number in the range 
+                                     0...10^{Digit}-1 
+     
+    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                                               | 
+    ------------------------------------------------------------- 
+    |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19| 
+    ------------------------------------------------------------- 
+    | Byte Value                                                | 
+    ------------------------------------------------------------- 
+    |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a| 
+    -------------------------------***********----------------++| 
+     
+    * 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 the 
+    dynamic truncation (DT) on distinct counter inputs are uniformly 
+    and independently distributed 31-bit strings. 
+     
+    The security analysis then details the impact of the conversion 
+    from a string to an integer and the final reduction modulo 
+    10^Digit, where Digit is the number of digits in an HOTP value. 
+     
+    The analysis demonstrates that these final steps introduce a 
+    negligible bias, which does not impact the security of the HOTP 
+    algorithm, in the sense that 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 
+     
+    Where: 
+     - 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 
+    usability.  
+     
+ 8. Protocol Extensions and Improvements 
+     
+    We introduce in this section several enhancements and suggestions 
+    to further improve the security of the algorithm HOTP 
+     
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 10] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+   8.1  Number of Digits 
+     
+    A simple enhancement in terms of security would be to extract more 
+    digits from the HMAC-SHA1 value. 
+     
+    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 
+    value. 
+     
+    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. 
+     
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 11] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+    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. 
+     
+   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 
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 12] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+    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. 
+     
+   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 
+                AuTHentication 
+     
+   13. Authors' Addresses 
+     
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 13] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+    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  
+     
+    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 
+    and 
+    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 
+    digits. 
+     
+    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. 
+     
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 14] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+   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}. 
+    
+    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 
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 15] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+    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 
+    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 
+    oracles: 
+     
+    Oracle AuthO() 
+       O = ALG(K,C) 
+       C = C + 1 
+       Return O to B 
+     
+    Oracle VerO() 
+       i = C 
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 16] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+       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 
+     
+    AuthO() is the authenticator oracle and VerO() is the verification 
+    oracle. 
+     
+    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 
+    user. 
+     
+    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 
+    case.  
+     
+    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}. 
+    Then: 
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 17] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+     
+    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] 
+     
+                = 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 
+    number. 
+     
+    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). 
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 18] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+     
+    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.  
+     
+    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.  
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 19] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+     
+    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 
+      
+                        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. 
+     
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 20] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+    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, 
+     
+                       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 
+    counterpart. 
+     
+    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.  
+     
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 21] 
+ HOTP: An HMAC-based One Time Password Algorithm           October 2004 
+  
+  
+    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. 
+     
+    This document and the information contained herein are provided on 
+    an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 
+    REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND 
+    THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, 
+    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT 
+    THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 
+    ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 
+    PARTICULAR PURPOSE.
+     
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+  
+  
+ OATH-HMAC-OTP            Expires - April 2005                [Page 22] 



Mime
View raw message