Predictable Password Topology

Classic Password Defences

In order to avoid having your passwords easily cracked, there are some classic defences that could help you improve the security. Just because they are considered classic, means that can be found embedded in almost every website’s registration process or in every corporations security policy.

The are three basic things that would help us in this situation:

  • Password complexity rules
    • Minimum length
    • Formation (character classes)
  • Password rotation
    • History rotation
  • Better hashing types

Debating this policy is actually counterproductive or not, has created many online threads that might never stop giving arguments supporting both sides.

As KeithS points out in Are password complexity rules counterproductive?  – a Stackoverflow thread,

[…] it is stupidly simple to get around most sets of independently-evaluatable password complexity rules; minimum length, case requirements, non-alpha character requirements. “Password1”, unless your name happens to be Joe Password, will get past most rule systems because it’s at least 8 characters long, with a capital and a number. It’s also the first thing any crackbot will try.

The cardinal rule of any password complexity requirement is, the harder you make your system to use, the fewer people will use it. This goes way beyond password complexity rules, but as the login screen (and the user registration screen you usually link to from there) are the first real interaction by the user with your system, the more unpleasant it is, the less your users will want to deal with it, and with you. This is especially important if you’re trying to “sell” your system to users as a product they didn’t know they needed, or if there are a lot of alternatives to you in the marketplace (like an online forum). Users in that situation will very quickly say “screw it, I’m out”, and you are unlikely every to get them back.

A few additional rules naturally follow. One is that you inform the user clearly and simply of the rules you have in place, before they type in anything. It’s not a security problem for the complexity rules you enforce to be public knowledge, unless those rules actually decrease possible entropy of acceptable passwords (which rules like a maximum length can do), and your user will be far less frustrated at your system than he would be if he had to learn the rules by reverse-engineering.

Another rule is, don’t deviate too much from rules users expect. Most users are smart enough to understand that minimum complexity is for their own good, and they also know that the bars most sites and applications set are of similar height (6-8 character minimum, a capital letter and number, can’t contain any of a few obvious words like “password”). Enforcing ridiculously long and complicated passwords in excess of the implied standard (minimum 20 characters, at least two groups of at least 4 numbers each and at least 5 symbols) is just going to piss people off, even if you tell them up front.

The last meta-rule I’ll state is, don’t enforce a rule for its own sake. Never use a rule just because you saw another site or application do it, or even just because it’s best practice. There are reasons behind best practices, but you should know and understand those reasons, including why they may not apply in your situation, before Scotch-taping together a security policy.

This is one good argument against over-commitment on these policies. Most corporations tend to bypass the common-sense limit and enforce policies that on the long term are turning back against them. Sure, no restrictions is not a serious option, but a good password policy has to accomplish at least the following guidelines:

  • Adapted to the systems you use
  • Natural balance between flexibility and restrictions
  • The items of the policy need to have a purpose
  • Users must understand the policy

It’s easy for the network administrators to re-use a password policy that they’ve already used some time ago and it was proven successful. If there weren’t any password leaks or no intrusions due to weak and easy-to-brake passwords, why not? Well, no incidents doesn’t always imply that there were no attacks or that you’re on the right track. Maybe it was stealth attack, maybe the attacker hasn’t found anything interesting or nobody had any interest in trying to break into your system. It’s always good to revise your policy and update it based on your current context.

Questions like: “Why is there a maximum length of 12 characters” should be raised on both the network administrators as on the client’s side. It’s possible to be a left-over rule from an important service you used a while ago, or it was a constrained imposed by the system’s architecture. If there is no correct answer that directly responds to this question, the policy needs to be removed. Otherwise it’s just providing essential information to the attacker without any benefit on your side.

Why on the client side as well? Wether the client is an employee or just a user of your service, this actually denotes the engagement in understanding how things work. There are no stupid questions, there are only stupid answers is less faulty than The IT department is always rightThings may get overlooked, old or deprecated. Also the engagement i’ve talked about will help the user understand the purpose of the policies and how are created to protect the user instead of giving him extra work. By making these things clear, maybe his next password will not have anything in common with the month the password was set. Just saying.

