Preventing reuse of passwords

Passwords are traditionally chosen by users themselves.  This presents a challenge for security engineers, since regardless of the minimum password length enforced, creative users might still choose cryptographically weak passwords that break security design assumptions.  Best-practices such as password hashing and hash salting are industrially well known but frequently ignored by software developers.  Password reuse further threatens security, either by giving attackers a greater opportunity to break in using old passwords that are more vulnerable to brute-force attack, or by enabling attackers to break in to a high-value computer system using password data stolen from a less secure system.

Preventing the reuse of historical passwords may be accomplished within a closed system by maintaining a history of password hashes (to prevent the user from choosing a password that would result in a similar hash to one generated previously); however, where systems are designed to prevent even their administrators from knowing users’ passwords, it’s hard to gauge directly how frequently identical passwords have been used across software systems run by different organisations.

Researchers have studied the prevalence of password reuse and the impact of this practice on system security.

Here I present a method of strongly discouraging password reuse across systems:

  1. Statistically evaluate the strength of new passwords: when users change their password, check the strength of the new password by using information theory to evaluate its unpredictability.
  2. If password strength is poor, or if the password hash is identical to a previous hash for a password used by the same user, prompt the user to try again Otherwise, amend the password and record the hash in a table of historical password hashes (I call this “hash caching”.)
  3. Enforce password validity periods  Ln for a user’s nth password where
    Ln = p × an;  Ln < LMAX;  where

    • p is a proportional constant period of time, e.g.
      20 days ≤ p ≤ 40 days
    • a controls the rate of increase in password validity period.
      1.4 ≤ a ≤ 2
    • LMAX is a hard cap on password validity periods, e.g.
      4p ≤ LMAX ≤ 16p
    • Values and limits for  a, p,  LMAX ∕ p  may vary according to administrative discretion and the strength of the selected password.  Where applicable, inform users that a longer, more convenient password validity period may apply if they strengthen their password.

    Graph showing password validity periods according to formulae described in this article, for a constant password strength score (example parameters: a=1.68, p=30)

System users will soon have comparatively unique and secure passwords; since each user’s favourite passwords will typically be exhausted during the initial six months of their user account, subsequent choices will be influenced by hard policies and soft ergonomics, and any new passwords reused on 3rd-party systems will eventually expire.

Can anyone devise an alternative way to prevent this folly?  Are there other vulnerabilities in this design?  How can I improve the design?  Comments are welcome.

