[1084] in cryptography@c2.net mail archive
Re: Thoughts on the next target.
daemon@ATHENA.MIT.EDU (Vin McLellan)
Tue Jun 24 22:10:46 1997
Date: Tue, 24 Jun 1997 21:26:09 -0500
To: cryptography@c2.net
From: Vin McLellan <vin@shore.net>
Cc: coderpunks@toad.com
Marcus Leech <mleech@nortel.ca> suggested:
>| Brute-forcing the SecurID hash algorithm, for example would require
>| that someone violate their license agreement with Security Dynamics/RSA.
>| "Algorithm Thieves today showed that SecurID cards aren't as secure
>| as manufacture claims".
Adam Shostack <adam@homeport.org> responded:
> If you mean the card hash, its not easy to go backwards
>from the output of the card to its seed with a small number of
>tokencodes. The output of the hash is substantially truncated. The
>card hash has (I think) a 64 bit output, of which you get 4-8 decimal
>digits (14-30 bits).
I think it's a 64-bit output too. But (although I wrote the
SecurID FAQ for SDTI) I don't _know_ that for a fact either;-)
> Going backwards from a set of tokencodes would be a cute
>trick, seeing as you need to find when the cards clock thinks it is,
>which may not closely relate to the real time. (Ace/Server stores
>clock drift info on a per card basis, and will actually accept a
>tokencode that is up to 10 minutes off in either direction, which gives
>you an idea of the accuracy of the card clocks. In fairness to SDI,
>the cards may well go unused for a couple of months.)
Well... yes and no.
In an ACE/SecurID system, the authentication server will only
immediately authenticate a call which comes in with the proper PIN and one
of only _three_ possible SecurID token-codes (what the server, with its
record of that token's drift, calculates and expects to receive; plus the
token-code for the 60 seconds prior, and the token-code for the subsequent
60 second slot.)
If that fails, the ACE/Server drops into a surety mode which --
while it will _never_ provides direct access or authentication -- will
attempt to match the token-code on the incoming authentication call against
a variable field (adding, by default, only _one_ 60-sec. tokencode on each
side of the initial field of three) in order to qualify this user for a
"second chance" -- and a demand from the Server to immediately provide a
second PRN from his SecurID. (As Adam noted, this is a feature designed to
deal with "drift" in either the Server's clock or the token's clock-chip,
and to minimize "false negatives"... but it's considerably more cautious in
praxis than he implied.)
Beyond the initial extension of the search window (as the
ACE/Server drops the account into what ACE-mavens like Adam call "Next PRN"
mode) the search window is further extended according to a simple formula
which adds _one_ additional minute/PRN to each side of the core 3-PRN field
for each week that this particular SecurID has been unused. This extended
search field is never extended by more than ten minutes to either side of
the PRN initially pre-calculated for that SecurID -- and that field can be
further truncated by the ACE administrator.
Because the ACE/Server stores a record of each token's historic
pattern of drift (relative to a presumed exactitude in the Server's clock,)
it's initial projection of what that SecurID will use for Current Time
(hashed with the token-specific secret key to generate the PRN token-code)
is surprisingly accurate. And, again, the search for a match against the
broadest-possible window (21 minutes/PRNs) is never to validate a user's
ID, but only to pre-qualify him or her before the Server demands a second
PRN token-code (which the Server will compare against a now-repositioned
field of three PRNs for an absolute yea or nay on the authentication.)
(Actually, SDTI warranties that each SecurID token will never --
over a three-year lifespan -- drift more than 10 minutes off GMT. Free
replacement; no questions asked!) Ok, so much for the functional security
issues.
For a brute force attack on a SecurID's seed or secret key --
presuming the attacker has somehow obtained the proprietary SecurID hash
and a record of output -- the attack can thus presume, with fair odds, that
the Current Time used as input in the hash is within that 21 minute window.
Adam calculated:
>
> In conjunction with the time (to the minute), you need to find
>the cards seed, which I think is also 64 bits.
>
> Time is calculated as (time(0)+N+1000000)/60
>
> N was a three every time I looked at it, but unlike the
>million, was stored as data, not a constant.
>
> So, you need to search some number of time possibilities
>(about 2^20 for a year, 2^11 for a day?) on top of 2^64 seeds.
The 21 minute window is arguably a more managable solution-space
than a day's worth of SecurID PRNs, certainly more feasible than a year's
worth!
Even then, however -- given a sequence of token-codes and a
corresponding Current Time, and rounding off a little for conceptual
clarity -- I figure a brute force attack on a token's seed requires an
average search of half of
21 (possible Current-Time(s) * 2 ^ 64 (possible seeds)
Let's conservatively ballpark that at about 10^20 calculations.
Adam suggested:
>On the
>bright side, the card hash runs on an 8 bit processor, and would
>probably be way efficient on a pentium.
I understand a moderately-optimized Pentium implementation of the
SecurID hash can do1K calculations-per-second. Even assuming Peter Trei or
some other optimizing wiz could improve that by an order of magnitude, a
solution-space of that magnitude remains a challenge.
If an attacker can calculate 10^4 codes per second (3 * 10^11 codes
per year,) brute-forcing a single SecurID seed should take somewhere about
300,000,000 years on a single Pentium... or 1 year on 300,000,000 Pentiums
(depending on your budget and sense of humor;-)
Granted, Moore's Law makes what seems inconceivable today feasible
in a decade. SDTI announced last year that -- with an eye to Moore's Law
-- the next generation of SecurID tokens, whenever they appear, will use a
longer seed, as well as a published hash. (SDTI also promised to publish
its new ACE protocol -- RSA-based, and due to market this year -- which
will replace its seven year-old proprietary ACE client/server protocol,
and allow for both open review and extended functionality.
Frank Willoughby <frankw@in.net> is, of course, correct to note
that any session over TCP/IP (with or without initial user authentication)
can be hijacked unless it is protected by encryption or some continuous
message authentication. (That's why so many sites now use OTPs over SSH.)
Mr. Willoughby is incorrect, however, in suggesting that the strength of
the SecurID hash is irrelevant just because session hijacking is possible.
Without going into who, where, might run OTP authentication without
crypto, let me just point out that an attack able to retrieve a SecurID
seed would allow a bad guy to whip up his own PRN generator and masquerade
as the valid user at will. As Frank explained, session hijacking generally
requires that the attacker flood or blow off the valid user's machine, in
order to steal a current _ongoing_ session. A reversible hash is a threat
of a different dimension.
Suerte,
_Vin
Vin McLellan + The Privacy Guild + <vin@shore.net>
53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
-- <@><@> --
