Rivest evaluation of SecurID smart card

[nobody@eli-remailer]

-----BEGIN PGP SIGNED MESSAGE-----

I thought this might be of some interest to the CypherPunks list.

DEADBEAT <na5877@anon.penet.fi>

- - - - - - - - - 

TO:	Kenneth P. Weiss, Chairman
	Security Dynamics, Inc.
	2067 Massachusetts Avenue
	Cambridge, Massachusetts  02140 
FROM:	Ronald L. Rivest /initials RLR/
DATE:	April 7, 1987
RE:	Evaluation of SecurID Approach to User Identification

This memo provides a brief overall evaluation of your SecurID product,
as you have requested, suitable for limited distribution.  (It does not
contain any of the proprietary information you have disclosed to me.)

			General Approach

The SecurID card generates a pseudorandom sequence of displayed
numbers:  the displayed number us changed every 60 seconds.  The
sequence is "pseudorandom" rather than truly "random" in the sense that
it is generated by applying a (proprietary) algorithm and secret key to
a representation of the current time.  Thus, a host computer knowing
the algorithm and the secret key in the card can compute the number
displayed on the user's card at any moment.

Clearly, the numbers produced by such a card can be used in place of a
conventional "PIN" or "password" for access control or user
authentication, if the host is prepared to compute the number currently
displayed on the user's card.  That is, the user could enter the
displayed number instead of a remembered PIN or password when he is
asked to authenticate himself when initiating a login or financial
transaction.

One can obtain additional security by first combining a user-remembered
PIN with the displayed number, so that the user is authenticated both
by "what he knows" as well as "what he possesses".  For example, if
both the displayed number and the user's PIN are decimal numbers, the
combining operation could be "add digit-by-digit without carry".  The
host computer, knowing both the user's PIN and the displayed number,
can compute the correct value for comparison.

			Security Evaluation

1. An End-to-End Approach

One major advantage of your approach is that it is an "end-to-end"
technique: no intermediate nodes in the communication network are
entrusted with any security responsibilities.  The only places where
secret information needs to be maintained and manipulated are the
user's card and his host computer.

By contrast, an approach which encrypts PINs and transmits them in
encrypted form to the user's host computer may -- in a large, diverse,
multiorganization network -- require tremendous complexity in terms of
key management overhead and will necessitate a great deal of trust
between the participating organizations.

In my consulting work I have seen large organizations work very hard to
design "end-to-end" authentication protocols because of their
intrinsically greater security and simplicity.

2. Pseudo-random number generation

As noted above, your card generates a pseudo-random sequence of numbers
by applying a proprietary algorithm to a secret key and the current
time (measured to the minute).  The secret key is known only by the
user's card and host computer.

The system could be compromised if an "enemy" could predict future
numbers to be displayed by the card, from past observed values.  (These
numbers are transmitted in the clear, and are not encrypted.  This
makes your approach valuable for logging in from a "dumb" terminal, but
makes it possible for a wiretapper to obtain a set of previously values
produced by the card.)

However, I do not believe this attack can be successfully mounted
against your system.   I have tried to "break" your system in this
manner, without success.  The proprietary algorithm (which you have
disclosed to me) is based on sound cryptographic principles; it is
likely that the best approach to "breaking" this system is a
brute-force search for the secret key.  Since the secret key you use is
longer than that used by DES, I believe that this approach is
infeasible in practice.

(I should note that while my examination of your algorithm was
intensive and covered all aspects of the algorithm, it was of necessity
an examination of limited duration.  Some of your customers, such as
those involved with matters of national security, will certainly want
to see your algorithm subjected to additional intensive scutiny [sic]
before adopting it for use.)

Thus, I believe the sequence of numbers produced by your card will be
unpredictable by an "enemy", even if he sees previously produced
numbers.  Therefore:

   o    The ability to produce the number that is correct for the
	current time is a sound guarantee that the person logging in
	actually posesses [sic] the correct SecurID card.

   o    The numbers produced do not need to be encrypted, since
	knowledge of past values will not allow an enemy to predict
	future values.

Of course, other cryptographic algorithms could be used to produce the
pseudo-random number sequence from the secret key and the current
time.  For example, one could use DES.  (Given recent events, the
algorithms should perhaps be called "ODES" for the _Old_ Data
Encryption Standard".)  However, given the shorter key length and
greater implementation cost of DES, I don't see any advantage here
other than that it is (or was) a standard that withstood at one time a
careful review.  (This, however, may be significant to some of your
customers.) It is also perhaps worth noting that your algorithm, while
easier to implement than DES, is more computation-intensive than DES,
making a brute-force search substantially more difficult to mount.

3. Combining operations

Additional security can be obtained by combining the displayed number
with a user-remembered PIN, say by adding them digit-wise with carries
omitted.

While this combining operation is very simple, it is easy to prove that
if the displayed number sequence is unpredictable, then adding a PIN to
the sequence won't change this fact.

Furthermore, the PIN itself is protected from disclosure, unless the
"enemy" can obtain both the current displayed value and the value after
the PIN has been added.  However, to obtain the first requires access
to the card, and to obtain the second requires wiretapping; these are
not likely to be simultaneously available.  (The risk here seems less
than the risk that the keyboard is tapped in a conventional password
scheme.)  A similar analysis applies to using the displayed number
sequence to "encrypt" values other that the PIN; this operation should
provide the desired security.

			Summary

The approach used in your SecurID product is novel, and offers security
advantages over conventional PIN or password schemes.  The
cryptographic algorithm employed should provide a high degree of
security.




Dr. Ronald L. Rivest is a Professor in the Electrical Engineering and
Computer Science Department of the Massachusetts Institute of
Technology.  He is a renowned world class cryptologist.

Professor Rivest is one of the co-inventors of the RSA public-key
cryptosystem, is a founder of RSA Data Security, Inc., and is on the
Board of the International Association for Cryptologic Research.

-----BEGIN PGP SIGNATURE-----
Version: 2.2

iQBFAgUBLAPfX/FZTpBW/B35AQFSFAF/T+Bcc2a7PWGeyn1UN0rGcWj65u+1vdyv
O8Vh5sjyr1J5ELZ99fwEuO29OmQJvwCD
=QVMm
-----END PGP SIGNATURE-----