Abstract or Summary:
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 in 1977 and which has being recently adopted as a standard by NIST.

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 accounts(s).

Conceptually, the password space can be thought of as a large bucket, of size K from which users pick passwords. It is also tru that one can arbitrarily partition this bucket into several smaller buckets, perhaps of different sizes. Consider a small bucket of size b. It might be natural to assume that exactly K/b 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.