10 thoughts on “Preventing reuse of passwords

  1. What I’ve seen in environments with a very strict password policy is post-it notes attached to either monitor or keyboard with the current password. This exposes the password to any colleague and visitor passing through.

    The limited memory capacity and the hurdle of learning a new password every 2^n weeks is a problem from a user perspective and I don’t see anything in your method addressing this.

  2. True—people often take the “path of least resistance”.  Your point deserves a broader treatment which you will find in Professor Ross Anderson's book, “Security Engineering”.  The section on passwords (section 2.4) is available as a free sample.  Professor Anderson makes a similar point, that monthly enforcement of password updates is too frequent and inconvenient in practice.  So let’s require updates every 40 days × 1.8^n (article edited accordingly.)

    Post-it notes are most often used when passwords are chosen by a third party; such as where multiple users have the same password (e.g. for a network resource) or where passwords are randomly generated.  Neither of those scenarios applies to the case of personal passwords chosen by the user.  In contrast with a short and constant validity period, an exponentially relaxing regime should be “very strict” for just enough time to flush out the users' favourite passwords.

    Perhaps some real usability testing is necessary to prove or dismiss this idea—we may need a field trial to calibrate my formula and measure real-world policy compliance and password strength.  Any volunteers?

  3. hash caching” (to prevent the reinstatement of old passwords) requires the cryptographic hashing salt to be constant for each user through successive password updates.  Where an attacker (such as a corrupt insider) has access to your database, and where other systems contain similar passwords to ones from your users' history; this policy might make it easier to obtain information for compromising those other systems through directed rainbow table attacks against individual high-value user accounts.  It is therefore especially important to select a strong hash function and salting technique and to require new passwords to be reasonably strong.

  4. Bonneau’s article at lightbluetouchpaper is about re-using passwords between different websites. Website passwords pretty well never have expiry times in the first place, because the users wouldn’t stand for it. If you tried this at a typical web business, you would probably go broke.

    This policy also doesn’t stop me reusing my password between different sites anyway. My “favourite” password is “cat”, and you make me change it to “dog.” OK, so I change it to “dog” everywhere, on all the sites I use!

    But let’s consider it for operating system logins. How does it do there?

    Well, apart from gradually relaxing the password non-reuse period, this system is not too dissimilar to some of the optional parameters in Windows NT based security (Win 2K, etc. are the same.)

    You can set it to memorise the last n password hashes, and forbid reuse of any password still on the list. You can also set a minimum period before the next reset, as well as the more usual maximum.

    The purpose of the minimum period is said to be “to stop users quickly cycling through n passwords to get back to an old favourite.” As an accidental benefit, it might make it harder for a user to synchronise the same new password across multiple hosts. However, that’s rarely a policy goal in system security; actually the current preference is the exact opposite, SSO!

    In any case, this bizarre policy creates far more severe security problems than the “movie plot” threat that it seeks to solve, and is best avoided.

    Well, forget about minimum change periods; otherwise, how does NT’s no-reuse policy work in practice? Back in my dark journeyman days when I administered some NT boxes, I discovered (by being told to my face) that users with a “favourite password” simply appended a counter at each forced change: Mary1, Mary2, Mary3, and so.

    With some pretty severe re-writing of the password hasher, you could defeat that by keeping “old_passwd” in memory and doing a similarity match to “new_passwd.” However I suspect the wily user might hit back with: Mary1, Anne2, Mary3, Anne4, …. There is no way to defeat this that does not expose the password to much more serious security risks!!

    I think the only real solution is to:
    1. Educate the user about the dangers of reusing high security passwords on low security web sites; AND
    2. Provide the tools to make password diversification practical and painless (i.e., a password manager, such as Password Safe.)

  5. @Roger:————————

    Your general point about the inevitable perpetual arms-race between IT departments implementing clever password strength metrics to enforce the use of strong passwords, and system users looking for easy ways to generate and remember passwords, is correct.  Please allow me to correct a few misconceptions that you appear to harbour, and demonstrate why my method retains value in the context of your objections.

    Professor Ross Anderson explains why passwords are still used for access control in high-value systems with high security requirements.  For such systems, Professor Anderson appears to endorse the multi-factor authentication approach, in which passwords constitute one component (see Section 2.4, Paragraph 3 on Page 31 in Professor Anderson’s book, “Security Engineering”.)  If such systems must use passwords at all where users can choose their own passwords (e.g. based on a passphrase, an approach recommended in Section 2.4.4 of Professor Anderson's text), then we should try to make them more secure and calibrate system ergonomics to encourage users in the right direction.  The method I describe represents an incremental improvement upon the state-of-the-art by calibrating system ergonomics with smooth functions that transition gradually from an inevitably vulnerable starting state with fresh and tolerant but naive users to a comparatively secure steady state with weary but pretrained users.  The application of complementary personnel management principles, such as gradual promotion of users from low to high system access levels, will enhance the benefits of my approach.

    Website passwords pretty well never have expiry times in the first place, because the users wouldn’t stand for it.  If you tried this at a typical web business, you would probably go broke.”—Which is part of my point.  My method is exclusively intended for use in high security applications (where users, who gain something from maintaining their user account, can actually be threatened with losing privileges in the event of non-compliance).  Low security systems will rarely implement strict password management methods (which gives us a potentially strong way to exploit ergonomics and psychology so as to differentiate between high-value and low-value systems).  Any low-value systems attempting to implement such a strict regime would risk their own customer-base and existence; thus once again, reducing the window of opportunity for an attacker and reducing the chances that a weak third-party system will provide an entry point for an attacker into the stronger system.

    My new idea is only worthwhile if other well-known principles of password management are applied too.

    I reckon users typically have 1–5 high-value accounts, 2–15 medium-value accounts, and 5–100 low-value accounts.  Users will not bother to change passwords on twenty separate low-value accounts every 250 days to keep them synchronised with a high-value account that forces them to update their password that often.  Even if they do so at first, then the initial period of high-frequency password update demands will persuade them that’s a bad idea.

    Your notes on advanced Windows NT password management settings are interesting.  You rightly note the variable validity period as a potential difference between my scheme and the traditional Windows NT scheme.  This difference, i.e. the password validity period function that I describe, is the main point of my article, and this curve is designed to implement a smooth inverse relationship between the probability of a given user choosing a favourite password, and the length of time the bad guys have to use that common password as a point of entry.  Ergonomically, since the probability of a “favourite password” being used is inversely related to the difficulty of remembering that password, this means that the password validity period can be directly related to the inherent difficulty of remembering that password, so that users get proportionally longer to learn and remember a less predictable password and attackers get a proportionally smaller window of opportunity for using the more predictable passwords that are more likely to be common with low-value systems.

    As with any other component of password management policy (or access control mechanisms in general), my technique is not a panacea, and cannot work 100% of the time—it is merely designed to help reduce the probability of a significant breach of perimeter security.  Remember that this system is designed for the case where you cannot tell directly whether or not passwords have been reused.  It is a purely psychological, ergonomic method, designed to organically train system users into doing the right thing, by subtly changing the topology of the path of least resistance so that users who insist on taking that path (i.e. the majority) will gradually learn to do the right thing, or at least to do something that approximates the right thing.

    You can set it to memorise the last n password hashes, and forbid reuse of any password still on the list.”—My system is different.  The default implementation should remember ALL password history, so there’s no chance of a user merely cycling through a list of non-favourite passwords to flush the cache and reuse their favourite one again.  If the cache is ever flushed in your implementation (e.g. for application-specific security reasons, or to replace an obsolete hashing or salting method), then cached passwords might be flushed on the basis of age (according to date) with no consideration to the number of passwords used in the interim period.  With this implementation, you won’t need the bizarre (as you put it) and clumsy method of enforcing minimum password validity periods, and you won't see the side effects of that kludge.

    Professor Anderson’s book addresses the question of SSO (single sign-on) see Section of his book (link provided above).  SSO has its own drawbacks, as Professor Anderson explains.

    As noted in my article, one essential complementary component in a system such as that I describe, is a comparatively strong method of statistically evaluating the strength of new passwords.  I propose a method that incorporates the following techniques:

    • Evaluation of the randomness of the sequence of different types of character used within the password (this could be evaluated at various levels, where the different types of characters are considered as part of a hierarchy of types.)
    • Any groups of keyboard-contiguous keys in the password should reduce the strength score (doing this properly might require comparison with multiple keyboard layouts such as those defined by IBM's proprietary data sheets—note that IBM's permission is required to use these data.)
    • Compare passwords with dictionaries of common proper names and real words.  Use spelling-checking software to capture misspelt words.  (Comparing candidate passwords with actual database contents might create a small covert data channel, so unless your database is extremely large and password update attempts are limited, you should consider using a separate dictionary for this purpose.)  Also, compare your dictionary with portions of the proposed password that consist of various types of characters (so that, for example, you will examine whether the password contains a dictionary word when numbers and symbols are stripped out, or when common letter-number substitutions are reversed.)
    • Password strength metrics should be periodically upgraded using real-world data such as that available from compromised systems (similar to the data likely to be used by your attackers).  Observe common methods of generating passwords (which are inherently more predictable), and discourage people from using them.  A proper name or dictionary word followed by a number is an obvious case to discourage (such a password would get a very low strength score, and should therefore be rejected).

    An effective system might implement principles of information theory using real-world statistics gleaned from publicly available databases of common passwords.  A simpler approach to testing password strength might involve the internal application of reverse-engineered publicly available password-cracking “warez”, in blue-team/ red-team war games.

    Password hashing is fundamentally opposed to any possibility of comparing substrings between several original passwords, and keeping “old_passwd” in any portion of memory would defeat the object of hashing passwords.  Storing hashes of various portions of the plaintext password (such as first half/ last half), for comparison purposes so as to defeat certain naive password generation methods; would defeat the security of your password hashing mechanism by opening it up to an attack similar to the one described in Section, Paragraph 1 of Professor Anderson’s text.  So by implementing a secure system, with a strong hashing mechanism incorporating an appropriate random salt, we ought to abandon all hope of comparing plain-text passwords across websites, users or password revisions.  We can only evaluate plain-text passwords at the point in the password update process before the system accepts each new password and hashes it for later validation.

    Your solutions however are good ones.  Appropriate user education and tooling should form part of any high-security password administration regime.

  6. Pingback: New Data on Password Re-use « Shiny Pebbles…

  7. I used to be a Sysadmin, and more recently have been managing programmers. Mostly, though, I struggle to follow corporate password policy. It’s hard.

    At my work, I have 7 different password domains (two different single sign-on systems, plus four other non-integrated applications). All of these have slightly different password requirements, but need to be reset every 6 to 12 weeks, approximately. The fastest I can change a password, on the most restrictive system is only a day.

    When I started here I made an incredibly difficult password, fully unique to this job, memorized it, and I put the same one on every system at work. Then forced changes come around. I did the 10 day cycle, to get my password back. Eventually that stopped working.

    Now, I change my password (in all places) every month in a progressive pattern. I’ve yet to find anything that can figure out password similarity if I change the first three letters of my password, so that is what changes. All the same, in order. 0-9. I was able to cycle through those a few times. That stopped working, so I’m on a-z, now.

    But why do I go through this great length to subvert the system? Because if I didn’t, I would attach a sticky note to redacted, like everyone else who is fed up with this stuff. Your assertion that if I can choose my own password, I will not write it down is absolutely crazy. As a human being, I can only remember so much. So far, I’ve been able to keep myself from having to put my password on a sticky note. The minute my patterns are defeated, I will have no choice but to go sticky.

    My story should also let you know that staggering password policies across systems is absolutely no barrier. Within the first five days of the month, my passwords have all changed, and all changed to the same thing. Synchronization is good. I dread the day they force me to use a sticky note. I will NOT tell you where I’ll hide it though. And my password has never been said aloud, or written down, not ever. Neither my mother nor mistress know it.

    What I do like about your system is that it would let me continue this practice longer without running out of letters. So, I hope it catches on at my company in the next redacted number of months.

    What I don’t like about any of these systems is that if humans are such a problem, why rely on them? At around $250 per user, you can get some decent biometric systems in place, and not worry about a user and a password making things complicated.

  8. I have updated this article to better reflect what typical visitors are looking for, and to prevent some of the misunderstandings experienced by previous visitors.

  9. Another way to estimate the probability that someone is reusing an old password on your system: statistically profile the timing of the keystrokes while the password is being entered.

Comments are closed.