TRI-D Systems :: Documentation :: Whitepapers

This document describes the probabilities behind passcode guessing attacks, in order to help the reader safely deploy One-Time Password tokens. It will be shown that for some types of tokens the safe limits are suprisingly low, and are highly sensitive to system configuration. For example, we show a worst-case scenario (but taken from a sizable real deployment) where One-Time Passwords can support only 160 users if the system is to withstand a one week attack.

The reader should have at least a basic understanding of cryptography (e.g. properties of a cipher vs. a hash) and should be familiar with the TRI-D software architecture.

Background

One-Time Password (OTP) tokens, in general, work by taking some challenge value, applying encryption or a keyed hash, and transforming the result into a response value. The response is used as the OTP. All tokens available today have a synchronous mode where the challenge is generated programmatically and need not be entered into the token by the user.

Event-based tokens, generate this synchronous challenge with an event counter. Each time the token is used, the event counter "increments" (which is generally not a simple +1 addition). The token and the authentication server start at the same initial state and increment in tandem. However, the server does not know when the user operates the token. It only knows when the user actually tries to authenticate. The user may play with the token, or mistype a passcode, or otherwise "burn" a passcode, causing the token and the server to get out of sync. This is one of several well known weaknesses of event-based tokens.

To compensate for this weakness, TRI-D's One-Time Password daemon (otpd) has the ewindow option. This option sets the event lookahead window, or the number of events the token can be ahead of the server. It is also the number of valid passcodes that will be accepted and, therefore, cannot be set arbitrarily high or else the odds of guessing a passcode become too large. For a 7-digit decimal response, there is generally a 1/10,000,000 chance of guessing the current passcode correctly. If ewindow is set to 99 (100 valid passcodes), this drops to only 1/100,000.

Because 1 out of even 10,000,000 numeric passcodes (ewindow=0) is trivially guessable by an automated attack, the softfail option is available to limit the number of failed login attempts. It sets the number of failed login attempts before authentication delays are enforced. After softfail consecutive failed authentications, a 1 "minute" (64 seconds) delay is imposed during which time all authentication attempts fail. The delay doubles for each subsequent failure, up to a cap of 32 "minutes".

The purpose of the delay is to limit the rate of passcode guesses so that an automated attack against a single user cannot be done quickly enough to be feasible. At the same time, the actual user must be able to login at some point, so the delay is just a temporary lockout.

If not for the softfail option, it would be essential to "permanently" (requiring administrator intervention) lockout any user who has too many failed authentication attempts, given the ease of automated passcode guessing. Thus, the softfail option prevents the trivial attack of arbitrarily locking out any given user (which might then open up a social engineering attack), while still offering resistance against the passcode guessing attack.

