36

Note: I'm not asking about this password scheme is the best or not (of course it isn't); I'm asking about its theoretical or practical secureness relative to the optimal password scheme based on the algorithms commonly used in authentication and encryption. As I already say in my question, mathematically this scheme (as I've defined it here) is as secure as what people are told to do (but rarely do; though irrelevant here), but I don't know whether there are weird aspects of authentication or encryption that invalidate the mathematical analysis based on entropy alone.

Well so I had this interesting thought. Since password-protected systems often require users to change their password frequently, many people just increment a counter appended to some prefix, such as:

awefjio;1

awefjio;2

...

I wonder whether using such a family of passwords is as secure as choosing a completely random new password each time, as long as the prefix is uniformly randomly chosen and as long as each random new password plus about 10 bits. I ignored the extra bits from the counter since that might be guessable within a small error margin given the frequency that users are required to change their password. Mathematically this password scheme is good enough because the extra 10 bits lets the attacker try 1024 times as long to crack the password as compared to the completely random one, assuming one does not change a password more than 1024 times. (Here I'm assuming the attacker somehow has a hash of the password, including any salt needed.)

Now I know one obvious disadvantage to this, which is that an attacker who somehow gets hold of the current password will know all previous passwords, nevertheless this seems completely irrelevant in most practical situations, where once logged in the user has full access to his/her account and never needs the old passwords.

Hence my question; is there any concrete reason why users should not use this scheme for changing passwords? I'm guessing that if the answer is positive, it will depend on the authentication or encryption algorithms involved themselves, in which case I'm fine with restricting the question to the most commonly used algorithms.

To be clear, I'm only asking about the situation where:

  1. Users have no choice but to change their passwords at some fixed frequency, and do not have the option to use a password manager (such as on a workplace computer). They therefore have to decide on some scheme. This question is about whether one particular scheme is better than another.

  2. Choose a fixed constant n. I have in mind n ≥ 64 at minimum, if that matters.

    a. The first scheme is to choose a new independent random string with n-bit entropy every time one needs to change the password.

    b. The second scheme is to choose a fixed random string with (n+10)-bit entropy and append a counter that is incremented every time one needs to change the password.

The question is whether (b) is at least as secure as (a) for common types of password-protected systems.

  • 11
  • Comments are not for extended discussion; this conversation has been moved to chat. – Rory Alsop May 13 '16 at 10:37
  • This is one reason why some consider frequently expiring passwords to be less secure overall. The only way a user can reasonably be able to remember the password when they have to change it every, say, three months is to either use a simple increment or write down, both of which are arguably worse than a less frequent expiration (ie: once per year). – Joel Coehoorn May 16 '16 at 3:42

12 Answers 12

71

If an attacker has found out your password, he can access the system up until you change the password. Changing passwords often prevents attackers that already have your password to have undetected access indefinitely.

Now, if your password is secret-may16 and the attacker is locked out when you change your password, he is certainly going to try secret-june16 as the password. So changing the password in a predictable way is not secure.

  • 2
    @Anders: But that said, I personally consider a breach as 'worst-case' already... – user21820 May 12 '16 at 10:44
  • 37
    @user21820: it's not just about people who have your clear password prior to you changing it. It's also about people who get your salted hashed password and set about trying to crack it. It might take them longer to do that than it takes you to change your password, but even if it does, and your password is predictably based on your old password, then they could figure out your new password from the one that (by the time they got it) was too old to use. – Steve Jessop May 12 '16 at 14:03
  • 2
    So a new n-bit word each time is better against this scenario than one re-used n+10-bit word together with a counter. Although of course if +10 just happens to be the difference between an n that's stupid small and falls to brute force, vs. an n+10 that holds up OK, then the second scheme would win out because this scenario is predicated on someone getting your old password after the point where it would be directly useful to them. Leaked passwords presumably do sometimes sit around for a while before they're used, regardless of how they were acquired. – Steve Jessop May 12 '16 at 14:07
  • 1
    @SteveJessop: I indeed have in mind prefixes with 100-bit entropy, which therefore seemed secure enough to leave alone and just change the counter. Of course, the various points brought up so far by you and others cast doubt on practical security of such a scheme despite the theoretical unbreakability. – user21820 May 12 '16 at 15:12
  • 7
    @user21820: well, both in theory and in practice an old password can leak somehow (maybe that time you accidentally typed it into the wrong website, nobody reviews the "evil log" for months, or maybe spies gathered it by filming you in an internet cafe but had no reason to further investigate you until today). Don't let "in theory" trick you into ignoring all attack scenarios but one, that's not merely "in theory" but "in my imagination" :-) – Steve Jessop May 12 '16 at 15:12