The defences are actually in the attacker’s favour

The classic defences have their amount of benefits that will increase the security level. But on the one hand, the complexity rules are not that good. Your complex, really-hard-to-read password is most probably not that efficient as you think.

On the same Stackoverflow thread mentioned above, Are password complexity rules counterproductive?, the user Gilles provides a very interesting point of view about how entropy affects the complexity of the passwords:

There is no “presumably” about ease of brute force: this can be measured. For a given attacker, the cost of a brute-force attack is the average number of attempts before finding a password. While you don’t know your attacker, you can assume that he is smart and will build his attack around your password choice methods. (It’s the smartest attackers you need to most defend against anyway.) What the attacker will definitely not know is the part that you pick at random for every password. The amount of randomness in a password is called entropy; it is the number of coins that are flipped to determine the password, expressed in bits. The entropy also measures the number of brute force attempts that a smart attacker will require: with n bits of entropy, there are 2n possible passwords, and the attacker will on average need to try half of that, 2n-1.

Requiring punctuation, digits or uppercase letter is common, but it doesn’t help security much. Just about every user who would have picked a dictionary word as a password capitalizes the first letter and adds a 1 at the end. People who crack passwords aren’t stupid: they include this and other l33tspeak variations in their cracking dictionaries. All in all, this requirement may add one or two bits of entropy in practice. There are better ways to make memorable passwords with more entropy. This is illustrated in xkcd 936 and discussed on this site in XKCD #936: Short complex password, or long dictionary passphrase?

password_strength

 

So the complexity of the passwords cannot be easily measured by simply looking at it and thinking that it’s going to be difficult to guess/crack by the number of character classes you’ve used, or by the length it has. Neither using some of the password generators available doesn’t really suffice if you don’t know the complexity of the algorithm behind it. Basically, there are two choices here: Either you use a good password management tool (LastPass, KeePass, …) or live enough to write down the passwords (in historically ordered) you have chosen and try to analyse the entropy between them.

Speaking of deprecation of the password policies, writing down your password(s) and keeping them somewhere safe is not such a bad practice anymore. Beside the fact that almost nobody does this and obviously nobody’s searching for it, your password is out of your computer and having it in your locked drawer may be a lot safer. Back in the 70’s, this was a ridiculous bad practice since it could’ve get stolen and based on your job it was pretty easy to guess where it could be used. Now the hostile area has moved from the office area, and it’s spread all over the internet, so stepping back to the basics is a pretty good strategy.

Moore’s law has helped tremendously

Moore’s law basically states that the number of transistors you can place on a substrate doubles every two years. This can result in a doubling of processing power approximately every 18 months

Transistor_Count_and_Moore's_Law_-_2011

From the attacker’s perspective, if we were to assume the following based on the Moore’s Law :

  • Transistor counts double every 2 years.
  • Hash computation speed is directly proportionate to transistor count.
  • Hash computation speed is not bound by other constrains
  • There is no upper limit on transistor count.
  • We can transition to new hardware immediately.

… and we’re starting with a high-end multi-GPU mining rig (just like the ones used for BitCoin mining)  to hack a very complex password, our initial estimation based on the current technology might be something like a billion years!

But if we were to apply the premises of the Moore’s Law it will take us probably 50 years. That’s even doable in a life time if your start young enough :).
So we must take in considerations the following factors:

  • Technology exponentially evolves and there’s no actual indicator that we might hit the tech-cap anytime soon.
  • Flaws of the encryption algorithm or implementation can be found and this will drastically improve the attack and reduce the length of it.
  • Multiple attack points will also reduce the time required to break the encryption.

If all these were to be true… well the estimation will drop to probably 10 years. Once again, this is a grosso modo probabilistic determination, I have no accurate facts to sustain it.

