Password security: brute-forcing and Big O notation
Welcome back to the 16th iteration of this blog series. In this series, we’re growing our cybersecurity knowledge starting from the very basics using the overthewire.org challenges as a guide. First, I’d like to thank everyone for their feedback based on the last post! I’ll do my best to implement it and as always, more feedback is always welcome.
We’ll be skipping a CTF challenge in favor of taking a deeper dive into how password cracking works. This might get a little technical but I’ll try to keep it simple. We’ll just cover the basics to explain the theory without necessarily diving into the specifics. Let’s get started!
You’ve definitely come across a password requirement of some sort when creating an account. Most security-minded platforms now require accounts to have at least 8 characters and include the following: one upper case letter, one lower case letter, and even a symbol.
To approach password cracking we need to talk about something called Big O notation. It’s a simplified mathematic formula to determine the efficiency of an algorithm and it’s commonly written as O(n), or O times N.
In most cases, program efficiency refers to the time it takes to perform it. Let’s take an example of a combination lock. I’ve had this old suitcase that had an integrated lock with a 3 digit combination. Now I haven’t used that suitcase in a long time and don’t remember the code. But say I remember the numbers but not their order. Let’s say the numbers are 3 of the same digit such as 111, 222, 333 etc. If we start with 000 and go all the way to 999, there’s a total of 10 combinations. If it takes us 1 second to try a combination, we’ll have it in 10 seconds.
This is a great example because no matter how many digits there are to the combination if we know that they’re all the same, we’ll have the combination in 10 tries or less. In fact, it’s the equivalent of having a 1 combination lock. Now although 333 is one of 999 combinations, the fact that it’s a common combination increases the chances of cracking it: enter wordlists. But we’ll get back to this.
The process of going through a simple list like this is linear and since we wouldn’t (in a normal password cracking scenario) know what on the list we’re looking for, we have to go through every combination. Now going through an item on the list takes a fixed amount of time and going through the whole list just adds time in a fixed manner: this is a linear process and is the equivalent of time per item times the number of items.
If we change our example to just repeat only 2 of the 3 digits (such as 244, 477, 633), we’re essentially making it a two-digit combination and increases the total number of combinations to 99. If we have 3 unique digits then in this new scenario we have 999 combinations. All we’re doing here though is just adding more items to our list. To get an idea of how long it takes for a computer to try numbers, go to http://pythontutor.com/composingprograms.html#mode=edit
In the code field select python and type the following:
Make sure you type it in exactly that way, including the white space before “print”. Press on visualize execution and click on “last”. This will execute all the steps without doing it one by one. How fast was it to go through 98 combinations? Try changing the “99” to another number and see how long it takes.
I should note: congratulations on writing your first brute-force program! “Brute forcing” is trying every possible combination of a password until it works. Going back to the little program we wrote, that is a “for loop”. A for loops in this case creates an on the fly list to help us try every combination. As such, a for loop follows the O(N) (it is linear). I should mention that BigO notation assumes the worst-case scenario in that in a 3 digit combination, we start at 000 and the passcode will be 999.
Imagine we added another for loop inside the first one:
Since one “for loop” is O(N), 2 of them running inside of each other (called nesting) is O(N*N) or O(N squared). The factor to keep track of here is that 2 independent “for loops” is just O(2N). If we run them independently, we’re going through 2 lists of 10 members, which is just adding two lists together. On the other hand, nested loops like this one take 2 lists of 10 members and multiply them together to get 100 combinations. Every nested loop adds another power to the time requirement of the algorithm.
The math behind combinations like passwords is called permutations. Since every character in a password is not used up and can be repeated, the number of possibilities of a password is equal to the number of possible characters times the length of the password. Using the digits 0–9 gives us 10 possibilities per digit space. What if we used alphabetical characters? The 26 possibilities. What if we used the upper case, lower case letters, and 0–9? That’s 62 possibilities. What if we add symbols? You get the picture. Try out this site to get a good picture of how different combinations affect password strength: https://www.my1login.com/resources/password-strength-test/
Brute-forcing is only one method of cracking passwords, and it’s the slowest. There are other kinds of attacks now like dictionary attacks which try known passwords first starting most commonly used ones. Malicious hackers have also devised clever ways of guessing passwords if they use letters, numbers, symbols if they’re close on the keyboard. They’ve also figured out a way to get around passwords that incorporate numbers as letters (such as using 3’s for e’s).
Perhaps the most important thing to remember is that cracking passwords is not a process that requires a malicious actor to sit there and spend time. It’s completely automated and optimized to use computer clusters to increase cracking efficiency. In fact, the development of quantum computing is putting password security at risk regardless of how long and complex they are.
Many browsers now incorporate password generators and there are sites the let you generate strong passwords based on your needs. This one even gives you mnemonics to try and remember them: https://passwordsgenerator.net/