36

You should not use this scheme, because once this password is known to an attacker, he can derive the "later" passwords.

This could be the case in these situations:

  • The password is shared between you and some other trused persons, and some day you decide to not trust (one of) them anymore. In this case, they could easily guess the next passwords.
  • An attacker gets hold of the password. Once he cracks it (which might take some time) he can then guess the derivations of the password.

By using such "numbered passwords", you destroy the (little) security benefit of changing passwords regularly.

Related Question: How does changing your password every 90 days increase security?

  • 2
    Furthermore, only a stupid person who decides not to trust someone anymore would still use the same password that he/she knew was shared with that one. – user21820 May 12 '16 at 9:52
  • 2
    Even if your password was 100 digits long, there might still be possible attacks like keyloggers, trojan horses, malware on the server-side... So only relying on the computational strengh of the password might not be enough. I don't want to say your system is completely insecure - you just loose the benefits from password change. And one more note: Neither Google nor Microsoft nor Facebook require you to change your password. – Lukas May 12 '16 at 9:53
  • 1
    As I said, you're not answering my question! My very first sentence says that my question is about password-protected systems that require users to change their passwords regularly. Whether it is good or not is irrelevant to my question. – user21820 May 12 '16 at 9:55
  • 1
    Secondly, I specifically asked about comparing this password changing scheme with the known optimal scheme of completely changing the password. – user21820 May 12 '16 at 9:56
  • 1
    @user21820 I'm not sure how this doesn't answer your question. Your literal question as you specify it is "is there any concrete reason why users should not use this scheme for changing passwords?" to which the answer is the second point of this answer: should one password be compromised, they are all compromised, and since in the real world it can take a long time before the compromise is detected, this is a very real problem. – Cronax May 13 '16 at 9:33
11

Changing only some portion of the password is [citation needed] very common, and a very bad practice.

Entropy is a measure of how unknown something is. for the first time you choose random-fixed-beginning or a whole new password, both with the same amount of entropy, both alternatives will be equivalent. Ok.

For the time you need to change your password, if you are completely sure that no previous password will be discovered, you're also good. Because something that is not known will keep the same amount of entropy.

But... and there's always a but... what if some previous password is recovered? Or two?

That can happen with sites/systems that store previous passwords in plaintext. Can also happen with sites/systems that store previous passwords as hashes.

Because plaintext, well, will easily show that your previous password was IamGod_april16. And someone will try using IamGod_may16... Just changing a part, in some predictable way, will easily expose your new password.

Even if it was stored as a hash: it will be harder when properly done, but what if someone brakes the hash and discovers what your password was? He then will be able to try IamGod_december18, and if you didn't change your scheme in the future... bang! Got hit because of a leak that happened 2 years before.

See that is doesn't matter if the "IamGod_" part is random, is human-readable, or whatever: what kicks you is that some part of if can leak some information: the month, the number, the letter in the end... even if your scheme was "IamGodh", someone could try "IamGodi", "IamGodj", and so on.

So, the first part of the answer to your specific question on whether the (b) scheme is less, equal or more secure than (a): it isn't more secure. Because if just use a changing number, changing month, changing letter... in the end, it's very easy to try new combinations, be it offline or in some online system.

And there is the second part: even if you devise a very good scheme, and the changing part is in the middle of the password... what if someone recovers 2 or more old passwords? And finds out that they were "3VQ2NMkK", "3VQ3NMkK" and "3VQ4NMkK" ? Well, can you see some pattern?

So, (a) and (b) can even be equally secure if your scheme doesn't get detected. But it's a strong assumption that one can devise a good scheme, so, in general, it's very safe to assume that (b) will be less secure, for any kind of system.

Of course, that assumes that the system gets broken somehow: that the database is leaked because someone invades a site, or because some internal folk copies the database, or someone looses the backup tape, or the maiden runs a man-in-the-middle attack inside the company, or because some update in the site leaked the password, or because the heartbleed attack revealed some passwords, or because the company let one old computer to be available in the network, or...

Given that those situations (and many more) are beyond your control, the advice is to choose the safe side: just don't assume that old passwords won't be leaked.

  • So the real solution would be to combine a random, ever changing string at the beginning, with a random, ever changing number at the end! Got it! Now, I just need to remember the string and the number... for multiple sites... changing over time... I could use a computer to do that! Yes! Solution found. – user82913 May 13 '16 at 17:43
7