This would be the estimation of a naive brute-force attack‘s length, which we’ve determined that will have a life-span of about 10 years on a stupendous complex password. We’ll see that if we take in account the password topologies and the fact that the target is highly predisposed on human error, this time will get even lower.

Predictable password topologies

I’ll actually start with a small note on this:


The following content relies on what’ i’ve seen and understood from KoreLogic presentations from the OWASP AppSecUSA 2014 and BSides Ashville 2014.
I’ve recently made the stupid mistake of just copy/paste and throwing up in my page these people’s work and of course this came along with some rough responses from the community. 

This is NOT my research, and i will definitely start giving more attention to the implications of public posting about someone’s work.

https://www.youtube.com/watch?feature=player_detailpage&v=KIGhA4_7dtw#t=27003

Sorry again guys, the presentations are awesome and also is your research on this. I will not make the same mistake, and if you feel offended only by mentioning of you again, please tell me. 
Also, since there may be some other people having the same crappy habits, I’ve also started a post that will help me and any other interested,  understand how you can reference other people content or work – as in legal implications along with common-sense. 

The main idea behind this, is that as long there’s a human component involved in the password generation process, the entire flow will be error prone. This is not applicable for an individual, but statistically on a larger scale. The main factor behind this? Password policies. Weak implemented, miss-understood, however you want to look at them, they actual dictate the behaviour of a high percentage of people when creating a password through the complexity rules. 

Let’s take some common password policies and try to see how most of the people will response on them:

  • Must contain at least one uppercase letter → Capitalise the first letter(s) of words.
    Ex. MyWeakPassword,
  • Must contain at least one digit  → The digits will be at the end.
    Ex. Password1, Password2014
  • Must contain at least one special character → No surprise here, the character will also be at the end. Also, it will most probably be the exclamation mark (!).
    Ex. Password2014!, Password2@
  • Must be at least 6 character long  → The average length will probably be 7. 

Looking at this, there’s clear a pattern created only by the complexity rules alone. But what if we also take in account the password rotation? The predictability of the passwords is even more obvious:

  • Password##3 → Password##(monthly rotation)
  • PwdMarch2014 → PwdMay2014 (90 days rotation)
  • Unique12Pasword! → Unique23Pasword!

The history retention that doesn’t allow you to re-use a password doesn’t help to much in this case, as it usually covers last “x” passwords, where x is lower than 12, so after a year you can re-use the old passwords again.

People are lazy when it comes to do a certain thing multiple times. And not the good laziness when you’re suddenly bored of doing something over and over again and start automating it. This is just a lazy semi-automation: Create a pattern, remember, reuse it. 0% entropy. 

All these patterns are creating the password topologies. So, by using the same notation as the Hashcat tools:

  • u for “uppercase letter”
  • l for “lowercase letter”
  • d for “digit”
  • s for “special”

… all the passwords following a certain pattern are actually part of the same topology.

P4ssw0rd1!, D1nosaur9@, H0rsefly3# are actually following the same pattern and they fall under the udllllllds topology

If we were to consider a 86 characters range password, the number of possible combinations would be 86^10 using the simple brute force attack on a 10 character passwords like the one’s mentioned above.

But if we target specific password topologies instead, the number of combinations significantly reduces based on the following premises:

  • For a n character password, there are 4^n topologies  (the Hashcat notation reduces everything to 4 groups – u,l,d,s)
  • Target the most used topologies for a n-character password – the step where the actual number of combinations is drastically reduced.

On KoreLogic’s blog there’s actually a Top100 topologies that worth be taken in consideration. Based on the information from their blog and the BSides Ashiville video, i’ll enumerate just the top 5 most popular:

  • ullllldd    (8 character)
  • ulllllldd   (9 character)
  • ullldddd  (8 character)
  • ullllllldd  (10 character)
  • ulllldddd (9 character)

How to escape from these topologies?

