[3958] in Kerberos
New Attack on Some Random Pron. Pass. Generators
daemon@ATHENA.MIT.EDU (Ganesan)
Thu Sep 29 19:21:14 1994
From: bf4grjc@socrates.MIT.EDU (Ganesan)
To: risks@csl.sri.com, tc11-i@hearn.nic.surfnet.nl, ifip113@itd.nrl.navy.mil,
ifip-nm@BBN.COM, kerberos@MIT.EDU
Date: Thu, 29 Sep 1994 19:01:35 -0500 (EDT)
Cc: bbh7rqj@if000353.bell-atl.com (CHRISTOPHER I. DAVIES),
bkd879a@bafco.bell-atl.com (RICHARD W. AUSTIN),
bfqapxt@bafco.bell-atl.com (RAYMOND H. PYLE),
bfba2h1@bafco.bell-atl.com (LUANNE MILLER)
Reply-To: bf4grjc@bell-atl.com
A paper: A New Attack on Random Pronounceable Password Generators, Ravi
Ganesan & Chris Davies, will appear at the National Computer Security
Conference in October. The paper describes a new attack on random
pronouncable password generators. If you use such a generator you
might want to read on....
We have developed a new attack on random pronouncable password
generators including for e.g. the generator incorporated in the
Kerberos V5 code (Sandia version), and the recently announced NIST
standard for randomly pronuncable passwords.
Our attack will NOT allow the attacker to gain any advantage when
trying to compromise a PARTICULAR account (say on a UNIX /etc/passwd
file with 100 users), but an attacker who will settle for compromising
any, say 5, out of 100 accounts, will be successful. As an example, in
a 100 user UNIX system which uses the generator SANDIA distributed,
the total password space is about 14.5 billion passwords but the
attacker can, with very high probability, guess one user's password
correctly after searching through 3.5 million passwords.
The impact of the attack can range from devastating (e.g. you may have
been much better of letting user's pick their own passowrds) to
negligible. For instance if your 'salting constant' is VERY HIGH
than, then even the small sub-space which the attacker knows contains
a user password may get expanded greatly. So for regular UNIX in the
above example, the attacker will have to search 4096 * 3.5 million
passwords which you might be willing to live with. [Do note that your
security parameter is now 4096*3.5million, and not as you might have
hoped, 4096*14.5 BILLION].
Discussions with Sandia suggest that because of the salting and the
fact that they operate behind a 'secure fence' this attack does not
impact them. NIST is aware of the weakness in its standard and will
work on fixing the standard.
How to fix:
- As a quick fix we would recommend moving to a random password
generator (i.e. NOT pronouncable).
- We will be soon making available a random pronoouncable generator
that is engineered to be less vulnerable to the above attack
(the software should be available freely to any Govt.(military, etc.)
or educational institution). To be added to a distribution list for
this software please send e-mail to Luanne.Miller@Bell-Atl.Com
- Switch to using a proactive password checker.
More info can be got by:
- Retreiving the postscript (attack.ps) file via anonymous
ftp from pub/ganesan at ftp.cs.jhu.edu. A HTML document will soon
be available at Bell Atlantic's web server.
- Get the paper from the NCSC proceedings (conference starts
OCt 12)
- Send me e-mail at Ravi.Ganesan@Bell-Atl.Com
An abstract of the paper is enclosed below my signature.
Thanks,
Ravi
************************************************************
Ravi Ganesan
Senior Manager
Center of Excellence for Electronic Commerce, Bell Atlantic
e-mail: Ravi.Ganesan@Bell-Atl.Com
v-mail: (301) 236-7583
Fax: (301) 236-8569
************************************************************
A New Attack on Random Pronounceable Password Generators
Ravi Ganesan & Chris Davies
Bell Atlantic
Silver Spring, Maryland 20904
ABSTRACT
Given the choice, most users pick poor passwords that are vulnerable
to attack. Using random machine generated passwords can ensure that
`good' passwords are chosen, but are user-unfriendly. Machine
generated passwords which are `pronounceable' represent a potential
compromise between security considerations and user friendliness.
Several such generators have been designed, perhaps the most prominent
being the scheme developed by Morrie Gasser [5] in 1977 and which has
being recently adopted as a standard by NIST [3].
The security of such generators is typically characterized by the
overall size of the password space, which is typically a fairly large
number. This is a fairly good security parameter, if the objective of
the attacker is to try and compromise a particular account. On the
other hand, if an attacker achieves her objective by compromising any
account(s) on the system, then the overall size of the password space,
in itself, provides an insufficient characterization of the level of
security. In fact, as we show in this work, the size of the password
space of the pronounceable password generators we examined are fairly
huge, yet all suffer from a serious weakness, which allows the
attacker to compromise accounts on the system with significantly less
effort than the size of the password space would suggest. The attacker
cannot choose which accounts to compromise, but in many realistic
situations, an attacker's objectives can be met by compromising any
account(s).
Conceptually, the password space can be thought of as a large bucket,
of size , from which users pick passwords. It is also true that one
can arbitrarily partition this bucket into several smaller buckets,
perhaps of different sizes. Consider a small bucket of size . It might
be natural to assume that exactly of the users would pick passwords
from this bucket. Unfortunately, in the pronounceable password
generators we examine in this work, it so happens that a
disproportionately large number of users pick passwords from
reasonably small buckets. For instance, in the NIST standard, one such
bucket contains only 0.22% of all passwords but it can be expected
that about 5% of all users pick passwords from this bucket. The
bottomline is that while the NIST standard claims a password space
size of "5.7 billion" for 8 character passwords, an attacker who
wishes to compromise any 5 user accounts on a multiuser system with a
100 users, need only search through less than 18 million passwords.
The impact of the attack depends on the particular implementation and
on factors such as `salting'. Nevertheless, the generators we examined
are so acutely vulnerable to our new attack, that we do not recommend
that they be used.