Keeping a specific scheme is never a good idea even if enterprise environments that require frequent password updates/changes. For example if, like in your example, someone kept the same basic characters and only changed the password by a single integer, someone whom learns an old password could use the scheme to predict the changes. Take for example, the tool called "crunch." Using the example you provided, all possible permutations of the scheme could be generated and used in a dictionary attack.

#!/bin/bash

crunch 9 9 0123456789 -t awefjio@@

Crunch will now generate the following amount of data: 1000 bytes
0 MB
0 GB
0 TB
0 PB
Crunch will now generate the following number of lines: 100 
awefjio00
awefjio01
awefjio02
awefjio03
awefjio04
awefjio05
awefjio06
awefjio07
awefjio08
awefjio09
awefjio10
.........

And so on and so forth. Keeping a predictable password pattern makes hacking into credential-protected website login forums very easy. It is best practice to make a unique and completely new password each and everytime. Another thing that is a threat is the information gathering stage of hacking. The more a hacker learns about a target's habits, likes, dislikes, hobbies, family names, birth dates, special life event dates, etc, the more they will have to go on with dictionary/wordlist creation for cracking a login.

So to answer your question, no, it is not, ever, in any circumstance, a good practice to use simple integer increments with password changes,

5

Yes it is.

Requiring users to regularly change passwords is a counter-productive bit of security-theatre (see CESG article) as it forces users to write down their passwords. If an attacker has managed to obtain a password, then they may have several weeks to install back-doors or slurp gigabytes of data off the system anyway before the password is next changed.

Using a simple numbering scheme allows you to pick a password that you can remember without writing it down, then you can game the system to allow you to keep using your memorable password indefinitely.

If your existing password has n bits of entropy, then it will continue to have as much entropy as any other n bit entropy password. Constantly switching passwords doesn't change that. Adding a single digit on the end adds about 2.3 bits (ln(10) bits). But even if your numbering scheme is so easily guessable that it adds no entropy, you still have the n bits you started with.

If the hashing algorithm used is any good, then a password a will hash to what appears to be a random string. Another password b will give what appears to be a completely different string (except in the extraordinarily rare case of a hash collision). There should be no possible way, by looking at the two hashes, to determine whether the two passwords are completely different, or vary by only one character (perhaps a digit on the end). If it is possible to tell if only one character has changed, then your hashing algorithm is broken, and you need a better one.

The same argument goes for any encryption system used to transfer passwords from a client to a host. If two similar passwords give similar encrypted messages, then the encryption is already useless.

  • That's exactly my point about the motivation for my question. However, it doesn't answer my question about the actual security of this scheme in comparison with the other one, though I didn't (can't) downvote. – user21820 May 12 '16 at 11:06
  • 1
    @user21820 Expanded my answer. – Simon B May 12 '16 at 12:29
  • Still not answering my question! Did you read it carefully? I said: "Mathematically this password scheme is good enough because the extra 10 bits lets the attacker try 1024 times as long to crack the password as compared to the completely random one, assuming one does not change a password more than 1024 times." And then later I said that if this scheme is no good then presumably "it will depend on the authentication or encryption algorithms involved themselves". Specifically, using such a family of passwords might render it easier to crack because of the chosen algorithms. – user21820 May 12 '16 at 12:33
  • 1
    @user21820 Third time lucky? See latest edits. – Simon B May 12 '16 at 13:44
  • Now that's exactly my point; how sure are we that our hashing algorithms (for authentication) are secure enough to not be breakable even if all the passwords differ only in the counter? – user21820 May 12 '16 at 14:22
4

In your case, the security of the sequencing scheme is decreased primarily due to non-cryptologic factors. Consider shoulder surfing. If you type the same password, day after day, year after year, your coworkers or other observers could notice the patterns. You could type the same password in different locations that have different levels of physical security, such as a coffeehouse, where an ordinary camera could pick up the password.

Consider the case where the attacker doesn't use the knowledge at the same time as they learn it. I may be a co-worker who accidentally observed your password last year, but this year we're bitter rivals for the same account. Knowing one of your old passwords was qwerty1007 and another was qwerty1011 means I will be successful with some pretty simple guesses.

By employing a pattern, you increase the risk of loss over a longer period of time.