Normally, the softfail limit is reached due to user error, not because of an attack. So, what happens is that after softfail failed authentication attempts, the user is too far ahead in the event window to ever login correctly (they've operated the token enough times to be out of ewindow range and/or they are attempting to authenticate too frequently and are stuck in the delay period). To reduce the need to set ewindow or softfail to a high value (because they significantly impact vulnerability to a guessing attack), the rwindow option allows extension of the event window without a corresponding increase in exposure to the guessing attack by requiring two consecutive correct passcodes to escape the softfail-imposed delay. For a 7-digit decimal response, there is generally a 1/10¹⁴ chance of guessing two consecutive passcodes correctly. Even if a million guesses could be made per second, it would take about 115 days to guess a passcode pair.

Time-based tokens, such as those sold by TRI-D and RSA, generate the synchronous challenge with an internal clock. Because of clock drift and the delay from generating a passcode to entering the passcode into the computer, otpd allows a window of passcodes to be accepted for this type of token, however the range of allowable clock drift is automatically determined by otpd, i.e. there is no configuration option to control this.

Passcode Weaknesses

We were very careful to use the word "generally" above whenever discussing the likelihood of guessing a passcode. That's because, for the sake of simplicity, we assumed that both guessed and passcode digits were evenly distributed from 0-9. However, this is not always the case.

For example, some ANSI X9.9 tokens take the X9.9 MAC hex output and convert it to decimal by compressing or folding the hex values A-F to decimal 0-5. This makes 0-5 twice as likely to appear as passcode digits than 6-9 (2/16 vs. 1/16).

If we guessed random digits 0-9, the probability of guessing a passcode digit is, as before, 1 in 10:

$\sum_{i=0}^5 P(guessing\ i) \cdot P(i\ is\ correct) + \sum_{i=6}^9 P(guessing\ i) \cdot P(i\ is\ correct)$
$\sum_{i=0}^5 \frac{1}{10} \cdot \frac{2}{16} + \sum_{i=6}^9 \frac{1}{10} \cdot \frac{1}{16}$
$= \frac{1}{10}$

If, however, we take into account the increased frequency of digits 0-5 and so only guess those digits, we increase our chances to 1 in 8:

$\sum_{i=0}^5 P(guessing\ i) \cdot P(i\ is\ correct) + \sum_{i=6}^9 P(guessing\ i) \cdot P(i\ is\ correct)$
$\sum_{i=0}^5 \frac{1}{6} \cdot \frac{2}{16}$
$= \frac{1}{8}$

NOTE: This assumes that there is an equal chance of generating any given hex passcode (before decimal conversion), which may not be true.

For the first response, generated from a constant initial event counter, there are only 2⁵⁶ out of 2⁶⁴ possible hex passcodes since DES has a 56-bit key (including weak and semi-weak keys). We can determine the frequency of each digit for the first response if we know the initial event counter value. This isn't worthwhile since the skew is limited to 2⁸/10⁸, an insignificant factor.

For subsequent responses, some tokens derive the next challenge value from the previous one in a lossy way instead of using an independent event counter. This might cause the passcode sequence to become a cycle after an initial linear run and alter the frequency distribution. Determining whether or not this is the case is a fairly compute and data intensive analysis, so we discount this possibility for now.

The good news is that while a 1 in 8⁷, or 1 in about 2 million, chance of guessing a 7 digit passcode, is a severe blow compared to the best case 1 in 10 million chance, it is still not very good odds for an attacker. Or is it?

Attack Analysis

Let's assume a threat model where an attacker is not targeting a specific user, but would just like to authenticate as any valid user. Usernames are generally easily guessable/verifiable, at least we consider them so in our threat model (e.g. polling SMTP servers for valid email addresses, as spammers do, is one easy way to get a list of usernames).

The number of guesses we have to make in order to have a 50% shot of guessing correctly is about 1.45 million:

$\frac{1}{2}$	$= 1 - (1 - P(guessing\ a\ passcode))^n$
$\frac{1}{2}$	$= 1 - (1 - 8^{-7})^n$
$(1 - 8^{-7})^n$	$= 1 - \frac{1}{2}$
$n \ln(1 - 8^{-7})$	$= \ln(\frac{1}{2})$
	$= \frac{\ln(\frac{1}{2})}{\ln(1 - 8^{-7})}$
	$\approx 1,453,635$

Turning this around, if we had ~1.45 million users and could guess one passcode per user, we'd have a 50% chance of success. So the maximum number of users that can be safely supported if we are only allowed to make one guess per user, is ~1.45 million.

Of course, an attacker can make more than one guess per user. Once enough incorrect guesses have been made to put the user into the maximum softfail delay period (2048s), the maximum number of guesses per user per day is ~42.

So with an ewindow value of 0, which allows one correct passcode per user, this gives a maximum of about 34,500 (1,453,635/42) users that can be safely supported, resisting a single day's worth of a guessing attack. With a more useful minimal ewindow value of 5 (six correct passcodes per user), we can support a maximum of about 5,700 (1,453,635/(42*6)) users, again to resist a single day of an attack. If we increase our resistance to one week's worth of an attack, this drops to 820 users.

Here is a chart comparing the number of users that can be supported for different strengths of passcodes, with ewindow=5:

type of passcode	max users (1 day)	max users (1 week)
7 digit 0-5 biased decimal	5,743	820
7 digit non-biased decimal	27,384	3,912
7 digit hex	735,130	105,108

If we increase ewindow to 30, a value taken from an actual implementation (set based on user experience issues), the maximum size of the userbase is much lower (by a factor of 31/6):

type of passcode	max users (1 day)	max users (1 week)
7 digit 0-5 biased decimal	1,111	159
7 digit non-biased decimal	5,300	757
7 digit hex	142,283	20,326

As mentioned in the Background section, in addition to ewindow, otpd has an rwindow option, which likewise sets the lookahead window, but requires two consecutive correct passcodes to authenticate. The rwindow is activated when the user is in the softfail delay period.

Even for the weaker 0-5 biased decimal passcode, the increased difficulty of having to guess a passcode pair makes it seemingly impossible to attack, however, the lack of any rate limiting must be taken into account.

Let's consider an example with rwindow set to 30. This extends the lookahead window to 30 events, but requires two consecutive correct passcodes, making the single-attempt odds of guessing correctly 30 in 8¹⁴. rwindow guesses are not rate-limited by a delay, so whether or not this is more resistant to attack depends on if enough guesses can be made in a day to overcome the 8⁷ increase in single-guess difficulty (or 10⁷ or 16⁷ increase for non-biased decimal and hex passcodes, respectively). For 0-5 biased decimal passcodes, with rwindow=30 it would require more than 100 billion guesses to correctly guess two consecutive passcodes, compared to the 1.45 million to guess just one passcode, or ~1.18 million guesses per second. The math is left as an exercise to the reader.

The exponential increase in difficulty of the rwindow attack depends on the attacker receiving no feedback on whether the first guess (of the two consecutive passcodes) is correct. Some authentication server plugins support informing the user that a passcode entry was correct but that the next passcode is also required, to give better feedback to the user. If this option is set, the increase in difficulty is only doubled (vs. squared), with a successful attack requiring ~390,000 guesses per second. Again, we leave the math as an exercise.

Configuration Reference Card

The reader not interested in otpd configuration guidelines can safely skip this section.

U	= number of users
D	= number of days of attack resistance
P	= probability target (0.5 nominal)
C	= chance of guessing a passcode (e.g. 8^-7, 10^-7, or 16^-7)
E	= `ewindow` value
R	= `rwindow` value
r	= daily guess rate

The equations for E and R indicate the maximum safe value, not the recommended value. Both E and R should be set only to the value that works in a given environment, not the maximum safe value. These equations are only useful to verify that a given configuration is within safety limits.

Tuning

As detailed in this paper, the main problem introduced by a passcode guessing attack across the entire userbase is the number of users that a given combination of ewindow, passcode length, and passcode strength can support.

The typical problem faced by an enterprise is a growing number of users that need to be supported. How can this be done?

Changing ewindow has only an inverse proportional effect on the number of users that can be supported. This is beneficial in that ewindow can be increased (as needed to improve the user experience) with only a proportional decrease in the number of supportable users, but detrimental in that lowering it does not drastically increase the number of supportable users. Not that this is a problem, because lowering ewindow is typically not an option. When ewindow is increased beyond an initial minimum value (5 is recommended), it is because as the userbase grows, there are more users that have difficulty, necessitating the increase. Reducing usefulness or ease of use in the name of security is rarely an acceptable solution. It is unfortunate that the reason ewindow has to be increased—a larger userbase—is the contraindication for increasing it.

Changing passcode strength has an exponential effect. Simply removing the 0-5 bias in the passcode, decreasing the chance of guessing a digit from 8^-7 to 10^-7, quadruples the number of users that can be supported. By just doubling the range of passcode digits from 8 to 16, we introduce a 128-fold increase in the number of supportable users. While this is highly effective, unfortunately, like reducing ewindow, changing from decimal to hex passcodes will probably be received poorly. Needless to say, the 0-5 bias inherent in some tokens' decimal mode severely and artificially limits their utility.

Changing passcode length also has an exponential effect. For instance, for ewindow=5, 820 users can be supported at one week of attack resistance (see chart above) with 7 digit 0-5 biased passcodes. By adding just one passcode digit, 6,500 users can be supported. Unfortunately, going to 8 digits is fairly cumbersome for users, as token displays are not well designed and don't break the digits up into groups; reading and entering 8 digits is prone to error. (With a 7 digit passcode, a gap or a dash can be used in the 4th position.)

As those are the only three variables we have to work with (let's assume a hiring freeze or a layoff is not a good solution), and we've presented realistic reasons against changing them, it would seem that we are stuck.

But there is an easy way to increase the passcode length—use the soft PIN feature of otpd. Not only does this increase the passcode length but, because the PIN can be alphanumeric and symbolic, it vastly increases the strength as well. One of the reasons to deploy OTP is to render a password compromise useless, so it must be noted that if a soft PIN is compromised, this does not affect the chances of mounting a successful attack; since the PIN is user-specific it doesn't reduce the chances of guessing across the entire userbase. In fact, it doesn't impact the chances of guessing even the single compromised user's passcode, since single user guesses are essentially impossible even with the weaker 0-5 biased decimal passcodes.

Even with only a numeric PIN, at ewindow=5 an 11 digit (5 PIN + 6 OTP) non-biased decimal passcode (as recommended for use with TRI-D access cards) can resist a week's attack for almost 40 million users or, to scale it down below very-large-government sized installations, can resist five years of an attack for 150,000 users. This makes the one week of resistance for only 820 users, as seen in our worst case (but real-life) example, seem pitiful in comparison.

Unfortunately, if event-based tokens are deployed, it is generally difficult or inconvenient to add a soft PIN. Event-based tokens generally require PIN entry into the token itself to prevent accidental passcode generation. Imposing a soft PIN requirement on users, in addition to the hard PIN, would probably result in unacceptable usability of the token. The best solution is to replace the token with a time-based one. Interestingly, even with a much longer passcode (11 digits vs. 7 digits), the soft PIN has higher user acceptance since fewer digits actually come from the token.

Conclusion

In addition to describing a powerful OTP attack and countermeasures for it, this paper also demonstrates the importance of fully understanding the implementation of any security hardware or software in use or under evaluation, and not just trusting the vendor to get it right. Black box security is not security at all.

This is especially important for the authentication infrastructure. The one component, identity, that provides assurance to the rest of the infrastructure should not itself have to be blindly trusted.

TRI-D provides better security, supports more users and has superior user acceptance than any other product on the market.

Please contact sales@tri-dsystems.com for more information on any aspect of TRI-D hardware or software.