How are your passwords cracked? How to improve password security?

We often see news that users’ passwords of some well-known apps with large user bases are leaked. You may feel that since you don't use that particular app, such incidents have nothing to do with you, but that is not the case in reality.

Recently, there was also news on Twitter that AI methods can greatly accelerate the speed of cracking passwords. So we wanted to understand the intricacies behind it, and see how we can improve the security of our passwords.

How passwords are cracked?

In general, account passwords are typically processed using various hashing algorithms and then stored in databases. You can refer to our previous blog to gain a better understanding of password hashing. Unfortunately, some service providers, lacking common sense, store passwords in plain text within their databases. This practice can result in even more significant damage if the data is leaked.

By saving hashed passwords, even database administrators cannot access your original password, significantly enhancing security. When verifying the correctness of an input password, the same hash algorithm is used to process the entered password. The resulting hash is then compared with the stored value in the database. If the two hash values match, the input password is considered correct.

In simple terms, password cracking involves generating strings that adhere to the permitted password rules. It then involves continuously checking these strings using the aforementioned method to eventually uncover the correct plain text password.

Common methods for cracking passwords

In this section, we will briefly introduce three common ways to crack passwords.

Brute-force attack

Brute force attacks usually enumerate all possibilities within the allowed password rules and try them one by one.

For example, mobile phones can set a 4-digit numeric password. Brute-force attacks will try all possibilities one by one from 0000, 0001, 0002, …, all the way to 9999.

Brute-force attacks are very time consuming, because there are too many attempts. Assuming the password length is $L$, and the number of possible characters per password digit is $n$, then the number of possibilities brute-force attacks need to try is $n^L$, which is a very large number.

The reason many passwords require a combination of numbers, uppercase and lowercase letters, and special characters, is to increase $n$, which greatly increases the number of possibilities, thus increasing the difficulty of cracking the password.

Dictionary attack

Dictionary attacks utilize words from dictionaries, often combined with spaces, numbers, special symbols, and other elements, to form various password combinations. These combinations are then used to attempt password matches.

Many individuals opt to use sentences with clear meanings as passwords for ease of recall. Dictionary attacks prove to be an efficient method for cracking passwords with such characteristics.

Rainbow table attack

A rainbow table is a precomputed mapping of plaintext passwords to their corresponding hash values. By directly comparing the hash values stored in the database with those in the rainbow table, any matches found can be used to look up and directly retrieve the corresponding plaintext password.

Rainbow tables offer the advantage of providing immediate access to plaintext passwords if the hash value has been pre-calculated (and recorded in rainbow table). However, it's important to note that if the hash value has not been precomputed (and therefore not present in the table), a rainbow table cannot be utilized.

In addition to the methods described above, there are numerous other techniques not covered here. Generally, a combination of these methods is employed to encompass all possible passwords and speed up the cracking process.

How to speed up password cracking?

In the previous section, we briefly introduced some classic password cracking methods. From them we can summarize some ideas for improving password cracking speed or success rate.

To crack a password, it often involves two steps:

1. Determine the search space for the password (generate possible passwords)
2. Use the hash algorithm to generate hashes for the possible passwords obtained in the previous step, and compare them with the hash of the password to be cracked

The dictionary attack and rainbow table attack mentioned above optimize these two steps respectively:

• The dictionary attack narrows down the search space for passwords. Building on the assumption that "users tend to create passwords using word combinations with actual meanings", words like zzzz are not included in the dictionary, which means they won't be attempted as potential passwords. This practice is akin to preemptively ruling out incorrect answers. Analogous to tackling multiple-choice questions, while you may not be certain about the correct option, you can identify which choices are definitely wrong. By eliminating these obviously incorrect options, your chances of guessing correctly among the remaining choices are enhanced.
• The rainbow table attack accelerates the execution time of the hash algorithm. For individuals well-versed in data structures, lookup is an $O(1)$-complexity operation, and no operation can be simpler than $O(1)$ in terms of time complexity. In contrast, the time complexity of commonly used hash algorithms like MD5 and SHA are $O(n)$, which is markedly slower than $O(1)$.

In practice, optimizing the password cracking process also starts from the above two perspectives. It is worth mentioning that due to the relatively small room for optimizing the $O(n)$ time complexity for string hashing algorithms, more considerations are made in improving hardware or computing methods, which will not be elaborated here.

So how does AI help to crack passwords?

In the entire endeavor of password cracking, the role of AI extends to learning certain patterns and construction methods from exposed plaintext passwords. Subsequently, AI can simulate these password construction patterns to generate a bunch of potential passwords. Following this, AI can employ hashing algorithms or even specialized hardware to execute password cracking.

In fact, compared to other password cracking tools, PassGAN's killing advantage is that it can "guess the most likely passwords as quickly as possible", which is the "reducing possible password search space" idea we mentioned above.

How to make password safer?

We will explain how to protect passwords from two perspectives. Here we simply start from the password itself, without discussing other means to ensure account security, such as multi-factor authentication (MFA) and so on.

From identity service providers side

As providers of identity services, they host all users' passwords, which imparts upon them the responsibility to safeguard the security of these passwords. Here are several schemes that can be implemented to enhance the security of users' passwords:

1. Avoid storing passwords in plaintext: While this might seem like common sense, some service providers still store passwords in plaintext within their databases. Using hash values to store passwords adds a layer of security; even if the database is compromised, hackers would need considerable effort to crack the hashed passwords.

2. Apply rate limits to the API interface for password verification: Let's revisit the password-cracking process mentioned earlier. An integral part of this process involves "verifying" whether a password is correct. Since passwords are entrusted to identity service providers, they are the sole entities equipped to offer API for password verification. By limiting the frequency of accessing this API, we can impede hackers from quickly attempting various passwords, even if they possess highly probable password guesses.

3. Enforce more complex password compositions: For instance, as mentioned previously, greater character variety within passwords of a given length contributes to heightened complexity. Additionally, employing AI techniques akin to those discussed earlier enables the evaluation of password security prior to submission. If a password is deemed weak, users can be prompted to select a more robust alternative.

On users perspective

As account owners and associated digital assets, users need to pay the utmost attention to ensuring the security of their account passwords.

1. Avoid using the same password on different websites: After obtaining passwords from certain websites, many hackers attempt to utilize those account credentials to access other websites. If multiple accounts for different services share the same password, there could be a risk of losing accounts and experiencing information leakage in the aforementioned scenario.

2. Opt for purely random passwords whenever possible: This approach helps prevent the reuse of common password patterns that most people employ (as mentioned earlier, using English sentences), thereby complicating hackers' efforts to "narrow down the password search space" and increasing the level of password complexity.

As the infrastructure provider for identity services, Logto has implemented many of the aforementioned best practices to safeguard user account security. This enables users to engage with various apps without the concern of account loss, while also allowing online service providers to ensure user data security with minimal effort, thereby enabling them to concentrate on their core business activities.