view Side-By-Side changes
Internet Draft D. M'Raihi
Category: Informational VeriSign
Document: draft-mraihi-oath-hmac-otp-03.txt draft-mraihi-oath-hmac-otp-04.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 each author represents that any
applicable patent or other IPR claims of which I am he or she is aware
have been disclosed, or will be disclosed, and any of which I become he or she becomes
aware will be disclosed, in accordance with RFC 3668. Section 6 of BCP 79.
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 as "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....................................................3 Overview...................................................3
2. Introduction................................................3 Introduction...............................................3
3. Requirements Terminology....................................4 Terminology...................................4
4. Algorithm Requirements......................................4 Requirements.....................................4
5. HOTP Algorithm..............................................5 Algorithm.............................................5
5.1 Notation and Symbols.......................................5
5.2 Description................................................6 Description................................................5
5.3 Generating an HOTP value...................................6
5.4 Example of HOTP computation for Digit = 6..................7
6. Security Considerations.....................................8 Considerations....................................7
6.1 Authentication Protocol Requirements.......................8
6.2 Validation of HOTP values..................................9 values..................................8
6.3 Bi-directional Authentication..............................9
6.4 Throttling at the server...................................9
6.4
6.5 Resynchronization of the counter...........................9
6.5
6.6 Management of Shared Secrets..............................10
7. HOTP Algorithm Security: Overview..........................12 Overview.........................12
8. Protocol Extensions and Improvements.......................12
8.1 Number of Digits..........................................13
8.2 Alpha-numeric Values......................................13
8.3 Sequence of HOTP values...................................13
8.4 A Counter-based Re-Synchronization Method.................14
8.5 Composite Shared Secrets..................................14
8.6 Data Field................................................15 Secrets..................................13
9. Conclusion.................................................15 IANA Considerations.......................................13
10. Acknowledgements...........................................16 Conclusion................................................13
11. Contributors...............................................16 Acknowledgements..........................................13
12. References.................................................16 Contributors..............................................13
13. References................................................14
12.1 Normative.................................................16 Normative...............................................14
12.2 Informative...............................................16
13. Informative.............................................14
14. Authors' Addresses........................................17 Addresses........................................15
15. Full Copyright Statement...................................15
16. Intellectual Property......................................16
Appendix A - HOTP Algorithm Security: Detailed Analysis........18 Analysis........16
A.1 Definitions and Notations..................................18 Notations..................................16
A.2 The idealized algorithm: HOTP-IDEAL........................18 HOTP-IDEAL........................17
A.3 Model of Security..........................................19 Security..........................................17
A.4 Security of the ideal authentication algorithm.............20 algorithm.............19
A.4.1 From bits to digits......................................21 digits......................................19
A.4.2 Brute force attacks......................................22 attacks......................................20
A.4.3 Brute force attacks are the best possible attacks........23 attacks........21
A.5 Security Analysis of HOTP..................................24 HOTP..................................22
Appendix B - SHA-1 Attacks.....................................25 Attacks.....................................23
B.1 SHA-1 status...............................................25 status...............................................23
B.2 HMAC-SHA-1 status..........................................26 status..........................................24
B.3 HOTP status................................................27
OATH-HMAC-OTP Expires - April 2005 [Page 2]
HOTP: An HMAC-based One Time Password Algorithm October 2004 status................................................25
Appendix C - HOTP Algorithm: Reference Implementation..........27 Implementation..........25
Appendix D - HOTP Algorithm: Test Values.......................31 Values.......................29
Appendix E - Extensions........................................29
E.1 Number of Digits..........................................30
E.2 Alpha-numeric Values......................................30
E.3 Sequence of HOTP values...................................30
E.4 A Counter-based Re-Synchronization Method.................31
E.5 Data Field................................................31
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
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
OATH-HMAC-OTP Expires - April 2005 [Page 3]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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
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.
R3 - 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.
OATH-HMAC-OTP Expires - April 2005 [Page 4]
HOTP: An HMAC-based One Time Password Algorithm October 2004
R3
R4 - 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
R5 - 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.
R5
R6 - 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 counter value, 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
OATH-HMAC-OTP Expires - April 2005 [Page 5]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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.
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 Key (K) and (K), the Counter (C) and Data values are hashed high-order
byte first.
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
OATH-HMAC-OTP Expires - April 2005 [Page 6]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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
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|
-------------------------------***********----------------++|
OATH-HMAC-OTP Expires - April 2005 [Page 7]
HOTP: An HMAC-based One Time Password Algorithm October 2004
* 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.
We then take this number modulo 1,000,000 (10^6) to generate the
6-digit HOTP value 872921 decimal.
6. Security 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.
It is also important to remark that the HOTP algorithm is not a
substitute for encryption and does not provide for the privacy of
data transmission. Other mechanisms should be used to defeat
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
RP2 - P MUST SHOULD NOT be vulnerable to brute force attacks. This
implies that a throttling/lockout scheme is REQUIRED RECOMMENDED on the
validation server side.
RP4
RP3 - 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.)
OATH-HMAC-OTP Expires - April 2005 [Page 8]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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.
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 Bi-directional Authentication
Interestingly enough, the HMAC-SHA1 value HOTP client could also be used to
authenticate the validation server, claiming that it is a shorter value makes a brute
force attack possible. Therefore, genuine
entity knowing the shared secret.
Since the HOTP client and the authentication server needs
to detect are synchronized and stop brute force attacks.
We RECOMMEND setting a throttling parameter T, which defines share the
maximum number of possible attempts
same secret (or a method to recompute it) a simple 3-pass protocol
could be put in place:
1- The end user enter the TokenID and a first OTP value OTP1;
2- The server checks OTP1 and if correct, sends back OTP2;
3- The end user checks OTP2 using his HOTP device and if correct,
uses the web site.
Obviously, as indicated previously, all the OTP communications have
to take place over secure https (SSL) connections.
6.4 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
Another option would be to implement a delay scheme to avoid a
brute force attack. After each failed attempt A, the authentication
server would wait for an increased T*A number of seconds, e.g. say
T = 5, then after 1 attempt, the server waits for 5 seconds, at the
second failed attempt, it waits for 5*2 = 10 seconds, etc.
The delay or lockout schemes MUST be across login sessions to
prevent attacks based on multiple parallel guessing techniques.
6.5 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.
OATH-HMAC-OTP Expires - April 2005 [Page 9]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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.
6.5
6.6 Management of Shared Secrets
The operations dealing with the shared secrets used to generate and
verify OTP values must be performed securely, in order to mitigate
risks of any leakage of sensitive information. We describe in this
section different modes of operations and techniquest to perform
these different operations with respect of the state of the art in
terms of data security.
We can consider two different avenues for generating and storing
(securely) shared secrets in the Validation system:
* Deterministic Generation: secrets are derived from a master
seed, both at provisioning and verification stages and generated
on-the-fly whenever it is required;
* Random Generation: secrets are generated randomly at
provisioning stage, and must be stored immediately and kept secure
during their life cycle.
Deterministic Generation
------------------------
A possible strategy is to derive the shared secrets from a master
secret. In this case, a The master secret will be stored at the server only. A
tamper resistant device SHOULD MUST be
generating used to store the master key and
derive the shared secrets based on from the master seed key and some public
information. The main benefit would be to avoid the exposure of the
shared secrets at any time and also avoid specific requirements on
storage, since the shared secrets could be generated on-demand when
needed at provisioning and validation time.
The drawback in this case is that the exposure of the
We distinguish two different cases:
- A single master secret
would obviously enable an attacker key MK is used to rebuild any derive the shared secret
based on correct secrets;
each HOTP device has a different secret, K_i = SHA-1 (MK,i)
where i stands for a public information. On the other hand, piece of information that
identifies uniquely the HOTP device
being tamper resistant, and also, obvioulsly not exposed outside
OATH-HMAC-OTP Expires - April 2005 [Page 10]
HOTP: An HMAC-based One Time Password Algorithm October 2004
the security perimeter of the validation system, the risk of such as a
break-out could be reduced.
Another option to mitigate the risk, would be to use serial number, a series
token ID, etc.; obviously, this is in the context of an
application or service - different application or service
providers will have different secrets and settings;
- Several master secrets, say MS1 to MS5, keys MK_i are used and generate each HOTP device stores a
set of shared
secrets to different derived secrets, {K_i,j = SHA-1(MK_i,j)} where
j stands for a public piece of information identifying the
device. The idea would be stored to store ONLY the active master key
at the validation server, in the OTP generator devices. HSM, and keep in a safe place,
using secret sharing methods such as [Shamir] for instance. In
this case, if a master secret was MK_i is compromised, then the system could it is
possible to switch to another shared secret by selecting without replacing all the proper secret
devices.
The drawback in the device.
This deterministic case is probably not applicable in that the exposure of the
master secret would obviously enable an attacker to rebuild any
shared secret based on correct public information. The revocation
of all situations, secrets would be required, or switching to a new set of
secrets in the case of multiple master keys.
On the other hand, the device used to store the master key(s) and therefore,
generate the random generation method describes hereafter might shared secrets MUST be more
suited in some cases. tamper resistant. Furthermore,
the HSM will not be exposed outside the security perimeter of the
validation system, therefore reducing the risk of leakage.
Random Generation
-----------------
The shared secrets are randomly generated. We RECOMMEND to follow
the usage
of recommendations in [RFC1750] and to select a good and secure
random source for generating them. these secrets. A (true) random
generator requires a naturally occurring source of randomness.
Practically, there are two possible avenues to consider for the
generation of the shared secrets:
* Hardware-based generators: they exploit the randomness which
occurs in physical phenomena. A nice implementation can be based on
oscillators, and built in such ways that active attacks are more
difficult to perform.
* Software-based generators: designing a good software random
generator is not an easy task. A simple, but efficient,
implementation should be based on various sources, and apply to the
sampled sequence a one-way function such as SHA-1.
We RECOMMEND to select proven products, being hardware or software
generators for the computation of shared secrets.
We also RECOMMEND storing the shared secrets securely, and more
specifically encrypting the shared secrets when stored using
tamper-resistant hardware encryption, and exposing them only when
required: e.g. the shared secret is decrypted when needed to verify
an HOTP value, and re-encrypted immediately to limit exposure in
the RAM for a short period of time. The data store holding the
shared secrets MUST be in a secure area, to avoid as much as
possible direct attack on the validation system and secrets
database.
Particularly, access to the shared secrets should be limited to
programs and processes required by the validation system only. We
will not elaborate on the different security mechanisms to put in
place, but obviously, the protection of shared secrets is of the
uttermost importance.
OATH-HMAC-OTP Expires - April 2005 [Page 11]
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 Composite Shared Secrets
It may be desirable to include additional authentication factors in this section several enhancements and suggestions
to further improve
the security shared secret K. These additional factors can consist of any
data known at the algorithm HOTP
OATH-HMAC-OTP Expires - April 2005 [Page 12]
HOTP: An HMAC-based One Time Password Algorithm October 2004
8.1 Number of Digits
A simple enhancement in terms token but not easily obtained by others. Examples
of security would be to extract more
digits from such data include:
* PIN or Password obtained as user input at the HMAC-SHA1 value.
For instance, calculating token
* Phone number
* Any unique identifier programmatically available at the HOTP token
In this scenario the composite shared secret K is constructed
during the provisioning process from a random seed value modulo 10^8 to combined
with one or more additional authentication factors. The server
could either build an
8-digit on-demand or store composite secrets - in any
case, depending on implementation choice, the token only stores the
seed value. When the token performs the HOTP calculation it
computes K from the seed value would reduce and the probability locally derived or input
values of success the other authentication factors.
The use of composite shared secrets can strengthen HOTP based
authentication systems through the
adversary from sv/10^6 to sv/10^8.
This could give inclusion of additional
authentication factors at 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 token. To the theoretical optimum for 6-digit code when s = 1.
8.2 Alpha-numeric Values
Another option extent that the token
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 trusted device this approach has the same on a small display.
The immediate consequence is that further benefit of not
requiring exposure of the security is now in authentication factors (such as the order
of sv/32^6 for a 6-digit HOTP value and sv/32^8 user
input PIN) to other devices.
9. IANA Considerations
This document has no actions for an 8-digit HOTP
value.
32^6 > 10^9 so the security of a 6-alphanumeric HOTP code is
slightly better than IANA.
10. Conclusion
This draft describes HOTP, a 9-digit HOTP value, which is HMAC-based One-Time Password
algorithm. It also recommends the maximum
length preferred implementation and
related modes of an HOTP code supported by operations for deploying the proposed algorithm.
32^8 > 10^12 so the security
The draft also exhibits elements 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 security and entering demonstrates that
the HOTP value, algorithm is practical and sound, the choice of alphanumeric
values could be best possible attack
being a simple and efficient way 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 at a
reduced cost if needed for specific applications.
11. Acknowledgements
The authors would like to thank Siddharth Bajaj, Alex Deacon, Loren
Hart and impact on users.
8.3 Sequence of HOTP values
As we suggested Nico Popp for their help during the resynchronization to enter a short sequence
(say 2 or 3) of HOTP values, we could generalize the concept to the
protocol, conception and add a parameter L that would define the length
redaction of the
HOTP sequence this document.
12. Contributors
The authors of this draft would like to enter.
Per default, emphasize the value L SHOULD be set to 1, but if security needs
to be increased, users might be asked (possibly for a short period role of time, or three
persons who have made a specific operation) key contribution to enter L HOTP values.
OATH-HMAC-OTP Expires this document:
- April 2005 [Page 13]
HOTP: An HMAC-based One Time Password Algorithm October 2004
This Laszlo Elteto 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 architect with SafeNet, Inc.
- Ernesto Frutos is director of L HOTP values.
8.4 A Counter-based Re-Synchronization Method
In this case, we assume that the client can access Engineering with Authenex, Inc.
- Fred McClain is Founder and send not
only the HOTP value but also other information, more specifically
the counter value.
A more efficient CTO with Boojum Mobile, Inc.
Without their advice and secure method for resynchronization is
possible in valuable inputs, this case. The client application will draft would not send the
HOTP-client value only, but be
the HOTP-client same.
13. References
12.1 Normative
[BCK1] M. Bellare, R. Canetti and the related
C-client counter value, the HOTP value acting as a message
authentication code H. Krawczyk, "Keyed Hash
Functions and Message Authentication", Proceedings 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
Crypto'96, LNCS Vol. 1109, pp. 1-15.
[BCK2] M. Bellare, R. Canetti and client is
authenticated
In this case, there is no need H. Krawczyk, "HMAC:
Keyed-Hashing for managing a look-ahead window
anymore. The probability of success of the adversary is only v/10^6
or roughly v Message Authentication", IETF Network
Working Group, RFC 2104, February 1997.
[RFC1750] D. Eastlake, 3rd., S. Crocker and J. Schiller,
"Randomness Recommendantions for Security", IETF
Network Working Group, RFC 1750, December 2004.
[RFC2119] S. Bradner, "Key words for use in one million. A side benefit is obviously to be able RFCs to increase s "infinitely" Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC3668] S. Bradner, "Intellectual Propery Rights in IETF
Technology", BCP 79, RFC 3668, February 2004.
12.2 Informative
[OATH] Initiative for Open AuTHentication
http://www.openauthentication.org
[PrOo] B. Preneel and therefore improve the system
usability without impacting the security.
This resynchronization protocol SHOULD be use whenever the related
impact on the client P. van Oorschot, "MD-x MAC and server applications is deemed acceptable.
8.5 Composite Shared Secrets
It may be desirable to include additional authentication factors building
fast MACs from hash functions", Advances in
the shared secret K. These additional factors can consist of any
data known at the token but not easily obtained by others. Examples
of such data include:
* PIN or Password obtained as user input at the token
* Phone number
* Any unique identifier programmatically available at the token
OATH-HMAC-OTP Expires - April 2005 [Page 14]
HOTP: An HMAC-based One Time Password Algorithm October 2004
In this scenario the composite shared secret K is constructed
during the provisioning process from a random seed value combined
with one or more additional authentication factors. The server
could either build on-demand or store composite secrets - in any
case, depending on implementation choice, the token only stores the
seed value. When the token performs the HOTP calculation it
computes K from the seed value and the locally derived or input
values of the other authentication factors.
The use of composite shared secrets can strengthen HOTP based
authentication systems through the inclusion of additional
authentication factors at the token. To the extent that the token
is a trusted device this approach has the further benefit of not
requiring exposure of the authentication factors (such as the user
input PIN) to other devices.
8.6 Data Field
Another possibility would be to introduce the notion of a Data
field, that would be used for generating the One-Time password
values: HOTP (K, C, [Data]) where Data is an optional field that
can be the concatenation of various pieces of identity-related
information - e.g. Data = Address | PIN.
We could also use a Timer, either as the only moving factor or in
combination with the Counter - Cryptology
CRYPTO '95, Lecture Notes in this case, e.g. Data = Timer,
where Timer could be the UNIX-time (GMT seconds since 1/1/1970)
divided by some factor (8, 16, 32, etc.) Computer Science Vol. 963,
D. Coppersmith ed., Springer-Verlag, 1995.
[Crack] Crack in order SHA-1 code 'stuns' security gurus
http://www.eetimes.com/showArticle.jhtml?articleID=60402150
[Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005.
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
[Res] Researchers: Digital encryption standard flawed
http://news.com.com/Researchers+Digital+encryption+standard+flawed/
2100-1002-5579881.html?part=dht&tag=ntop&tag=nl.e703
[Shamir] How to give Share a
specific time step. The time window for the One-Time Password is
then equal to the time step multiplied Secret, by Adi Shamir. In Communications
of the resynchronization
parameter as defined before - e.g. if we take 64 seconds as the
time step ACM, Vol. 22, No. 11, pp. 612-613, November, 1979.
14. Authors' Addresses
Primary point of contact (for sending comments and 7 for the resynchronization parameter, we obtain an
acceptance window 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 +/- 3 minutes.
Using a Data field opens for more flexibility in the algorithm
implementation, provided that the Data field is clearly specified.
9. Conclusion
This draft describes HOTP, a HMAC-based One-Time Password
algorithm. It also recommends the preferred implementation 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
related modes
Information Security Group,
Royal Holloway,
University of operations for deploying the algorithm. 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
15. Full Copyright Statement
Copyright (C) The draft also exhibits elements of security and demonstrates that
the HOTP algorithm Internet Society (2005).
This document is practical and sound, subject to the best possible attack
being a brute force attack that can be prevented by careful
implementation of countermeasures rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the validation server.
OATH-HMAC-OTP Expires - April 2005 [Page 15]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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, Loren
Hart and Nico Popp for
retain all their help during rights.
This document and the conception information contained herein are provided on
an "AS IS" basis and
redaction of this document.
11. Contributors 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.
16. Intellectual Property
The authors of this draft would like to emphasize IETF takes no position regarding the role validity or scope of three
persons who have made a key contribution any
Intellectual Property Rights or other rights that might be claimed
to this document:
- Laszlo Elteto is system architect with SafeNet, Inc.
- Ernesto Frutos is director pertain to the implementation or use of Engineering with Authenex, Inc.
- Fred McClain is Founder and CTO with Boojum Mobile, Inc.
Without their advice and valuable inputs, the technology described
in this draft would document or the extent to which any license under such
rights might or might 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] S. Bradner, "Key words for use in RFCs available; nor does it represent that
it has made any independent effort to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC3668] S. Bradner, "Intellectual Propery Rights in IETF
Technology", BCP 79, RFC 3668, February 2004.
12.2 Informative
[OATH] Initiative for Open AuTHentication
http://www.openauthentication.org
[PrOo] B. Preneel and P. van Oorschot, "MD-x MAC and building
fast MACs from hash functions", Advances in Cryptology
OATH-HMAC-OTP Expires - April 2005 [Page 16]
HOTP: An HMAC-based One Time Password Algorithm October 2004
CRYPTO '95, Lecture Notes in Computer Science Vol. 963,
D. Coppersmith ed., Springer-Verlag, 1995.
[Crack] Crack identify any such rights.
Information on the procedures with respect to rights in SHA-1 code 'stuns' security gurus
http://www.eetimes.com/showArticle.jhtml?articleID=60402150
[Sha1] Bruce Schneier. SHA-1 broken. February 15, 2005.
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
[Res] Researchers: Digital encryption standard flawed
http://news.com.com/Researchers+Digital+encryption+standard+flawed/
2100-1002-5579881.html?part=dht&tag=ntop&tag=nl.e703
13. Authors' Addresses
Primary point of contact (for sending comments RFC
documents can be found in BCP 78 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 BCP 79.
Copies of Computer Science IPR disclosures made to the IETF Secretariat and Engineering, Mail Code 0114
University any
assurances 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 licenses to be made available, or the result of London, Egham,
Surrey TW20 0EX, UK Email: david.naccache@rhul.ac.uk
Ohad Ranen
Aladdin Knowledge Systems Ltd.
15 Beit Oved Street
OATH-HMAC-OTP Expires - April 2005 [Page 17]
HOTP: An HMAC-based One Time Password Algorithm October 2004
Tel Aviv, Israel 61110 Email: Ohad.Ranen@ealaddin.com an
attempt made to obtain a general license or permission for the use
of such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository
at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Appendix A - 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.
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
OATH-HMAC-OTP Expires - April 2005 [Page 18]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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
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.
OATH-HMAC-OTP Expires - April 2005 [Page 19]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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()
--------------
A = ALG(K,C)
C = C + 1
Return O to B
Oracle VerO(A)
--------------
i = C
While (i <= C + s - 1 and Win == FALSE) do
If A == ALG(K,i) then Win = TRUE; C = i + 1
Else i = i + 1
Return Win to B
AuthO() is the authenticator oracle and VerO(A) 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.
OATH-HMAC-OTP Expires - April 2005 [Page 20]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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:
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
OATH-HMAC-OTP Expires - April 2005 [Page 21]
HOTP: An HMAC-based One Time Password Algorithm October 2004
----------------------------------------------------------------
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.
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
OATH-HMAC-OTP Expires - April 2005 [Page 22]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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
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
OATH-HMAC-OTP Expires - April 2005 [Page 23]
HOTP: An HMAC-based One Time Password Algorithm October 2004
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 [PrOo],
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,
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
OATH-HMAC-OTP Expires
queries, a <= 2^c - April 2005 [Page 24]
HOTP: An HMAC-based One Time Password Algorithm October 2004 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^c - s authenticator oracle queries, and running
time t. Let T denote the time 2^40 due to perform one computation of H. If
Assumption 1 is true then
Adv(B) <= sv * (q + 1)/2^31 + the throttling and bounds on
s. So:
(t/T)/2^k + ((sv + a)^2)/2^n
In practice, the (t/T)2^-k + ((sv <= 2^60/2^160 + a)^2)2^-n term (2^41)^2/2^160
roughly <= 2^-78
which is much smaller than the sv(q + 1)/2^n term, so success probability of Equation 1
and negligible compared to it.
Appendix B - SHA-1 Attacks
This sections addresses the impact of the recent attacks on SHA-1
on the security of the HMAC-SHA-1 based HOTP. We begin with some
discussion of the situation of SHA-1 and then discuss the relevance
to HMAC-SHA-1 and HOTP. Cited references are at the bottom of the
document.
B.1 SHA-1 status
A collision for a hash function h means a pair x,y of different
inputs such that h(x)=h(y). Since SHA-1 outputs 160 bits, a
birthday attack finds a collision in 2^{80} trials. (A trial means
one computation of the above says function.) This was thought to be the best
possible until Wang, Yin and Yu announced on February 15, 2005 that for all
they had an attack finding collisions in 2^{69} trials.
Is SHA-1 broken? For most practical purposes we would say probably
not, since the success rate of an adversary attacking HOTP
is sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning resources needed to mount the HOTP
algorithm attack are huge. Here
is one way to get a sense of it: we can estimate it is in practice essentially as good about the
same as its idealized
counterpart.
In the case m = 10^6 of time we would need to factor a 6-digit output 760-bit RSA modulus, and
this means that an
adversary making v authentication attempts will have a success rate
that is at most that currently considered out of Equation 1.
For example, consider an adversary with running time at most 2^60
that sees at most 2^40 authentication attempts reach.
Burr of NIST is quoted [Crack] as saying ``Large national
intelligence agencies could do this in a reasonable amount of time
with a few million dollars in computer time.'' However, the user. Both
these choices are very generous to the adversary, who will
typically not have these resources,
computation may be out of reach of all but we are saying that even such well-funded
agencies.
One should also ask what impact finding SHA-1 collisions actually
has on security of real applications such as signatures. To exploit
a powerful adversary will not have more success than indicated
by Equation 1.
We can safely assume sv <= 2^40 due collision x,y to the throttling forge signatures, you need to somehow obtain a
signature of x 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 then you can forge a signature of y. How
damaging this is much smaller than depends on the success probability content of Equation 1
and negligible compared y: the y created by the
attack may not be meaningful in the application context. Also, one
needs a chosen-message attack to it.
Appendix B - SHA-1 Attacks
This sections addresses get the impact signature of x. This seems
possible in some contexts, but not others. Overall, it is not clear
the recent attacks on SHA-1 impact on the security of the HMAC-SHA-1 based HOTP. We begin with some
discussion of the situation of signatures is significant.
Indeed, one can read that SHA-1 is ``broken,'' [Sha1], that
encryption and then discuss the relevance
to HMAC-SHA-1 and HOTP. Cited references SSL are at the bottom of the
document.
B.1 SHA-1 status
A collision for a hash function h means a pair x,y of different
inputs such that h(x)=h(y). Since SHA-1 outputs 160 bits, a
birthday attack finds a collision ``broken'' [Res], in 2^{80} trials. (A trial means
one computation of the function.) This was thought press. The media
have a tendency to magnify events: it would hardly be interesting
to announce in the best
possible until Wang, Yin and Yu announced on February 15, 2005 news that
they had a team of cryptanalysts did very
interesting theoretical work in attacking SHA-1.
Cryptographers are excited too. But mainly because this is an attack finding collisions
important theoretical breakthrough. Attacks can only get beter with
time: it is therefore important to monitor any progress in 2^{69} trials.
OATH-HMAC-OTP Expires - April 2005 [Page 25]
HOTP: An HMAC-based One Time Password Algorithm October 2004
Is SHA-1 broken? For most hash
functions cryptanalysis and be prepared for any really practical purposes we would say probably
not, since
break with a sound migration plan for the resources needed to mount future.
B.2 HMAC-SHA-1 status
The new attacks on SHA-1 have no impact on the security of HMAC-
SHA-1. The best attack are huge. Here
is on the latter remains one way to get needing a sense of it: we can estimate it is about the
same as the time we would need sender
to factor authenticate 2^{80} messages before an adversary can create a 760-bit RSA modulus, and
this
forgery. Why?
HMAC is currently considered out of reach.
Burr of NIST not a hash function. It is quoted [Crack] as saying ``Large national
intelligence agencies could do this in a reasonable amount of time message authentication code
(MAC) that uses a hash function internally. A MAC depends on a
secret key, while hash functions don't. What one needs to worry
about with a few million dollars MAC is forgery, not collisions. HMAC was designed so
that collisions in computer time.'' However, the
computation may be out of reach of all but such well-funded
agencies.
One should also ask what impact finding SHA-1 collisions actually
has on security of real applications such as signatures. To exploit hash function (here SHA-1) do not yield
forgeries for HMAC.
Recall that HMAC-SHA-1(K,x) = SHA-1(K_o,SHA-1(K_i,x)) where the
keys K_o,K_i are derived from K. Suppose the attacker finds a collision pair
x,y to forge signatures, you need to somehow obtain such that SHA-1(K_i,x)=SHA-1(K_i,y). (Call this a
signature hidden-key
collision.) Then if it can obtain the MAC of x and then you (itself a tall
order), it can forge a signature of y. How
damaging this is depends on the content MAC of y: the y created by the
attack may not be meaningful in y. (These values are the application context. Also, one
needs a chosen-message attack to get same.) But
finding hidden-key collisions is harder than finding collisions,
because the signature of x. This seems
possible in some contexts, but attacker does not others. Overall, know the hidden key K_i. All it may
have is not clear some outputs of HMAC-SHA-1 with key K. To date there are no
claims or evidence that the impact recent attacks on SHA-1 extend to find
hidden-key collisions.
Historically, the security of signatures HMAC design has already proven itself in this
regard. MD5 is significant.
Indeed, one can read considered broken in that SHA-1 collisions in this hash
function can be found relatively easily. But there is ``broken,'' [Sha1], that
encryption and SSL still no
attack on HMAC-MD5 better than the trivial 2^{64} time birthday
one. (MD5 outputs 128 bits, not 160.) We are ``broken'' [Res], seeing this strength
of HMAC coming into play again in the press. SHA-1 context.
B.3 HOTP status
Since no new weakness has surfaced in HMAC-SHA-1, there is no
impact on HOTP. The media
have a tendency to magnify events: it would hardly be interesting
to announce best attacks on HOTP remain those described in
the news document, namely to try to guess output values.
The security proof of HOTP requires that HMAC-SHA-1 behave like a team
pseudorandom function. The quality of cryptanalysts did very
interesting theoretical work in attacking SHA-1.
Cryptographers are excited too. But mainly because HMAC-SHA-1 as a pseudorandom
function is not impacted by the new attacks on SHA-1, and so
neither is this proven guarantee.
Appendix C - HOTP Algorithm: Reference Implementation
/*
* OneTimePasswordAlgorithm.java
* OATH Initiative,
* HOTP one-time password algorithm
*
*/
/* Copyright (C) 2004, OATH. All rights reserved.
*
* License to copy and use this software is an
important theoretical breakthrough. Attacks can only get beter with
time: granted provided that it
* is therefore important to monitor any progress identified as the "OATH HOTP Algorithm" in hash
functions cryptanalysis all material
* mentioning or referencing this software or this function.
*
* License is also granted to make and be prepared for any really practical
break with a sound migration plan for use derivative works provided
* that such works are identified as
* "derived from OATH HOTP algorithm"
* in all material mentioning or referencing the future.
B.2 HMAC-SHA-1 status
The new attacks on SHA-1 have derived work.
*
* OATH (Open AuTHentication) and its members make no impact on
* representations concerning either the security merchantability of HMAC-
SHA-1. The best attack on this
* software or the latter remains one needing a sender
to authenticate 2^{80} messages before an adversary can create a
forgery. Why?
HMAC is not a hash function. suitability of this software for any particular
* purpose.
*
* It is a message authentication code
(MAC) that uses a hash function internally. A MAC depends on a
secret key, while hash functions don't. What one needs provided "as is" without express or implied warranty
* of any kind and OATH AND ITS MEMBERS EXPRESSELY DISCLAIMS
* ANY WARRANTY OR LIABILITY OF ANY KIND relating to worry
about with a MAC is forgery, not collisions. HMAC was designed so this software.
*
* These notices must be retained in any copies of any part of this
* documentation and/or software.
*/
package org.openauthentication.otp;
import java.io.IOException;
import java.io.File;
import java.io.DataInputStream;
import java.io.FileInputStream ;
import java.lang.reflect.UndeclaredThrowableException;
import java.security.GeneralSecurityException;
import java.security.NoSuchAlgorithmException;
import java.security.InvalidKeyException;
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
/**
* This class contains static methods that collisions in are used to calculate the hash function (here SHA-1) do not yield
forgeries for HMAC.
OATH-HMAC-OTP Expires - April 2005 [Page 26]
HOTP: An HMAC-based One Time
* One-Time Password Algorithm October 2004
Recall that HMAC-SHA-1(K,x) = SHA-1(K_o,SHA-1(K_i,x)) where (OTP) using
* JCE to provide the
keys K_o,K_i HMAC-SHA1.
*
* @author Loren Hart
* @version 1.0
*/
public class OneTimePasswordAlgorithm {
private OneTimePasswordAlgorithm() {}
// These are derived from K. Suppose used to calculate the attacker finds a pair
x,y such check-sum digits.
// 0 1 2 3 4 5 6 7 8 9
private static final int[] doubleDigits =
{ 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
/**
* Calculates the checksum using the credit card algorithm.
* This algorithm has the advantage that SHA-1(K_i,x)=SHA-1(K_i,y). (Call this a hidden-key
collision.) Then if it can obtain the MAC detects any single
* mistyped digit and any single transposition of x (itself a tall
order), it can forge
* adjacent digits.
*
* @param num the MAC of y. (These values are number to calculate the same.) But
finding hidden-key collisions is harder than finding collisions,
because checksum for
* @param digits number of significant places in the attacker does not know number
*
* @return the hidden key K_i. All it may
have is some outputs checksum of HMAC-SHA-1 with key K. To date there are no
claims or evidence that num
*/
public static int calcChecksum(long num, int digits) {
boolean doubleDigit = true;
int total = 0;
while (0 < digits--) {
int digit = (int) (num % 10);
num /= 10;
if (doubleDigit) {
digit = doubleDigits[digit];
}
total += digit;
doubleDigit = !doubleDigit;
}
int result = total % 10;
if (result > 0) {
result = 10 - result;
}
return result;
}
/**
* This method uses the recent attacks on SHA-1 extend JCE to find
hidden-key collisions.
Historically, provide the HMAC-SHA1
* algorithm.
* HMAC design has already proven itself computes a Hashed Message Authentication Code and
* in this
regard. MD5 case SHA1 is considered broken in that collisions in this the hash
function can be found relatively easily. But there is still no
attack on HMAC-MD5 better than algorithm used.
*
* @param keyBytes the trivial 2^{64} time birthday
one. (MD5 outputs 128 bits, not 160.) We are seeing this strength
of HMAC coming into play again in bytes to use for the SHA-1 context.
B.3 HOTP status
Since no new weakness has surfaced in HMAC-SHA-1, there is no
impact on HOTP. The best attacks on HOTP remain those described in HMAC-SHA1 key
* @param text the document, namely to try message or text to guess output values.
The security proof of HOTP requires that HMAC-SHA-1 behave like a
pseudorandom function. The quality of HMAC-SHA-1 as a pseudorandom
function is not impacted by the new attacks on SHA-1, and so
neither is this proven guarantee.
Appendix C - HOTP Algorithm: Reference Implementation
/* be authenticated.
*
* @throws NoSuchAlgorithmException if no provider makes
* either HmacSHA1 or HMAC-SHA1
* OneTimePasswordAlgorithm.java digest algorithms available.
* OATH Initiative, @throws InvalidKeyException
* HOTP one-time password algorithm The secret provided was not a valid HMAC-SHA1 key.
*
*/
/* Copyright (C) 2004, OATH. All rights reserved.
public static byte[] hmac_sha1(byte[] keyBytes, byte[] text)
throws NoSuchAlgorithmException, InvalidKeyException
{
// try {
Mac hmacSha1;
try {
hmacSha1 = Mac.getInstance("HmacSHA1");
} catch (NoSuchAlgorithmException nsae) {
hmacSha1 = Mac.getInstance("HMAC-SHA1");
}
SecretKeySpec macKey =
new SecretKeySpec(keyBytes, "RAW");
hmacSha1.init(macKey);
return hmacSha1.doFinal(text);
// } catch (GeneralSecurityException gse) {
// throw new UndeclaredThrowableException(gse);
// }
}
private static final int[] DIGITS_POWER
// 0 1 2 3 4 5 6 7 8
= {1,10,100,1000,10000,100000,1000000,10000000,100000000};
/**
* This method generates an OTP value for the given
* License to copy and use this software is granted provided that it set of parameters.
* is identified as
* @param secret the "OATH HOTP Algorithm" in all material shared secret
* mentioning or referencing this software @param movingFactor the counter, time, or this function.
* other value that
* License is also granted to make and changes on a per use derivative works provided basis.
* that such works are identified as @param codeDigits the number of digits in the OTP, not
* "derived from OATH HOTP algorithm" including the checksum, if any.
* in all material mentioning or referencing @param addChecksum a flag that indicates if a checksum digit
* should be appended to the derived work.
OATH-HMAC-OTP Expires - April 2005 [Page 27]
HOTP: An HMAC-based One Time Password Algorithm October 2004 OTP.
* @param truncationOffset the offset into the MAC result to
* OATH (Open AuTHentication) and its members make no begin truncation. If this value is out of
* representations concerning either the merchantability range of this 0 ... 15, then dynamic
* software or truncation will be used.
* Dynamic truncation is when the suitability last 4
* bits of this software for any particular the last byte of the MAC are
* purpose. used to determine the start offset.
* @throws NoSuchAlgorithmException if no provider makes
* It is provided "as is" without express either HmacSHA1 or implied warranty HMAC-SHA1
* of any kind and OATH AND ITS MEMBERS EXPRESSELY DISCLAIMS digest algorithms available.
* ANY WARRANTY OR LIABILITY OF ANY KIND relating to this software. @throws InvalidKeyException
* The secret provided was not
* a valid HMAC-SHA1 key.
* These notices must be retained
* @return A numeric String in any copies of any part of this base 10 that includes
* documentation and/or software. {@link codeDigits} digits plus the optional checksum
* digit if requested.
*/
package org.openauthentication.otp;
import java.io.IOException;
import java.io.File;
import java.io.DataInputStream;
import java.io.FileInputStream ;
import java.lang.reflect.UndeclaredThrowableException;
import java.security.GeneralSecurityException;
import java.security.NoSuchAlgorithmException;
import java.security.InvalidKeyException;
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
/**
static public String generateOTP(byte[] secret,
long movingFactor,
int codeDigits,
boolean addChecksum,
int truncationOffset)
throws NoSuchAlgorithmException, InvalidKeyException
{
// put movingFactor value into text byte array
String result = null;
int digits = addChecksum ? (codeDigits + 1) : codeDigits;
byte[] text = new byte[8];
for (int i = text.length - 1; i >= 0; i--) {
text[i] = (byte) (movingFactor & 0xff);
movingFactor >>= 8;
}
// compute hmac hash
byte[] hash = hmac_sha1(secret, text);
// put selected bytes into result int
int offset = hash[hash.length - 1] & 0xf;
if ( (0<=truncationOffset) &&
(truncationOffset<(hash.length-4)) ) {
offset = truncationOffset;
}
int binary =
((hash[offset] & 0x7f) << 24)
| ((hash[offset + 1] & 0xff) << 16)
| ((hash[offset + 2] & 0xff) << 8)
| (hash[offset + 3] & 0xff);
int otp = binary % DIGITS_POWER[codeDigits];
if (addChecksum) {
otp = (otp * This class contains static methods that are used to calculate 10) + calcChecksum(otp, codeDigits);
}
result = Integer.toString(otp);
while (result.length() < digits) {
result = "0" + result;
}
return result;
}
}
Appendix D - HOTP Algorithm: Test Values
The following test data uses the
* One-Time Password (OTP) using
* JCE to provide ASCII string
"123456787901234567890" for the HMAC-SHA1.
*
* @author Loren Hart
* @version 1.0
*/
public class OneTimePasswordAlgorithm {
private OneTimePasswordAlgorithm() {}
// These are used to calculate secret:
Secret = 0x3132333435363738393031323334353637383930
Table 1 details for each count, the check-sum digits.
// intermediate hmac value.
Count Hexadecimal HMAC-SHA1(secret, count)
0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0
1 75a48a19d4cbe100644e8ac1397eea747a2d33ab
2 0bacb7fa082fef30782211938bc1c5e70416ff44
3 66c28227d03a2d5529262ff016a1e6ef76557ece
4 a904c900a64b35909874b33e61c5938a8e15ed1c
5 a37e783d7b7233c083d4f62926c7a25f238d0316
6 bc9cd28561042c83f219324d3c607256c03272ae
7 a4fb960c0bc06e1eabb804e5b397cdc4b45596fa
8 1b3c89f65e6c9e883012052823443f048b4332db
9
private static final int[] doubleDigits =
{ 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
/**
* Calculates 1637409809a679dc698207310c8c7fc07290d9e5
Table details for each count the checksum using truncated values (both in
hexadecimal and decimal) and then the HOTP value.
Truncated
Count Hexadecimal Decimal HOTP
0 4c93cf18 1284755224 755224
1 41397eea 1094287082 287082
2 82fef30 137359152 359152
3 66ef7655 1726969429 969429
4 61c5938a 1640338314 338314
5 33c083d4 868254676 254676
6 7256c032 1918287922 287922
7 4e5b397 82162583 162583
8 2823443f 673399871 399871
9 2679dc69 645520489 520489
Appendix E - Extensions
We introduce in this section several enhancements to the credit card HOTP
algorithm.
* This algorithm has These are not recommended extensions or part of the advantage
standard algorithm, but merely variations that it detects any single
* mistyped digit and any single transposition could be used for
customized implementations.
E.1 Number of
OATH-HMAC-OTP Expires - April 2005 [Page 28]
HOTP: An HMAC-based One Time Password Algorithm October 2004
* adjacent digits.
*
* @param num Digits
A simple enhancement in terms of security would be to extract more
digits from the number HMAC-SHA1 value.
For instance, calculating the HOTP value modulo 10^8 to calculate build an
8-digit HOTP value would reduce the checksum for
* @param digits number probability of success of significant places in the number
*
* @return
adversary from sv/10^6 to sv/10^8.
This could give the checksum of num
*/
public static int calcChecksum(long num, int digits) {
boolean doubleDigit = true;
int total = 0; opportunity to improve usability, e.g. by
increasing T and/or s, while (0 < digits--) {
int digit = (int) (num % 10);
num /= 10;
if (doubleDigit) {
digit = doubleDigits[digit];
}
total += digit;
doubleDigit still achieving a better security
overall. For instance, s = !doubleDigit;
}
int result 10 and 10v/10^8 = total % 10;
if (result > 0) {
result v/10^7 < v/10^6 which
is the theoretical optimum for 6-digit code when s = 10 - result;
}
return result;
}
/**
* This method uses 1.
E.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 JCE alphanumerical alphabet in order to provide avoid
any confusion between characters: 0, O and Q as well as l, 1 and I
are very similar, and can look the HMAC-SHA1
* algorithm.
* HMAC computes same on a Hashed Message Authentication Code and
* in this case SHA1 small display.
The immediate consequence is that the hash algorithm used.
*
* @param keyBytes security is now in the bytes to use order
of sv/32^6 for the HMAC-SHA1 key
* @param text the message or text to be authenticated.
*
* @throws NoSuchAlgorithmException if no provider makes
* either HmacSHA1 or HMAC-SHA1
* digest algorithms available.
* @throws InvalidKeyException
* The secret provided was not a valid HMAC-SHA1 key.
*
*/
public static byte[] hmac_sha1(byte[] keyBytes, byte[] text)
throws NoSuchAlgorithmException, InvalidKeyException
{
// try {
Mac hmacSha1;
try {
OATH-HMAC-OTP Expires - April 2005 [Page 29]
HOTP: An HMAC-based One Time Password Algorithm October 2004
hmacSha1 = Mac.getInstance("HmacSHA1");
} catch (NoSuchAlgorithmException nsae) {
hmacSha1 = Mac.getInstance("HMAC-SHA1");
}
SecretKeySpec macKey =
new SecretKeySpec(keyBytes, "RAW");
hmacSha1.init(macKey);
return hmacSha1.doFinal(text);
// } catch (GeneralSecurityException gse) {
// throw new UndeclaredThrowableException(gse);
// }
}
private static final int[] DIGITS_POWER
// 0 1 2 3 4 5 6 7 8
= {1,10,100,1000,10000,100000,1000000,10000000,100000000};
/**
* This method generates an OTP 6-digit HOTP value and sv/32^8 for an 8-digit HOTP
value.
32^6 > 10^9 so the given
* set security of parameters.
*
* @param secret a 6-alphanumeric HOTP code is
slightly better than a 9-digit HOTP value, which is the shared secret
* @param movingFactor maximum
length of an HOTP code supported by the counter, time, or other value that
* changes on proposed algorithm.
32^8 > 10^12 so the security of an 8-alphanumeric HOTP code is
significantly better than a per use basis.
* @param codeDigits 9-digit HOTP value.
Depending on the number of digits in application and token/interface used for
displaying and entering the OTP, not
* including HOTP value, the checksum, if any.
* @param addChecksum a flag that indicates if a checksum digit
* should choice of alphanumeric
values could be appended a simple and efficient way to improve security at a
reduced cost and impact on users.
E.3 Sequence of HOTP values
As we suggested for the OTP.
* @param truncationOffset the offset into the MAC result resynchronization to
* begin truncation. If this value is out enter a short sequence
(say 2 or 3) of
* HOTP values, we could generalize the range of 0 ... 15, then dynamic
* truncation will be used.
* Dynamic truncation is when concept to the last 4
* bits of
protocol, and add a parameter L that would define the last byte length of the MAC are
* used
HOTP sequence to determine enter.
Per default, the start offset.
* @throws NoSuchAlgorithmException value L SHOULD be set to 1, but if no provider makes
* either HmacSHA1 security needs
to be increased, users might be asked (possibly for a short period
of time, or HMAC-SHA1
* digest algorithms available.
* @throws InvalidKeyException
* 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 secret provided was not
* 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 valid HMAC-SHA1 key.
*
* @return sequence of L HOTP values.
E.4 A numeric String in base 10 Counter-based Re-Synchronization Method
In this case, we assume that includes
* {@link codeDigits} digits plus the optional checksum
* digit if requested.
*/
static public String generateOTP(byte[] secret,
long movingFactor,
int codeDigits,
OATH-HMAC-OTP Expires - April 2005 [Page 30]
HOTP: An HMAC-based One Time Password Algorithm October 2004
boolean addChecksum,
int truncationOffset)
throws NoSuchAlgorithmException, InvalidKeyException
{
// put movingFactor client can access and send not
only the HOTP value into text byte array
String result = null;
int digits = addChecksum ? (codeDigits + 1) : codeDigits;
byte[] text = new byte[8]; but also other information, more specifically
the counter value.
A more efficient and secure method for (int i = text.length - 1; i >= 0; i--) {
text[i] = (byte) (movingFactor & 0xff);
movingFactor >>= 8;
}
// compute hmac hash
byte[] hash = hmac_sha1(secret, text);
// put selected bytes into result int
int offset = hash[hash.length - 1] & 0xf;
if ( (0<=truncationOffset) &&
(truncationOffset<(hash.length-4)) ) {
offset = truncationOffset;
}
int binary =
((hash[offset] & 0x7f) << 24)
| ((hash[offset + 1] & 0xff) << 16)
| ((hash[offset + 2] & 0xff) << 8)
| (hash[offset + 3] & 0xff);
int otp = binary % DIGITS_POWER[codeDigits];
if (addChecksum) {
otp = (otp * 10) + calcChecksum(otp, codeDigits);
}
result = Integer.toString(otp);
while (result.length() < digits) {
result = "0" + result;
}
return result;
}
}
Appendix D - 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 Algorithm: Test Values value acting as a message
authentication code of the counter.
Resynchronization Counter-based Protocol (RCP)
----------------------------------------------
The server accepts if the following test data uses 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 ASCII string
"123456787901234567890" 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 secret:
Secret = 0x3132333435363738393031323334353637383930
Table 1 details 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.
E.5 Data Field
Another interesting option is the introduction of a Data field,
that would be used for each count, generating the intermediate hmac value.
OATH-HMAC-OTP Expires One-Time password values:
HOTP (K, C, [Data]) where Data is an optional field that can be the
concatenation of various pieces of identity-related information - April 2005 [Page 31]
HOTP: An HMAC-based One Time Password Algorithm October 2004
Count Hexadecimal HMAC-SHA1(secret, count)
0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0
1 75a48a19d4cbe100644e8ac1397eea747a2d33ab
2 0bacb7fa082fef30782211938bc1c5e70416ff44
3 66c28227d03a2d5529262ff016a1e6ef76557ece
4 a904c900a64b35909874b33e61c5938a8e15ed1c
5 a37e783d7b7233c083d4f62926c7a25f238d0316
6 bc9cd28561042c83f219324d3c607256c03272ae
7 a4fb960c0bc06e1eabb804e5b397cdc4b45596fa
8 1b3c89f65e6c9e883012052823443f048b4332db
9 1637409809a679dc698207310c8c7fc07290d9e5
Table details for each count
e.g. Data = Address | PIN.
We could also use a Timer, either as the only moving factor or in
combination with the truncated values (both Counter - in
hexadecimal and decimal) and then this case, e.g. Data = Timer,
where Timer could be the HOTP value.
Truncated
Count Hexadecimal Decimal HOTP
0 4c93cf18 1284755224 755224
1 41397eea 1094287082 287082
2 82fef30 137359152 359152
3 66ef7655 1726969429 969429
4 61c5938a 1640338314 338314
5 33c083d4 868254676 254676
6 7256c032 1918287922 287922
7 4e5b397 82162583 162583
8 2823443f 673399871 399871
9 2679dc69 645520489 520489
Full Copyright Statement
Copyright (C) UNIX-time (GMT seconds since 1/1/1970)
divided by some factor (8, 16, 32, etc.) in order to give a
specific time step. The Internet Society 2004. This document time window for the One-Time Password is subject
then equal to the rights, licenses and restrictions contained in BCP 78, and
except time step multiplied by the resynchronization
parameter as defined before - e.g. if we take 64 seconds as set forth therein, the authors retain all their rights.
This document
time step and 7 for the information contained herein are provided on resynchronization parameter, we obtain 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 32]
acceptance window of +/- 3 minutes.
Using a Data field opens for more flexibility in the algorithm
implementation, provided that the Data field is clearly specified.
----