[ Your proposal superficially resembles a common scheme used by two-factor authentication systems. A user has to enter a remembered password, plus they have to enter a code displayed on their hardware device.

But the reason it's secure is not that the security is markedly improved by the size of the code from the token; it's that the system will limit the number of incorrect password+code guesses to a finite number, then lock out the user ID. ]

  • Valid reason; thanks. Now makes me wonder how safe passwords are from no-contact physical observation. – user21820 May 12 '16 at 14:38
  • Also, the hardware device in the good versions of this scheme doesn't just increment, it's a secure PRNG. So knowing that it was qwerty1007 three weeks ago and qwerty1011 yesterday just tells me that it's qwerty plus 4 digits today, whereas an incrementing counter tells me that it's almost certainly either qwerty1011 or qwerty1012 today. The PRNG is enough that limited tries before lockout actually will stop the majority of attempts to guess the 4 digits. If it just incremented then attacker would only need 2 guesses, so wouldn't get locked out... – Steve Jessop May 12 '16 at 15:35
3

I would elaborate somewhat on the explanation Sjoerd gives and approach it from a somewhat different angle.

First one should ask what security goal is being achieved by the scheduled (as opposed to reactive) change of passwords? Why is your security division or best practice document forcing you to change a password every couple of months?

There is a couple reasons:

  1. to complicate brute force attacks

    When someone gains access to the hash of your password chances are it will take them a fair amount of time before they manage to break it. If the amount of time to perform a brute force attack is longer than the validity period of the password they can't actually profit from gaining the password since you have change it already

  2. To bound the amount of time that a compromised password may be useful

    People do not always find out that their password was compromised. A regular password change makes sure that the password doesn't allow the attacker to get in forever. (Of course in some cases when they are in once they are in always due to malware, apt's what have you but this is not always the case.) This also takes care of situations where the attacker only finds out about the compromise late due to some circumstances.

  3. To slightly curb password reuse

    People will often reuse their passwords in multiple systems (work and private). Most private systems (gmail, that sports center registration web page etc.) don't force regular password changes so chances are that even if the user starts out with the same password everywhere password changes will make him differentiate them.

  4. To bound pass the hash attacks

    If an attacker only gains access to the hash of your password he can often use that hash to authenticate against the systems if he/she is sophisticated enough. Changing the underlying password will change the hash and thus again stop the attacker.

Now we can ask how do the two schemes you propose stack up against the goals we've outlined. In any case where the attacker gains access to the plain text of your password (certainly 1,2) the first scheme (incrementing) is much weaker then the second. Any non-brain-dead attacker will try incrementation. In the third situation it's a bit more tricky to judge since it depends on whether the password on outside service contains the counter at all and in general what the real impact of the regulation is. For the fourth goal the incrementation is pretty much on par with the second scheme assuming the hash function used behaves closely enough as a random oracle.

All together just incrementing the counter on a password is certainly much weaker than choosing new arbitrary passwords, but by just how much depends on the types of attacks you expect.

  • 1
    These are all very commonly provided reasons, but each is wrong in its own way. 1) Brute force should be mitigated by strong hashing protocols, such as PBKDF2. 2) An attacker will almost always provision himself an alternate back door as a first step. 3) This scheme is so common and weak that anyone knowing the original password will guess all common permutations of the password. 4) this is another implementation problem. Hashes must expire independently of the passwords, and at a much faster rate. – John Deters May 12 '16 at 13:47
  • @JohnDeters Hmm I can't really agree with you. In the second case it might be the case that it is not possible to provision an alternate backdoor (user access to a mail server for example). I agree with the fact that brute force should be mitigated by strong hashing protocols but no amount of iterations saves you if your user chooses bad(ish) passwords. 3) I don't see how we're in disagreement here, I'm saying the scheme is bad. 4) Not disagreeing but you don't always get to choose what technical solution is being used. – DRF May 12 '16 at 13:54
  • Thanks. (1) can be disregarded because of course the user in my question will pick a large enough n. (2) is roughly the same as Sjoerd's reason, which is valid. (3) doesn't work at all; almost everyone I know uses variants of their original password exactly as described in my question, though it is bad because of the original password. But in my case it's not relevant because I didn't mean using the same prefix for different password-protected systems; that's silly. (4) is really dumb, since any system that uses the same hash every time is not worth using with a secure password... – user21820 May 12 '16 at 14:36
  • Given a random password, discovering an identical hash is unlikely to yield the actual password, and thus knowing that there is a number that gets incremented at best yields the fact that it is not the actual password, it doesn't let an attacker guess the next password. – jmoreno May 15 '16 at 15:18
  • @jmoreno That's a pretty strong claim. Can you back that up with math? As far as I know it's even unknown whether something like SHA256 is one-to-one on inputs of size 256 bits. Even if it were not though it seems quite likely that it will be one-to-one on small inputs (the usual password will be less then 128 bits or 16 characters long). – DRF May 15 '16 at 16:40
1

You should roll an entire new password.

