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 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.
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 in Section 13.
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 function.) This was thought to be the best
possible until Wang, Yin, and Yu announced on February 15, 2005, that
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 resources needed to mount the attack are huge. Here
is one way to get a sense of it: we can estimate it is about the same
as the time we would need to factor a 760-bit RSA modulus, and this
is currently considered out of reach.
Burr of NIST is quoted in [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
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 a
collision x,y to forge signatures, you need to somehow obtain a
signature of x and then you can forge a signature of y. How damaging
this is depends on the content of y: the y created by the attack may
not be meaningful in the application context. Also, one needs a
chosen-message attack to get the signature of x. This seems possible
in some contexts, but not others. Overall, it is not clear that the
impact on the security of signatures is significant.
Indeed, one can read in the press that SHA-1 is "broken" [Sha1] and
that encryption and SSL are "broken" [Res]. The media have a
tendency to magnify events: it would hardly be interesting to
announce in the news that a team of cryptanalysts did very
interesting theoretical work in attacking SHA-1.
Cryptographers are excited too. But mainly because this is an
important theoretical breakthrough. Attacks can only get better with
time: it is therefore important to monitor any progress in hash
functions cryptanalysis and be prepared for any really practical
break with a sound migration plan for the 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 on 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. 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 to worry
about with a MAC is forgery, not collisions. HMAC was designed so
that collisions in the 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 pair x,y
such that SHA-1(K_i,x) = SHA-1(K_i,y). (Call this a hidden-key
collision.) Then if it can obtain the MAC of x (itself a tall
order), it can forge the MAC of y. (These values are the same.) But
finding hidden-key collisions is harder than finding collisions,
because the attacker does not know the hidden key K_i. All it may
have is some outputs of HMAC-SHA-1 with key K. To date, there are no
claims or evidence that the recent attacks on SHA-1 extend to find
hidden-key collisions.
Historically, the HMAC design has already proven itself in this
regard. MD5 is considered broken in that collisions in this hash
function can be found relatively easily. But there is still no
attack on HMAC-MD5 better than 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 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 the
document, namely, to try 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
/*
* OneTimePasswordAlgorithm.java
* OATH Initiative,
* HOTP one-time password algorithm
*
*/
/* Copyright (C) 2004, OATH. All rights reserved.
*
* License to copy and use this software is granted provided that it
* is identified as the "OATH HOTP Algorithm" in all material
* mentioning or referencing this software or this function.
*
* License is also granted to make and use derivative works provided
* that such works are identified as
* "derived from OATH HOTP algorithm"
* in all material mentioning or referencing the derived work.
*
* OATH (Open AuTHentication) and its members make no
* representations concerning either the merchantability of this
* software or the suitability of this software for any particular
* purpose.
*
* It is provided "as is" without express or implied warranty
* of any kind and OATH AND ITS MEMBERS EXPRESSaLY DISCLAIMS
* ANY WARRANTY OR LIABILITY OF ANY KIND relating to 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 are used to calculate the
* One-Time Password (OTP) using
* JCE to provide the HMAC-SHA-1.
*
* @author Loren Hart
* @version 1.0
*/
public class OneTimePasswordAlgorithm {
private OneTimePasswordAlgorithm() {}
// These are used to calculate the 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 it detects any single
* mistyped digit and any single transposition of
* adjacent digits.
*
* @param num the number to calculate the checksum for
* @param digits number of significant places in the number
*
* @return the checksum of 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 JCE to provide the HMAC-SHA-1
* algorithm.
* HMAC computes a Hashed Message Authentication Code and
* in this case SHA1 is the hash algorithm used.
*
* @param keyBytes the bytes to use for the HMAC-SHA-1 key
* @param text the message or text to be authenticated.
*
* @throws NoSuchAlgorithmException if no provider makes
* either HmacSHA1 or HMAC-SHA-1
* digest algorithms available.
* @throws InvalidKeyException
* The secret provided was not a valid HMAC-SHA-1 key.
*
*/
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-SHA-1");
}
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
* set of parameters.
*
* @param secret the shared secret
* @param movingFactor the counter, time, or other value that
* changes on a per use basis.
* @param codeDigits the number of digits in the OTP, not
* including the checksum, if any.
* @param addChecksum a flag that indicates if a checksum digit
* should be appended to the OTP.
* @param truncationOffset the offset into the MAC result to
* begin truncation. If this value is out of
* the range of 0 ... 15, then dynamic
* truncation will be used.
* Dynamic truncation is when the last 4
* bits of the last byte of the MAC are
* used to determine the start offset.
* @throws NoSuchAlgorithmException if no provider makes
* either HmacSHA1 or HMAC-SHA-1
* digest algorithms available.
* @throws InvalidKeyException
* The secret provided was not
* a valid HMAC-SHA-1 key.
*
* @return A numeric String in base 10 that includes
* {@link codeDigits} digits plus the optional checksum
* digit if requested.
*/
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 * 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 ASCII string
"12345678901234567890" for the secret:
Secret = 0x3132333435363738393031323334353637383930
Table 1 details for each count, the intermediate HMAC value.
Count Hexadecimal HMAC-SHA-1(secret, count)
0 cc93cf18508d94934c64b65d8ba7667fb7cde4b0
1 75a48a19d4cbe100644e8ac1397eea747a2d33ab
2 0bacb7fa082fef30782211938bc1c5e70416ff44
3 66c28227d03a2d5529262ff016a1e6ef76557ece
4 a904c900a64b35909874b33e61c5938a8e15ed1c
5 a37e783d7b7233c083d4f62926c7a25f238d0316
6 bc9cd28561042c83f219324d3c607256c03272ae
7 a4fb960c0bc06e1eabb804e5b397cdc4b45596fa
8 1b3c89f65e6c9e883012052823443f048b4332db
9 1637409809a679dc698207310c8c7fc07290d9e5
Table 2 details for each count the 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 HOTP
algorithm. These are not recommended extensions or part of the
standard algorithm, but merely variations that could be used for
customized implementations.
E.1. Number of Digits
A simple enhancement in terms of security would be to extract more
digits from the HMAC-SHA-1 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.
E.2. Alphanumeric 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.
E.3. Sequence of HOTP Values
As we suggested for the resynchronization to enter a short sequence
(say, 2 or 3) of HOTP values, we could generalize the concept to the
protocol, and add a parameter L that would define the length of the
HOTP sequence to enter.
Per default, the value L SHOULD be set to 1, but if security needs to
be increased, users might be asked (possibly for a short period of
time, or a specific operation) to enter L HOTP values.
This is another way, without increasing the HOTP length or using
alphanumeric values to tighten security.
Note: The system MAY also be programmed to request synchronization on
a regular basis (e.g., every night, twice a week, etc.) and to
achieve this purpose, ask for a sequence of L HOTP values.
E.4. A Counter-Based Resynchronization 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 used 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, which
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 -- 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.) in order to give a specific
time step. The time window for the One-Time Password is then equal
to the time step multiplied by the resynchronization parameter as
defined before. For example, if we take 64 seconds as the time step
and 7 for the resynchronization parameter, we obtain an 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.
Authors’ Addresses
David M’Raihi (primary contact for sending comments and questions)
VeriSign, Inc.