Brute force: when everything is a nail
We have all heard about brute force attacks, especially against passwords. How do they work and how can you stop them?
Brute forcing is an attack technique where the attacker tries to guess a secret – e.g. a password or a secret key – by trying every possible value for it in an exhaustive manner. In any case, the ultimate target of the brute force is to defeat the confidentiality of a piece of data. OWASP considers brute force attacks a critical part of the Top Ten (A2 – Broken Authentication).
As computing power increases, brute force attacks against certain types of cryptography are steadily becoming more viable. For this reason, we need to talk about the scope of these attacks, the types of attacks in use today, and the best way to protect against them during design and development.
Degrees of brute force: jewelry hammers and sledgehammers
At its core, a brute force attack is simple: try every single possible value for a particular secret and verify whether the data recovered by this approach is correct. The longer the secret (both in length and complexity), the harder the attack it is to execute. A non-trivial brute force attack will always involve some investment in time, hardware, and power consumption from the attacker’s side.
The two main types of brute force attack are online (where the attacker performs the attack by directly interacting with the application) and offline (where the attacker can attack the data directly, such as an in an extracted database, using their own equipment). For example, if the attacker wants to brute force a user’s password, an online attack is going to take the form of continuous login attempts, while an offline attack will consist of transforming each candidate password using the same method as the program (typically some sort of hash function) until it matches the one stored in the database.
Modern brute forcing: easier than ever
There are numerous tools designed to help in both online and offline brute forcing – such as Hydra and John the Ripper. Offline brute forcing has additional tools to make it more efficient, such as hashcat that makes use of consumer GPUs, or RainbowCrack that uses so-called rainbow tables to trade off some storage space (on the scale of hundreds of gigabytes – not significant) in exchange for much faster brute forcing of certain hash algorithms. And of course, attackers can make custom hardware such as FPGA or ASIC to make offline brute force attacks against a certain algorithm even faster. It is not difficult to make hundreds of billions of guesses per second with a little investment.
Online attacks are significantly easier to protect against: enforced time delays, account lockouts, and anti-automation measures such as a CAPTCHA will all limit the attacker’s possibilities. In case of login functionality, multi-factor authentication can thwart brute force attacks as well.
However, let’s assume the worst case – the attacker has managed to get a hold of the data, and can perform brute forcing without interacting with the application. In this case, countermeasures built into the application won’t help – data storage must be designed in a way to require significant time or space investment by the attackers. But how is it possible to do that without degrading the user experience?
Putting a 128-bit thumb on the scale
Consider that the attacker’s time and resources are not infinite, and the developer can scale-up the difficulty of the problem much easier than the attacker can scale their brute forcing efforts. If the execution of the cryptographic algorithm takes a significant amount of time but doesn’t impact the overall user experience (say, up to 500 milliseconds), even attackers with a lot of computing power will fail to carry out a successful brute force attack in a reasonable amount of time.
This can be accomplished in several different ways:
- Most importantly, the secrets need to have enough unpredictability (entropy) to increase the search space beyond feasible brute-forcing. For passwords specifically, complexity increase is not linear. A 13-character mixed-case alphanumeric password or a 6-word passphrase will take nearly 100 years to break even with a hundred trillion attempts per second – but reduce the password’s length by 2 characters and the passphrase’s length by one word, and they will be breakable under 9 days at the same speed. For cryptographic secret keys, anything 128-bit and above is unfeasible to brute force – but stay away from weaker constructs like DES (56-bit).
- When using hashes or similar one-way transformations (key derivation, password storage), make sure to use a salt – a random value that is unique for each piece of data. This prevents pre-calculation-based optimizations such as rainbow tables.
- When storing a password, use a key derivation function instead of a simple hash, and specify a large enough parameter to make the process take at least 100 milliseconds. Argon2, scrypt, bcrypt, or PBKDF2 are all OK, and we recommend them in this order – unless you need to use a specific technology for compliance or compatibility reasons.
Guessing a secret or password can never be made impossible. However, after a certain level of complexity, the attacker’s chances are going to be miniscule, and it will not be worth it for them to carry out a brute force attack at all. And at that point, you have won the cat-and-mouse game!