Short answer, you can’t. Whatever you’ll do, you’re going to fall into one of these topologies. It’s obviously different than creating a unique password, because the topologies are taking in account just the character classes, so your password behind it doesn’t really matter if it’s a simple or complex one. Of course, the complexity of the topology is directly related to the complexity of the password, but under the same topology, all passwords have the same strength.

However, it is important  to find unique and complex topologies that are respecting your password policy and try not to repeat them in the process of regenerating a new password. Check for the entropy even if you decide to use a password management system that will generate the passwords for you. Avoid having dictionary words in your password or character substitutions in the dictionary words (p4$$w0rd5)

Passwords are the weak link in IT security

On their blog, LastPass announced the latest Global Security Report, along with the following data:

The recently-published Trustwave 2012 Global Security Report details the current threats to user data and identifies the vulnerabilities that persist within organizations. The statistics were generated from their investigation of about 300 breaches across 18 countries. They also analyzed the usage and weakness trends of more than 2 million real-world passwords used within corporate information systems. The verdict? After an initial foothold in a system (via malware and other threat vectors), 80% of security incidents were due to the use of weak administrative passwords.

Yes, that’s correct: 80 percent. From weak passwords.

“The use of weak and/or default credentials continues to be one of the primary weaknesses exploited by attackers for internal propagation,” the report comments. “This is true for both large and small organisations, and largely due to poor administration.”

So, with all these restrictive policies that actually have the role to increase the complexity of the passwords, still 80% percent of the security incidents are due to weak passwords. Rather than looking for tools that will help them create unique passwords, people are actually following the common patterns and create weak passwords while actually respecting the policies.

The exploited loopholes are:

  • Setting usernames as the password when complexity requirements aren’t forced
  • Adding simple variations to fit complexity requirements, such as capitalizing a letter and adding an exclamation point to the end
  • Using dictionary words or applying simple modifications

Also, another thing to be added on the loophole list is the fact that companies assign poor default passwords such as changeme without any other enforcement for changing the password later. Also, combinations such as “administrator:password”, “guest:guest”, and “admin:admin” are pretty common to be found, on systems that are exposed to the internet, and have public access.

In another alarming example, the report highlights Active Directory’s policy of password complexity, which states that a password is required to have a minimum of eight characters and three of the five character types (Lower Case, Upper Case, Numbers, Special, Unicode). Guess what meets those requirements? “Password1”, “Password2”, and “Password3”, the first being the most widely used across the pool of two million passwords studied in the report.

Accordingly to the Trustwave 2012 Global Security Reporttop 10 passwords identified were:

  1. Password1
  2. welcome
  3. password
  4. Welcome1
  5. welcome1
  6. Password2
  7. 123456
  8. Password01
  9. Password3
  10. P@ssw0rd

Variations of “password” made up about 5% of passwords and 1.3% used “welcome” in some form.

Other keywords included:

passwordstats

People are getting more and more creative when it comes to bypassing the rules, and very few of them aren’t falling in the most common password topology bucket.

However, moving forward into 2015 and beyond, it’s clear that there are steps both end-users and businesses should be taking to change their password habits, prioritising:

  • Employee educational training on basic security practices
  • Implementation of a password management tool that makes it easy to maintain high security standards
  • Standardisation of this implementation across all platforms and devices

Forcing people to create and remember their password will only lead to more and more bad passwords. But helping them instead, to understand the policy and see them as a benefit instead of an inconvenient should be the place to start for every organisation’s security team.

  • This post originally had 90% stolen content from KoreLogic’s presentations at DEFCON, BSides and OWASP national conference as stated by many people including KoreLogic itself. There were references at the end, but these are not adequate.

    I feel obligated to preserve the comments’ main idea, since I’ve created a new post, which i hope that complies with the intellectual property infringement that I’ve been fairly accused of.

    I’d like to mention that this wasn’t my goal, although exactly this happened. I will give more attention to this and give people the credit they deserve, rather than adding content just for the sake adding it. I know that there’s been a huge credibility loss and i’m willing to assume this as my goal is to try and create a small community around some common interests

    Thanks and sincere apologises for everyone that felt offended.