If there isn't a breach, I don't see the value in constantly rotating passwords. However--when you do rotate passwords, this is the key:

You want to regenerate the password using a system with the same assumedly secure constraint you made the original password under. I.e. incrementing a number is NOT acceptable because you're only making a one byte change since you probably had a generator give you P3588swrOd4.

So if your password rules are 3 actual random words "BadgerYtterbiumLancet" picking a new non-random word, it makes your password much more guessable, "BadgerFoxSquirrel".

The other big issue with just incrementing passwords is it creates a situation--say your company does this for 10 years...people change passwords every month. You're creating hashes of the passwords that are dangerously similar to one another. (this is why you use anything 'random', 'picking' passwords--well people tend to use Password, a common phrase, etc.) You want as much uniqueness to every password compared to each other--you want to treat new passwords for the same thing as new passwords. I.e. Password1, Password2, 3,4,5,etc. this ends up in a really bad place. Even worse if you are compromised and fix the problem, if your data is valuable to the cracker, you can bet they'll try near variations of what they found to work before.

Also, it should be noted that it's insecure for people outside your organisation (i.e. fired/old employees) to know the method for password generation. Again this is why I point back to the 'random'--nobody should know how to predict your password generation beyond something vague "they picked 4 random words in the dictionary" or "they used a strong random password generator".

  • 3
    You're creating hashes of the passwords that are dangerously similar to one another : do you have actual examples of hash algorithms that do that? – gbr May 13 '16 at 14:50
1

If your password database is leaked, a good password can take some time to crack. By which time, quite likely, you have been forced to change your password. That concept is a large part of why these "security theater" forced password resets exist.

HOWEVER, gaining access to your account is typically handled using an automated script. If the password attempted fails, then the script still has a few more attempts until lockout. If, on May 12 2016, a password like "fredJune15" was rejected, and the script has been informed that the data was acquired in July 2015, then the script might well try fredApril15, fredApril12, fredApril16 before lockout: you have given the script clues for things to try.

If the script knows the password-reset-period to your system, or can guess it, then it can guess with a simple incrementing number, about how many times the number will have been incremented. So "fred12", after seven forced password reset periods, will almost certainly be "fred19". Password reset periods are almost always a month, so guessing them will almost always work.

Worth noting as well: if you use the same password across multiple systems, but with different numbers because one gets incremented at a different rate, or because you created your accounts at a different time, then if one system is compromised, both systems are.

So in short: no, generate a new random password each time. Use a password manager. If you can use two-factor authentication, do so.

  • I normally recommend using password managers as well. However many of the places where frequent password changes are enforced are for computer logins in the workplace, where password managers are no help. For that, I use a passphrase...but I'm not 100% happy with memorizing a new one every couple months, nor with typing 40+ characters every day when I log in to my work computer. – Ben May 15 '16 at 17:14
0

When I'm cracking passwords I will get your new password within the same second if all you do is increment. This is because I'm trying appended and prepended passwords before anything else and only after qwerty related schemes and the basic list of discovered passwords since it's been my experience that's what we humans are apt to do.

0

Probably not the most secure answer, but I recently heard advice about what to use for passwords that change regularly: What is your goal or something else you are looking forward to doing in the next X months? Use that to make a password. So, if you are going on a trip to Disney World before your password is going to expire you could do something like Looking4wrd2SpaceMtn!

In X months, when that password expires, consider something else, maybe a goal you are working on: Wrk-out-35mincard!o

Your password can't be deduced from previous passwords (if you are smart about it), they have decent length, and they help you remember a goal you are working on or an event you are looking forward to.

If the trick is trying to remember the password and it changes frequently, I think this isn't a terrible option.

  • 3
    Interesting idea! I guess it's far better than what people usually do (which is to write on a sticky-note and paste underneath the keyboard where nobody else will see it, or to increment a counter). – user21820 May 14 '16 at 1:47
0

You might be somewhat safe if your suffix looks like a year of birth.

If I use myname1977 then there is less, but probably not zero, chance that someone knowing that password will guess that I changed it to myname1978.

But why take the risk? (do as I say, not as I do; I increment, but only at work, because that's the only place that asks me to change my password and, as far as I am concerned, anyone in the company is free to see everything on my work PC. Your mileage definitely will vary).

Personally, I find Edward Lear to be a great source of inspiration for passwords :-)

And the simplest, most memorable, "tick all the boxes" of minimum 8 characters, one number, one upper case & one special character is surely cat plus one big dog AKA cat+1Dog

protected by Rory Alsop May 14 '16 at 13:58

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.